## 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**

2022

EUROCRYPT 2022

EpiGRAM: Practical Garbled RAM
📺 Abstract

★

**Best Paper Award**Garbled RAM (GRAM) is a powerful technique introduced by Lu and Ostrovsky that equips Garbled Circuit (GC) with a sublinear cost RAM without adding rounds of interaction. While multiple GRAM constructions are known, none are suitable for practice, due to costs that have high constants and poor scaling.
We present the first GRAM suitable for practice. For computational security parameter $\kappa$ and for a size-$n$ RAM that stores blocks of size $w = \Omega(\log^2 n)$ bits, our GRAM incurs only amortized $O(w \cdot \log^2 n \cdot \kappa)$ communication and computation per access. We evaluate the concrete cost of our GRAM; our approach outperforms trivial linear-scan-based RAM for as few as $512$ $128$-bit elements.

2022

PKC 2005

Password-Based Authenticated Key Exchange in the Three-Party Setting

★

**PKC Test of Time Award**
2021

TCHES 2021

My other car is your car: compromising the Tesla Model X keyless entry system
📺 Abstract

★

**CHES 2021 Best Paper Award**This paper documents a practical security evaluation of the Tesla Model X keyless entry system. In contrast to other works, the keyless entry system analysed in this paper employs secure symmetric-key and public-key cryptographic primitives implemented by a Common Criteria certified Secure Element. We document the internal workings of this system, covering the key fob, the body control module and the pairing protocol. Additionally, we detail our reverse engineering techniques and document several security issues. The identified issues in the key fob firmware update mechanism and the key fob pairing protocol allow us to bypass all of the cryptographic security measures put in place. To demonstrate the practical impact of our research we develop a fully remote Proof-of-Concept attack that allows to gain access to the vehicle’s interior in a matter of minutes and pair a modified key fob, allowing to drive off. Our attack is not a relay attack, as our new key fob allows us to start the car anytime anywhere. Finally, we provide an analysis of the update performed by Tesla to mitigate our findings. Our work highlights how the increased complexity and connectivity of vehicular systems can result in a larger and easier to exploit attack surface.

2021

CHES 2001

A Sound Method for Switching between Boolean and Arithmetic Masking

★

**CHES Test of Time Award**
2021

PKC 2004

An Efficient Signature Scheme from Bilinear Pairings and Its Applications

★

**PKC Test-Of-Time Award**
2021

ASIACRYPT 2006

Simulation-Sound NIZK Proofs for a Practical Language and Constant Size Group Signatures

★

**IACR Test of Time Award**
2021

CRYPTO 2006

New Proofs for NMAC and HMAC: Security Without Collision-Resistance

★

**IACR Test of Time Award**
2020

ASIACRYPT 2020

Finding Collisions in a Quantum World: Quantum Black-Box Separation of Collision-Resistance and One-Wayness
📺 Abstract

★

**Best Paper Award**Since the celebrated work of Impagliazzo and Rudich (STOC 1989), a number of black-box impossibility results have been established. However, these works only ruled out classical black-box reductions among cryptographic primitives.
Therefore it may be possible to overcome these impossibility results by using quantum reductions.
To exclude such a possibility, we have to extend these impossibility results to the quantum setting.
In this paper, we study black-box impossibility in the quantum setting.
We first formalize a quantum counterpart of fully-black-box reduction following the formalization by Reingold, Trevisan and Vadhan (TCC 2004).
Then we prove that there is no quantum fully-black-box reduction from collision-resistant hash functions to one-way permutations (or even trapdoor permutations).
We take both of classical and quantum implementations of primitives into account.
This is an extension to the quantum setting of the work of Simon (Eurocrypt 1998) who showed a similar result in the classical setting.

2020

ASIACRYPT 2020

New results on Gimli: full-permutation distinguishers and improved collisions
📺 Abstract

★

**Best Paper Award**Gimli is a family of cryptographic primitives (both a hash function and an AEAD scheme) that has been selected for the second round of the NIST competition for standardizing new lightweight designs. The candidate Gimli is based on the permutation Gimli, which was presented at CHES 2017. In this paper, we study the security of both the permutation and the constructions that are based on it. We exploit the slow diffusion in Gimli and its internal symmetries to build, for the first time, a distinguisher on the full permutation of complexity $2^{64}$. We also provide a practical distinguisher on 23 out of the full 24 rounds of Gimli that has been implemented.
Next, we give (full state) collision and semi-free-start collision attacks on Gimli-Hash, reaching respectively up to 12 and 18 rounds. On the practical side, we compute a collision on 8-round Gimli-Hash. In the quantum setting, these attacks reach 2 more rounds. Finally, we perform the first study of linear trails in the permutation, and we propose differential-linear cryptanalysis that reach up to 17 rounds of Gimli.

2020

ASIACRYPT 2020

SQISign: Compact Post-Quantum signatures from Quaternions and Isogenies
📺 Abstract

★

**Best Paper Award**We introduce a new signature scheme, \emph{SQISign}, (for \emph{Short Quaternion and Isogeny Signature}) from isogeny graphs of supersingular elliptic curves. The signature scheme is derived from a new one-round, high soundness, interactive identification protocol. Targeting the post-quantum NIST-1 level of security, our implementation results in signatures of $204$ bytes, secret keys of $16$ bytes and public keys of $64$ bytes. In particular, the signature and public key sizes combined are an order of magnitude smaller than all other post-quantum signature schemes. On a modern workstation, our implementation in C takes 0.6s for key generation, 2.5s for signing, and 50ms for verification.
While the soundness of the identification protocol follows from classical assumptions, the zero-knowledge property relies on the second main contribution of this paper.
We introduce a new algorithm to find an isogeny path connecting two given supersingular elliptic curves of known endomorphism rings.
A previous algorithm to solve this problem, due to Kohel, Lauter, Petit and Tignol, systematically reveals paths from the input curves to a `special' curve. This leakage would break the zero-knowledge property of the protocol. Our algorithm does not directly reveal such a path, and subject to a new computational assumption, we prove that the resulting identification protocol is zero-knowledge.

2020

TOSC 2019

On Beyond-Birthday-Bound Security: Revisiting the Development of ISO/IEC 9797-1 MACs
📺 Abstract

★

**Best Paper FSE 2020**ISO/IEC 9797-1 is an international standard for block-cipher-based Message Authentication Code (MAC). The current version ISO/IEC 9797-1:2011 specifies six single-pass CBC-like MAC structures that are capped at the birthday bound security. For a higher security that is beyond-birthday bound, it recommends to use the concatenation combiner of two single-pass MACs. In this paper, we reveal the invalidity of the suggestion, by presenting a birthday bound forgery attack on the concatenation combiner, which is essentially based on Joux’s multi-collision. Notably, our new forgery attack for the concatenation of two MAC Algorithm 1 with padding scheme 2 only requires 3 queries. Moreover, we look for patches by revisiting the development of ISO/IEC 9797-1 with respect to the beyond-birthday bound security. More specifically, we evaluate the XOR combiner of single-pass CBC-like MACs, which was used in previous version of ISO/IEC 9797-1.

2020

TCHES 2020

Minerva: The curse of ECDSA nonces Systematic analysis of lattice attacks on noisy leakage of bit-length of ECDSA nonces
📺 Abstract

★

**Best Paper CHES 2020**We present our discovery of a group of side-channel vulnerabilities in implementations of the ECDSA signature algorithm in a widely used Atmel AT90SC FIPS 140-2 certified smartcard chip and five cryptographic libraries (libgcrypt, wolfSSL, MatrixSSL, SunEC/OpenJDK/Oracle JDK, Crypto++). Vulnerable implementations leak the bit-length of the scalar used in scalar multiplication via timing. Using leaked bit-length, we mount a lattice attack on a 256-bit curve, after observing enough signing operations. We propose two new methods to recover the full private key requiring just 500 signatures for simulated leakage data, 1200 for real cryptographic library data, and 2100 for smartcard data. The number of signatures needed for a successful attack depends on the chosen method and its parameters as well as on the noise profile, influenced by the type of leakage and used computation platform. We use the set of vulnerabilities reported in this paper, together with the recently published TPM-FAIL vulnerability [MSE+20] as a basis for real-world benchmark datasets to systematically compare our newly proposed methods and all previously published applicable lattice-based key recovery methods. The resulting exhaustive comparison highlights the methods’ sensitivity to its proper parametrization and demonstrates that our methods are more efficient in most cases. For the TPM-FAIL dataset, we decreased the number of required signatures from approximately 40 000 to mere 900.

2020

CHES 1999

Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems

★

**CHES Test of Time Award**
2020

CRYPTO 2020

Handling Adaptive Compromise for Practical Encryption Schemes
📺 Abstract

★

**Early Career Researcher Award**We provide a new definitional framework capturing the multi-user security of encryption schemes and pseudorandom functions in the face of adversaries that can adaptively compromise users' keys. We provide a sequence of results establishing the security of practical symmetric encryption schemes under adaptive compromise in the random oracle or ideal cipher model. The bulk of analysis complexity for adaptive compromise security is relegated to the analysis of lower-level primitives such as pseudorandom functions.
We apply our framework to give proofs of security for the BurnBox system for privacy in the face of border searches and the in-use searchable symmetric encryption scheme due to Cash et al. In both cases, prior analyses had bugs that our framework helps avoid.

2020

CRYPTO 2020

Improved Differential-Linear Attacks with Applications to ARX Ciphers
Abstract

★

**Best Paper Award**We present several improvements to the framework of differential-linear attacks with a special focus on ARX ciphers. As a demonstration of their impact, we apply them to Chaskey and ChaCha and we are able to significantly improve upon the best attacks published so far.

2020

CRYPTO 2020

Chosen Ciphertext Security from Injective Trapdoor Functions
Abstract

★

**Best Paper Award**We provide a construction of chosen ciphertext secure public-key encryption from (injective) trapdoor functions. Our construction is black box and assumes no special properties (e.g. ``lossy'', ``correlated product secure'') of the trapdoor function.

2020

CRYPTO 2020

Breaking the decisional Diffie-Hellman problem for class group actions using genus theory
Abstract

★

**Best Paper Award**In this paper, we use genus theory to analyze the hardness of the decisional Diffie--Hellman problem (DDH) for ideal class groups of imaginary quadratic orders, acting on sets of elliptic curves through isogenies; such actions are used in the Couveignes--Rostovtsev--Stolbunov protocol and in CSIDH. Concretely, genus theory equips every imaginary quadratic order $\mathcal{O}$ with a set of assigned characters $\chi : \text{cl}(\mathcal{O}) \to \{ \pm 1 \}$, and for each such character and every secret ideal class $[\mathfrak{a}]$ connecting two public elliptic curves $E$ and $E' = [\mathfrak{a}] \star E$, we show how to compute $\chi([\mathfrak{a}])$ given only $E$ and $E'$, i.e., without knowledge of $[\mathfrak{a}]$. In practice, this breaks DDH as soon as the class number is even, which is true for a density $1$ subset of all imaginary quadratic orders. For instance, our attack works very efficiently for all supersingular elliptic curves over $\mathbb{F}_p$ with $p \equiv 1 \bmod 4$. Our method relies on computing Tate pairings and walking down isogeny volcanoes.

2020

PKC 2003

2020

PKC 2001

2020

EUROCRYPT 2020

Private Information Retrieval with Sublinear Online Time
📺 Abstract

★

**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
Abstract

★

**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
Abstract

★

**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
Abstract

★

**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

Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency

★

**TCC Test of Time Award**
2019

CRYPTO 2019

Cryptanalysis of OCB2: Attacks on Authenticity and Confidentiality
📺 Abstract

★

**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
📺 Abstract

★

**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
📺 Abstract

★

**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
📺 Abstract

★

**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
📺 Abstract

★

**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

CRYPTO 2004

Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions

★

**2019 IACR Test of Time Award**
2019

EUROCRYPT 2004

Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data

★

**2019 IACR Test of Time Award**
2019

PKC 2001

The Gap-Problems: A New Class of Problems for the Security of Cryptographic Schemes

★

**PKC Test of Time Award**
2019

PKC 1999

How to Enhance the Security of Public-Key Encryption at Minimum Cost

★

**PKC Test of Time Award**
2018

ASIACRYPT 2018

Block Cipher Invariants as Eigenvectors of Correlation Matrices
Abstract

★

**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

Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices

★

**TCC Test of Time Award**
2018

TCC 2004

2018

CRYPTO 2018

Yes, There is an Oblivious RAM Lower Bound!
📺 Abstract

★

**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
📺 Abstract

★

**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

2018

TCC 2018

On Basing Search SIVP on NP-Hardness
Abstract

★

**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
Abstract

★

**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
Abstract

★

**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

Watermarking Cryptographic Functionalities from Standard Lattice Assumptions
📺

★

**Best young researcher paper**
2017

CHES 2017

Nanofocused X-Ray Beam to Reprogram Secure Circuits
Abstract

★

**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

CHES 2016

2016

FSE 2016

2015

ASIACRYPT 2015

2014

EUROCRYPT 2014

2014

CHES 2014

2014

FSE 2014

2013

CRYPTO 2013

2013

CRYPTO 2013

Counter-cryptanalysis: reconstructing Flame's new variant collision attack
📺

★

**Best Young-Author Paper**
2012

CRYPTO 2012

2012

EUROCRYPT 2012

2011

ASIACRYPT 2011

2011

CHES 2011

2011

TCC 2011

2009

CRYPTO 2009

2009

CHES 2009

2009

PKC 2009

2008

EUROCRYPT 2008

2008

CHES 2008

2008

CHES 2008

2006

EUROCRYPT 2006