## CryptoDB

### Nir Bitansky

#### Publications

**Year**

**Venue**

**Title**

2021

TCC

Post-quantum Resettably-Sound Zero Knowledge
Abstract

We study post-quantum zero-knowledge (classical) protocols that are sound against quantum resetting attacks. Our model is inspired by the classical model of resetting provers (Barak-Goldreich-GoldwasserLindell, FOCS ‘01), providing a malicious efficient prover with oracle access to the verifier’s next-message-function, fixed to some initial random tape; thereby allowing it to effectively reset (or equivalently, rewind) the verifier. In our model, the prover has quantum access to the verifier’s function, and in particular can query it in superposition. The motivation behind quantum resettable soundness is twofold: First, ensuring a strong security guarantee in scenarios where quantum resetting may be possible (e.g., smart cards, or virtual machines). Second, drawing intuition from the classical setting, we hope to improve our understanding of basic questions regarding post-quantum zero knowledge. We prove the following results:
– Black-Box Barriers. Quantum resetting exactly captures the power of black-box zero knowledge quantum simulators. Accordingly, resettable soundness cannot be achieved in conjunction with black-box zero knowledge, except for languages in BQP. Leveraging this, we prove that constant-round public-coin, or three message, protocols cannot be black-box post-quantum zero-knowledge. For this, we show how to transform such protocols into quantumly resettably sound ones. The transformations are similar to classical ones, but their analysis is very different due to the essential difference between classical and quantum resetting.
– A Resettably-Sound Non-Black-Box Zero-Knowledge Protocol. Under the (quantum) Learning with Errors assumption and quantum fully-homomorphic encryption, we construct a post-quantum resettably sound zero knowledge protocol for NP. We rely on non-black-box simulation techniques, thus overcoming the black-box barrier for such protocols.
– From Resettable Soundness to The Impossibility of Quantum Obfuscation. Assuming one-way functions, we prove that any quantumly resettably-sound zero-knowledge protocol for NP implies the impossibility of quantum obfuscation. Combined with the above result, this gives an alternative proof to several recent results on quantum unobfuscatability.

2021

TCC

Classical Binding for Quantum Commitments
Abstract

In classical commitments, statistical binding means that for almost any commitment transcript there is at most one possible opening. While quantum commitments (for classical messages) sometimes have benefits over their classical counterparts (e.g. in terms of assumptions), they provide a weaker notion of binding. Essentially that the sender cannot open a given commitment to a random value with probability noticeably greater than 1/2.
We introduce a notion of classical binding for quantum commitments which provides guarantees analogous to the classical case. In our notion, the receiver performs a (partial) measurement of the quantum commitment string, and the outcome of this measurement determines a single value that the sender may open. We expect that our notion can replace classical commitments in various settings, leaving the security proof essentially unchanged. As an example we show a soundness proof for the GMW zero-knowledge proof system.
We construct a non-interactive quantum commitment scheme which is classically statistically-binding and has a classical opening, based on the existence of any post-quantum one-way function. Prior candidates had inherently quantum openings and were not classically binding.
In contrast, we show that it is impossible to achieve classical binding for statistically hiding commitments, regardless of assumption or round complexity.
Our scheme is simply Naor's commitment scheme (which classically requires a common random string, CRS), but executed in superposition over all possible values of the CRS, and repeated several times. We hope that this technique for using quantum communication to remove a CRS may find other uses.

2020

TCC

Weakly Extractable One-Way Functions
📺
Abstract

A family of one-way functions is extractable if given a random function in the family, an efficient adversary can only output an element in the image of the function if it knows a corresponding preimage.
This knowledge extraction guarantee is particularly powerful since it does not require interaction.
However, extractable one-way functions (EFs) are subject to a strong barrier: assuming indistinguishability obfuscation, no EF can have a knowledge extractor that works against all polynomial-size non-uniform adversaries. This holds even for non-black-box extractors that use the adversary's code.
Accordingly, the literature considers either EFs based on non-falsifiable knowledge assumptions, where the extractor is not explicitly given, but it is only assumed to exist, or EFs against a restricted class of adversaries with a bounded non-uniform advice. This falls short of cryptography's gold standard of security that requires an explicit reduction against non-uniform adversaries of arbitrary polynomial size.
Motivated by this gap, we put forward a new notion of weakly extractable one-way functions (WEFs) that circumvents the known barrier. We then prove that WEFs are inextricably connected to the long standing question of three-message zero knowledge protocols. We show that different flavors of WEFs are sufficient and necessary for three-message zero knowledge to exist. The exact flavor depends on whether the protocol is computational or statistical zero knowledge and whether it is publicly or privately verifiable.
Combined with recent progress on constructing three message zero-knowledge, we derive a new connection between keyless multi-collision resistance and the notion of incompressibility and the feasibility of non-interactive knowledge extraction. Another interesting corollary of our result is that in order to construct three-message zero knowledge arguments, it suffices to construct such arguments where the honest prover strategy is unbounded.

2019

CRYPTO

On Round Optimal Statistical Zero Knowledge Arguments
📺
Abstract

We construct the first three message statistical zero knowledge arguments for all of NP, matching the known lower bound. We do so based on keyless multi-collision resistant hash functions and the Learning with Errors assumption—the same assumptions used to obtain round optimal computational zero knowledge.The main component in our construction is a statistically witness indistinguishable argument of knowledge based on a new notion of statistically hiding commitments with subset opening.

2019

EUROCRYPT

Distributional Collision Resistance Beyond One-Way Functions
📺
Abstract

Distributional collision resistance is a relaxation of collision resistance that only requires that it is hard to sample a collision (x, y) where x is uniformly random and y is uniformly random conditioned on colliding with x. The notion lies between one-wayness and collision resistance, but its exact power is still not well-understood. On one hand, distributional collision resistant hash functions cannot be built from one-way functions in a black-box way, which may suggest that they are stronger. On the other hand, so far, they have not yielded any applications beyond one-way functions.Assuming distributional collision resistant hash functions, we construct constant-round statistically hiding commitment scheme. Such commitments are not known based on one-way functions, and are impossible to obtain from one-way functions in a black-box way. Our construction relies on the reduction from inaccessible entropy generators to statistically hiding commitments by Haitner et al. (STOC ’09). In the converse direction, we show that two-message statistically hiding commitments imply distributional collision resistance, thereby establishing a loose equivalence between the two notions.A corollary of the first result is that constant-round statistically hiding commitments are implied by average-case hardness in the class $${\textsf {SZK}}$$ (which is known to imply distributional collision resistance). This implication seems to be folklore, but to the best of our knowledge has not been proven explicitly. We provide yet another proof of this implication, which is arguably more direct than the one going through distributional collision resistance.

2019

TCC

On the Complexity of Collision Resistant Hash Functions: New and Old Black-Box Separations
Abstract

The complexity of collision-resistant hash functions has been long studied in the theory of cryptography. While we often think about them as a Minicrypt primitive, black-box separations demonstrate that constructions from one-way functions are unlikely. Indeed, theoretical constructions of collision-resistant hash functions are based on rather structured assumptions.We make two contributions to this study: 1.A New Separation: We show that collision-resistant hashing does not imply hard problems in the class Statistical Zero Knowledge in a black-box way.2.New Proofs: We show new proofs for the results of Simon, ruling out black-box reductions of collision-resistant hashing to one-way permutations, and of Asharov and Segev, ruling out black-box reductions to indistinguishability obfuscation. The new proofs are quite different from the previous ones and are based on simple coupling arguments.

2019

JOFC

From Cryptomania to Obfustopia Through Secret-Key Functional Encryption
Abstract

Functional encryption lies at the frontiers of the current research in cryptography; some variants have been shown sufficiently powerful to yield indistinguishability obfuscation (IO), while other variants have been constructed from standard assumptions such as LWE. Indeed, most variants have been classified as belonging to either the former or the latter category. However, one mystery that has remained is the case of secret-key functional encryption with an unbounded number of keys and ciphertexts. On the one hand, this primitive is not known to imply anything outside of minicrypt, the land of secret-key cryptography, but, on the other hand, we do no know how to construct it without the heavy hammers in obfustopia. In this work, we show that (subexponentially secure) secret-key functional encryption is powerful enough to construct indistinguishability obfuscation if we additionally assume the existence of (subexponentially secure) plain public-key encryption. In other words, secret-key functional encryption provides a bridge from cryptomania to obfustopia. On the technical side, our result relies on two main components. As our first contribution, we show how to use secret-key functional encryption to get “exponentially efficient indistinguishability obfuscation” (XIO), a notion recently introduced by Lin et al. (PKC’16) as a relaxation of IO. Lin et al. show how to use XIO and the LWE assumption to build IO. As our second contribution, we improve on this result by replacing its reliance on the LWE assumption with any plain public-key encryption scheme. Lastly, we ask whether secret-key functional encryption can be used to construct public-key encryption itself and therefore take us all the way from minicrypt to obfustopia. A result of Asharov and Segev (FOCS’15) shows that this is not the case under black-box constructions, even for exponentially secure functional encryption. We show, through a non-black-box construction, that subexponentially secure-key functional encryption indeed leads to public-key encryption. The resulting public-key encryption scheme, however, is at most quasi-polynomially secure, which is insufficient to take us to obfustopia.

2019

JOFC

Verifiable Random Functions from Non-interactive Witness-Indistinguishable Proofs
Abstract

Verifiable random functions (VRFs) are pseudorandom functions where the owner of the seed, in addition to computing the function’s value y at any point x , can also generate a non-interactive proof $$\pi $$ π that y is correct, without compromising pseudorandomness at other points. Being a natural primitive with a wide range of applications, considerable efforts have been directed toward the construction of such VRFs. While these efforts have resulted in a variety of algebraic constructions (from bilinear maps or the RSA problem), the relation between VRFs and other general primitives is still not well understood. We present new constructions of VRFs from general primitives, the main one being non-interactive witness-indistinguishable proofs (NIWIs). This includes: (1) a selectively secure VRF assuming NIWIs and non-interactive commitments. As usual, the VRF can be made adaptively secure assuming subexponential hardness of the underlying primitives. (2) An adaptively secure VRF assuming (polynomially hard) NIWIs, non-interactive commitments, and ( single-key ) constrained pseudorandom functions for a restricted class of constraints. The above primitives can be instantiated under various standard assumptions, which yields corresponding VRF instantiations, under different assumptions than were known so far. One notable example is a non-uniform construction of VRFs from subexponentially hard trapdoor permutations, or more generally, from verifiable pseudorandom generators (the construction can be made uniform under a standard derandomization assumption). This partially answers an open question by Dwork and Naor (FOCS ’00). The construction and its analysis are quite simple. Both draw from ideas commonly used in the context of indistinguishability obfuscation .

2018

TCC

One-Message Zero Knowledge and Non-malleable Commitments
Abstract

We introduce a new notion of one-message zero-knowledge (1ZK) arguments that satisfy a weak soundness guarantee—the number of false statements that a polynomial-time non-uniform adversary can convince the verifier to accept is not much larger than the size of its non-uniform advice. The zero-knowledge guarantee is given by a simulator that runs in (mildly) super-polynomial time. We construct such 1ZK arguments based on the notion of multi-collision-resistant keyless hash functions, recently introduced by Bitansky, Kalai, and Paneth (STOC 2018). Relying on the constructed 1ZK arguments, subexponentially-secure time-lock puzzles, and other standard assumptions, we construct one-message fully-concurrent non-malleable commitments. This is the first construction that is based on assumptions that do not already incorporate non-malleability, as well as the first based on (subexponentially) falsifiable assumptions.

2016

TCC

2015

TCC

2014

EPRINT

2010

EPRINT

On Strong Simulation and Composable Point Obfuscation
Abstract

The Virtual Black Box (VBB) property for program obfuscators
provides a strong guarantee: Anything computable by an efficient
adversary given the obfuscated program can also be computed by an
efficient simulator with only oracle access to the program. However,
we know how to achieve this notion only for very restricted classes
of programs.
This work studies a simple relaxation of VBB: Allow the simulator
unbounded computation time, while still allowing only polynomially
many queries to the oracle. We then demonstrate the viability of
this relaxed notion, which we call Virtual Grey Box (VGB), in the
context of fully composable obfuscators for point programs: It is
known that, w.r.t. VBB, if such obfuscators exist then there exist
multi-bit point obfuscators (aka ``digital lockers'') and
subsequently also very strong variants of encryption that are
resilient to various attacks, such as key leakage and
key-dependent-messages. However, no composable VBB-obfuscators for
point programs have been shown. We show fully composable {\em
VGB}-obfuscators for point programs under a strong variant of the
Decision Diffie Hellman assumption. We show they suffice for the
above applications and even for extensions to the public key setting
as well as for encryption schemes with resistance to certain related
key attacks (RKA).

#### Program Committees

- Eurocrypt 2019
- TCC 2019
- Eurocrypt 2018
- Eurocrypt 2017
- PKC 2017
- TCC 2017
- TCC 2016
- TCC 2015

#### Coauthors

- Boaz Barak (1)
- Zvika Brakerski (2)
- Ran Canetti (12)
- Alessandro Chiesa (4)
- Henry Cohn (1)
- Dana Dachman-Soled (2)
- Akshay Degwekar (2)
- Noa Eizenstadt (1)
- Sanjam Garg (2)
- Shafi Goldwasser (5)
- Iftach Haitner (1)
- Shai Halevi (2)
- Yuval Ishai (1)
- Abhishek Jain (2)
- Yael Tauman Kalai (7)
- Michael Kellner (1)
- Ilan Komargodski (1)
- Huijia Lin (6)
- Adriana López-Alt (1)
- Ryo Nishimaki (2)
- Rafail Ostrovsky (1)
- Omer Paneth (17)
- Rafael Pass (1)
- Alain Passelègue (2)
- Alon Rosen (2)
- Guy N. Rothblum (1)
- Aviad Rubinstein (2)
- Amit Sahai (1)
- Omri Shmueli (1)
- Sidharth Telang (1)
- Eran Tromer (2)
- Vinod Vaikuntanathan (7)
- Brent Waters (1)
- Daniel Wichs (5)
- Eylon Yogev (1)