International Association
for Cryptologic Research

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.

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.

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.

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 http://photoencryption.org.

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.

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.

Registration for Eurocrypt 2019 is now open; information can be found at https://eurocrypt.iacr.org/2019/registration.html. 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.

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.

Forkciphers are a new kind of primitive proposed recently by Andreeva et al. for efficient encryption and authentication of small messages. They fork the middle state of a cipher and encrypt it twice under two smaller independent permutations. Thus, forkciphers produce two output blocks in one primitive call.

Andreeva et al. proposed ForkAES, a tweakable AES-based forkcipher that splits the state after five out of ten rounds. While their authenticated encrypted schemes were accompanied by proofs, the security discussion for ForkAES was not provided, and founded on existing results on the AES and KIASU-BC. Forkciphers provide a unique interface called reconstruction queries that use one ciphertext block as input and compute the respective other ciphertext block. Thus, they deserve a careful security analysis.

This work fosters the understanding of the security of ForkAES with three contributions: (1) We observe that security in reconstruction queries differs strongly from the existing results on the AES. This allows to attack nine out of ten rounds with differential, impossible-differential and yoyo attacks. (2) We observe that some forkcipher modes may lack the interface of reconstruction queries, so that attackers must use encryption queries. We show that nine rounds can still be attacked with rectangle and impossible-differential attacks. (3) We present forgery attacks on the AE modes proposed by Andreeva et al. with nine-round ForkAES.

Modern block ciphers are facing the threat of side-channel attacks by power leakage whose main target are the non-linear components known as S-boxes. A theoretical measure for the resistance of an S-box against this type of attacks is the confusion coefficient variance property. A higher value of this property represents a better theoretical resistance. In this work we use the leaders and followers meta-heuristic in order to achieve good confusion coefficient variance’s valued S-boxes.

We propose a general method for security evaluation of SNOW 2.0-like ciphers against correlation attacks that are built similarly to known attacks on SNOW 2.0. Unlike previously known methods, the method we propose is targeted at security proof and allows obtaining lower bounds for efficiency of attacks from the class under consideration directly using parameters of stream cipher components similarly to techniques for security proofs of block ciphers against linear cryptanalysis. The method proposed is based upon automata-theoretic approach to evaluation the imbalance of discrete functions. In particular, we obtain a matrix representation and upper bounds for imbalance of an arbitrary discrete function being realized by a sequence of finite automata. These results generalize a number of previously known statements on matrix (linear) representations for imbalance of functions having specified forms, and may be applied to security proofs for other stream ciphers against correlation attacks. Application of this method to SNOW 2.0 and Strumok ciphers shows that any of the considered correlation attacks on them over the field of the order 256 has an average time complexity not less than $2^{146.20}$ and $2^{249.40}$ respectively, and requires not less than $2^{142.77}$ and, respectively, $2^{249.38}$ keystream symbols.

Boolean functions used in some cryptosystems of stream ciphers should satisfy various criteria simultaneously to resist some known attacks. The fast algebraic attack (FAA) is feasible if one can find a nonzero function $g$ of low algebraic degree and a function $h$ of algebraic degree significantly lower than $n$ such that $f\cdot g=h$. Then one new cryptographic property fast algebraic immunity was proposed, which measures the ability of Boolean functions to resist FAAs. It is a great challenge to determine the exact values of the fast algebraic immunity of an infinite class of Boolean functions with optimal algebraic immunity. In this letter, we explore the exact fast algebraic immunity of two subclasses of the majority function.

A geometry is a measure of restraint over the allowed 0.5n(n-1) distances between a set of n points (e.g. the metric and topological spaces). So defined, geometries lead to associated algebra. The complexities of such algebras are used to build cryptographic primitives. We propose then to push geometries to the limit -- unbound geometries -- where any two points may be assigned an arbitrary distance value, which may reflect a planning process or a randomized assignment. Regarding these distances as a cryptographic key, one could use the resultant algebras to carry out cryptographic missions. We define the mathematical framework for this aim, then present a few cryptographic primitives. Most effective implementation is through the new technology for “rock of randomness” establishing random distances through 3D printed molecular compounds. Security is proportional to the size of the ‘rock’. We use the term SpaceFlip to collectively refer to the unbound geometry, its associated algebra and the cryptographic tools derived from it.

In ISO/IEC 20008-2, several anonymous digital signature schemes are specified. Among these, the scheme denoted as Mechanism 6, is the only plain group signature scheme that does not aim at providing additional functionalities. The Intel Enhanced Privacy Identification (EPID) scheme, which has many applications in connection with Intel Software Guard Extensions (Intel SGX), is in practice derived from Mechanism 6. In this paper, we firstly show that Mechanism 6 does not satisfy anonymity in the standard security model, i.e., the Bellare-Shi-Zhang model [CT-RSA 2005]. We then provide a detailed analysis of the security properties offered by Mechanism 6 and characterize the conditions under which its anonymity is preserved. Consequently, it is seen that Mechanism 6 is secure under the condition that the issuer, who generates user signing keys, does not join the attack. We also derive a simple patch for Mechanism 6 from the analysis.

In this paper, we describe an attack on RSA cryptosystem which is based on Euclid's algorithm. Given a public key $(n,e)$ with corresponding private key $d$ such that $e$ has the same order of magnitude as $n$ and one of the integers $k = (ed-1)/\phi(n)$ and $e-k$ has at most one-quarter as many bits as $e$, it computes the factorization of $n$ in deterministic time $O((\log n)^2)$ bit operations.

Event date: 8 January to 10 January 2020
Submission deadline: 1 September 2019
Notification: 1 November 2019