Benny Applebaum

STOC Conference 2025 Conference Paper

The Meta-complexity of Secret Sharing

• Benny Applebaum
• Oded Nir

A secret-sharing scheme allows the distribution of a secret s among n parties, such that only certain predefined “authorized” sets of parties can reconstruct the secret, while all other “unauthorized” sets learn nothing about s . The collection of authorized/unauthorized sets is defined by a monotone function f : {0,1} n → {0,1}. It is known that any monotone function can be realized by a secret-sharing scheme; thus, the smallest achievable total share size , S ( f ), serves as a natural complexity measure. In this paper, we initiate the study of the following meta-complexity question: Given a monotone function f , is it possible to efficiently distinguish between cases where the secret-sharing complexity of f is small versus large? We examine this question across several computational models, yielding the following main results. (Hardness for formulas and circuits) : Given a monotone formula f of size L , it is coNP-hard to distinguish between “cheap” functions, where the maximum share size is 1 bit and the total share size is O ( L 0.01 ), and “expensive” functions, where the maximum share size is Ω(√ L ) and the total share size is Ω( L /log L ). This latter bound nearly matches known secret-sharing constructions yielding a total share size of L bits. For monotone circuits, we strengthen the bound on the expensive case to a maximum share size of Ω( L /log L ) and a total share size of Ω( L 2 /log L ). These results rule out the existence of instance-optimal compilers that map a formula f to a secret-sharing scheme with complexity polynomially related to S ( f ). (Hardness for truth tables) : Under cryptographic assumptions, either (1) every n -bit slice function can be realized by a poly( n )-size secret-sharing scheme, or (2) given a truth-table representation of f of size N = 2 n , it is computationally infeasible to distinguish in time poly( N ) between cases where S ( f ) = poly( n ) and S ( f ) = n ω(1) . Option (1) would be considered a breakthrough result, as the best-known construction for slices has a sub-exponential complexity of 2 Õ(√ n ) (Liu, Vaikuntanathan, and Wee; Eurocrypt 2018). Our proof introduces a new worst-case-to-average-case reduction for slices, which may be of independent interest. (Hardness for graphs) : We examine the simple case where f is given as a 2-DNF, represented by a graph G whose edges correspond to 2-terms, and ask whether it is possible to distinguish between cases where the share size is constant and those where the share size is large, say Ω(log n ). We establish several connections between this question and questions in communication complexity. For instance, we show that graphs admitting constant-cost secret sharing form a subclass of graphs with constant randomized communication complexity and constant-size adjacency sketches (Harms, Wild, and Zamaraev; STOC 2022). We leverage these connections to establish new lower bounds for specific graph families, derive a combinatorial characterization of graphs with constant-size linear secret-sharing schemes, and show that a natural class of myopic algorithms fails to distinguish cheap graphs from expensive ones.

SODA Conference 2024 Conference Paper

Conflict Checkable and Decodable Codes and Their Applications

• Benny Applebaum
• Eliran Kachlon

FOCS Conference 2023 Conference Paper

Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography

• Benny Applebaum
• Oded Nir

A major open problem in information-theoretic cryptography is to obtain a super-polynomial lower bound for the communication complexity of basic cryptographic tasks. This question is wide open even for very powerful non-interactive primitives such as private information retrieval (or locally-decodable codes), general secret sharing schemes, conditional disclosure of secrets, and fully-decomposable randomized encoding (or garbling schemes). In fact, for all these primitives we do not even have super-linear lower bounds. Furthermore, it is unknown how to relate these questions to each other or to other complexity-theoretic questions. In this note, we relate all these questions to the classical topic of query/space trade-offs, lifted to the setting of interactive proof systems. Specifically, we consider the following Advisor-Verifier-Prover (AVP) game: First, a function f is given to the advisor who computes an advice a. Next, an input x is given to the verifier and to the prover who claims that $f(x) \quad =1. $ The verifier should check this claim via a single round of interaction based on the private advice a and without having any additional information on f. We focus on the case where the prover is laconic and communicates only a constant number of bits, and, mostly restrict the attention to the simplest, purely information-theoretic setting, where all parties are allowed to be computationally unbounded. The goal is to minimize the total communication complexity which is dominated by the length of the advice plus the length of the verifier’s query. As our main result, we show that a super-polynomial lower bound for AVPs implies a super-polynomial lower bound for a wide range of information-theoretic cryptographic tasks. In particular, we present a communication-efficient transformation from any of the above primitives into an AVP protocol. Interestingly, each primitive induces some additional property over the resulting protocol. Thus AVP games form a new common yardstick that highlights the differences between all the above primitives. Equipped with this view, we revisit the existing (somewhat weak) lower bounds for the above primitives, and show that many of these lower bounds can be unified by proving a single counting-based lower bound on the communication of AVPs, whereas some techniques are inherently limited to specific domains. The latter is shown by proving the first polynomial separations between the complexity of secret-sharing schemes and conditional disclosure of secrets and between the complexity of randomized encodings and conditional disclosure of secrets.

STOC Conference 2023 Conference Paper

Succinct Computational Secret Sharing

• Benny Applebaum
• Amos Beimel
• Yuval Ishai
• Eyal Kushilevitz
• Tianren Liu
• Vinod Vaikuntanathan

A secret-sharing scheme enables a dealer to share a secret s among n parties such that only authorized subsets of parties, specified by a monotone access structure f :{0,1} n →{0,1}, can reconstruct s from their shares. Other subsets of parties learn nothing about s .

STOC Conference 2023 Conference Paper

The Round Complexity of Statistical MPC with Optimal Resiliency

• Benny Applebaum
• Eliran Kachlon
• Arpita Patra

In STOC 1989, Rabin and Ben-Or (RB) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with statistical (information-theoretic) security in the presence of an active (aka Byzantine) rushing adversary that controls up to half of the parties. We study the round complexity of general secure multiparty computation and several related tasks in the RB model. Our main result shows that every functionality can be realized in only four rounds of interaction which is known to be optimal. This completely settles the round complexity of statistical actively-secure optimally-resilient MPC, resolving a long line of research. Along the way, we construct the first round-optimal statistically-secure verifiable secret sharing protocol (Chor, Goldwasser, Micali, and Awerbuch; STOC 1985), show that every single-input functionality (e.g., multi-verifier zero-knowledge) can be realized in 3 rounds, and prove that the latter bound is optimal. The complexity of all our protocols is exponential in the number of parties, and the question of deriving polynomially-efficient protocols is left for future research. Our main technical contribution is a construction of a new type of statistically-secure signature scheme whose existence was open even for smaller resiliency thresholds. We also describe a new statistical compiler that lifts up passively-secure protocols to actively-secure protocols in a round-efficient way via the aid of protocols for single-input functionalities. This compiler can be viewed as a statistical variant of the GMW compiler (Goldreich, Micali, Wigderson; STOC, 1987) that originally employed zero-knowledge proofs and public-key encryption.

STOC Conference 2020 Conference Paper

Better secret sharing via robust conditional disclosure of secrets

• Benny Applebaum
• Amos Beimel
• Oded Nir
• Naty Peter

A secret-sharing scheme allows to distribute a secret s among n parties such that only some predefined “authorized” sets of parties can reconstruct the secret, and all other “unauthorized” sets learn nothing about s . For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secret-sharing scheme whose shares are of size 2 n − o ( n ) and until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan (STOC 2018) have reduced the share size to 2 0.994 n + o ( n ) , which was later improved to 2 0.892 n + o ( n ) by Applebaum et al. (EUROCRYPT 2019).

FOCS Conference 2020 Conference Paper

The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency

• Benny Applebaum
• Eliran Kachlon
• Arpita Patra

In STOC 1988, Ben-Or, Goldwasser, and Wigderson (BGW) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with perfect (information-theoretic and error-free) security at the presence of an active (aka Byzantine) rushing adversary that controls up to n/3 of the parties. We study the round complexity of general secure multiparty computation in the BGW model. Our main result shows that every functionality can be realized in only four rounds of interaction, and that some functionalities cannot be computed in three rounds. This completely settles the round-complexity of perfect actively-secure optimally-resilient MPC, resolving a long line of research. Our lower-bound is based on a novel round-reduction technique that allows us to lift existing three-round lower-bounds for verifiable secret sharing to four-round lower-bounds for general MPC. To prove the upper-bound, we develop new round-efficient protocols for computing degree-2 functionalities over large fields, and establish the completeness of such functionalities. The latter result extends the recent completeness theorem of Applebaum, Brakerski and Tsabary (TCC 2018, Eurocrypt 2019) that was limited to the binary field.

FOCS Conference 2019 Conference Paper

Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error

• Benny Applebaum
• Eliran Kachlon

Suppose that you wish to sample a random graph G over n vertices and m edges conditioned on the event that G does not contain a “small" t-size graph H (e. g. , clique) as a subgraph. Assuming that most such graphs are H-free, the problem can be solved by a simple rejected-sampling algorithm (that tests for t-cliques) with an expected running time of n O(t). Is it possible to solve the problem in running time that does not grow polynomially with n t? In this paper, we introduce the general problem of sampling a “random looking'' graph G with a given edge density that avoids some arbitrary predefined t-size subgraph H. As our main result, we show that the problem is solvable with respect to some specially crafted k-wise independent distribution over graphs. That is, we design a sampling algorithm for k-wise independent graphs that supports efficient testing for subgraph-freeness in time f(t) · n c where f is a function of t and the constant c in the exponent is independent of t. Our solution extends to the case where both G and H are d-uniform hypergraphs. We use these algorithms to obtain the first probabilistic construction of constant-degree polynomially-unbalanced expander graphs whose failure probability is negligible in n (i. e. , n -ω(1) ). In particular, given constants d>c, we output a bipartite graph that has n left nodes, n c right nodes with right-degree of d so that any right set of size at most n Ω(1) expands by factor of Ω(d). This result is extended to the setting of unique expansion as well. We observe that such a negligible-error construction can be employed in many useful settings, and present applications in coding theory (batch codes and LDPC codes), pseudorandomness (low-bias generators and randomness extractors) and cryptography. Notably, we show that our constructions yield a collection of polynomial-stretch locally-computable cryptographic pseudorandom generators based on Goldreich's one-wayness assumption resolving a central open problem in parallel-cryptography (cf. , Applebaum-Ishai-Kushilevitz, FOCS 2004; and Ishai-Kushilevitz-Ostrovsky-Sahai, STOC 2008).

FOCS Conference 2017 Conference Paper

Exponentially-Hard Gap-CSP and Local PRG via Local Hardcore Functions

• Benny Applebaum

The gap-ETH assumption (Dinur 2016; Manurangsi and Raghavendra 2016) asserts that it is exponentially-hard to distinguish between a satisfiable 3-CNF formula and a 3-CNF formula which is at most 0. 99-satisfiable. We show that this assumption follows from the exponential hardness of finding a satisfying assignment for smooth 3-CNFs. Here smoothness means that the number of satisfying assignments is not much smaller than the number of almost-satisfying assignments. We further show that the latter (smooth-ETH) assumption follows from the exponential hardness of solving constraint satisfaction problems over well-studied distributions, and, more generally, from the existence of any exponentially-hard locally-computable one-way function. This confirms a conjecture of Dinur (ECCC 2016). We also prove an analogous result in the cryptographic setting. Namely, we show that the existence of exponentially-hard locally-computable pseudorandom generator with linear stretch (el-PRG) follows from the existence of an exponentially-hard locally-computable almost regular one-way functions. None of the above assumptions (gap-ETH and el-PRG) was previously known to follow from the hardness of a search problem. Our results are based on a new construction of general (GL-type) hardcore functions that, for any exponentially-hard one-way function, output linearly many hardcore bits, can be locally computed, and consume only a linear amount of random bits. We also show that such hardcore functions have several other useful applications in cryptography and complexity theory.

STOC Conference 2016 Conference Paper

Algebraic attacks against random local functions and their countermeasures

• Benny Applebaum
• Shachar Lovett

Suppose that you have n truly random bits x =( x 1 ,…, x n ) and you wish to use them to generate m ≫ n pseudorandom bits y =( y 1 ,…, y m ) using a local mapping, i.e., each y i should depend on at most d = O (1) bits of x . In the polynomial regime of m = n s , s >1, the only known solution, originates from (Goldreich, ECCC 2000), is based on Random Local Functions : Compute y i by applying some fixed (public) d -ary predicate P to a random (public) tuple of distinct inputs ( x i 1 ,…, x i d ). Our goal in this paper is to understand, for any value of s , how the pseudorandomness of the resulting sequence depends on the choice of the underlying predicate. We derive the following results:

STOC Conference 2012 Conference Paper

Pseudorandom generators with long stretch and low locality from random local one-way functions

• Benny Applebaum

We continue the study of locally-computable pseudorandom generators (PRG) G:{0,1} n -> {0,1} m that each of their outputs depend on a small number of d input bits. While it is known that such generators are likely to exist for the case of small sub-linear stretch m=n+n 1-δ , it is less clear whether achieving larger stretch such as m=n+Ω(n), or even m=n 1+δ is possible. The existence of such PRGs, which was posed as an open question in previous works, has recently gained an additional motivation due to several interesting applications. We make progress towards resolving this question by obtaining several local constructions based on the one-wayness of "random" local functions -- a variant of an assumption made by Goldreich (ECCC 2000). Specifically, we construct collections of PRGs with the following parameters: 1. Linear stretch m=n+Ω(n) and constant locality d=O(1). 2. Polynomial stretch m=n 1+δ and any (arbitrarily slowly growing) super-constant locality d=ω(1), e.g., log*n. 3. Polynomial stretch m=n 1+δ , constant locality d=O(1), and inverse polynomial distinguishing advantage (as opposed to the standard case of n -ω(1) ). As an additional contribution, we show that our constructions give rise to strong inapproximability results for the densest-subgraph problem in d-uniform hypergraphs for constant d. This allows us to improve the previous bounds of Feige (STOC 2002) and Khot (FOCS 2004) from constant inapproximability factor to n ε -inapproximability, at the expense of relying on stronger assumptions.

FOCS Conference 2011 Conference Paper

How to Garble Arithmetic Circuits

• Benny Applebaum
• Yuval Ishai
• Eyal Kushilevitz

Yao's garbled circuit construction transforms a boolean circuit C: {0, 1} n → {0, 1} m into a "garbled circuit" Ĉ along with n pairs of k-bit keys, one for each input bit, such that Ĉ together with the n keys corresponding to an input x reveal C(x) and no additional information about x. The garbled circuit construction is a central tool for constant-round secure computation and has several other applications. Motivated by these applications, we suggest an efficient arithmetic variant of Yao's original construction. Our construction transforms an arithmetic circuit C: ℤ n → ℤ m over integers from a bounded (but possibly exponential) range into a garbled circuit Ĉ along with n affine functions L i: ℤ → ℤ k such that Ĉ together with the n integer vectors L i (x i ) reveal C(x) and no additional information about x. The security of our construction relies on the intractability of the learning with errors (LWE) problem.

STOC Conference 2010 Conference Paper

Public-key cryptography from different assumptions

• Benny Applebaum
• Boaz Barak
• Avi Wigderson

This paper attempts to broaden the foundations of public-key cryptography. We construct new public-key encryption schemes based on new hardness-on-average assumptions for natural combinatorial NP-hard optimization problems. We consider the following assumptions: It is infeasible to solve a random set of sparse linear equations mod 2, of which a small fraction is noisy. It is infeasible to distinguish between a random unbalanced bipartite graph, and such a graph in which we "plant" at random in the large side a set S with only |S|/3 neighbors. There is a pseudorandom generator in NCz where every output depends on a random constant-size subset of the inputs. We obtain semantically secure public key encryption schemes based on several combinations of these assumptions with different parameters. In particular we obtain public key encryption from Assumption~1 on its own, yielding the first noisy-equations type public key scheme in which the noise rate is higher than one over the square root of the number of equations. We also obtain public-key encryption based on a combination of Assumptions~2 and~3. These are arguably of more "combinatorial"/"private-key" nature than any assumptions used before for public-key cryptography. Our proof involves novel "search to decision" and "search to prediction" reductions for sparse noisy linear equations. The strength of our assumptions raise new algorithmic and pseudorandomness questions (and new parameters for old ones). We give some evidence for these assumptions by studying their resistance to certain classes of natural algorithms, including semi-definite programs, ACO circuits, low-degree polynomials, and cycle counting. We also relate our assumptions to other problems such as planted clique and learning juntas.

FOCS Conference 2008 Conference Paper

On Basing Lower-Bounds for Learning on Worst-Case Assumptions

• Benny Applebaum
• Boaz Barak
• David Xiao

We consider the question of whether P ne NP implies that there exists some concept class that is efficientlyrepresentable but is still hard to learn in the PAC model of Valiant (CACM '84), where the learner is allowed to output any efficient hypothesis approximating the concept, including an "improper" hypothesis that is not itself in the concept class. We show that unless the polynomial hierarchy collapses, such a statement cannot be proven via a large class of reductions including Karp reductions, truth-table reductions, and a restricted form of non-adaptive Turing reductions. Also, a proof that uses a Turing reduction of constant levels of adaptivity would imply an important consequence in cryptography as it yields a transformation from any average-case hard problem in NP to a one-way function. Our results hold even in the stronger model of agnostic learning. These results are obtained by showing that lower bounds for improper learning are intimately related to the complexity of zero-knowledge arguments and to the existence of weak cryptographic primitives. In particular, we prove that if alanguage L reduces to the task of improper learning of circuits, then, depending on the type of the reduction in use, either (1) L has a statistical zero-knowledge argument system, or (2) the worst-case hardness of L implies the existence of a weak variant of one-way functions defined by Ostrovsky-Wigderson (ISTCS '93). Interestingly, we observe that the converse implication also holds. Namely, if (1) or (2) hold then the intractability of L implies that improper learning is hard.

FOCS Conference 2004 Conference Paper

Cryptography in NC 0

• Benny Applebaum
• Yuval Ishai
• Eyal Kushilevitz

We study the parallel time-complexity of basic cryptographic primitives such as one-way functions (OWFs) and pseudorandom generators (PRGs). Specifically, we study the possibility of computing instances of these primitives by NC/sup 0/ circuits, in which each output bit depends on a constant number of input bits. Despite previous efforts in this direction, there has been no significant theoretical evidence supporting this possibility, which was posed as an open question in several previous works. We essentially settle this question by providing overwhelming positive evidence for the possibility of cryptography in NC/sup 0/. Our main result is that every "moderately easy" OWF (resp. , PRG), say computable in NC/sup 1/, can be compiled into a corresponding OWF (resp. , low-stretch PRG) in NC/sub 4//sup 0/, i. e. whose output bits each depend on at most 4 input bits. The existence of OWF and PRG in NC/sup 1/ is a relatively mild assumption, implied by most number-theoretic or algebraic intractability assumptions commonly used in cryptography. Hence, the existence of OWF and PRG in NC/sup 0/ follows from a variety of standard assumptions. A similar compiler can also be obtained for other cryptographic primitives such as one-way permutations, encryption, commitment, and collision-resistant flashing. The above results leave a small gap between the possibility of cryptography in NC/sub 4//sup 0/, and the known impossibility of implementing even OWF in NC/sub 2//sup 0/. We partially close this gap by providing evidence for the existence of OWF in NC/sub 3//sup 0/. Finally, our techniques can also be applied to obtain unconditionally provable constructions of non-cryptographic PRGs. In particular, we obtain e-biased generators in NC/sub 3//sup 0/, resolving an open question posed by Mossel et al. (2003), as well as a PRG for logspace in NC/sup 0/. Our results make use of the machinery of randomizing polynomials which was originally motivated by questions in the domain of information-theoretic secure multiparty computation.