All reports by Author Benny Applebaum:

__
TR24-108
| 28th June 2024
__

Benny Applebaum, Eliran Kachlon#### Stochastic Secret Sharing with $1$-Bit Shares and Applications to MPC

__
TR24-105
| 13th June 2024
__

Benny Applebaum, Kaartik Bhushan, Manoj Prabhakaran#### Communication Complexity vs Randomness Complexity in Interactive Proofs

__
TR23-136
| 14th September 2023
__

Benny Applebaum, Oded Nir#### Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography

__
TR23-091
| 18th June 2023
__

Benny Applebaum, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tianren Liu, Vinod Vaikuntanathan#### Succinct Computational Secret Sharing

__
TR23-087
| 9th June 2023
__

Benny Applebaum, Oded Nir, Benny Pinkas#### How to Recover a Secret with $O(n)$ Additions

Revisions: 1

__
TR23-062
| 2nd May 2023
__

Benny Applebaum, Eliran Kachlon#### Conflict Checkable and Decodable Codes and Their Applications

__
TR23-031
| 23rd March 2023
__

Benny Applebaum, Eliran Kachlon, Arpita Patra#### The Round Complexity of Statistical MPC with Optimal Resiliency

__
TR22-006
| 12th January 2022
__

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi#### Secret Sharing, Slice Formulas, and Monotone Real Circuits

__
TR21-052
| 12th April 2021
__

Benny Applebaum, Oded Nir#### Upslices, Downslices, and Secret-Sharing with Complexity of $1.5^n$

__
TR20-076
| 17th May 2020
__

Benny Applebaum, Eliran Kachlon, Arpita Patra#### The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency

__
TR20-008
| 26th January 2020
__

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter#### Better Secret-Sharing via Robust Conditional Disclosure of Secrets

Revisions: 2

__
TR19-011
| 27th January 2019
__

Benny Applebaum, Eliran Kachlon#### Sampling Graphs without Forbidden Subgraphs and Almost-Explicit Unbalanced Expanders

Revisions: 3

__
TR18-208
| 27th November 2018
__

Benny Applebaum, Prashant Nalini Vasudevan#### Placing Conditional Disclosure of Secrets in the Communication Complexity Universe

Revisions: 2

__
TR18-033
| 16th February 2018
__

Benny Applebaum, Thomas Holenstein, Manoj Mishra, Ofer Shayevitz#### The Communication Complexity of Private Simultaneous Messages, Revisited

Revisions: 2

__
TR17-189
| 25th December 2017
__

Benny Applebaum, Barak Arkis#### Conditional Disclosure of Secrets and $d$-Uniform Secret Sharing with Constant Information Rate

Revisions: 1

__
TR17-067
| 21st April 2017
__

Benny Applebaum#### Garbled Circuits as Randomized Encodings of Functions: a Primer

__
TR17-063
| 10th April 2017
__

Benny Applebaum#### Exponentially-Hard gap-CSP and local PRG via Local Hardcore Functions

__
TR17-038
| 23rd February 2017
__

Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan#### Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations

Revisions: 1

__
TR17-008
| 14th January 2017
__

Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz, Vinod Vaikuntanathan#### Low-Complexity Cryptographic Hash Functions

__
TR16-082
| 22nd May 2016
__

Benny Applebaum, Pavel Raykov#### Fast Pseudorandom Functions Based on Expander Graphs

__
TR15-206
| 15th December 2015
__

Benny Applebaum, Pavel Raykov#### From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back

__
TR15-186
| 24th November 2015
__

Benny Applebaum, Pavel Raykov#### On the Relationship between Statistical Zero-Knowledge and Statistical Randomized Encodings

__
TR15-172
| 3rd November 2015
__

Benny Applebaum, Shachar Lovett#### Algebraic Attacks against Random Local Functions and Their Countermeasures

Revisions: 1

__
TR15-061
| 14th April 2015
__

Benny Applebaum, Jonathan Avron, Christina Brzuska#### Arithmetic Cryptography

Revisions: 1

__
TR15-051
| 5th April 2015
__

Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang#### Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterminsitic Reductions

Revisions: 2

__
TR15-045
| 1st April 2015
__

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz#### Minimizing Locality of One-Way Functions via Semi-Private Randomized Encodings

Revisions: 1

__
TR15-027
| 25th February 2015
__

Benny Applebaum#### Cryptographic Hardness of Random Local Functions -- Survey

Revisions: 1

__
TR13-098
| 28th June 2013
__

Benny Applebaum, Yoni Moses#### Locally Computable UOWHF with Linear Shrinkage

Revisions: 2

__
TR12-058
| 5th May 2012
__

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz#### How to Garble Arithmetic Circuits

Revisions: 1

__
TR11-126
| 17th September 2011
__

Benny Applebaum, Andrej Bogdanov, Alon Rosen#### A Dichotomy for Local Small-Bias Generators

__
TR11-007
| 17th January 2011
__

Benny Applebaum#### Pseudorandom Generators with Long Stretch and Low locality from Random Local One-Way Functions

Revisions: 3

Benny Applebaum, Eliran Kachlon

The problem of minimizing the share size of threshold secret-sharing schemes is a basic research question that has been extensively studied. Ideally, one strives for schemes in which the share size equals the secret size. While this is achievable for large secrets (Shamir, CACM '79), no similar solutions are known ... more >>>

Benny Applebaum, Kaartik Bhushan, Manoj Prabhakaran

In this note, we study the interplay between the communication from a verifier in a general private-coin interactive protocol and the number of random bits it uses in the protocol. Under worst-case derandomization assumptions, we show that it is possible to transform any $I$-round interactive protocol that uses $\rho$ random ... more >>>

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 ... more >>>

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\to\{0,1\}$, can reconstruct $s$ from their shares. Other subsets of parties learn nothing about $s$.

The question of minimizing the (largest) share size ... more >>>

Benny Applebaum, Oded Nir, Benny Pinkas

Threshold cryptography is typically based on the idea of secret-sharing a private-key $s\in F$ ``in the exponent'' of some cryptographic group $G$, or more generally, encoding $s$ in some linearly homomorphic domain. In each invocation of the threshold system (e.g., for signing or decrypting) an ``encoding'' of the secret is ... more >>>

Benny Applebaum, Eliran Kachlon

Let $C$ be an error-correcting code over a large alphabet $q$ of block length $n$, and assume that, a possibly corrupted, codeword $c$ is distributively stored among $n$ servers where the $i$th entry is being held by the $i$th server. Suppose that every pair of servers publicly announce whether the ... more >>>

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 ... more >>>

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi

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 ... more >>>

Benny Applebaum, Oded Nir

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$.

The collection of authorized/unauthorized sets can be captured by a monotone function $f:\{0,1\}^n\rightarrow \{0,1\}$.

more >>>

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 ... more >>>

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$. The collection of authorized sets is called the access structure. For over 30 years, it was ... more >>>

Benny Applebaum, Eliran Kachlon

We initiate the study of the following hypergraph sampling problem: Sample a $d$-uniform hypergraph over $n$ vertices and $m$ hyperedges from some pseudorandom distribution $\mathcal{G}$ conditioned on not having some small predefined $t$-size hypergraph $H$ as a subgraph. The algorithm should run in $\mathrm{poly}(n)$-time even when the size of the ... more >>>

Benny Applebaum, Prashant Nalini Vasudevan

In the *Conditional Disclosure of Secrets* (CDS) problem (Gertner et al., J. Comput. Syst. Sci., 2000) Alice and Bob, who hold $n$-bit inputs $x$ and $y$ respectively, wish to release a common secret $z$ to Carol (who knows both $x$ and $y$) if and only if the input $(x,y)$ satisfies ... more >>>

Benny Applebaum, Thomas Holenstein, Manoj Mishra, Ofer Shayevitz

Private Simultaneous Message (PSM) protocols were introduced by Feige, Kilian and Naor (STOC '94) as a minimal non-interactive model for information-theoretic three-party secure computation. While it is known that every function $f:\{0,1\}^k\times \{0,1\}^k \rightarrow \{0,1\}$ admits a PSM protocol with exponential communication of $2^{k/2}$ (Beimel et al., TCC '14), the ... more >>>

Benny Applebaum, Barak Arkis

Consider the following secret-sharing problem. Your goal is to distribute a long file $s$ between $n$ servers such that $(d-1)$-subsets cannot recover the file, $(d+1)$-subsets can recover the file, and $d$-subsets should be able to recover $s$ if and only if they appear in some predefined list $L$. How small ... more >>>

Benny Applebaum

Yao's garbled circuit construction is a central cryptographic tool with numerous applications. In this tutorial, we study garbled circuits from a foundational point of view under the framework of \emph{randomized encoding} (RE) of functions. We review old and new constructions of REs, present some lower bounds, and describe some applications. ... more >>>

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 ... more >>>

Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan

In the \emph{conditional disclosure of secrets} problem (Gertner et al., J. Comput. Syst. Sci., 2000) Alice and Bob, who hold inputs $x$ and $y$ respectively, wish to release a common secret $s$ to Carol (who knows both $x$ and $y$) if only if the input $(x,y)$ satisfies some predefined predicate ... more >>>

Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz, Vinod Vaikuntanathan

Cryptographic hash functions are efficiently computable functions that shrink a long input into a shorter output while achieving some of the useful security properties of a random function. The most common type of such hash functions is {\em collision resistant} hash functions (CRH), which prevent an efficient attacker from finding ... more >>>

Benny Applebaum, Pavel Raykov

We present direct constructions of pseudorandom function (PRF) families based on Goldreich's one-way function. Roughly speaking, we assume that non-trivial local mappings $f:\{0,1\}^n\rightarrow \{0,1\}^m$ whose input-output dependencies graph form an expander are hard to invert. We show that this one-wayness assumption yields PRFs with relatively low complexity. This includes weak ... more >>>

Benny Applebaum, Pavel Raykov

Goos, Pitassi and Watson (ITCS, 2015) have recently introduced the notion of Zero-Information Arthur-Merlin Protocols (ZAM). In this model, which can be viewed as a private version of the standard Arthur-Merlin communication complexity game, Alice and Bob are holding a pair of inputs $x$ and $y$ respectively, and Merlin, the ... more >>>

Benny Applebaum, Pavel Raykov

\emph{Statistical Zero-knowledge proofs} (Goldwasser, Micali and Rackoff, SICOMP 1989) allow a computationally-unbounded server to convince a computationally-limited client that an input $x$ is in a language $\Pi$ without revealing any additional information about $x$ that the client cannot compute by herself. \emph{Randomized encoding} (RE) of functions (Ishai and Kushilevitz, FOCS ... more >>>

Benny Applebaum, Shachar Lovett

Suppose that you have $n$ truly random bits $x=(x_1,\ldots,x_n)$ and you wish to use them to generate $m\gg n$ pseudorandom bits $y=(y_1,\ldots, 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, ... more >>>

Benny Applebaum, Jonathan Avron, Christina Brzuska

We study the possibility of computing cryptographic primitives in a fully-black-box arithmetic model over a finite field F. In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field elements, the honest parties are implemented by arithmetic circuits which make only a ... more >>>

Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang

A circuit $C$ \emph{compresses} a function $f:\{0,1\}^n\rightarrow \{0,1\}^m$ if given an input $x\in \{0,1\}^n$ the circuit $C$ can shrink $x$ to a shorter $\ell$-bit string $x'$ such that later, a computationally-unbounded solver $D$ will be able to compute $f(x)$ based on $x'$. In this paper we study the existence of ... more >>>

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

A one-way function is $d$-local if each of its outputs depends on at most $d$ input bits. In (Applebaum, Ishai, and Kushilevitz, FOCS 2004) it was shown that, under relatively mild assumptions, there exist $4$-local one-way functions (OWFs). This result is not far from optimal as it is not hard ... more >>>

Benny Applebaum

Constant parallel-time cryptography allows to perform complex cryptographic tasks at an ultimate level of parallelism, namely, by local functions that each of their output bits depend on a constant number of input bits. A natural way to obtain local cryptographic constructions is to use \emph{random local functions} in which each ... more >>>

Benny Applebaum, Yoni Moses

We study the problem of constructing locally computable Universal One-Way Hash Functions (UOWHFs) $H:\{0,1\}^n \rightarrow \{0,1\}^m$. A construction with constant \emph{output locality}, where every bit of the output depends only on a constant number of bits of the input, was established by [Applebaum, Ishai, and Kushilevitz, SICOMP 2006]. However, this ... more >>>

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

Yao's garbled circuit construction transforms a boolean circuit $C:\{0,1\}^n\to\{0,1\}^m$

into a ``garbled circuit'' $\hat{C}$ along with $n$ pairs of $k$-bit keys, one for each

input bit, such that $\hat{C}$ together with the $n$ keys

corresponding to an input $x$ reveal $C(x)$ and no additional information about $x$.

The garbled circuit ...
more >>>

Benny Applebaum, Andrej Bogdanov, Alon Rosen

We consider pseudorandom generators in which each output bit depends on a constant number of input bits. Such generators have appealingly simple structure: they can be described by a sparse input-output dependency graph and a small predicate that is applied at each output. Following the works of Cryan and Miltersen ... more >>>

Benny Applebaum

We continue the study of pseudorandom generators (PRG) $G:\{0,1\}^n \rightarrow \{0,1\}^m$ in NC0. While it is known that such generators are likely to exist for the case of small sub-linear stretch $m=n+n^{1-\epsilon}$, it remains unclear whether achieving larger stretch such as $m=2n$ or even $m=n+n^2$ is possible. The existence of ... more >>>