Daniel Wichs

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

Succinct Non-interactive Arguments of Proximity

• Liyan Chen
• Zhengzhong Jin
• Daniel Wichs

We study succinct non-interactive arguments of proximity (SNAP), which allow a prover to convince a verifier that a statement is true through a short message. Moreover, the verifier reads only a sublinear number of bits of the statement, and soundness is required to hold against polynomial-time adversaries when the statement is є-far from any true statements. SNAPs can be seen as the natural analog of property testing in the context of succinct non-interactive arguments (SNARGs). We obtain both positive and negative results for SNAPs. For any є ∈ (0, 1), we construct the first adaptively sound SNAPs for P with є-proximity based on standard assumptions: LWE or subexponential DDH or DLIN over bilinear maps. Our proof size, verifier’s query complexity, and verification time are n 1/2 + o (1) · poly (λ), where n is the length of the statement and λ is the security parameter. By additionally assuming sub-exponentially secure indistinguishability obfuscation, we upgrade this result to SNAPs for NP with essentially the same parameters. Previously, we only had non-adaptively sound SNAPs for P in the designated verifier setting with O ( n 1−δ ) proof size, query complexity, and verification time for some constant δ > 0. We show that our parameters in the adaptive soundness setting are nearly optimal, up to an n o (1) · poly (λ) factor: in any adaptive SNAP for P, the product of proof size and verifier query complexity must be Ω( n ). Our lower bound is unconditional. For any constant є ∈ (0, 1), we construct the first non-adaptively sound SNAPs for NP with є-proximity, based on learning with errors and indistinguishability obfuscation. The proof size, verifier’s query complexity, and verification time in our constructions are fixed polynomials in the security parameter. We also show that, restricting such SNAPs to just P would already imply non-adaptively sound SNARGs for NP. Central to our SNAP constructions is a new notion of commitment of proximity, which enables sublinear-time verification of the commitment. To derive our unconditional lower bound, we adopt and generalize theorems from oracle-presampling techniques in the random oracle literature. Both techniques may be of independent interest.

STOC Conference 2025 Conference Paper

Unambiguous SNARGs for P from LWE with Applications to PPAD Hardness

• Liyan Chen
• Cody Freitag
• Zhengzhong Jin
• Daniel Wichs

We construct the first unambiguous succinct non-interactive arguments (SNARGs) for P and incrementally verifiable computation (IVC) for P from the polynomial hardness of learning with errors (LWE). Unambiguity guarantees that it is computationally hard to find two distinct accepting proofs for the same statement. As an application, we establish the first PPAD hardness result based on the polynomial hardness of LWE combined with a widely believed complexity assumption. Central to our approach is a new notion of rate-1 witness-unambiguous batch arguments for NP, which we give the first construction from the polynomial hardness of LWE. This notion may be of independent interest.

FOCS Conference 2024 Conference Paper

How to Simulate Random Oracles with Auxiliary Input

• Yevgeniy Dodis
• Aayush Jain
• Huijia Lin
• Ji Luo 0002
• Daniel Wichs

The random oracle model (ROM) allows us to opti-mistically reason about security properties of cryptographic hash functions, and has been hugely influential in designing practical cryptosystems. But it is overly optimistic against non-uniform adversaries, and often suggests security properties and security levels unachievable by any real hash function. To reconcile with this discrepancy, Unruh [CRYPTO '07] proposed the auxiliary-input random oracle model (AI-ROM), where a non-uniform attacker additionally gets a bounded amount of advice about the random oracle. Proving security in the AI-ROM is often much more difficult, but a series of works starting with Unruh provided useful technical tools to do so. Although these tools lead to good results in the information-theoretic setting, they are unsatisfactory in the computational setting, where the random oracle is used alongside other computational hardness assumptions. At the most basic level, we did not even know whether it is possible to efficiently simulate random oracle queries given auxiliary input, which has remained as an explicit open problem since the work of Unruh. In this work, we resolve the above open problem and show how to efficiently simulate auxiliary-input random oracles. Moreover, the simulation has low concrete overhead, leading to small losses in exact security. We use it to prove the security of a broad class of computational schemes in the AI-ROM, including the first non-interactive zero-knowledge (NIZK) scheme in the AI-ROM. As a tool of independent interest, we develop a new notion of ultra-secure pseudorandom functions with fast RAM evaluation, which can achieve $2^{\lambda}$ security while having sublinear $\mathrm{o}(\lambda)$ evaluation time.

STOC Conference 2023 Conference Paper

Boosting Batch Arguments and RAM Delegation

• Yael Tauman Kalai
• Alex Lombardi
• Vinod Vaikuntanathan
• Daniel Wichs

We show how to generically improve the succinctness of non-interactive publicly verifiable batch argument ( BARG ) systems. In particular, we show (under a mild additional assumption) how to convert a BARG that generates proofs of length poly ( m )· k 1−є , where m is the length of a single instance and k is the number of instances being batched, into one that generates proofs of length poly ( m , log k ), which is the gold standard for succinctness of BARG s. By prior work, such BARG s imply the existence of SNARG s for deterministic time T computation with succinctness poly (log T ). Our result reduces the long-standing challenge of building publicly-verifiable delegation schemes to a much easier problem: building a batch argument system that beats the trivial construction. It also immediately implies new constructions of BARG s and SNARG s with polylogarithmic succinctness based on either bilinear maps or a combination of the DDH and QR assumptions. Along the way, we prove an equivalence between BARG s and a new notion of SNARG s for (deterministic) RAM computations that we call “ flexible RAM SNARG s with partial input soundness .” This is the first demonstration that SNARG s for deterministic computation (of any kind) imply BARG s. Our RAM SNARG notion is of independent interest and has already been used in a recent work on constructing rate-1 BARG s (Devadas et. ‍al. FOCS 2022).

STOC Conference 2023 Conference Paper

Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE

• Wei-Kai Lin
• Ethan Mook
• Daniel Wichs

A (single server) private information retrieval (PIR) allows a client to read data from a public database held on a remote server, without revealing to the server which locations she is reading. In a doubly efficient PIR (DEPIR) , the database is first preprocessed, but the server can subsequently answer any client’s query in time that is sub-linear in the database size. Prior work gave a plausible candidate for a public-key variant of DEPIR, where a trusted party is needed to securely preprocess the database and generate a corresponding public key for the clients; security relied on a new non-standard code-based assumption and a heuristic use of ideal obfuscation. In this work we construct the stronger unkeyed notion of DEPIR, where the preprocessing is a deterministic procedure that the server can execute on its own. Moreover, we prove security under just the standard ring learning-with-errors (RingLWE) assumption. For a database of size N and any constant ε>0, the preprocessing run-time and size is O ( N 1+ε ), while the run-time and communication-complexity of each PIR query is poly log( N ). We also show how to update the preprocessed database in time O ( N ε ). Our approach is to first construct a standard PIR where the server’s computation consists of evaluating a multivariate polynomial; we then convert it to a DEPIR by preprocessing the polynomial to allow for fast evaluation, using the techniques of Kedlaya and Umans (STOC ’08). Building on top of our DEPIR, we construct general fully homomorphic encryption for random-access machines (RAM-FHE) , which allows a server to homomorphically evaluate an arbitrary RAM program P over a client’s encrypted input x and the server’s preprocessed plaintext input y to derive an encryption of the output P ( x , y ) in time that scales with the RAM run-time of the computation rather than its circuit size. Prior work only gave a heuristic candidate construction of a restricted notion of RAM-FHE. In this work, we construct RAM-FHE under the RingLWE assumption with circular security. For a RAM program P with worst-case run-time T , the homomorphic evaluation runs in time T 1+ε · (| x | + | y |).

STOC Conference 2019 Conference Paper

Fiat-Shamir: from practice to theory

• Ran Canetti
• Yilei Chen 0001
• Justin Holmgren
• Alex Lombardi
• Guy N. Rothblum
• Ron D. Rothblum
• Daniel Wichs

FOCS Conference 2018 Conference Paper

Laconic Function Evaluation and Applications

• Willy Quach
• Hoeteck Wee
• Daniel Wichs

We introduce a new cryptographic primitive called laconic function evaluation (LFE). Using LFE, Alice can compress a large circuit f into a small digest. Bob can encrypt some data x under this digest in a way that enables Alice to recover f(x) without learning anything else about Bob's data. For the scheme to be laconic, we require that the size of the digest, the run-time of the encryption algorithm and the size of the ciphertext should all be small, much smaller than the circuit-size of f. We construct an LFE scheme for general circuits under the learning with errors (LWE) assumption, where the above parameters only grow polynomially with the depth but not the size of the circuit. We then use LFE to construct secure 2-party and multi-party computation (2PC, MPC) protocols with novel properties: We construct a 2-round 2PC protocol between Alice and Bob with respective inputs x A, x B in which Alice learns the output f(x A, x B ) in the second round. This is the first such protocol which is “Bob-optimized”, meaning that Alice does all the work while Bob's computation and the total communication of the protocol are smaller than the size of the circuit f or even Alice's input xA. In contrast, prior solutions based on fully homomorphic encryption are “Alice-optimized”. . We construct an MPC protocol, which allows N parties to securely evaluate a function f(x 1, .. ., x N ) over their respective inputs, where the total amount of computation performed by the parties during the protocol execution is smaller than that of evaluating the function itself! Each party has to individually pre-process the circuit f before the protocol starts and post-process the protocol transcript to recover the output after the protocol ends, and the cost of these steps is larger than the circuit size. However, this gives the first MPC where the computation performed by each party during the actual protocol execution, from the time the first protocol message is sent until the last protocol message is received, is smaller than the circuit size.

STOC Conference 2018 Conference Paper

Succinct delegation for low-space non-deterministic computation

• Saikrishna Badrinarayanan
• Yael Tauman Kalai
• Dakshita Khurana
• Amit Sahai
• Daniel Wichs

We construct a delegation scheme for verifying non-deterministic computations, with complexity proportional only to the non-deterministic space of the computation. Specifically, letting n denote the input length, we construct a delegation scheme for any language verifiable in non-deterministic time and space (T(n), S(n)) with communication complexity poly(S(n)), verifier runtime n.polylog(T(n))+poly(S(n)), and prover runtime poly(T(n)). Our scheme consists of only two messages and has adaptive soundness, assuming the existence of a sub-exponentially secure private information retrieval (PIR) scheme, which can be instantiated under standard (albeit, sub-exponential) cryptographic assumptions, such as the sub-exponential LWE assumption. Specifically, the verifier publishes a (short) public key ahead of time, and this key can be used by any prover to non-interactively prove the correctness of any adaptively chosen non-deterministic computation. Such a scheme is referred to as a non-interactive delegation scheme. Our scheme is privately verifiable, where the verifier needs the corresponding secret key in order to verify proofs. Prior to our work, such results were known only in the Random Oracle Model, or under knowledge assumptions. Our results yield succinct non-interactive arguments based on sub-exponential LWE, for many natural languages believed to be outside of P.

FOCS Conference 2017 Conference Paper

Obfuscating Compute-and-Compare Programs under LWE

• Daniel Wichs
• Giorgos Zirdelis

We show how to obfuscate a large and expressive class of programs, which we call compute-and-compare programs, under the learning-with-errors (LWE) assumption. Each such program CC[f, y] is parametrized by an arbitrary polynomial-time computable function f along with a target value y and we define CC[f, y](x) to output 1 if f(x) = y and 0 otherwise. In other words, the program performs an arbitrary computation f and then compares its output against a target y. Our obfuscator satisfies distributional virtual-blackbox security, which guarantees that the obfuscated program does not reveal any partial information about the function f or the target value y, as long as they are chosen from some distribution where y has sufficient pseudo-entropy given f. We also extend our result to multi-bit compute-and-compare programs MBCC[f, y, z](x) which output a message z if f(x) = y. Compute-and-compare programs are powerful enough to capture many interesting obfuscation tasks as special cases. This includes obfuscating conjunctions, and therefore we improve on the prior work of Brakerski et al. (ITCS '16) which constructed a conjunction obfuscator under a non-standard “entropic” ring-LWE assumption, while here we obfuscate a significantly broader class of programs under standard LWE. We show that our obfuscator has several interesting applications. For example, we can take any encryption scheme and publish an obfuscated plaintext equality tester that allows users to check whether a ciphertext decrypts to some target value y; as long as y has sufficient pseudo-entropy this will not harm semantic security. We can also use our obfuscator to generically upgrade attribute-based encryption to predicate encryption with one-sided attribute-hiding security, and to upgrade witness encryption to indistinguishability obfuscation which is secure for all “null circuits”. Furthermore, we show that our obfuscator gives new circular-security counterexamples for public-key bit encryption and for unbounded length key cycles. Our result uses the graph-induced multi-linear maps of Gentry, Gorbunov and Halevi (TCC '15), but only in a carefully restricted manner which is provably secure under LWE. Our technique is inspired by ideas introduced in a recent work of Goyal, Koppula and Waters (EUROCRYPT '17) in a seemingly unrelated context.

STOC Conference 2016 Conference Paper

Watermarking cryptographic capabilities

• Aloni Cohen
• Justin Holmgren
• Ryo Nishimaki
• Vinod Vaikuntanathan
• Daniel Wichs

STOC Conference 2015 Conference Paper

Leveled Fully Homomorphic Signatures from Standard Lattices

• Sergey Gorbunov 0001
• Vinod Vaikuntanathan
• Daniel Wichs

In a homomorphic signature scheme, a user Alice signs some large dataset x using her secret signing key and uploads the signed data to an untrusted remote server. The server can then run some computation y=f(x) over the signed data and homomorphically derive a short signature σ f,y certifying that y is the correct output of the computation f. Anybody can verify the tuple (f, y, σ f,y ) using Alice's public verification key and become convinced of this fact without having to retrieve the entire underlying data. In this work, we construct the first leveled fully homomorphic signature} schemes that can evaluate arbitrary {circuits} over signed data. Only the maximal {depth} d of the circuits needs to be fixed a-priori at setup, and the size of the evaluated signature grows polynomially in d, but is otherwise independent of the circuit size or the data size. Our solution is based on the (sub-exponential) hardness of the small integer solution (SIS) problem in standard lattices and satisfies full (adaptive) security. In the standard model, we get a scheme with large public parameters whose size exceeds the total size of a dataset. In the random-oracle model, we get a scheme with short public parameters. In both cases, the schemes can be used to sign many different datasets. The complexity of verifying a signature for a computation f is at least as large as that of computing f, but can be amortized when verifying the same computation over many different datasets. Furthermore, the signatures can be made context-hiding so as not to reveal anything about the data beyond the outcome of the computation. These results offer a significant improvement in capabilities and assumptions over the best prior homomorphic signature schemes, which were limited to evaluating polynomials of constant degree. As a building block of independent interest, we introduce a new notion called homomorphic trapdoor functions (HTDF) which conceptually unites homomorphic encryption and signatures. We construct HTDFs by relying on the techniques developed by Gentry et al. (CRYPTO '13) and Boneh et al. (EUROCRYPT '14) in the contexts of fully homomorphic and attribute-based encryptions.

FOCS Conference 2014 Conference Paper

Outsourcing Private RAM Computation

• Craig Gentry
• Shai Halevi
• Mariana Raykova 0001
• Daniel Wichs

We construct the first schemes that allow a client to privately outsource arbitrary program executions to a remote server while ensuring that: (I) the client's work is small and essentially independent of the complexity of the computation being outsourced, and (II) the server's work is only proportional to the run-time of the computation on a random access machine (RAM), rather than its potentially much larger circuit size. Furthermore, our solutions are non-interactive and have the structure of reusable garbled RAM programs, addressing an open question of Lu and Ostrovsky (Eurocrypt 2013). We also construct schemes for an augmented variant of the above scenario, where the client can initially outsource a large private and persistent database to the server, and later outsource arbitrary program executions with read/write access to this database. Our solutions are built from non-reusable garbled RAM in conjunction with new types of reusable garbled circuits that are more efficient than prior solutions but only satisfy weaker security. For the basic setting without a persistent database, we can instantiate the required type of reusable garbled circuits from indistinguishability obfuscation or from functional encryption for circuits as a black-box. For the more complex setting with a persistent database, we can instantiate the required type of reusable garbled circuits using stronger notions of obfuscation. Our basic solution also requires the client to perform a one-time pre-processing step to garble a program at the cost of its RAM run-time, and we can avoid this cost using stronger notions of obfuscation. It remains an open problem to instantiate these new types of reusable garbled circuits under weaker assumptions, possibly avoiding obfuscation altogether. We show several simple extensions of our results and techniques to achieve: efficiency proportional to the input-specific RAM run-time, verifiability of outsourced RAM computation, functional encryption for RAMs, and a candidate obfuscation for RAMs.

STOC Conference 2011 Conference Paper

Separating succinct non-interactive arguments from all falsifiable assumptions

• Craig Gentry
• Daniel Wichs

An argument system for NP is succinct, if its communication complexity is polylogarithmic the instance and witness sizes. The seminal works of Kilian '92 and Micali '94 show that such arguments can be constructed under standard cryptographic hardness assumptions with four rounds of interaction, and that they be made non-interactive in the random-oracle model. However, we currently do not have any construction of succinct non-interactive arguments (SNARGs) in the standard model with a proof of security under any simple cryptographic assumption. In this work, we give a broad black-box separation result, showing that black-box reductions cannot be used to prove the security of any SNARG construction based on any falsifiable cryptographic assumption. This includes essentially all common assumptions used in cryptography (one-way functions, trapdoor permutations, DDH, RSA, LWE etc.). More generally, we say that an assumption is falsifiable if it can be modeled as an interactive game between an adversary and an efficient challenger that can efficiently decide if the adversary won the game. This is similar, in spirit, to the notion of falsifiability of Naor '03, and captures the fact that we can efficiently check if an adversarial strategy breaks the assumption. Our separation result also extends to designated verifier SNARGs, where the verifier needs a trapdoor associated with the CRS to verify arguments, and slightly succinct SNARGs, whose size is only required to be sublinear in the statement and witness size.

FOCS Conference 2011 Conference Paper

Storing Secrets on Continually Leaky Devices

• Yevgeniy Dodis
• Allison Bishop Lewko
• Brent Waters
• Daniel Wichs

We consider the question of how to store a value secretly on devices that continually leak information about their internal state to an external attacker. If the secret value is stored on a single device from which it is efficiently retrievable, and the attacker can leak even a single predicate of the internal state of that device, then she may learn some information about the secret value itself. Therefore, we consider a setting where the secret value is shared between multiple devices (or multiple components of a single device), each of which continually leaks arbitrary adaptively chosen predicates its individual state. Since leakage is continual, each device must also continually update its state so that an attacker cannot just leak it entirely one bit at a time. In our model, the devices update their state individually and asynchronously, without any communication between them. The update process is necessarily randomized, and its randomness can leak as well. As our main result, we construct a sharing scheme for two devices, where a constant fraction of the internal state of each device can leak in between and during updates. Our scheme has the structure of a public-key encryption, where one share is a secret key and the other is a ciphertext. As a contribution of independent interest, we also get public-key encryption in the continual leakage model, introduced by Brakerski et al. and Dodis et al. (FOCS '10). This scheme tolerates continual leakage on the secret key and the updates, and simplifies the recent construction of Lewko, Lewko and Waters (STOC '11). For our main result, we show how to update the ciphertexts of the encryption scheme so that the message remains hidden even if an attacker interleaves leakage on secret key and ciphertext shares. The security of our scheme is based on the linear assumption in prime-order bilinear groups. We also provide an extension to general access structures realizable by linear secret sharing schemes across many devices. The main advantage of this extension is that the state of some devices can be compromised entirely, while that of the all remaining devices is susceptible to continual leakage. Lastly, we show impossibility of information theoretic sharing schemes in our model, where continually leaky devices update their state individually.

FOCS Conference 2010 Conference Paper

Cryptography against Continuous Memory Attacks

• Yevgeniy Dodis
• Kristiyan Haralambiev
• Adriana López-Alt
• Daniel Wichs

We say that a cryptographic scheme is Continuous Leakage-Resilient (CLR), if it allows users to refresh their secret keys, using only fresh local randomness, such that: 1. The scheme remains functional after any number of key refreshes, although the public key never changes. Thus, the “outside world'' is neither affected by these key refreshes, nor needs to know about their frequency. 2. The scheme remains secure even if the adversary can continuously leak arbitrary information about the current secret-key, as long as the amount of leaked information is bounded in between any two successive key refreshes. There is no bound on the total amount of information that can be leaked during the lifetime of the system. In this work, we construct a variety of practical CLR schemes, including CLR one-way relations, CLR signatures, CLR identification schemes, and CLR authenticated key agreement protocols. For each of the above, we give general constructions, and then show how to instantiate them efficiently using a well established assumption on bilinear groups, called the K-Linear assumption (for any constant K greater than or equal to 1). Our constructions are highly modular, and we develop many interesting techniques and building-blocks along the way, including: leakage-indistinguishable re-randomizable relations, homomorphic NIZKs, and leakage-of-cipher text non-malleable encryption schemes.

STOC Conference 2009 Conference Paper

Non-malleable extractors and symmetric key cryptography from weak secrets

• Yevgeniy Dodis
• Daniel Wichs

We study the question of basing symmetric key cryptography on weak secrets. In this setting, Alice and Bob share an n-bit secret W, which might not be uniformly random, but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Since standard symmetric-key primitives require uniformly random secret keys, we would like to construct an authenticated key agreement protocol in which Alice and Bob use W to agree on a nearly uniform key R, by communicating over a public channel controlled by an active adversary Eve. We study this question in the information theoretic setting where the attacker is computationally unbounded. We show that single-round (i.e. one message) protocols do not work when k ≤ n/2, and require poor parameters even when n/2<k<<n . On the other hand, for arbitrary values of k, we design a communication efficient two-round (challenge-response) protocol extracting nearly k random bits. This dramatically improves the previous construction of Renner and Wolf [32], which requires Θ(λ + log(n)) rounds where λ is the security parameter. Our solution takes a new approach by studying and constructing "non-malleable" seeded randomness extractors -- if an attacker sees a random seed X and comes up with an arbitrarily related seed X', then we bound the relationship between R= Ext(W;X) and R' = Ext(W;X'). We also extend our two-round key agreement protocol to the "fuzzy" setting, where Alice and Bob share "close" (but not equal) secrets W A and W B , and to the Bounded Retrieval Model (BRM) where the size of the secret W is huge.