## CryptoDB

### IACR Publication Awards

The list below includes awards given for publications at IACR conferences. Best paper awards and young researcher awards at individual conferences are given at the discretion of the program committee.

Papers below are listed in the order in which they were awarded, rather than when the paper was published. Starting in 2019, IACR started giving Test-of-Time awards. The PKC and TCC conferences have started issuing their own test-of-time awards, given 15 years after publication.

Award year
Published
Title
2020
EUROCRYPT 2020
Private Information Retrieval with Sublinear Online Time 📺
Best Young Researcher Award
We present the first protocols for private information retrieval that allow fast (sublinear-time) database lookups without increasing the server-side storage requirements. To achieve these efficiency goals, our protocols work in an offline/online model. In an offline phase, which takes place before the client has decided which database bit it wants to read, the client fetches a short string from the servers. In a subsequent online phase, the client can privately retrieve its desired bit of the database by making a second query to the servers. By pushing the bulk of the server-side computation into the offline phase (which is independent of the client’s query), our protocols allow the online phase to complete very quickly—in time sublinear in the size of the database. Our protocols can provide statistical security in the two-server setting and computational security in the single-server setting. Finally, we prove that, in this model, our protocols are optimal in terms of the trade-off they achieve between communication and running time.
2020
EUROCRYPT 2020
Optimal Broadcast Encryption from Pairings and LWE
Best Paper Award
Boneh, Waters and Zhandry (CRYPTO 2014) used multilinear maps to provide a solution to the long-standing problem of public-key broadcast encryption (BE) where all parameters in the system are small. In this work, we improve their result by providing a solution that uses only {\it bilinear} maps and Learning With Errors (LWE). Our scheme is fully collusion-resistant against any number of colluders, and can be generalized to an identity-based broadcast system with short parameters. Thus, we reclaim the problem of optimal broadcast encryption from the land of Obfustopia''. Our main technical contribution is a ciphertext policy attribute based encryption (CP-ABE) scheme which achieves special efficiency properties -- its ciphertext size, secret key size, and public key size are all independent of the size of the circuits supported by the scheme. We show that this special CP-ABE scheme implies BE with optimal parameters; but it may also be of independent interest. Our constructions rely on a novel interplay of bilinear maps and LWE, and are proven secure in the generic group model.
2020
ASIACRYPT 2005
Discrete-Log-Based Signatures May Not Be Equivalent to Discrete Log
Best Paper and IACR Test of Time Award: For developing a new meta-reduction approach in the security proof of cryptosystems
2020
CRYPTO 2005
Finding Collisions in the Full SHA-1
IACR Test of Time Award: For a breakthrough in the cryptanalysis of hash functions
2020
EUROCRYPT 2005
Fuzzy Identity-Based Encryption
IACR Test of Time Award: For laying the foundations of attribute-based encryption and other advanced notions of encryption
2019
ASIACRYPT 2019
Wave: A New Family of Trapdoor One-Way Preimage Sampleable Functions Based on Codes
Best Paper
We present here a new family of trapdoor one-way functions that are Preimage Sampleable on Average (PSA) based on codes, the Wave-PSA family. The trapdoor function is one-way under two computational assumptions: the hardness of generic decoding for high weights and the indistinguishability of generalized $(U,U+V)$-codes. Our proof follows the GPV strategy [28]. By including rejection sampling, we ensure the proper distribution for the trapdoor inverse output. The domain sampling property of our family is ensured by using and proving a variant of the left-over hash lemma. We instantiate the new Wave-PSA family with ternary generalized $(U,U+V)$-codes to design a “hash-and-sign” signature scheme which achieves existential unforgeability under adaptive chosen message attacks (EUF-CMA) in the random oracle model.
2019
TCC 2019
The Function-Inversion Problem: Barriers and Opportunities
Best Young Researcher
The task of function inversion is central to cryptanalysis: breaking block ciphers, forging signatures, and cracking password hashes are all special cases of the function-inversion problem. In 1980, Hellman showed that it is possible to invert a random function $f{:}\,[N] \rightarrow [N]$ in time $T = \widetilde{O}(N^{2/3})$ given only $S = \widetilde{O}(N^{2/3})$ bits of precomputed advice about f. Hellman’s algorithm is the basis for the popular “Rainbow Tables” technique (Oechslin 2003), which achieves the same asymptotic cost and is widely used in practical cryptanalysis.Is Hellman’s method the best possible algorithm for inverting functions with preprocessed advice? The best known lower bound, due to Yao (1990), shows that $ST = \widetilde{\Omega }(N)$, which still admits the possibility of an $S = T = \widetilde{O}(N^{1/2})$ attack. There remains a long-standing and vexing gap between Hellman’s $N^{2/3}$ upper bound and Yao’s $N^{1/2}$ lower bound. Understanding the feasibility of an $S = T = N^{1/2}$ algorithm is cryptanalytically relevant since such an algorithm could perform a key-recovery attack on AES-128 in time $2^{64}$ using a precomputed table of size $2^{64}$.For the past 29 years, there has been no progress either in improving Hellman’s algorithm or in strengthening Yao’s lower bound. In this work, we connect function inversion to problems in other areas of theory to (1) explain why progress may be difficult and (2) explore possible ways forward.Our results are as follows:We show that any improvement on Yao’s lower bound on function-inversion algorithms will imply new lower bounds on depth-two circuits with arbitrary gates. Further, we show that proving strong lower bounds on non-adaptive function-inversion algorithms would imply breakthrough circuit lower bounds on linear-size log-depth circuits.We take first steps towards the study of the injective function-inversion problem, which has manifold cryptographic applications. In particular, we show that improved algorithms for breaking PRGs with preprocessing would give improved algorithms for inverting injective functions with preprocessing.Finally, we show that function inversion is closely related to well-studied problems in communication complexity and data structures. Through these connections we immediately obtain the best known algorithms for problems in these domains.
2019
TCC 2008
2019
CRYPTO 2019
Cryptanalysis of OCB2: Attacks on Authenticity and Confidentiality 📺
Best paper
We present practical attacks on OCB2. This mode of operation of a blockcipher was designed with the aim to provide particularly efficient and provably-secure authenticated encryption services, and since its proposal about 15 years ago it belongs to the top performers in this realm. OCB2 was included in an ISO standard in 2009.An internal building block of OCB2 is the tweakable blockcipher obtained by operating a regular blockcipher in $\text {XEX} ^*$ mode. The latter provides security only when evaluated in accordance with certain technical restrictions that, as we note, are not always respected by OCB2. This leads to devastating attacks against OCB2’s security promises: We develop a range of very practical attacks that, amongst others, demonstrate universal forgeries and full plaintext recovery. We complete our report with proposals for (provably) repairing OCB2. To our understanding, as a direct consequence of our findings, OCB2 is currently in a process of removal from ISO standards. Our attacks do not apply to OCB1 and OCB3, and our privacy attacks on OCB2 require an active adversary.
2019
CRYPTO 2019
Quantum Cryptanalysis in the RAM Model: Claw-Finding Attacks on SIKE 📺
Best Young Researcher Paper
We introduce models of computation that enable direct comparisons between classical and quantum algorithms. Incorporating previous work on quantum computation and error correction, we justify the use of the gate-count and depth-times-width cost metrics for quantum circuits. We demonstrate the relevance of these models to cryptanalysis by revisiting, and increasing, the security estimates for the Supersingular Isogeny Diffie–Hellman (SIDH) and Supersingular Isogeny Key Encapsulation (SIKE) schemes. Our models, analyses, and physical justifications have applications to a number of memory intensive quantum algorithms.
2019
CRYPTO 2019
Fully Secure Attribute-Based Encryption for t-CNF from LWE 📺
Best young researcher
Attribute-based Encryption (ABE), first introduced by [SW05, GPSW06], is a public key encryption system that can support multiple users with varying decryption permissions. One of the main properties of such schemes is the supported function class of policies. While there are fully secure constructions from bilinear maps for a fairly large class of policies, the situation with lattice-based constructions is less satisfactory and many efforts were made to close this gap. Prior to this work the only known fully secure lattice construction was for the class of point functions (also known as IBE).In this work we construct for the first time a lattice-based (ciphertext-policy) ABE scheme for the function class t-CNF, which consists of CNF formulas where each clause depends on at most t bits of the input, for any constant t. This class includes NP-verification policies, bit-fixing policies and t-threshold policies. Towards this goal we also construct a fully secure single-key constrained PRF from OWF for the same function class, which might be of independent interest.
2019
EUROCRYPT 2019
Efficient Verifiable Delay Functions 📺
Best Young Researcher Paper
We construct a verifiable delay function (VDF). A VDF is a function whose evaluation requires running a given number of sequential steps, yet the result can be efficiently verified. They have applications in decentralised systems, such as the generation of trustworthy public randomness in a trustless environment, or resource-efficient blockchains. To construct our VDF, we actually build a trapdoor VDF. A trapdoor VDF is essentially a VDF which can be evaluated efficiently by parties who know a secret (the trapdoor). By setting up this scheme in a way that the trapdoor is unknown (not even by the party running the setup, so that there is no need for a trusted setup environment), we obtain a simple VDF. Our construction is based on groups of unknown order such as an RSA group, or the class group of an imaginary quadratic field. The output of our construction is very short (the result and the proof of correctness are each a single element of the group), and the verification of correctness is very efficient.
2019
EUROCRYPT 2019
Quantum Lightning Never Strikes the Same State Twice 📺
Best Paper
Public key quantum money can be seen as a version of the quantum no-cloning theorem that holds even when the quantum states can be verified by the adversary. In this work, we investigate quantum lightning where no-cloning holds even when the adversary herself generates the quantum state to be cloned. We then study quantum money and quantum lightning, showing the following results:We demonstrate the usefulness of quantum lightning beyond quantum money by showing several potential applications, such as generating random strings with a proof of entropy, to completely decentralized cryptocurrency without a block-chain, where transactions is instant and local.We give Either/Or results for quantum money/lightning, showing that either signatures/hash functions/commitment schemes meet very strong recently proposed notions of security, or they yield quantum money or lightning. Given the difficulty in constructing public key quantum money, this suggests that natural schemes do attain strong security guarantees.We show that instantiating the quantum money scheme of Aaronson and Christiano [STOC’12] with indistinguishability obfuscation that is secure against quantum computers yields a secure quantum money scheme. This construction can be seen as an instance of our Either/Or result for signatures, giving the first separation between two security notions for signatures from the literature.Finally, we give a plausible construction for quantum lightning, which we prove secure under an assumption related to the multi-collision resistance of degree-2 hash functions. Our construction is inspired by our Either/Or result for hash functions, and yields the first plausible standard model instantiation of a non-collapsing collision resistant hash function. This improves on a result of Unruh [Eurocrypt’16] which is relative to a quantum oracle.
2019
ASIACRYPT 2004
How Far Can We Go Beyond Linear Cryptanalysis?
2019 IACR Test of Time Award
2019
CRYPTO 2004
2019
EUROCRYPT 2004
2019
JOFC 2001
Selecting Cryptographic Key Sizes
PKC Test of Time Award
2019
PKC 2001
2019
PKC 2000
Selecting Cryptographic Key Sizes
PKC Test of Time Award
2019
PKC 1999
2018
ASIACRYPT 2018
Block Cipher Invariants as Eigenvectors of Correlation Matrices
Best Paper Award
A new approach to invariant subspaces and nonlinear invariants is developed. This results in both theoretical insights and practical attacks on block ciphers. It is shown that, with minor modifications to some of the round constants, Midori-64 has a nonlinear invariant with $2^{96}$ corresponding weak keys. Furthermore, this invariant corresponds to a linear hull with maximal correlation. By combining the new invariant with integral cryptanalysis, a practical key-recovery attack on 10 rounds of unmodified Midori-64 is obtained. The attack works for $2^{96}$ weak keys and irrespective of the choice of round constants. The data complexity is $1.25 \cdot 2^{21}$ chosen plaintexts and the computational cost is dominated by $2^{56}$ block cipher calls. Finally, it is shown that similar techniques lead to a practical key-recovery attack on MANTIS-4. The full key is recovered using 640 chosen plaintexts and the attack requires about $2^{56}$ block cipher calls.
2018
TCC 2006
2018
TCC 2006
2018
TCC 2005
Evaluating 2-DNF Formulas on Ciphertexts
TCC Test of Time Award
2018
TCC 2004
2018
TCC 2004
2018
CRYPTO 2018
Yes, There is an Oblivious RAM Lower Bound! 📺
Best Paper Award
An Oblivious RAM (ORAM) introduced by Goldreich and Ostrovsky [JACM’96] is a (possibly randomized) RAM, for which the memory access pattern reveals no information about the operations performed. The main performance metric of an ORAM is the bandwidth overhead, i.e., the multiplicative factor extra memory blocks that must be accessed to hide the operation sequence. In their seminal paper introducing the ORAM, Goldreich and Ostrovsky proved an amortized $\varOmega (\lg n)$ bandwidth overhead lower bound for ORAMs with memory size n. Their lower bound is very strong in the sense that it applies to the “offline” setting in which the ORAM knows the entire sequence of operations ahead of time.However, as pointed out by Boyle and Naor [ITCS’16] in the paper “Is there an oblivious RAM lower bound?”, there are two caveats with the lower bound of Goldreich and Ostrovsky: (1) it only applies to “balls in bins” algorithms, i.e., algorithms where the ORAM may only shuffle blocks around and not apply any sophisticated encoding of the data, and (2), it only applies to statistically secure constructions. Boyle and Naor showed that removing the “balls in bins” assumption would result in super linear lower bounds for sorting circuits, a long standing open problem in circuit complexity. As a way to circumventing this barrier, they also proposed a notion of an “online” ORAM, which is an ORAM that remains secure even if the operations arrive in an online manner. They argued that most known ORAM constructions work in the online setting as well.Our contribution is an $\varOmega (\lg n)$ lower bound on the bandwidth overhead of any online ORAM, even if we require only computational security and allow arbitrary representations of data, thus greatly strengthening the lower bound of Goldreich and Ostrovsky in the online setting. Our lower bound applies to ORAMs with memory size n and any word size $r \ge 1$ . The bound therefore asymptotically matches the known upper bounds when $r = \varOmega (\lg ^2 n)$ .
2018
CRYPTO 2018
Multi-Theorem Preprocessing NIZKs from Lattices 📺
Best Young Researcher Paper
Non-interactive zero-knowledge (NIZK) proofs are fundamental to modern cryptography. Numerous NIZK constructions are known in both the random oracle and the common reference string (CRS) models. In the CRS model, there exist constructions from several classes of cryptographic assumptions such as trapdoor permutations, pairings, and indistinguishability obfuscation. Notably absent from this list, however, are constructions from standard lattice assumptions. While there has been partial progress in realizing NIZKs from lattices for specific languages, constructing NIZK proofs (and arguments) for all of $\mathsf {NP}$ from standard lattice assumptions remains open.   In this work, we make progress on this problem by giving the first construction of a multi-theorem NIZK argument for $\mathsf {NP}$ from standard lattice assumptions in the preprocessing model. In the preprocessing model, a (trusted) setup algorithm generates proving and verification keys. The proving key is needed to construct proofs and the verification key is needed to check proofs. In the multi-theorem setting, the proving and verification keys should be reusable for an unbounded number of theorems without compromising soundness or zero-knowledge. Existing constructions of NIZKs in the preprocessing model (or even the designated-verifier model) that rely on weaker assumptions like one-way functions or oblivious transfer are only secure in a single-theorem setting. Thus, constructing multi-theorem NIZKs in the preprocessing model does not seem to be inherently easier than constructing them in the CRS model.   We begin by constructing a multi-theorem preprocessing NIZK directly from context-hiding homomorphic signatures. Then, we show how to efficiently implement the preprocessing step using a new cryptographic primitive called blind homomorphic signatures. This primitive may be of independent interest. Finally, we show how to leverage our new lattice-based preprocessing NIZKs to obtain new malicious-secure MPC protocols purely from standard lattice assumptions.
2018
EUROCRYPT 2018
Simple Proofs of Sequential Work 📺
Best Paper
2018
EUROCRYPT 2018
2018
EUROCRYPT 2018
2018
EUROCRYPT 2018
The Discrete-Logarithm Problem with Preprocessing 📺
Best Young Researcher
2018
TCC 2018
On Basing Search SIVP on NP-Hardness
Best Student Paper
The possibility of basing cryptography on the minimal assumption $\mathbf{NP }\nsubseteq \mathbf{BPP }$ NP⊈BPP is at the very heart of complexity-theoretic cryptography. The closest we have gotten so far is lattice-based cryptography whose average-case security is based on the worst-case hardness of approximate shortest vector problems on integer lattices. The state-of-the-art is the construction of a one-way function (and collision-resistant hash function) based on the hardness of the $\tilde{O}(n)$ O~(n)-approximate shortest independent vector problem ${\textsf {SIVP}}_{\tilde{O}(n)}$ SIVPO~(n).Although ${\textsf {SIVP}}$ SIVP is NP-hard in its exact version, Guruswami et al. (CCC 2004) showed that ${\textsf {gapSIVP}}_{\sqrt{n/\log n}}$ gapSIVPn/logn is in $\mathbf{NP } \cap \mathbf{coAM }$ NP∩coAM and thus unlikely to be $\mathbf{NP }$ NP-hard. Indeed, any language that can be reduced to ${\textsf {gapSIVP}}_{\tilde{O}(\sqrt{n})}$ gapSIVPO~(n) (under general probabilistic polynomial-time adaptive reductions) is in $\mathbf{AM } \cap \mathbf{coAM }$ AM∩coAM by the results of Peikert and Vaikuntanathan (CRYPTO 2008) and Mahmoody and Xiao (CCC 2010). However, none of these results apply to reductions to search problems, still leaving open a ray of hope: can $\mathbf{NP }$ NPbe reduced to solving search SIVP with approximation factor $\tilde{O}(n)$ O~(n)?We eliminate such possibility, by showing that any language that can be reduced to solving search ${\textsf {SIVP}}$ SIVP with any approximation factor $\lambda (n) = \omega (n\log n)$ λ(n)=ω(nlogn) lies in AM intersect coAM.
2018
TCHES 2018
Cold Boot Attacks on Ring and Module LWE Keys Under the NTT
Best Paper at CHES 2019
In this work, we consider the ring- and module- variants of the LWE problem and investigate cold boot attacks on cryptographic schemes based on these problems, wherein an attacker is faced with the problem of recovering a scheme’s secret key from a noisy version of that key. The leakage resilience of cryptography based on the learning with errors (LWE) problem has been studied before, but there are only limited results considering the parameters observed in cold boot attack scenarios. There are two main encodings for storing ring- and module-LWE keys, and, as we show, the performance of cold boot attacks can be highly sensitive to the exact encoding used. The first encoding stores polynomial coefficients directly in memory. The second encoding performs a number theoretic transform (NTT) before storing the key, a commonly used method leading to more efficient implementations. We first give estimates for a cold boot attack complexity on the first encoding method based on standard algorithms; this analysis confirms that this encoding method is vulnerable to cold boot attacks only at very low bit-flip rates. We then show that, for the second encoding method, the structure introduced by using an NTT is exploitable in the cold boot setting: we develop a bespoke attack strategy that is much cheaper than our estimates for the first encoding when considering module-LWE keys. For example, at a 1% bit-flip rate (which corresponds roughly to what can be achieved in practice for cold boot attacks when applying cooling), a cold boot attack on Kyber KEM parameters has a cost of 243 operations when the second, NTT-based encoding is used for key storage, compared to 270 operations with the first encoding. On the other hand, in the case of the ring-LWE-based KEM, New Hope, the cold boot attack complexities are similar for both encoding methods.
2018
TOSC 2018
Key-Recovery Attacks on Full Kravatte
Best Paper FSE 2018
This paper presents a cryptanalysis of full Kravatte, an instantiation of the Farfalle construction of a pseudorandom function (PRF) with variable input and output length. This new construction, proposed by Bertoni et al., introduces an efficiently parallelizable and extremely versatile building block for the design of symmetric mechanisms, e.g. message authentication codes or stream ciphers. It relies on a set of permutations and on so-called rolling functions: it can be split into a compression layer followed by a two-step expansion layer. The key is expanded and used to mask the inputs and outputs of the construction. Kravatte instantiates Farfalle using linear rolling functions and permutations obtained by iterating the Keccak round function.We develop in this paper several attacks against this PRF, based on three different attack strategies that bypass part of the construction and target a reduced number of permutation rounds. A higher order differential distinguisher exploits the possibility to build an affine space of values in the cipher state after the compression layer. An algebraic meet-in-the-middle attack can be mounted on the second step of the expansion layer. Finally, due to the linearity of the rolling function and the low algebraic degree of the Keccak round function, a linear recurrence distinguisher can be found on intermediate states of the second step of the expansion layer. All the attacks rely on the ability to invert a small number of the final rounds of the construction. In particular, the last two rounds of the construction together with the final masking by the key can be algebraically inverted, which allows to recover the key.The complexities of the devised attacks, applied to the Kravatte specifications published on the IACR ePrint in July 2017, or the strengthened version of Kravatte recently presented at ECC 2017, are far below the security claimed.
2017
ASIACRYPT 2017
2017
CRYPTO 2017
2017
CRYPTO 2017
2017
CRYPTO 2017
2017
EUROCRYPT 2017
Scrypt Is Maximally Memory-Hard 📺
Best Paper
2017
CHES 2017
Nanofocused X-Ray Beam to Reprogram Secure Circuits
Best Paper
Synchrotron-based X-ray nanobeams are investigated as a tool to perturb microcontroller circuits. An intense hard X-ray focused beam of a few tens of nanometers is used to target the flash, EEPROM and RAM memory of a circuit. The obtained results show that it is possible to corrupt a single transistor in a semi-permanent state. A simple heat treatment can remove the induced effect, thus making the corruption reversible. An attack on a code stored in flash demonstrates unambiguously that this new technique can be a threat to the security of integrated circuits.
2016
ASIACRYPT 2016
2016
CRYPTO 2016
The Magic of ELFs 📺
Early Career Award
2016
CRYPTO 2016
2016
EUROCRYPT 2016
2016
CHES 2016
2016
FSE 2016
2015
ASIACRYPT 2015
2015
CRYPTO 2015
2015
EUROCRYPT 2015
2015
CHES 2015
2015
FSE 2015
2014
ASIACRYPT 2014
2014
EUROCRYPT 2014
2014
EUROCRYPT 2014
2014
CHES 2014
2014
FSE 2014
2014
FSE 2014
2013
ASIACRYPT 2013
2013
CRYPTO 2013
2013
CRYPTO 2013
2013
EUROCRYPT 2013
2013
CHES 2013
2012
CRYPTO 2012
2012
EUROCRYPT 2012
2012
CHES 2012
Best Paper
2012
FSE 2012
2012
FSE 2012
2012
FSE 2012
2012
TCC 2012
2012
TCC 2012
Lower Bounds in Differential Privacy
Best Student Paper
2011
ASIACRYPT 2011
2011
ASIACRYPT 2011
2011
CRYPTO 2011
2011
EUROCRYPT 2011
2011
CHES 2011
2011
FSE 2011
2011
TCC 2011
2010
ASIACRYPT 2010
2010
CRYPTO 2010
2010
EUROCRYPT 2010
2010
CHES 2010
2010
FSE 2010
2010
PKC 2010
2010
TCC 2010
2009
ASIACRYPT 2009
2009
CRYPTO 2009
2009
EUROCRYPT 2009
2009
CHES 2009
2009
CHES 2009
2009
CHES 2009
2009
FSE 2009
2009
PKC 2009
2008
ASIACRYPT 2008
2008
ASIACRYPT 2008
2008
ASIACRYPT 2008
2008
CRYPTO 2008
2008
EUROCRYPT 2008
2008
CHES 2008
2008
CHES 2008
2008
PKC 2008
2007
ASIACRYPT 2007
Cryptanalysis of Grindahl
Best Paper
2007
ASIACRYPT 2007
2007
CRYPTO 2007
2007
EUROCRYPT 2007
2007
CHES 2007
2007
CHES 2007
2007
PKC 2007
2007
TCC 2007
2006
ASIACRYPT 2006
2006
CRYPTO 2006
2006
EUROCRYPT 2006
2006
PKC 2006
2005
EUROCRYPT 2005
2005
EUROCRYPT 2005
2005
CHES 2005
2005
PKC 2005
2004
ASIACRYPT 2004