Jad Silbak

FOCS Conference 2025 Conference Paper

Binary Codes for Computationally Bounded Errors Under Standard Crypto Assumptions

• George Lu
• Jad Silbak
• Daniel Wichs

We study error-detection and error-correction codes for computationally bounded adversarial channels. We consider seeded codes where the polynomial-time encoding and decoding procedures share a public random seed, but are otherwise deterministic. An adversarial channel gets this seed and can perform arbitrary polynomial-time computation to adaptively select both the message to be encoded and a bounded number of errors to be added to the resulting codeword. The goal is to detect or correct such errors with overwhelming probability, while achieving better trade-offs between rate and error tolerance than those possible for computationally unbounded channels. For large alphabets, prior work (ITCS ‘25) achieves essentially optimal parameters under minimal cryptographic assumptions. However, for the binary alphabet, prior works (TCC ‘20, EUROCRYPT ‘25) either only achieved a weaker notion of selective security under the learning with errors (LWE) assumption, or relied on non-standard cryptographic assumptions to get the full notion of adaptive security. In this work, we construct binary codes that achieve the full notion of adaptive security assuming trapdoor hashing, which can in turn be instantiated under a variety of standard cryptographic assumptions such as LWE, or Decisional DiffieHellman (DDH), or Quadratic Residuosity (QR), or Decisional Composite Residuosity (DCR). For error detection, our codes get essentially optimal rate $R \approx 1$ and relative error tolerance $p \approx \frac{1}{2}$. For error correction, they can uniquely correct $p\lt1 / 4$ fraction of errors with a rate R matching that of the best known list-decodable codes for this error tolerance. As a central technical tool of potentially independent interest, we construct multi-input correlation intractable hashing for “shifted output relations” under the standard cryptographic assumptions above.

STOC Conference 2025 Conference Paper

Extractors for Samplable Distributions with Low Min-Entropy

• Marshall Ball
• Ronen Shaltiel
• Jad Silbak

Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions. They showed that under a very strong complexity theoretic hardness assumption, there are extractors for samplable distributions with large min-entropy of k =(1−γ) · n , for some small constant γ>0. Recent work by Ball, Goldin, Dachman-Soled and Mutreja (FOCS 2023) weakened the hardness assumption. However, since the original paper by Trevisan and Vadhan, there has been no improvement in the min-entropy threshold k . In this paper we give a construction of extractors for samplable distributions with low min-entropy of k = n 1−γ for some constant γ>0, and in particular we achieve k 0, and a problem in =(2 O ( n ) ) that cannot be computed by size 2 β n circuits that have an oracle to Σ 5 ¶ . Our approach builds on the technique of Trevisan and Vadhan, while introducing new objects and ideas. We introduce and construct two objects: an errorless (seedless) condenser for samplable distributions, and functions that are hard to compute on every samplable distributions with sufficient min-entropy. We use techniques by Shaltiel and Silbak (STOC 2024), as well as additional tools and ideas, to construct the two new objects, under the hardness assumption. We then show how to modify the construction of Trevisan and Vadhan, using these new objects, so that the barrier of k = n /2 can be bypassed, and we can achieve an extractor for samplable distributions with low min-entropy.

STOC Conference 2024 Conference Paper

Explicit Codes for Poly-Size Circuits and Functions That Are Hard to Sample on Low Entropy Distributions

• Ronen Shaltiel
• Jad Silbak

FOCS Conference 2022 Conference Paper

Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits

• Ronen Shaltiel
• Jad Silbak

Guruswami and Smith (J. ACM 2016) considered codes for channels that are poly-size circuits which modify at most a p-fraction of the bits of the codeword. This class of channels is significantly stronger than Shannon’s binary symmetric channel (BSC), but weaker than Hamming’s channels which are computationally unbounded. Guruswami and Smith gave an explicit Monte-Carlo construction of codes with optimal rate of R(p) = 1 − H(p) that achieve list-decoding in this scenario. Here, “explicit Monte-Carlo” means that both encoding and decoding algorithms run in polynomial time. However, the encoding and decoding algorithms also receive a uniformly chosen string of polynomial length (which is chosen and published, once and for all, in a pre-processing stage) and their correctness is guaranteed w. h. p. over this random choice. Guruswami and Smith asked whether it is possible to obtain uniquely decodable codes for poly-size channels with rate that beats the Gilbert-Varshamov bound $R^{GV}(p)=1-H(2p)$. We give an affirmative answer, Specifically: •For every $0\leq p\lt\frac{1}{4}$, we give an explicit Monte-Carlo construction of uniquely-decodable codes with optimal rate R(p) = 1 − H(p). This matches the rate achieved by Guruswami and Smith for the easier task of list-decoding, and also matches the capacity of binary symmetric channels. Moreover, this rate is strictly larger than that of codes for the standard coding scenario (namely, uniquely-decodable codes for Hamming channels). •Even ignoring explicitness, our result implies a characterization of the capacity of poly-size channels, which was not previously understood. Our technique builds on the earlier list-decodable codes of Guruswami and Smith, achieving unique-decoding by extending and modifying the construction so that we can identify the correct message in the list. For this purpose we use ideas from coding theory and pseudorandomness, specifically: •We construct codes for binary symmetric channels that beat the Gilbert-Varshamov bound, and are “evasive” in the sense that a poly-size circuit that receives a random (or actually pseudorandom) string, cannot find a codeword within relative distance 2p. This notion of evasiveness is inspired by the recent work of Shaltiel and Silbak (STOC 2021) on codes for space bounded channels. •We develop a methodology (that is inspired by proofs of t-wise independent tail inequalities, and may be of independent interest) to analyze random codes, in scenarios where the success of the channel is measured in an additional random experiment (as in the evasiveness experiment above). •We introduce a new notion of “small-set non-malleable codes” that is tailored for our application, and may be of independent interest.

STOC Conference 2022 Conference Paper

On the complexity of two-party differential privacy

• Iftach Haitner
• Noam Mazor
• Jad Silbak
• Eliad Tsfadia

In distributed differential privacy, the parties perform analysis over their joint data while preserving the privacy for both datasets. Interestingly, for a few fundamental two-party functions such as inner product and Hamming distance, the accuracy of the distributed solution lags way behind what is achievable in the client-server setting. McGregor, Mironov, Pitassi, Reingold, Talwar, and Vadhan [FOCS ’10] proved that this gap is inherent, showing upper bounds on the accuracy of (any) distributed solution for these functions. These limitations can be bypassed when settling for computational differential privacy, where the data is differentially private only in the eyes of a computationally bounded observer, using oblivious transfer. We prove that the use of public-key cryptography is necessary for bypassing the limitation of McGregor et al., showing that a non-trivial solution for the inner product, or the Hamming distance, implies the existence of a key-agreement protocol. Our bound implies a combinatorial proof for the fact that non-Boolean inner product of independent (strong) Santha-Vazirani sources is a good condenser. We obtain our main result by showing that the inner-product of a (single, strong) SV source with a uniformly random seed is a good condenser, even when the seed and source are dependent.

STOC Conference 2021 Conference Paper

Explicit uniquely decodable codes for space bounded channels that achieve list-decoding capacity

• Ronen Shaltiel
• Jad Silbak

FOCS Conference 2019 Conference Paper

Quasilinear Time List-Decodable Codes for Space Bounded Channels

• Jad Silbak
• Swastik Kopparty
• Ronen Shaltiel

We consider codes for space bounded channels. This is a model for communication under noise that was studied by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in one pass, and modifies at most a p fraction of the bits of the codeword. Guruswami and Smith, and later work by Shaltiel and Silbak (RANDOM 2016), gave constructions of listdecodable codes with rate approaching 1 - H(p) against channels with space s = clog n, with encoding/decoding time poly(2 s ) = poly(n c ). In this paper we show that for every constant 0 0, there are codes with rate R ≥ 1 - H(p) - ε, list size poly(1/ε), and furthermore: . Our codes can handle channels with space s = n Ω(1), which is much larger than O(log n) achieved by previous work. . We give encoding and decoding algorithms that run in time n · polylog(n). Previous work achieved large and unspecified poly(n) time (even for space s = 1 · log n channels). . We can handle space bounded channels that read the codeword in any order, whereas previous work considered channels that read the codeword in the standard order. Our construction builds on the machinery of Guruswami and Smith (with some key modifications) replacing some nonconstructive codes and pseudorandom objects (that are found in exponential time by brute force) with efficient explicit constructions. For this purpose we exploit recent results of Haramaty, Lee and Viola (SICOMP 2018) on pseudorandom properties of “t-wise independence + low weight noise” which we quantitatively improve using techniques by Forbes and Kelly (FOCS 2018). To make use of such distributions, we give new explicit constructions of binary linear codes that have dual distance of n Ω(1), and are also polynomial time list-decodable from relative distance á1/2-ε, with list size poly(1/ε). To the best of our knowledge, no such construction was previously known. Somewhat surprisingly, we show that Reed-Solomon codes with dimension k <; √n, have this property if interpreted as binary codes (in some specific interpretation)which we term: “Raw Reed-Solomon Codes”. A key idea is viewing Reed-Solomon codes as “bundles” of certain dualBCH codewords.

FOCS Conference 2018 Conference Paper

Computational Two-Party Correlation: A Dichotomy for Key-Agreement Protocols

• Iftach Haitner
• Kobbi Nissim
• Eran Omri
• Ronen Shaltiel
• Jad Silbak

Let π be an efficient two-party protocol that given security parameter k, both parties output single bits X k and Y k, respectively. We are interested in how (X k, Y k ) "appears" to an efficient adversary that only views the transcript T k. We make the following contributions: · We develop new tools to argue about this loose notion, and show (modulo some caveats) that for every such protocol π, there exists an efficient simulator such that the following holds: on input T k, the simulator outputs a pair (X' k, Y' k ) such that (X' k, Y' k, T k ) is (somewhat) computationally indistinguishable from (X k, Y k, T k ). · We use these tools to prove the following dichotomy theorem: every such protocol π is: - either uncorrelated - it is (somewhat) indistinguishable from an efficient protocol whose parties interact to produce T k, but then choose their outputs independently from some product distribution (that is determined in poly-time from T k ), - or, the protocol implies a key-agreement protocol (for infinitely many k's). Uncorrelated protocols are uninteresting from a cryptographic viewpoint, as the correlation between outputs is (computationally) trivial. Our dichotomy shows that every protocol is either completely uninteresting or implies key-agreement. ·We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function. · A subsequent work of Haitner et al. uses the above dichotomy to makes progress on a long-standing open question regarding the complexity of fair two-party coin-flipping protocols. We highlight the following ideas regarding our technique: · The simulator algorithm is obtained by a carefully designed "competition" between efficient algorithms attempting to forecast ((X k, Y k )|T k = t). The winner is used to simulate the outputs of the protocol. · Our key-agreement protocol uses the simulation to reduce to an information theoretic setup, and is in some sense non-black box.