## CryptoDB

### Lior Rotem

#### Publications

**Year**

**Venue**

**Title**

2021

CRYPTO

Tighter Security for Schnorr Identification and Signatures: A High-Moment Forking Lemma for ${\Sigma}$-Protocols
📺
Abstract

The Schnorr identification and signature schemes have been amongst the most influential cryptographic protocols of the past three decades. Unfortunately, although the best-known attacks on these two schemes are via discrete-logarithm computation, the known approaches for basing their security on the hardness of the discrete logarithm problem encounter the ``square-root barrier''. In particular, in any group of order $p$ where Shoup's generic hardness result for the discrete logarithm problem is believed to hold (and is thus used for setting concrete security parameters), the best-known $t$-time attacks on the Schnorr identification and signature schemes have success probability $t^2/p$, whereas existing proofs of security only rule out attacks with success probabilities $(t^2/p)^{1/2}$ and $(q_{\Hash} \cdot t^2/p)^{1/2}$, respectively, where $q_{\Hash}$ denotes the number of random-oracle queries issued by the attacker.
We establish tighter security guarantees for identification and signature schemes which result from $\Sigma$-protocols with special soundness based on the hardness of their underlying relation, and in particular for Schnorr's schemes based on the hardness of the discrete logarithm problem. We circumvent the square-root barrier by introducing a high-moment generalization of the classic forking lemma, relying on the assumption that the underlying relation is ``$d$-moment hard'': The success probability of any algorithm in the task of producing a witness for a random instance is dominated by the $d$-th moment of the algorithm's running time.
In the concrete context of the discrete logarithm problem, already Shoup's original proof shows that the discrete logarithm problem is $2$-moment hard in the generic-group model, and thus our assumption can be viewed as a highly-plausible strengthening of the discrete logarithm assumption in any group where no better-than-generic algorithms are currently known. Applying our high-moment forking lemma in this context shows that, assuming the $2$-moment hardness of the discrete logarithm problem, any $t$-time attacker breaks the security of the Schnorr identification and signature schemes with probabilities at most $(t^2/p)^{2/3}$ and $(q_\Hash \cdot t^2/p)^{2/3}$, respectively.

2021

TCC

Simple and Efficient Batch Verification Techniques for Verifiable Delay Functions
📺
Abstract

We study the problem of batch verification for verifiable delay functions (VDFs), focusing on proofs of correct exponentiation (PoCE), which underlie recent VDF constructions. We show how to compile any PoCE into a batch PoCE, offering significant savings in both communication and verification time. Concretely, given any PoCE with communication complexity $c$, verification time $t$ and soundness error $\delta$, and any pseudorandom function with key length ${\sf k}_{\sf prf}$ and evaluation time $ t_{\sf prf}$, we construct:
-- A batch PoCE for verifying $n$ instances with communication complexity $m\cdot c +{\sf k}_{\sf prf}$, verification time $m\cdot t + n\cdot m\cdot O(t_{\sf op} + t_{\sf prf})$ and soundness error $\delta + 2^{-m}$, where $\lambda$ is the security parameter, $m$ is an adjustable parameter that can take any integer value, and $t_{\sf op}$ is the time required to evaluate the group operation in the underlying group.
This should be contrasted with the naive approach, in which the communication complexity and verification time are $n \cdot c$ and $n \cdot t$, respectively. The soundness of this compiler relies only on the soundness of the underlying PoCE and the existence of one-way functions.
-- An improved batch PoCE based on the low order assumption. For verifying $n$ instances, the batch PoCE requires communication complexity $c +{\sf k}_{\sf prf}$ and verification time $t + n\cdot (t_{\sf prf} + \log(s)\cdot O(t_{\sf op}))$, and has soundness error $\delta + 1/s$. The parameter $s$ can take any integer value, as long as it is hard to find group elements of order less than $s$ in the underlying group.
We discuss instantiations in which $s$ can be exponentially large in the security parameter $\lambda$.
If the underlying PoCE is constant round and public coin (as is the case for existing protocols), then so are all of our batch PoCEs, implying that they can be made non-interactive using the Fiat-Shamir transform.
Additionally, for RSA groups with moduli which are the products of two safe primes, we show how to efficiently verify that certain elements are not of order $2$. This protocol, together with the second compiler above and any (single-instance) PoCE in these groups, yields an efficient batch PoCE in safe RSA groups. To complete the picture, we also show how to extend Pietrzak's protocol (which is statistically sound in the group $QR_N^+$ when $N$ is the product of two safe primes) to obtain a statistically-sound PoCE in safe RSA groups.

2021

TCC

Non-Malleable Vector Commitments via Local Equivocability
📺
Abstract

Vector commitments (VCs), enabling to commit to a vector and locally reveal any of its entries, play a key role in a variety of both classic and recently-evolving applications. However, security notions for VCs have so far focused on passive attacks, and non-malleability notions considering active attacks have not been explored. Moreover, existing frameworks that may enable to capture the non-malleability of VCs seem either too weak (non-malleable non-interactive commitments that do not account for the security implications of local openings) or too strong (non-malleable zero-knowledge sets that support both membership and non-membership proofs).
We put forward a rigorous framework capturing the non-malleability of VCs, striking a careful balance between the existing weaker and stronger frameworks: We strengthen the framework of non-malleable non-interactive commitments by considering attackers that may be exposed to local openings, and we relax the framework of non-malleable zero-knowledge sets by focusing on membership proofs. In addition, we strengthen both frameworks by supporting (inherently-private) updates to entries of committed vectors, and discuss the benefits of non-malleable VCs in the context of both UTXO-based and account-based stateless blockchains, and in the context of simultaneous multi-round auctions (that have been adopted by the US Federal Communications Commission as the standard auction format for selling spectrum ranges).
Within our framework we present a direct approach for constructing non-malleable VCs whose efficiency essentially matches that of the existing standard VCs. Specifically, we show that any VC can be transformed into a non-malleable one, relying on a new primitive that we put forth. Our new primitive, locally-equivocable commitments with all-but-one binding, is evidently both conceptually and technically simpler compared to multi-trapdoor mercurial trapdoor commitments (the main building block underlying existing non-malleable zero-knowledge sets), and admits more efficient instantiations based on the same number-theoretic assumptions.

2021

JOFC

From Fairness to Full Security in Multiparty Computation
Abstract

In the setting of secure multiparty computation (MPC), a set of mutually distrusting parties wish to jointly compute a function, while guaranteeing the privacy of their inputs and the correctness of the output. An MPC protocol is called fully secure if no adversary can prevent the honest parties from obtaining their outputs. A protocol is called fair if an adversary can prematurely abort the computation, however, only before learning any new information. We present efficient transformations from fair computations to fully secure computations, assuming a constant fraction of honest parties (e.g., $$1\%$$ 1 % of the parties are honest). Compared to previous transformations that require linear invocations (in the number of parties) of the fair computation, our transformations require super-logarithmic, and sometimes even super-constant, such invocations. The main idea is to delegate the computation to random committees that invoke the fair computation. Apart from the benefit of uplifting security, the reduction in the number of parties is also useful, since only committee members are required to work, whereas the remaining parties simply “listen” to the computation over a broadcast channel. One application of these transformations is a new $$\delta $$ δ -bias coin-flipping protocol, whose round complexity has a super-logarithmic dependency on the number of parties, improving over the linear-dependency protocol of Beimel, Omri, and Orlov (Crypto 2010). A second application is a new fully secure protocol for computing the Boolean OR function, with a super-constant round complexity, improving over the protocol of Gordon and Katz (TCC 2009) whose round complexity is linear in the number of parties. Finally, we show that our positive results are in a sense optimal, by proving that for some functionalities, a super-constant number of (sequential) invocations of the fair computation is necessary for computing the functionality in a fully secure manner.

2021

JOFC

Injective Trapdoor Functions via Derandomization: How Strong is Rudich’s Black-Box Barrier?
Abstract

We present a cryptographic primitive $${\mathcal {P}}$$ P satisfying the following properties: Rudich’s seminal impossibility result (PhD thesis ’88) shows that $${\mathcal {P}}$$ P cannot be used in a black-box manner to construct an injective one-way function. $${\mathcal {P}}$$ P can be used in a non-black-box manner to construct an injective one-way function assuming the existence of a hitting-set generator that fools deterministic circuits (such a generator is known to exist based on the worst-case assumption that $$\text{ E } = \text{ DTIME }(2^{O(n)})$$ E = DTIME ( 2 O ( n ) ) has a function of deterministic circuit complexity $$2^{\Omega (n)}$$ 2 Ω ( n ) ). The non-black box aspect of our construction only requires a bound on the size of $${\mathcal {P}}$$ P ’s implementation. Augmenting $${\mathcal {P}}$$ P with a trapdoor algorithm enables a non-black-box construction of an injective trapdoor function (once again, assuming the existence of a hitting-set generator that fools deterministic circuits), while Rudich’s impossibility result still holds. The primitive $${\mathcal {P}}$$ P and its augmented variant can be constructed based on any injective one-way function and on any injective trapdoor function, respectively, and they are thus unconditionally essential for the existence of such functions. Moreover, $${\mathcal {P}}$$ P can also be constructed based on various known primitives that are secure against related-key attacks (e.g., pseudorandom functions), thus enabling to base the strong structural guarantees of injective one-way functions on the strong security guarantees of such primitives. Our application of derandomization techniques is inspired mainly by the work of Barak, Ong and Vadhan (CRYPTO ’03), which on one hand relies on any one-way function, but on the other hand only results in a non-interactive perfectly binding commitment scheme (offering significantly weaker structural guarantees compared to injective one-way functions) and does not seem to enable an extension to public-key primitives. The key observation underlying our approach is that Rudich’s impossibility result applies not only to one-way functions as the underlying primitive, but in fact to a variety of “unstructured” primitives. We put forward a condition for identifying such primitives, and then subtly tailor the properties of our primitives such that they are both sufficiently unstructured in order to satisfy this condition, and sufficiently structured in order to yield injective one-way and trapdoor functions. This circumvents the basic approach underlying Rudich’s long-standing evidence for the difficulty of constructing injective one-way functions (and, in particular, injective trapdoor functions) based on seemingly weaker or unstructured assumptions.

2020

EUROCRYPT

Generic-Group Delay Functions Require Hidden-Order Groups
📺
Abstract

Despite the fundamental importance of delay functions, underlying both the classic notion of a time-lock puzzle and the more recent notion of a verifiable delay function, the only known delay function that offers both sufficient structure for realizing these two notions and a realistic level of practicality is the ``iterated squaring'' construction of Rivest, Shamir and Wagner. This construction, however, is based on rather strong assumptions in groups of hidden orders, such as the RSA group (which requires a trusted setup) or the class group of an imaginary quadratic number field (which is still somewhat insufficiently explored from the cryptographic perspective). For more than two decades, the challenge of constructing delay functions in groups of known orders, admitting a variety of well-studied instantiations, has eluded the cryptography community.
In this work we prove that there are no constructions of generic-group delay functions in cyclic groups of known orders: We show that for any delay function that does not exploit any particular property of the representation of the underlying group, there exists an attacker that completely breaks the function's sequentiality when given the group's order. As any time-lock puzzle and verifiable delay function give rise to a delay function, our result holds for these two notions we well, and explains the lack of success in resolving the above-mentioned long-standing challenge. Moreover, our result holds even if the underlying group is equipped with a d-linear map, for any constant d>=2 (and even for super-constant values of d under certain conditions).

2020

CRYPTO

Generically Speeding-Up Repeated Squaring is Equivalent to Factoring: Sharp Thresholds for All Generic-Ring Delay Functions
📺
Abstract

Despite the fundamental importance of delay functions, repeated squaring in RSA groups (Rivest, Shamir and Wagner '96) is the only candidate offering both a useful structure and a realistic level of practicality. Somewhat unsatisfyingly, its sequentiality is provided directly by assumption (i.e., the function is assumed to be a delay function).
We prove sharp thresholds on the sequentiality of all generic-ring delay functions relative to an RSA modulus based on the hardness of factoring in the standard model. In particular, we show that generically speeding-up repeated squaring (even with a preprocessing stage and any polynomial number parallel processors) is equivalent to factoring.
More generally, based on the (essential) hardness of factoring, we prove that any generic-ring function is in fact a delay function, admitting a sharp sequentiality threshold that is determined by our notion of sequentiality depth. Moreover, we show that generic-ring functions admit not only sharp sequentiality thresholds, but also sharp pseudorandomness thresholds.

2020

TCC

Algebraic Distinguishers: From Discrete Logarithms to Decisional Uber Assumptions
📺
Abstract

The algebraic group model, introduced by Fuchsbauer, Kiltz and Loss (CRYPTO '18), is a substantial relaxation of the generic group model capturing algorithms that may exploit the representation of the underlying group. This idealized yet realistic model was shown useful for reasoning about cryptographic assumptions and security properties defined via computational problems. However, it does not generally capture assumptions and properties defined via decisional problems. As such problems play a key role in the foundations and applications of cryptography, this leaves a significant gap between the restrictive generic group model and the standard model.
We put forward the notion of algebraic distinguishers, strengthening the algebraic group model by enabling it to capture decisional problems. Within our framework we then reveal new insights on the algebraic interplay between a wide variety of decisional assumptions. These include the decisional Diffie-Hellman assumption, the family of Linear assumptions in multilinear groups, and the family of Uber assumptions in bilinear groups.
Our main technical results establish that, from an algebraic perspective, these decisional assumptions are in fact all polynomially equivalent to either the most basic discrete logarithm assumption or to its higher-order variant, the $q$-discrete logarithm assumption. On the one hand, these results increase the confidence in these strong decisional assumptions, while on the other hand, they enable to direct cryptanalytic efforts towards either extracting discrete logarithms or significantly deviating from standard algebraic techniques.

2018

CRYPTO

Out-of-Band Authentication in Group Messaging: Computational, Statistical, Optimal
📺
Abstract

Extensive efforts are currently put into securing messaging platforms, where a key challenge is that of protecting against man-in-the-middle attacks when setting up secure end-to-end channels. The vast majority of these efforts, however, have so far focused on securing user-to-user messaging, and recent attacks indicate that the security of group messaging is still quite fragile.We initiate the study of out-of-band authentication in the group setting, extending the user-to-user setting where messaging platforms (e.g., Telegram and WhatsApp) protect against man-in-the-middle attacks by assuming that users have access to an external channel for authenticating one short value (e.g., two users who recognize each other’s voice can compare a short value). Inspired by the frameworks of Vaudenay (CRYPTO ’05) and Naor et al. (CRYPTO ’06) in the user-to-user setting, we assume that users communicate over a completely-insecure channel, and that a group administrator can out-of-band authenticate one short message to all users. An adversary may read, remove, or delay this message (for all or for some of the users), but cannot undetectably modify it.Within our framework we establish tight bounds on the tradeoff between the adversary’s success probability and the length of the out-of-band authenticated message (which is a crucial bottleneck given that the out-of-band channel is of low bandwidth). We consider both computationally-secure and statistically-secure protocols, and for each flavor of security we construct an authentication protocol and prove a lower bound showing that our protocol achieves essentially the best possible tradeoff.In particular, considering groups that consist of an administrator and k additional users, for statistically-secure protocols we show that at least
$$(k+1)\cdot (\log (1/\epsilon ) - \varTheta (1))$$
(k+1)·(log(1/ϵ)-Θ(1)) bits must be out-of-band authenticated, whereas for computationally-secure ones
$$\log (1/\epsilon ) + \log k$$
log(1/ϵ)+logk bits suffice, where
$$\epsilon $$
ϵ is the adversary’s success probability. Moreover, instantiating our computationally-secure protocol in the random-oracle model yields an efficient and practically-relevant protocol (which, alternatively, can also be based on any one-way function in the standard model).

2018

TCC

Injective Trapdoor Functions via Derandomization: How Strong is Rudich’s Black-Box Barrier?
Abstract

We present a cryptographic primitive
$$\mathcal {P}$$
P satisfying the following properties:Rudich’s seminal impossibility result (PhD thesis ’88) shows that
$$\mathcal {P}$$
P cannot be used in a black-box manner to construct an injective one-way function.
$$\mathcal {P}$$
P can be used in a non-black-box manner to construct an injective one-way function assuming the existence of a hitting-set generator that fools deterministic circuits (such a generator is known to exist based on the worst-case assumption that
$$\text{ E } = \text{ DTIME }(2^{O(n)})$$
E=DTIME(2O(n)) has a function of deterministic circuit complexity
$$2^{\Omega (n)}$$
2Ω(n)).Augmenting
$$\mathcal {P}$$
P with a trapdoor algorithm enables a non-black-box construction of an injective trapdoor function (once again, assuming the existence of a hitting-set generator that fools deterministic circuits), while Rudich’s impossibility result still holds.
The primitive
$$\mathcal {P}$$
P and its augmented variant can be constructed based on any injective one-way function and on any injective trapdoor function, respectively, and they are thus unconditionally essential for the existence of such functions. Moreover,
$$\mathcal {P}$$
P can also be constructed based on various known primitives that are secure against related-key attacks, thus enabling to base the strong structural guarantees of injective one-way functions on the strong security guarantees of such primitives.Our application of derandomization techniques is inspired mainly by the work of Barak, Ong and Vadhan (CRYPTO ’03), which on one hand relies on any one-way function, but on the other hand only results in a non-interactive perfectly-binding commitment scheme (offering significantly weaker structural guarantees compared to injective one-way functions), and does not seem to enable an extension to public-key primitives.The key observation underlying our approach is that Rudich’s impossibility result applies not only to one-way functions as the underlying primitive, but in fact to a variety of “unstructured” primitives. We put forward a condition for identifying such primitives, and then subtly tailor the properties of our primitives such that they are both sufficiently unstructured in order to satisfy this condition, and sufficiently structured in order to yield injective one-way and trapdoor functions. This circumvents the basic approach underlying Rudich’s long-standing evidence for the difficulty of constructing injective one-way functions (and, in particular, injective trapdoor functions) based on seemingly weaker or unstructured assumptions.

2018

TCC

The Security of Lazy Users in Out-of-Band Authentication
Abstract

Faced with the threats posed by man-in-the-middle attacks, messaging platforms rely on “out-of-band” authentication, assuming that users have access to an external channel for authenticating one short value. For example, assuming that users recognizing each other’s voice can authenticate a short value, Telegram and WhatApp ask their users to compare 288-bit and 200-bit values, respectively. The existing protocols, however, do not take into account the plausible behavior of users who may be “lazy” and only compare parts of these values (rather than their entirety).Motivated by such a security-critical user behavior, we study the security of lazy users in out-of-band authentication. We start by showing that both the protocol implemented by WhatsApp and the statistically-optimal protocol of Naor, Segev and Smith (CRYPTO ’06) are completely vulnerable to man-in-the-middle attacks when the users consider only a half of the out-of-band authenticated value. In this light, we put forward a framework that captures the behavior and security of lazy users. Our notions of security consider both statistical security and computational security, and for each flavor we derive a lower bound on the tradeoff between the number of positions that are considered by the lazy users and the adversary’s forgery probability.Within our framework we then provide two authentication protocols. First, in the statistical setting, we present a transformation that converts any out-of-band authentication protocol into one that is secure even when executed by lazy users. Instantiating our transformation with a new refinement of the protocol of Naor et al. results in a protocol whose tradeoff essentially matches our lower bound in the statistical setting. Then, in the computational setting, we show that the computationally-optimal protocol of Vaudenay (CRYPTO ’05) is secure even when executed by lazy users – and its tradeoff matches our lower bound in the computational setting.

#### Coauthors

- Ran Cohen (3)
- Iftach Haitner (3)
- Moni Naor (1)
- Eran Omri (3)
- Gil Segev (9)
- Ido Shahaf (1)