CWI Cryptology Group

Abstract: We study succinct computationally sound proofs (arguments) for NP, whose 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. The latter construction also gives us some evidence that succinct non interactive arguments (SNARGs) may exist in the standard model with a common reference string (CRS), by replacing the oracle with a sufficiently complicated hash function whose description goes in the CRS. However, we currently do not know of any construction of SNARGs with a formal 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. Joint work with Craig Gentry

Abstract: A signature scheme is fully leakage resilient (Katz and Vaikuntanathan, ASIACRYPT '09) if it is secure even in a setting where an adversary may obtain bounded (yet arbitrary) leakage information on {\emph all intermediate values} that are used throughout the lifetime of the system. This is a strong and meaningful notion of security that captures a significantly wide range of side-channel attacks. One of the main challenges in constructing fully leakage-resilient signature schemes is dealing with leakage that may depend on the random bits used by the signing algorithm, and constructions of such schemes are known only in the random-oracle model. Moreover, even in the random-oracle model, known schemes are only resilient to leakage of less than half the length of their signing key. In this work, we construct the first fully leakage-resilient signature schemes without random oracles. We present a scheme that is resilient to any leakage of length $(1-o(1))L$ bits, where $L$ is the length of the signing key. Our approach relies on generic cryptographic primitives, and at the same time admits rather efficient instantiations based on specific number-theoretic assumptions. In addition, we show that our approach extends to the continual-leakage model, recently introduced by Dodis, Haralambiev, Lopez-Alt and Wichs (FOCS '10), and by Brakerski, Tauman Kalai, Katz and Vaikuntanathan (FOCS '10). In this model the signing key is allowed to be refreshed, while its corresponding verification key remains fixed, and the amount of leakage is assumed to be bounded only in between any two successive key refreshes. Joint work with Gil Segev and Daniel Wichs.

Abstract: The learning with errors (LWE) problem asks to distinguish "noisy" inner products of a secret vector with random vectors from uniform. Recently, this problem has found many applications in cryptography. It's appeal stems from two facts: 1. The hardness of the problem is very well understood. "Regev's LWE" is as hard as worst case lattice problems. The learning parities with noise (LPN) version is equivalent to decoding random linear codes. 2. Constructions based on LWE (and in particular LPN) tend to be extremely efficient, often just requiring few bit-lever operations. In this talk I will first introduce a (seemingly) much stronger "interactive" assumption called subspace LWE, but which can be proven to be equivalent to the original LWE problem. This result will immediately imply that the LWE/LPN problems are surprisingly robust with respect to tampering with the secret and/or the randomness used to generate the samples. This robustness directly translates to stronger security guarantees (e.g. it implies security against a broad class of related-key attacks) one can give for cryptosystems proven secure under the standard LWE assumption. In the second part of the talk I'll show simple and extremely efficient constructions of authentication protocols and message authentication codes (MACs) whose security can be reduced to subspace LPN. These new schemes are an order of magnitude more efficient than solutions based on AES, and unlike AES or any other practical schemes know to date, are based on a well known hardness assumption. This part of the talk is based on join work (to appear at Eurocrypt 2011) with Eike Kiltz, David Cash, Abhishek Jain and Daniele Venturi.