## CryptoDB

### Yael Tauman Kalai

#### Publications

**Year**

**Venue**

**Title**

2021

TCC

Somewhere Statistical Soundness, Post-Quantum Security, and SNARGs
📺
Abstract

The main conceptual contribution of this paper is a unification of two leading paradigms for constructing succinct argument systems, namely Kilian's protocol and the BMW (Biehl-Meyer-Wetzel) heuristic. We define the notion of a multi-extractable somewhere statistically binding (meSSB) hash family, an extension of the notion of somewhere statistically binding hash functions (Hubacek and Wichs, ITCS 2015), and construct it from LWE. We show that when instantiating Kilian's protocol with a meSSB hash family, the first two messages are simply an instantiation of the BMW heuristic. Therefore, if we also instantiate it with a PCP for which the BMW heuristic is sound, e.g., a computational non-signaling PCP, then the first two messages of the Kilian protocol is a sound instantiation of the BMW heuristic.
This leads us to two technical results. First, we show how to efficiently convert any succinct non-interactive argument (SNARG) for BatchNP into a SNARG for any language that has a computational non-signaling PCP. Put together with the recent and independent result of Choudhuri, Jain and Jin (Eprint 2021/808) which constructs a SNARG for BatchNP from LWE, we get a SNARG for any language that has a computational non-signaling PCP, including any language in P, but also any language in NTISP (non-deterministic bounded space), from LWE.
Second, we introduce the notion of a somewhere statistically sound (SSS) interactive argument, which is a hybrid between a statistically sound proof and a computationally sound proof (a.k.a. an argument), and
* prove that Kilian's protocol, instantiated as above, is an SSS argument;
* show that the soundness of SSS arguments can be proved in a straight-line manner, implying that they are also post-quantum sound if the underlying assumption is post-quantum secure; and
* conjecture that constant-round SSS arguments can be soundly converted into non-interactive arguments via the Fiat-Shamir transformation.

2020

EUROCRYPT

Low Error Efficient Computational Extractors in the CRS Model
📺
Abstract

In recent years, there has been exciting progress on building two-source extractors for sources with low min-entropy. Unfortunately, all known explicit constructions of two-source extractors in the low entropy regime suffer from non-negligible error, and building such extractors with negligible error remains an open problem. We investigate this problem in the computational setting, and obtain the following results.
We construct an explicit 2-source extractor, and even an explicit non-malleable extractor, with negligible error, for sources with low min-entropy, under computational assumptions in the Common Random String (CRS) model. More specifically, we assume that a CRS is generated once and for all, and allow the min-entropy sources to depend on the CRS. We obtain our constructions by using the following transformations.
- Building on the technique of [BHK11], we show a general transformation for converting any computational 2-source extractor (in the CRS model) into a computational non-malleable extractor (in the CRS model), for sources with similar min-entropy.
We emphasize that the resulting computational non-malleable extractor is resilient to arbitrarily many tampering attacks (a property that is impossible to achieve information theoretically). This may be of independent interest.
This transformation uses cryptography, and in particular relies on the sub-exponential hardness of the Decisional Diffie Hellman (DDH) assumption.
- Next, using the blueprint of [BACD+17], we give a transformation converting our computational non-malleable extractor (in the CRS model) into a computational 2-source extractor for sources with low min-entropy (in the CRS model). Our 2-source extractor works for unbalanced sources: specifically, we require one of the sources to be larger than a specific polynomial in the other.
This transformation does not incur any additional assumptions. Our analysis makes a novel use of the leakage lemma of Gentry and Wichs [GW11].

2020

PKC

Witness Indistinguishability for Any Single-Round Argument with Applications to Access Control
📺
Abstract

Consider an access policy for some resource which only allows access to users of the system who own a certain set of attributes. Specifically, we consider the case where such an access structure is defined by some monotone function $$f:{0,1}^N
ightarrow {0,1}$$ , belonging to some class of function $$F$$ (e.g. conjunctions, space bounded computation), where N is the number of possible attributes. In this work we show that any succinct single-round delegation scheme for the function class $$F$$ can be converted into a succinct single-round private access control protocol. That is, a verifier can be convinced that an approved user (i.e. one which holds an approved set of attributes) is accessing the system, without learning any additional information about the user or the set of attributes. As a main tool of independent interest, we show that assuming a quasi-polynomially secure two-message oblivious transfer scheme with statistical sender privacy (which can be based on quasi-polynomial hardness of the DDH, QR, DCR or LWE assumptions), we can convert any single-round protocol into a witness indistinguishable one, with similar communication complexity.

2020

CRYPTO

Delegation with Updatable Unambiguous Proofs and PPAD-Hardness
📺
Abstract

In this work, we show the hardness of finding a Nash equilibrium, a \PPAD-complete problem, based on the quasi-polynomial hardness of the decisional assumption on groups with bilinear maps introduced by Kalai, Paneth and Yang [STOC 2019].
Towards this goal, we construct an {\em unambiguous} and {\em updatable} delegation scheme under this assumption for deterministic computations running in super-polynomial time and polynomial space.
This delegation scheme, which is of independent interest, is publicly verifiable and non-interactive in the common reference string (CRS) model. It is {\em unambiguous} meaning that it is hard to compute two different proofs for the same statement. It is {\em updatable} meaning that given a proof for the statement that a Turing machine $M$ reaches configuration $\conf_T$ in $T$ steps, one can {\em efficiently} generate a proof for the statement that $M$ reaches configuration $\conf_{T+1}$ in $T+1$ steps.

2019

CRYPTO

Non-interactive Non-malleability from Quantum Supremacy
📺
Abstract

We construct non-interactive non-malleable commitments without setup in the plain model, under well-studied assumptions.First, we construct non-interactive non-malleable commitments w.r.t. commitment for $$\epsilon \log \log n$$ tags for a small constant $$\epsilon > 0$$, under the following assumptions:1.Sub-exponential hardness of factoring or discrete log.2.Quantum sub-exponential hardness of learning with errors (LWE).
Second, as our key technical contribution, we introduce a new tag amplification technique. We show how to convert any non-interactive non-malleable commitment w.r.t. commitment for $$\epsilon \log \log n$$ tags (for any constant $$\epsilon >0$$) into a non-interactive non-malleable commitment w.r.t. replacement for $$2^n$$ tags. This part only assumes the existence of sub-exponentially secure non-interactive witness indistinguishable (NIWI) proofs, which can be based on sub-exponential security of the decisional linear assumption.Interestingly, for the tag amplification technique, we crucially rely on the leakage lemma due to Gentry and Wichs (STOC 2011). For the construction of non-malleable commitments for $$\epsilon \log \log n$$ tags, we rely on quantum supremacy. This use of quantum supremacy in classical cryptography is novel, and we believe it will have future applications. We provide one such application to two-message witness indistinguishable (WI) arguments from (quantum) polynomial hardness assumptions.

2019

TCC

Fully Homomorphic NIZK and NIWI Proofs
Abstract

In this work, we define and construct fully homomorphic non-interactive zero knowledge (FH-NIZK) and non-interactive witness-indistinguishable (FH-NIWI) proof systems. We focus on the NP complete language L, where, for a boolean circuit C and a bit b, the pair $$(C,b)\in L$$ if there exists an input $$\mathbf {w}$$ such that $$C(\mathbf {w})=b$$. For this language, we call a non-interactive proof system fully homomorphic if, given instances $$(C_i,b_i)\in L$$ along with their proofs $$\varPi _i$$, for $$i\in \{1,\ldots ,k\}$$, and given any circuit $$D:\{0,1\}^k\rightarrow \{0,1\}$$, one can efficiently compute a proof $$\varPi $$ for $$(C^*,b)\in L$$, where $$C^*(\mathbf {w}^{(1)},\ldots ,\mathbf {w}^{(k)})=D(C_1(\mathbf {w}^{(1)}),\ldots ,C_k(\mathbf {w}^{(k)}))$$ and $$D(b_1,\ldots ,b_k)=b$$. The key security property is unlinkability: the resulting proof $$\varPi $$ is indistinguishable from a fresh proof of the same statement. Our first result, under the Decision Linear Assumption (DLIN), is an FH-NIZK proof system for L in the common random string model. Our more surprising second result (under a new decisional assumption on groups with bilinear maps) is an FH-NIWI proof system that requires no setup.

2018

CRYPTO

Promise Zero Knowledge and Its Applications to Round Optimal MPC
📺
Abstract

We devise a new partitioned simulation technique for MPC where the simulator uses different strategies for simulating the view of aborting adversaries and non-aborting adversaries. The protagonist of this technique is a new notion of promise zero knowledge (ZK) where the ZK property only holds against non-aborting verifiers. We show how to realize promise ZK in three rounds in the simultaneous-message model assuming polynomially hard DDH (or QR or N$$^{th}$$-Residuosity).We demonstrate the following applications of our new technique:We construct the first round-optimal (i.e., four round) MPC protocol for general functions based on polynomially hard DDH (or QR or N$$^{th}$$-Residuosity).We further show how to overcome the four-round barrier for MPC by constructing a three-round protocol for “list coin-tossing” – a slight relaxation of coin-tossing that suffices for most conceivable applications – based on polynomially hard DDH (or QR or N$$^{th}$$-Residuosity). This result generalizes to randomized input-less functionalities.
Previously, four round MPC protocols required sub-exponential-time hardness assumptions and no multi-party three-round protocols were known for any relaxed security notions with polynomial-time simulation against malicious adversaries.In order to base security on polynomial-time standard assumptions, we also rely upon a leveled rewinding security technique that can be viewed as a polynomial-time alternative to leveled complexity leveraging for achieving “non-malleability” across different primitives.

#### Program Committees

- TCC 2020
- TCC 2017 (Program chair)
- TCC 2013
- Crypto 2012
- Crypto 2010
- TCC 2007

#### Coauthors

- Prabhanjan Ananth (1)
- Saikrishna Badrinarayanan (1)
- Boaz Barak (2)
- Nir Bitansky (6)
- Elette Boyle (1)
- Zvika Brakerski (5)
- Ran Canetti (6)
- Kai-Min Chung (2)
- Henry Cohn (1)
- Dana Dachman-Soled (3)
- Apoorvaa Deshpande (1)
- Yevgeniy Dodis (1)
- Sanjam Garg (3)
- Ankit Garg (1)
- Shafi Goldwasser (7)
- Vipul Goyal (1)
- Shai Halevi (1)
- Abhishek Jain (4)
- Bhavana Kanukurthi (1)
- Dakshita Khurana (5)
- Feng-Hao Liu (1)
- Adriana López-Alt (1)
- Anna Lysyanskaya (1)
- Omer Paneth (8)
- Chris Peikert (1)
- Renen Perlman (1)
- Raluca A. Popa (1)
- Ran Raz (2)
- Ronald L. Rivest (1)
- Alon Rosen (1)
- Ron D. Rothblum (3)
- Guy N. Rothblum (3)
- Amit Sahai (6)
- Adi Shamir (2)
- Salil P. Vadhan (1)
- Vinod Vaikuntanathan (4)
- Mayank Varia (1)
- Daniel Wichs (2)
- Lizhen Yang (1)
- Nickolai Zeldovich (1)
- Rachel Yun Zhang (1)