## CryptoDB

### Yael Tauman Kalai

#### Publications

Year
Venue
Title
2021
TCC
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
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
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
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
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
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
EUROCRYPT
2018
CRYPTO
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.
2017
CRYPTO
2017
CRYPTO
2017
ASIACRYPT
2016
TCC
2016
TCC
2016
TCC
2015
TCC
2015
CRYPTO
2014
CRYPTO
2014
CRYPTO
2014
EUROCRYPT
2014
TCC
2014
TCC
2014
CRYPTO
2013
TCC
2013
CRYPTO
2013
CRYPTO
2012
TCC
2012
CRYPTO
2011
TCC
2011
CRYPTO
2011
CRYPTO
2011
ASIACRYPT
2010
TCC
2010
TCC
2010
CRYPTO
2009
CRYPTO
2008
CRYPTO
2005
EUROCRYPT
2001
ASIACRYPT
2001
CRYPTO

#### Program Committees

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