Results 1681 - 1690 of 23856

The Fiat–Shamir transformation is a fundamental cryptographic technique widely used to convert public-coin interactive protocols into non-interactive ones. This transformation is crucial in both theoretical and practical applications, particularly in the construction of succinct non-interactive arguments (SNARKs). While its security is well-established in the random oracle model, practical implementations replace the random oracle with a concrete hash function, where security is merely assumed to carry over.

A growing body of work has given theoretical examples of protocols that remain secure under the Fiat–Shamir transformation in the random oracle model but become insecure when instantiated with any white-box implementation of the hash function. Recent research has shown how these attacks can be applied to natural cryptographic schemes, including real-world systems. These attacks rely on a general diagonalization technique, where the protocol exploits its access to the white-box implementation of the hash function. These attacks cast serious doubt on the security of cryptographic systems deployed in practice today, leaving their soundness uncertain.

We propose a new Fiat–Shamir transformation (XFS) that aims to defend against a broad family of attacks. Our approach is designed to be practical, with minimal impact on the efficiency of the prover and verifier and on the proof length. At a high level, our transformation combines the standard Fiat–Shamir technique with a new type of proof-of-work that we construct.

We provide strong evidence for the security of our transformation by proving its security in a relativized random oracle model. Specifically, we show diagonalization attacks on the standard Fiat–Shamir transformation that can be mapped to analogous attacks within this model, meaning they do not rely on a concrete instantiation of the random oracle. In contrast, we prove unconditionally that our XFS variant of the Fiat–Shamir transformation remains secure within this model. Consequently, any successful attack on XFS must deviate from known techniques and exploit aspects not captured by our model.

We hope that our transformation will help preserve the security of systems relying on the Fiat–Shamir transformation.

Two central results in modern complexity theory can be summed up as follows:
* Everything provable is provable in zero knowledge (NP ⊆ CZK); and
* Everything provable is locally checkable (NP = PCP[log n, 1]).
In a pair of recent works, we show how to achieve these two properties simultaneously: Everything provable is locally checkable in zero knowledge.

That is, we demonstrate that for every polynomial Q, every NP language has a polynomial-size proof which can be verified by querying O(1) positions, but where querying any Q(n) positions reveals no information about the witness. Based on joint work with Tom Gur and Jack O'Connor.

I will put forward a new approach for achieving non-interactive zero-knowledge proofs (NIKZs) from the learning with errors (LWE) assumption. I will describe a LWE-based construction of a hidden bits generator that gives rise to a NIZK via the celebrated hidden bits paradigm. A notable feature of the construction is its simplicity. Our construction employs lattice trapdoors, but beyond that uses only simple operations. Unlike prior solutions, it does not rely on a correlation intractability argument nor does it utilize fully homomorphic encryption techniques.

We present new constructions of succinct non-interactive functional commitments and arguments for circuits (i.e. P/poly), based on the SIS assumption without random oracles. For boolean circuits of depth d, we obtain

* a non-interactive functional commitment scheme with O(1)-sized transparent CRS, O(1)-sized commitment, and O(d)-sized openings;

* a non-interactive succinct argument (SNARG for P/poly) with O(1)-sized transparent CRS, and O(d)-sized unambiguous proofs.

Moreover, both schemes support fast online verification after a circuit-dependent pre-processing phase, and do not impose a bound on circuit parameters during set-up. Our constructions are simple, elementary and do not rely on correlation-intractable hashing.

SP1 Hypercube is a new multilinear based proof-system for proving correctness of programs written in a high level programming language. In the talk I will give an overview of how such real-world proof-systems work, while focusing on a key novel component in Hypercube: the jagged polynomial commitment scheme.

SNARKs built from error-correcting codes have extremely efficient provers, reasonable verifier costs, and plausible post-quantum security. As such, they are widely used in industry and improving their efficiency remains an active area of research. Naturally, both prover and verifier costs depend heavily on the choice of error-correcting code. In this talk, I will give an overview of the families of error-correcting codes that yield efficient SNARKs, and distill the core properties that enable this efficiency. Furthermore, I will discuss some tradeoffs between prover-friendly properties and verifier-friendly properties. Lastly, I will conclude with some open questions.