International Association for Cryptologic Research

IACR News Central

Here you can see all recent updates to the IACR webpage. These updates are also available:

Now viewing news items related to:

22 March 2019
Event date: 12 June to 15 June 2019
Submission deadline: 31 March 2019
Notification: 10 April 2019
Event date: 14 June to 16 June 2019
Submission deadline: 15 April 2019
Notification: 15 May 2019
21 March 2019
We construct private-key and public-key functional encryption schemes secure against adversaries that corrupt an a-priori bounded number of users and obtain their functional keys, from minimal assumptions.

For a collusion bound of $Q=Q(\lambda)$ (where $\lambda$ is the security parameter), our public-key (resp. private-key) functional encryption scheme (a) supports the class of all polynomial-size circuits; (b) can be built solely from a vanilla public-key (resp. private-key) encryption scheme; and (c) has ciphertexts that grow linearly with the collusion bound $Q$. Previous constructions were sub-optimal with respect to one or more of the above properties. The first two of these properties are the best possible and any improvement in the third property, namely the ciphertext size dependence on the collusion bound $Q$, can be used to realize an indistinguishability obfuscation scheme.

In addition, our schemes are adaptively secure and make black-box use of the underlying cryptographic primitives.
Logical cryptanalysis, first introduced by Massacci in 2000, is a viable alternative to common algebraic cryptanalysis techniques over boolean fields. With XOR operations being at the core of many cryptographic problems, recent research in this area has focused on handling XOR clauses efficiently. In this paper, we investigate solving the point decomposition step of the index calculus method for prime degree extension fields $\mathbb{F}_{2^n}$, using SAT solving methods. We propose an original XOR-reasoning SAT solver, named WDSat, dedicated to this specific problem. While asymptotically solving the point decomposition problem with our method has exponential worst time complexity in the dimension $l$ of the vector space defining the factor base, experimental running times show that our solver is significantly faster than current algebraic methods based on Gröbner basis computation. For the values $l$ and $n$ considered in the experiments, WDSat was up to 300 times faster then MAGMA's F4 implementation, and this factor grows with $l$ and $n$. Our solver outperforms as well current best state-of-the-art SAT solvers for this specific problem.
20 March 2019
We are proud to announce the winners of the 2019 IACR Test-of-Time Award. This award honors papers published at the 3 IACR flagship conferences 15 years ago which have had a lasting impact on the field.

The Test-of-Time award for Eurocrypt 2004 is awarded to "Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data" (Yevgeniy Dodis, Leonid Reyzin, Adam D. Smith), for introducing new techniques for entropy extraction from noisy data.

The Test-of-Time award for Crypto 2004 is awarded to "Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions" (Antoine Joux), for the development of an important attack on a widely-used class of collision resistant hash functions.

The Test-of-Time award for Asiacrypt 2004 is awarded to "How Far Can We Go Beyond Linear Cryptanalysis?" (Thomas Baignères, Pascal Junod, Serge Vaudenay), for introducing new techniques in linear cryptanalysis of block ciphers.

For more information, see
ePrint Report Side-Channel Analysis of the TERO PUF Lars Tebelmann, Michael Pehl, Vincent Immler
Physical Unclonable Functions (PUFs) have the potential to provide a higher level of security for key storage than traditional Non-Volatile Memory (NVM). However, the susceptibility of the PUF primitives to non-invasive Side-Channel Analysis (SCA) is largely unexplored. While resistance to SCA was indicated for the Transient Effect Ring Oscillator (TERO) PUF, it was not backed by an actual assessment. To investigate the physical security of the TERO PUF, we first discuss and study the conceptual behavior of the PUF primitive to identify possible weaknesses. We support our claims by conducting an EM-analysis of a TERO design on an FPGA. When measuring TERO cells with an oscilloscope in the time domain, a Short Time Fourier Transform (STFT) based approach allows to extract the relevant information in the frequency domain. By applying this method we significantly reduce the entropy of the PUF. Our analysis shows the vulnerability of not only the originally suggested TERO PUF implementation but also the impact on TERO designs in general. We discuss enhancements of the design that potentially prevent the TERO PUF from exposing the secret and point out that regarding security the TERO PUF is similar to the more area-efficient Ring Oscillator PUF.
Event date: 22 July to 24 July 2019
Submission deadline: 30 April 2019
Notification: 21 May 2019
ePrint Report Cryptanalysis of OCB2: Attacks on Authenticity and Confidentiality Akiko Inoue, Tetsu Iwata, Kazuhiko Minematsu, Bertram Poettering
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 XEX$^\ast$ 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. As a direct consequence of our findings, OCB2 was removed from ISO standards in 2019.

Our privacy attacks on OCB2 require an active adversary and are not applicable to the related schemes OCB1 and OCB3.
ePrint Report A Formal Approach to Secure Speculation Kevin Cheang, Cameron Rasmussen, Sanjit Seshia, Pramod Subramanyan
Transient execution attacks like Spectre, Meltdown and Foreshadow have shown that combinations of microarchitectural side-channels can be synergistically exploited to create side-channel leaks that are greater than the sum of their parts. While both hardware and software mitigations have been proposed against these attacks, provably security has remained elusive.

This paper introduces a formal methodology for enabling secure speculative execution on modern processors. We propose a new class of of information flow security properties called trace property-dependent observational determinism (TPOD). We use this class to formulate a secure speculation property. Our formulation precisely characterises all transient execution vulnerabilities. We demonstrate its applicability by verifying secure speculation for several illustrative programs.
Many constructions based on multilinear maps require independent slots in the plaintext, so that multiple computations can be performed in parallel over the slots. Such constructions are usually based on CLT13 multilinear maps, since CLT13 inherently provides a composite encoding space. However, a vulnerability was identified at Crypto 2014 by Gentry, Lewko and Waters, with a lattice-based attack in dimension 2, and the authors have suggested a simple countermeasure. In this paper, we identify an attack based on higher dimension lattice reduction that breaks the author’s countermeasure for a wide range of parameters. Combined with the Cheon et al. attack from Eurocrypt 2015, this leads to a total break of CLT13 multilinear maps with independent slots. We also show how to apply our attack against various constructions based on composite-order CLT13, such as [FRS17]. Finally, we suggest a set of secure parameters for CLT13 multilinear maps that prevents our attack.
ePrint Report Obfuscation from Polynomial Hardness: Beyond Decomposable Obfuscation Yuan Kang, Chengyu Lin, Tal Malkin, Mariana Raykova
Every known construction of general indistinguishability obfuscation ($\mathsf{i}\mathcal{O}$) is either based on a family of exponentially many assumptions, or is based on a single assumption -- e.g.~functional encryption ($\mathsf{FE}$) -- using a reduction that incurs an exponential loss in security. This seems to be an inherent limitation if we insist on providing indistinguishability for any pair of functionally equivalent circuits.

Recently, Liu and Zhandry (TCC 2017) introduced the notion of decomposable $\mathsf{i}\mathcal{O}$ ($\mathsf{d}\mathcal{O}$), which provides indistinguishability for a restricted class of functionally equivalent circuit pairs, and, as the authors show, can be constructed from polynomially secure $\mathsf{FE}$.

In this paper we propose a new notion of obfuscation, termed $\mathsf{radi}\mathcal{O}$ (repeated-subcircuit and decomposable obfuscation), which allows us to obfuscate a strictly larger class of circuit pairs using a polynomial reduction to $\mathsf{FE}$.

Our notion builds on the equivalence criterion of Liu and Zhandry, combining it with a new incomparable criterion to obtain a strictly larger class.
Let $N_a$ be the number of solutions to the equation $x^{2^k+1}+x+a=0$ in $\mathbb F_{n}$ where $\gcd(k,n)=1$. In 2004, by Bluher it was known that possible values of $N_a$ are only 0, 1 and 3. In 2008, Helleseth and Kholosha have got criteria for $N_a=1$ and an explicit expression of the unique solution when $\gcd(k,n)=1$. In 2014, Bracken, Tan and Tan presented a criterion for $N_a=0$ when $n$ is even and $\gcd(k,n)=1$.

This paper completely solves this equation $x^{2^k+1}+x+a=0$ with only condition $\gcd(n,k)=1$. We explicitly calculate all possible zeros in $\mathbb F_{n}$ of $P_a(x)$. New criterion for which $a$, $N_a$ is equal to $0$, $1$ or $3$ is a by-product of our result.
Let $p$ be a small prime and $n=n_1n_2>1$ be a composite integer. For the function field sieve algorithm applied to $\mathbb{F}_{p^n}$, Guillevic (2019) had proposed an algorithm for initial splitting of the target in the individual logarithm phase. This algorithm generates polynomials and tests them for $B$-smoothness for some appropriate value of $B$. The amortised cost of generating each polynomial is $O(n_2^2)$ multiplications over $\mathbb{F}_{p^{n_1}}$. In this work, we propose a new algorithm for performing the initial splitting which also generates and tests polynomials for $B$-smoothness. The advantage over Guillevic splitting is that in the new algorithm, the cost of generating a polynomial is $O(n\log(1/\pi))$ multiplications in $\mathbb{F}_p$, where $\pi$ is the relevant smoothness probability.
ePrint Report Practical Algebraic Side-Channel Attacks Against ACORN Alexandre Adomnicai, Laurent Masson, Jacques J.A. Fournier
The authenticated cipher ACORN is one of the two finalists of the CAESAR competition and is intended for lightweight applications. Because such use cases require protection against physical attacks, several works have been undertaken to achieve secure implementations. Although dedicated threshold and masked schemes have been proposed, no practical side-channel attack against ACORN has been published in the literature yet. It has been theoretically demonstrated that ACORN is vulnerable against differential power analysis but the feasibility of the attack has not been validated in a practical manner. This paper details the results obtained when putting the attack into practice against a software implementation running on a 32-bit micro-controller. Especially, these practical results led us to propose two variants of the reference attack: one that requires less knowledge of initial vectors and another one that is less prone to errors in practice and requires fewer acquisitions.
ePrint Report Ternary Syndrome Decoding with Large Weight Rémi Bricout, André Chailloux, Thomas Debris-Alazard, Matthieu Lequesne
The Syndrome Decoding problem is at the core of many code-based cryptosystems. In this paper, we study ternary Syndrome Decoding in large weight. This problem has been introduced in the Wave signature scheme but has never been thoroughly studied. We perform an algorithmic study of this problem which results in an update of the Wave parameters. On a more fundamental level, we show that ternary Syndrome Decoding with large weight is a really harder problem than the binary Syndrome Decoding problem, which could have several applications for the design of code-based cryptosystems.
ePrint Report Analysis of TPL Signature Scheme Terry Shue Chien Lau, Chik How Tan, Theo Fanuela Prabowo
Tan et al. proposed a rank metric code-based signature (TPL) in the 2018 International Symposium on Information Theory and Its Application [3]. Their proposal has compact key size ($8.29$KB, $1.97$KB and $2.90$KB for public key, private key and signature respectively) compared to other code-based signature submitted to the NIST call for Post-Quantum Cryptography Standardization at $128$-bit post-quantum security level. This short paper aims to discuss the practical security of the TPL signature. In particular, we describes how to recover the private key in TPL with practical simulations. Our experimental results show that we are able to recover the private key of TPL in less than $23$ milliseconds for all the proposed schemes at $82$-bit, $98$-bit and $129$-bit post-quantum security level.
In the past 15 years, cryptography has made considerable progress in expanding the adversarial attack model to cover side-channel attacks, and has built schemes to provably defend against some of them. This survey covers the main models and results in this so-called "leakage-resilient" cryptography.
Encrypted computing is an emerging field in which inputs, outputs and intermediates are maintained in encrypted form in a processor, conferring security on user data against the operator and operating system as adversaries, which run unencrypted in the same machine. Systems that pass encrypted addresses to memory without decryption close a major attack vector and allow off-the-shelf memory to be used. But that makes memory unreliable from the program's perspective, as the many different encryptions of a plaintext address access different memory locations that the program sees as the same with varying contents. A clever `obfuscating' compiler solves the problem, opening up the field.
ePrint Report Transient Effect Ring Oscillators Leak Too Ugo Mureddu, Brice Colombier, Nathalie Bochard, Lilian Bossuet, Viktor Fischer
Up to now, the transient effect ring oscillator (TERO) seemed to be a better building block for PUFs than a standard ring oscillator, since it was thought to be immune to electromagnetic analysis. Here, we report for the first time that TERO PUFs are in fact vulnerable to electromagnetic analysis too. First, we propose a spectral model of a TERO cell output, showing how to fit it to experimental data obtained with the help of a spectrum analyser to recover the number of oscillations of a TERO cell. We then extend it to two TERO cells oscillating simultaneously, and show how this ability can be used to fully clone a TERO PUF. These results should help designers to better plan for susceptibility of TERO PUFs to electromagnetic analysis in their future designs.
Revocable identity-based encryption (RIBE) is an extension of IBE that supports a key revocation mechanism, which is important when deployed an IBE system in practice. Boneh and Franklin presented the first generic construction of RIBE, however, their scheme is not scalable where the size of key update is linear in the number of users in the system. Then, Boldyreva, Goyal and Kumar presented the first scalable RIBE where the size of key update is logarithmic in the number of users and linear in the number of revoked users.

In this paper, we present a generic construction of scalable RIBE from any IBE in a black-box way. Our construction has some merits both in theory and in practice. We obtain the first RIBE scheme based on quadratic residuosity problem and the first adaptively secure RIBE scheme based on lattices if we instantiate the underlying IBE with IBE schemes from quadratic residuosity assumption and adaptively secure IBE from lattices, respectively. In addition, the size of public parameters and secret keys are the same as that of the underlying IBE schemes. In server-aided model, the overheads of communication and computation for receivers are the same as those of underlying IBE schemes. Furthermore, the storage overhead for key update in our scheme is constant (in the number of users) while it was linear in the number of users in previous works.
ePrint Report Improved Classical Cryptanalysis of the Computational Supersingular Isogeny Problem Craig Costello, Patrick Longa, Michael Naehrig, Joost Renes, Fernando Virdia
Two recent papers have made significant advances towards a better understanding of the concrete hardness of the computational supersingular isogeny (CSSI) problem; this problem underlies the supersingular isogeny key encapsulation (SIKE) protocol, which is the only isogeny-based submission to the NIST post-quantum standardization effort. The first paper, by Adj, Cervantes-Vázquez, Chi-Domínguez, Menezes and Rodríguez-Henríquez, argues that the van Oorschot-Wiener (vOW) parallel collision finding algorithm is the best choice of classical algorithm for CSSI, and subsequently shows that the SIKE team were too conservative in their classical security estimates. The second paper, by Jaques and Schanck, gives an in-depth analysis into the best known quantum algorithms for CSSI, concluding that quantum algorithms do not achieve a significant advantage over the vOW algorithm and showing that the SIKE team were overly conservative in their quantum security analysis as well. Both papers agree that significantly smaller parameters could be used in the SIKE proposal to achieve NIST's security requirements.

The main contribution of this work is an implementation of the van Oorschot-Wiener algorithm. We present a number of novel improvements, both to practical instantiations of the generic vOW algorithm and to its instantiation in the context of SIKE, that culminate in an improved classical cryptanalysis of CSSI. Subsequently, we study a set of three SIKE parameterizations − one from the original proposal, SIKEp751, and two from the two papers above, SIKEp434 and SIKEp610 − that we endorse for inclusion in future versions of the SIKE proposal. We provide assembly-optimized performance benchmarks for these parameter sets, which show that the SIKE protocol can be computed in approximately 6.5, 15.6 and 26 milliseconds on a 3.4GHz Intel Skylake processor at NIST's levels 1, 3, and 5, respectively.
ePrint Report Towards Optimized and Constant-Time CSIDH on Embedded Devices Amir Jalali, Reza Azarderakhsh, Mehran Mozaffari Kermani, David Jao
We present an optimized, constant-time software library for commutative supersingular isogeny Diffie-Hellman key exchange (CSIDH) proposed by Castryck et al. which targets 64-bit ARM processors. The proposed library is implemented based on highly-optimized field arithmetic operations and computes the entire key exchange in constant-time. The proposed implementation is resistant to timing attacks. We adopt optimization techniques to evaluate the highest performance CSIDH on ARM-powered embedded devices such as cellphones, analyzing the possibility of using such a scheme in the quantum era. To the best of our knowledge, the proposed implementation is the first constant-time implementation of CSIDH and the first evaluation of this scheme on embedded devices. The benchmark result on a Google Pixel 2 smartphone equipped with 64-bit high-performance ARM Cortex-A72 core shows that it takes almost 12 seconds for each party to compute a commutative action operation in constant-time over the 511-bit finite field proposed by Castryck et al. However, using uniform but variable-time Montgomery ladder with security considerations improves these results significantly.
Last year Takashima proposed a version of Charles, Goren and Lauter’s hash function using Richelot isogenies, starting from a genus-2 curve that allows for all subsequent arithmetic to be performed over a quadratic finite field Fp^2 . In a very recent paper Flynn and Ti point out that Takashima’s hash function is insecure due to the existence of small isogeny cycles. We revisit the construction and show that it can be repaired by imposing a simple restriction, which moreover clarifies the security analysis. The runtime of the resulting hash function is dominated by the extraction of 3 square roots for every block of 3 bits of the message, as compared to one square root per bit in the elliptic curve case; however in our setting the extractions can be parallelized and are done in a finite field whose bit size is reduced by a factor 3. Along the way we argue that the full supersingular isogeny graph is the wrong context in which to study higher-dimensional analogues of Charles, Goren and Lauter’s hash function, and advocate the use of the superspecial subgraph, which is the natural framework in which to view Takashima’s Fp^2-friendly starting curve.
ePrint Report Balancing Image Privacy and Usability with Thumbnail-Preserving Encryption Kimia Tajik, Akshith Gunasekaran, Rhea Dutta, Brandon Ellis, Rakesh B. Bobba, Mike Rosulek, Charles V. Wright, Wu-chi Feng
In this paper, we motivate the need for image encryption techniques that preserve certain visual features in images and hide all other information, to balance privacy and usability in the context of cloud-based image storage services. In particular, we introduce the concept of ideal or exact Thumbnail-Preserving Encryption (TPE), a special case of format-preserving encryption, and present a concrete construction. In TPE, a ciphertext is itself an image that has the same thumbnail as the plaintext (unencrypted) image, but that provably leaks nothing about the plaintext beyond its thumbnail. We provide a formal security analysis for the construction, and a prototype implementation to demonstrate compatibility with existing services. We also study the ability of users to distinguish between thumbnail images preserved by TPE. Our findings indicate that TPE is an efficient and promising approach to balance usability and privacy concerns for images. Our code and a demo are available at
ePrint Report Semi-parallel Logistic Regression for GWAS on Encrypted Data Miran Kim, Yongsoo Song, Baiyu Li, Daniele Micciancio
The sharing of biomedical data is crucial to enable scientific discoveries across institutions and improve health care. For example, genome-wide association studies (GWAS) based on a large number of samples can identify disease-causing genetic variants. The privacy concern, however, has become a major hurdle for data management and utilization. Homomorphic encryption is one of the most powerful cryptographic primitives which can address the privacy and security issues. It supports the computation on encrypted data so that we can aggregate data and perform an arbitrary computation on an untrusted cloud environment without the leakage of sensitive information.

This paper presents a secure outsourcing solution to assess logistic regression models for quantitative traits to test their associations with genotypes. We adapt the semi-parallel training method by Sikorska et al., which builds a logistic regression model for covariates, followed by one-step parallelizable regressions on all individual single nucleotide polymorphisms (SNPs). In addition, we modify our underlying approximate homomorphic encryption scheme for performance improvement.

We evaluate the performance of our solution through experiments on real-world dataset. It achieves the best performance of homomorphic encryption system for GWAS analysis in terms of both complexity and accuracy. For example, given a dataset consisting of 245 samples, each of which has 10643 SNPs and 3 covariates, our algorithm takes about 41 seconds to perform logistic regression based genome wide association analysis over encryption. We demonstrate the feasibility and scalability of our solution.
ePrint Report Impossibility of Strong KDM Security with Auxiliary Input Cody Freitag, Ilan Komargodski, Rafael Pass
In this note, we show that a strong notion of KDM security cannot be obtained by any encryption scheme in the auxiliary input setting, assuming Learning With Errors (LWE) and one-way permutations. The notion of security we deal with guarantees that for any (possibly inefficient) function $f$, it is computationally hard to distinguish between an encryption of 0s and an encryption of f(pk, z), where pk is the public key and z is the auxiliary input. Furthermore, we show that this holds even when restricted to bounded-length auxiliary input where z is much shorter than pk under the additional assumption that (non-leveled) fully homomorphic encryption exists.
19 March 2019
Eurocrypt Eurocrypt 2019 registration now open Early registration deadline Apr 15
Registration for Eurocrypt 2019 is now open; information can be found at Prices will increase after April 15.

Eurocrypt will be held this year in Darmstadt, Germany from May 19-23, with affiliated events held on May 18-19.
ePrint Report Timing attacks on Error Correcting Codes in Post-Quantum Secure Schemes Jan-Pieter D'Anvers, Marcel Tiepelt, Frederik Vercauteren, Ingrid Verbauwhede
While error correcting codes (ECC) have the potential to significantly reduce the failure probability of post-quantum schemes, they add an extra ECC decoding step to the algorithm. As this additional computation handles secret information, it is susceptible to side-channel attacks. We show that if no precaution is taken, it is possible to use timing information to distinguish between ciphertexts that result in an error before decoding and ciphertexts that do not contain errors, due to the variable execution time of the ECC decoding algorithm. We demonstrate that this information can be used to break the IND-CCA security of post-quantum secure schemes by presenting an attack on both the Ring-LWE scheme LAC and the Mersenne prime scheme Ramstake. This attack recovers the full secret key using a limited number of timed decryption queries. The attack is implemented on the reference and the optimized implementations of both submissions. It is able to retrieve LAC's secret for all security levels in under 2 hours using less than $2^{21}$ decryption queries and Ramstake's secret in under 2 minutes using approximately $2400$ decryption queries. The attack generalizes to other schemes with ECC's in which side-channel information about the presence of errors is leaked during decoding.
We study the relationship among public-key encryption (PKE) satisfying indistinguishability against chosen plaintext attacks (IND-CPA security), that against chosen ciphertext attacks (IND-CCA security), and trapdoor functions (TDF). Specifically, we aim at finding a unified approach and some additional requirement to realize IND-CCA secure PKE and TDF based on IND-CPA secure PKE, and show the following two main results.

As the first main result, we show how to achieve IND-CCA security via a weak form of key-dependent-message (KDM) security. More specifically, we construct an IND-CCA secure PKE scheme based on an IND-CPA secure PKE scheme and a secret-key encryption (SKE) scheme satisfying one-time KDM security with respect to projection functions (projection-KDM security). Projection functions are very simple functions with respect to which KDM security has been widely studied. Since the existence of projection-KDM secure PKE implies that of the above two building blocks, as a corollary of this result, we see that the existence of IND-CCA secure PKE is implied by that of projection-KDM secure PKE.

As the second main result, we extend the above construction of IND-CCA secure PKE into that of TDF by additionally requiring a mild requirement for each building block. Our TDF satisfies adaptive one-wayness. We can instantiate our TDF based on a wide variety of computational assumptions. Especially, we obtain the first TDF (with adaptive one-wayness) based on the sub-exponential hardness of constant-noise learning-parity-with-noise (LPN) problem.
Invasive or semi-invasive attacks require, of course, because of their nature, the removal of metal layers or at least the package de-capsulation of the chip. For many people - not expert in those sample preparation techniques - the simple access to the die surface and the observation of the chip structure after metal layers removal are the first obstacles to conduct an attack. In another direction, the development of embedded secure devices, sometime with very dense and complex assembly process, adds a new difficulty for an attacker to get a physical access to the silicon without intensive use of advanced soldering capabilities. This paper will deal with those two challenges: the first one is to provide an in-situ depackaging solution with limited ressources and then, the second one consists in finding the minimum mandatory tools required to perform chip delayering before metal layers imaging - or reverse engineering.

  older items