## CryptoDB

### Prashant Nalini Vasudevan

#### Affiliation: UC Berkeley

#### Publications

**Year**

**Venue**

**Title**

2019

CRYPTO

Leakage Resilient Secret Sharing and Applications
📺
Abstract

A secret sharing scheme allows a dealer to share a secret among a set of n parties such that any authorized subset of the parties can recover the secret, while any unauthorized subset learns no information about the secret. A leakage-resilient secret sharing scheme (introduced in independent works by Goyal and Kumar, STOC ’18 and Benhamouda, Degwekar, Ishai and Rabin, CRYPTO ’18) additionally requires the secrecy to hold against every unauthorized set of parties even if they obtain some bounded leakage from every other share. The leakage is said to be local if it is computed independently for each share. So far, the only known constructions of local leakage resilient secret sharing schemes are for threshold access structures for very low (O(1)) or very high (
$$n -o(\log n)$$
) thresholds.In this work, we give a compiler that takes a secret sharing scheme for any monotone access structure and produces a local leakage resilient secret sharing scheme for the same access structure, with only a constant-factor asymptotic blow-up in the sizes of the shares. Furthermore, the resultant secret sharing scheme has optimal leakage-resilience rate, i.e., the ratio between the leakage tolerated and the size of each share can be made arbitrarily close to 1. Using this secret sharing scheme as the main building block, we obtain the following results:Rate Preserving Non-Malleable Secret Sharing. We give a compiler that takes any secret sharing scheme for a 4-monotone access structure (A 4-monotone access structure has the property that any authorized set has size at least 4.) with rate R and converts it into a non-malleable secret sharing scheme for the same access structure with rate
$$\varOmega (R)$$
. The previous such non-zero rate construction (Badrinarayanan and Srinivasan, EUROCRYPT ’19) achieved a rate of
$$\varTheta (R/{t_{\max }\log ^2 n})$$
, where
$$t_{\max }$$
is the maximum size of any minimal set in the access structure. As a special case, for any threshold
$$t \ge 4$$
and an arbitrary
$$n \ge t$$
, we get the first constant-rate construction of t-out-of-n non-malleable secret sharing.Leakage-Tolerant Multiparty Computation for General Interaction Patterns. For any function f, we give a reduction from constructing a leakage-tolerant secure multi-party computation protocol for computing f that obeys any given interaction pattern to constructing a secure (but not necessarily leakage-tolerant) protocol for a related function that obeys the star interaction pattern. Together with the known results for the star interaction pattern, this gives leakage tolerant MPC for any interaction pattern with statistical/computational security. This improves upon the result of (Halevi et al., ITCS 2016), who presented such a reduction in a leak-free environment.

2019

TCC

Statistical Difference Beyond the Polarizing Regime
Abstract

The polarization lemma for statistical distance (
$${\text {SD}}$$
), due to Sahai and Vadhan (JACM, 2003), is an efficient transformation taking as input a pair of circuits
$$(C_0,C_1)$$
and an integer k and outputting a new pair of circuits
$$(D_0,D_1)$$
such that if
$${\text {SD}}(C_0,C_1) \ge \alpha $$
then
$${\text {SD}}(D_0,D_1) \ge 1-2^{-k}$$
and if
$${\text {SD}}(C_0,C_1) \le \beta $$
then
$${\text {SD}}(D_0,D_1) \le 2^{-k}$$
. The polarization lemma is known to hold for any constant values
$$\beta < \alpha ^2$$
, but extending the lemma to the regime in which
$$\alpha ^2 \le \beta < \alpha $$
has remained elusive. The focus of this work is in studying the latter regime of parameters. Our main results are: 1.Polarization lemmas for different notions of distance, such as Triangular Discrimination (
$${{\,\mathrm{TD}\,}}$$
) and Jensen-Shannon Divergence (
$${{\,\mathrm{JS}\,}}$$
), which enable polarization for some problems where the statistical distance satisfies
$$ \alpha ^2< \beta < \alpha $$
. We also derive a polarization lemma for statistical distance with any inverse-polynomially small gap between
$$ \alpha ^2 $$
and
$$ \beta $$
(rather than a constant).2.The average-case hardness of the statistical difference problem (i.e., determining whether the statistical distance between two given circuits is at least
$$\alpha $$
or at most
$$\beta $$
), for any values of
$$\beta < \alpha $$
, implies the existence of one-way functions. Such a result was previously only known for
$$\beta < \alpha ^2$$
.3.A (direct) constant-round interactive proof for estimating the statistical distance between any two distributions (up to any inverse polynomial error) given circuits that generate them. Proofs of closely related statements have appeared in the literature but we give a new proof which we find to be cleaner and more direct.

2018

CRYPTO

From Laconic Zero-Knowledge to Public-Key Cryptography
📺
Abstract

Since its inception, public-key encryption (
$$\mathsf {PKE}$$
PKE) has been one of the main cornerstones of cryptography. A central goal in cryptographic research is to understand the foundations of public-key encryption and in particular, base its existence on a natural and generic complexity-theoretic assumption. An intriguing candidate for such an assumption is the existence of a cryptographically hard language .In this work we prove that public-key encryption can be based on the foregoing assumption, as long as the (honest) prover in the zero-knowledge protocol is efficient and laconic. That is, messages that the prover sends should be efficiently computable (given the witness) and short (i.e., of sufficiently sub-logarithmic length). Actually, our result is stronger and only requires the protocol to be zero-knowledge for an honest-verifier and sound against computationally bounded cheating provers.Languages in with such laconic zero-knowledge protocols are known from a variety of computational assumptions (e.g., Quadratic Residuocity, Decisional Diffie-Hellman, Learning with Errors, etc.). Thus, our main result can also be viewed as giving a unifying framework for constructing
$$\mathsf {PKE}$$
PKE which, in particular, captures many of the assumptions that were already known to yield
$$\mathsf {PKE}$$
PKE.We also show several extensions of our result. First, that a certain weakening of our assumption on laconic zero-knowledge is actually equivalent to
$$\mathsf {PKE}$$
PKE, thereby giving a complexity-theoretic characterization of
$$\mathsf {PKE}$$
PKE. Second, a mild strengthening of our assumption also yields a (2-message) oblivious transfer protocol.

2018

CRYPTO

Proofs of Work From Worst-Case Assumptions
📺
Abstract

We give Proofs of Work (PoWs) whose hardness is based on well-studied worst-case assumptions from fine-grained complexity theory. This extends the work of (Ball et al., STOC ’17), that presents PoWs that are based on the Orthogonal Vectors, 3SUM, and All-Pairs Shortest Path problems. These, however, were presented as a ‘proof of concept’ of provably secure PoWs and did not fully meet the requirements of a conventional PoW: namely, it was not shown that multiple proofs could not be generated faster than generating each individually. We use the considerable algebraic structure of these PoWs to prove that this non-amortizability of multiple proofs does in fact hold and further show that the PoWs’ structure can be exploited in ways previous heuristic PoWs could not.This creates full PoWs that are provably hard from worst-case assumptions (previously, PoWs were either only based on heuristic assumptions or on much stronger cryptographic assumptions (Bitansky et al., ITCS ’16)) while still retaining significant structure to enable extra properties of our PoWs. Namely, we show that the PoWs of (Ball et al., STOC ’17) can be modified to have much faster verification time, can be proved in zero knowledge, and more.Finally, as our PoWs are based on evaluating low-degree polynomials originating from average-case fine-grained complexity, we prove an average-case direct sum theorem for the problem of evaluating these polynomials, which may be of independent interest. For our context, this implies the required non-amortizability of our PoWs.

2017

CRYPTO

#### Program Committees

- Eurocrypt 2020
- TCC 2019

#### Coauthors

- Benny Applebaum (1)
- Barak Arkis (1)
- Marshall Ball (1)
- Itay Berman (3)
- Akshay Degwekar (4)
- Pavel Raykov (1)
- Alon Rosen (1)
- Ron D. Rothblum (3)
- Manuel Sabin (1)
- Akshayaram Srinivasan (1)
- Vinod Vaikuntanathan (3)