International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News

Updates on the COVID-19 situation are on the Announcement channel.

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

RSS symbol icon
via RSS feed
Twitter bird icon
via Twitter
Weibo icon
via Weibo
Facebook icon
via Facebook

12 July 2021

CRYPTO CRYPTO
Crypto 2021 will be held virtually August 16-20 2021.

The registration is now open and all relevant information can be found here:https://crypto.iacr.org/2021/registration.php

Information about the program and affiliated events can be found here: https://crypto.iacr.org/2021/
Expand
-
Event Calendar Event Calendar
Event date: to
Submission deadline: 2 August 2021
Expand
Award Award
The IACR Fellows Program recognizes outstanding IACR members for technical and professional contributions to the field of cryptology. Today we are pleased to announce five members that have been elevated to the rank of Fellow for 2021:
  • Craig Gentry, for breakthrough research on fully homomorphic encryption and other fundamental contributions to cryptography.
  • Yehuda Lindell, for fundamental contributions to theory and practice of secure multiparty computation, for sustained educational leadership, and for service to the IACR.
  • Josef Pieprzyk, for significant contributions to design and analysis of cryptosystems, and for exceptional service to the IACR and the Asia-Pacific cryptographic community.
  • Leonid Reyzin, for fundamental contributions to theory and practice of cryptography, and for service to the IACR.
  • Ingrid Verbauwhede, for pioneering and sustained contributions to cryptographic hardware and embedded systems, and for service to the IACR.
Congratulations to the new fellows! More information about the IACR Fellows Program can be found at https://iacr.org/fellows/.
Expand

09 July 2021

Artem Los
ePrint Report ePrint Report
Licensing of software that will run in offline environments introduces constraints on the licensing model that can be supported. The difficulty arises in cases where information needs to be recorded about the usage of the software, for example in a consumption-based licensing model. We describe a method that makes it harder for an adversary to tamper with the recorded data as well as ways for software vendors to detect if tampering with this information would still occur.
Expand
Jan Richter-Brockmann, Aein Rezaei Shahmirzadi, Pascal Sasdrich, Amir Moradi, Tim Güneysu
ePrint Report ePrint Report
Fault Injection Analysis is seen as a powerful attack against implementations of cryptographic algorithms. Over the last two decades, researchers proposed a plethora of countermeasures to secure such implementations. However, the design process and implementation are still error-prone, complex, and manual tasks which require long-standing experience in hardware design and physical security. Moreover, the validation of the claimed security is often only done by empirical testing in a very late stage of the design process. To prevent such empirical testing strategies, approaches based on formal verification are applied instead providing the designer early feedback.

In this work, we present a fault verification framework to validate the security of countermeasures against fault-injection attacks designed for ICs. The verification framework works on netlist-level, parses the given digital circuit into a model based on Binary Decision Diagrams, and performs symbolic fault injections. This verification approach constitutes a novel strategy to evaluate protected hardware designs against fault injections offering new opportunities as performing full analyses under a given fault models.

Eventually, we apply the proposed verification framework to real-world implementations of well-established countermeasures against fault-injection attacks. Here, we consider protected designs of the lightweight ciphers CRAFT and LED-64 as well as AES. Due to several optimization strategies, our tool is able to perform more than 90 million fault injections in a single-round CRAFT design and evaluate the security in under 50 min while the symbolic simulation approach considers all $2^128$ primary inputs.
Expand
Pedro Branco, Luís Fiolhais, Manuel Goulão, Paulo Martins, Paulo Mateus, Leonel Sousa
ePrint Report ePrint Report
Oblivious Transfer (OT) is a fundamental primitive in cryptography, supporting protocols such as Multi-Party Computation and Private Set Intersection (PSI), that are used in applications like contact discovery, remote diagnosis and contact tracing. Due to its fundamental nature, it is utterly important that its execution is secure even if arbitrarily composed with other instances of the same, or other protocols. This property can be guaranteed by proving its security under the Universal Composability model. Herein, a 3-round Random Oblivious Transfer (ROT) protocol is proposed, which achieves high computational efficiency, in the Random Oracle Model. The security of the protocol is based on the Ring Learning With Errors assumption (for which no quantum solver is known). ROT is the basis for OT extensions and, thus, achieves wide applicability, without the overhead of compiling ROTs from OTs. Finally, the protocol is implemented in a server-class Intel processor and four application-class ARM processors, all with different architectures. The usage of vector instructions provides on average a 40% speedup. The implementation shows that our proposal is at least one order of magnitude faster than the state-of-the-art, and is suitable for a wide range of applications in embedded systems, IoT, desktop, and servers. From a memory footprint perspective, there is a small increase (16%) when compared to the state-of-the-art. This increase is marginal and should not prevent the usage of the proposed protocol in a multitude of devices. In sum, the proposal achieves up to 37k ROTs/s in an Intel server-class processor and up to 5k ROTs/s in an ARM application-class processor. A PSI application, using the proposed ROT, is up to 6.6 times faster than related art.
Expand
Diego F. Aranha, Emil Madsen Bennedsen, Matteo Campanelli, Chaya Ganesh, Claudio Orlandi, Akira Takahashi
ePrint Report ePrint Report
We provide new constructions for zero-knowledge commit-and-prove SNARKs (CP-SNARKs) with a universal updatable SRS. Informally, a commit-and-prove argument system is one that can efficiently prove relations over committed inputs. They have many applications, including allowing for efficient composition of proof systems with different strength points.

We first show a general technique to compile Algebraic Holographic Proofs (AHP) with special ``decomposition'' properties into an efficient CP-SNARK with universal and updatable SRS. We require that the polynomials in an AHP can be easily decomposed into components that refer to the committed part of the witness and the rest of the witness respectively.

We then show that some of the most efficient AHP constructions---Marlin, PLONK, and Sonic---satisfy our compilation requirements. To obtain succinct instantiations of our protocols we rely on recent advancements in compressed $\Sigma$-protocol theory (Attema and Cramer, Crypto '20). Our constructions retain the succinct proof size of the underlying AHP and only impose an additional proof size that grows logarithmically with the size of the committed component of the witness.
Expand
Claus Peter Schnorr
ePrint Report ePrint Report
To factor an integer $N$ we construct $n$ triples of $p_n$-smooth integers $u,v,|u-vN|$ for the $n$-th prime $p_n$. Denote such triple a fac-relation. We get fac-relations from a nearly shortest vector of the lattice $\mathcal L(\mathbf R_{n, f})$ with basis matrix $\mathbf R_{n, f} \in \mathbb R^{(n+1)\times(n+1)}$ where $f\colon [1, n]\to[1, n]$ is a permutation of $[1, 2, \ldots, n]$ and $(f(1),\ldots,f(n),N'\ln N)$ is the diagonal and $(N' \ln p_1,\ldots, N' \ln p_n,N' \ln N)$ for $N' = N^{\frac{1}{n+1}}$ is the last line of $\mathbf R_{n, f}$. An independent permutation $f'$ yields an independent fac-relation. We find sufficiently short lattice vectors by strong primal-dual reduction of $\mathbf R_{n, f}$. We factor $N\approx 2^{400}$ by $n = 47$ and $N\approx 2^{800}$ by $n = 95$. Our accelerated strong primal-dual reduction of [GN08] factors integers $N\approx 2^{400}$ and $N\approx 2^{800}$ by $4.2\cdot 10^9$ and $8.4\cdot 10^{10}$ arithmetic operations, much faster then the quadratic sieve and the number field sieve and using much smaller primes $p_n$. This destroys the RSA cryptosystem.
Expand
Helger Lipmaa, Kateryna Pavlyk
ePrint Report ePrint Report
A succinct functional commitment (SFC) scheme for a circuit class $\mathbf{CC}$ enables, for any circuit $\mathcal{C} \in \mathbf{CC}$, the committer to first succinctly commit to a vector $\vec{\alpha}$, and later succinctly open the commitment to $\mathcal{C} (\vec{\alpha}, \vec{\beta})$, where the verifier chooses $\vec{\beta}$ at the time of opening. Unfortunately, SFC commitment schemes are known only for severely limited function classes like the class of inner products. By making non-black-box use of SNARK-construction techniques, we propose an SFC scheme for the large class of semi-sparse polynomials. The new SFC scheme can be used to, say, efficiently (1) implement sparse polynomials, and (2) aggregate various interesting SFC (e.g., vector commitment and polynomial commitment) schemes. The new scheme is evaluation-binding under a new instantiation of the computational uber-assumption. We provide a thorough analysis of the new assumption.
Expand
Orr Dunkelman, Maria Eichlseder, Daniel Kales, Nathan Keller, Gaëtan Leurent, Markus Schofnegger
ePrint Report ePrint Report
FlexAEAD is a block cipher candidate submitted to the NIST Lightweight Cryptography standardization project, based on repeated application of an Even-Mansour construction. In order to optimize performance, the designers chose a relatively small number of rounds, using properties of the mode and bounds on differential and linear characteristics to substantiate their security claims. Due to a forgery attack with complexity $2^{46}$, FlexAEAD was not selected to the second round of evaluation in the NIST project.

In this paper we present a practical key recovery attack on FlexAEAD, using clusters of differentials for the internal permutation and the interplay between different parts of the mode. Our attack, which was fully verified in practice, allows recovering the secret subkeys of FlexAEAD-64 with a time complexity of less than $2^{31}$ encryptions (with an experimental success rate of $75\,\%$). This is the first practical key recovery attack on a candidate of the NIST standardization project.
Expand
Ulrich Haböck, Alberto Garoffolo, Daniele Di Benedetto
ePrint Report ePrint Report
In this document we describe the Darlin proof carrying data scheme for the distributed computation of block and epoch proofs in a Latus sidechain of Zendoo (IACR eprint 2020/123). Recursion as well as base proofs rest on Marlin using the Pasta cycle of curves and the ‘dlog’ polynomial commitment scheme introduced by Bootle et al. EUROCRYPT 2016. We apply the amortization technique from Halo (IACR eprint 2019/099) to the non-succinct parts of the verifier, and we adapt their strategy for bivariate circuit encoding polynomials to aggregate Marlin’s inner sumchecks across the nodes of the proof carrying data scheme. Regarding performance, the advantage of Darlin over a scheme without inner sumcheck aggregation is about 30% in a tree-like scenario as ours, and beyond when applied to linear recursion.
Expand
Pierre Briaud, Jean-Pierre Tillich, Javier Verbel
ePrint Report ePrint Report
The Sidon cryptosystem is a new multivariate encryption scheme based on the theory of Sidon spaces which was presented at PKC 2021. As is usual for this kind of schemes, its security relies on the hardness of solving particular instances of the MQ problem and of the MinRank problem. A nice feature of the scheme is that it enjoys a homomorphic property due the bilinearity of its public polynomials. Unfortunately, we will show that the Sidon cryptosystem can be broken by a polynomial time key-recovery attack. This attack relies on the existence of solutions to the underlying MinRank instance which lie in a subfield and which are inherent to the structure of the secret Sidon space. We prove that such solutions can be found in polynomial time. Our attack consists in recovering an equivalent key for the cryptosystem by exploiting these particular solutions, and this task can be performed very efficiently.
Expand
Jianghua Zhong, Yingyin Pan , Wenhui Kong, Dongdai Lin
ePrint Report ePrint Report
Many recent stream ciphers use Galois NFSRs as their main building blocks, such as the hardware-oriented finalists Grain and Trivium in the eSTREAM project. Previous work has found some types of Galois NFSRs equivalent to Fibonacci ones, including that used in Grain. Based on the observability of an NFSR on [0,N-1], which means any two initial states of an NFSR are distinguishable from their corresponding output sequences of length N, the paper first presents two easily verifiable necessary and sufficient conditions for Galois NFSRs equivalent to Fibonacci ones. It then validates both conditions by the Galois NFSRs previously found (not) equivalent to Fibonacci ones. As an application, the paper finally reveals that the 288-stage Galois NFSR used in Trivium is neither equivalent to a 288-stage Fibonacci NFSR, nor observable on [0,287], theoretically verifying Trivium's good design criteria of confusion and diffusion.
Expand
Shuichi Katsumata
ePrint Report ePrint Report
Many of the recent advanced lattice-based $\Sigma$-/public-coin honest verifier (HVZK) interactive protocols based on the techniques developed by Lyubashevsky (Asiacrypt'09, Eurocrypt'12) can be transformed into a non-interactive zero-knowledge (NIZK) proof in the random oracle model (ROM) using the Fiat-Shamir transform. Unfortunately, although they are known to be secure in the $\mathit{classical}$ ROM, existing proof techniques are incapable of proving them secure in the $\mathit{quantum}$ ROM (QROM). Alternatively, while we could instead rely on the Unruh transform (Eurocrypt'15), the resulting QROM secure NIZK will incur a large overhead compared to the underlying interactive protocol.

In this paper, we present a new simple semi-generic transform that compiles many existing lattice-based $\Sigma$-/public-coin HVZK interactive protocols into QROM secure NIZKs. Our transform builds on a new primitive called $\textit{extractable linear homomorphic commitment}$ protocol. The resulting NIZK has several appealing features: it is not only a proof of knowledge but also straight-line extractable; the proof overhead is smaller compared to the Unruh transform; it enjoys a relatively small reduction loss; and it requires minimal background on quantum computation. To illustrate the generality of our technique, we show how to transform the recent Bootle et al.'s 5-round protocol with an exact sound proof (Crypto'19) into a QROM secure NIZK by increasing the proof size by a factor of $2.6$. This compares favorably to the Unruh transform that requires a factor of more than $50$.
Expand
Chethan Kamath, Karen Klein, Krzysztof Pietrzak
ePrint Report ePrint Report
We show that Yao’s garbling scheme is adaptively indistinguishable for the class of Boolean circuits of size S and treewidth w with only a S^O(w) loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions, we introduce a new pebble game that abstracts out our security reduction and then present a pebbling strategy for this game where the number of pebbles used is roughly O(d w log(S)), d being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity.
Expand
Marten van Dijk, Deniz Gurevin, Chenglu Jin, Omer Khan, Phuong Ha Nguyen
ePrint Report ePrint Report
Dijk et al. presents Remote Attestation (RA) for secure processor technology which is secure in the presence of an All Digital State Observing (ADSO) adversary. The scheme uses a combination of hardware security primitives and design principles together with a new cryptographic primitive called a Public Key Session based One-Time Signature Scheme with Secret Key Exposure (OTS-SKE). Dijk et al. show a hash based realization of OTS-SKE which is post quantum secure but suffers long $8.704$ KB signatures for 128-bit quantum security or 256-bit classical security. From a classical cryptographic perspective we complete the picture by introducing a bilinear map based OTS-SKE with short $0.125$ KB signatures, $65$ times shorter, and for which the security reduces to the Computational Diffie-Hellman Problem (CDHP) -- at the cost of a $9\times$ longer initialization phase in the RA scheme if implemented in software (this can be improved with appropriate elliptic curve hardware acceleration). Signing takes 560 ms at most $60\%$ of the $>936$ ms needed for the hash based scheme.
Expand
Rouzbeh Behnia, Yilei Chen, Daniel Masny
ePrint Report ePrint Report
Digital signatures following the methodology of “Fiat-Shamir with Aborts”, proposed by Lyubashevsky, are capable of achieving the smallest public-key and signature sizes among all the existing lattice signature schemes based on the hardness of the Ring-SIS and Ring-LWE problems. Since its introduction, several variants and optimizations have been proposed, and two of them (i.e., Dilithium and qTESLA) entered the second round of the NIST post-quantum cryptography standardization. This method of designing signatures relies on rejection sampling during the signing process. Rejection sampling is crucial for ensuring both the correctness and security of these signature schemes. In this paper, we investigate the possibility of removing the two rejection conditions used both in Dilithium and qTESLA. First, we show that removing one of the rejection conditions is possible, and provide a variant of Lyubashevsky’s signature with comparable parameters with Dilithium and qTESLA. Second, we give evidence on the difficulty of removing the other rejection condition, by showing that two very general approaches do not yield a signature scheme with correctness or security.
Expand
Luca De Feo, Bertram Poettering, Alessandro Sorniotti
ePrint Report ePrint Report
Roughly four decades ago, Taher ElGamal put forward what is today one of the most widely known and best understood public key encryption schemes. ElGamal encryption has been used in many different contexts, chiefly among them by the OpenPGP standard. Despite its simplicity, or perhaps because of it, in reality there is a large degree of ambiguity on several key aspects of the cipher. Each library in the OpenPGP ecosystem seems to have implemented a slightly different "flavour" of ElGamal encryption. While --taken in isolation-- each implementation may be secure, we reveal that in the interoperable world of OpenPGP, unforeseen cross-configuration attacks become possible. Concretely, we propose different such attacks and show their practical efficacy by recovering plaintexts and even secret keys.
Expand
Kunal Dey, Sumit Kumar Debnath
ePrint Report ePrint Report
Digital signature is one of the most important public key cryptographic primitive for message authentication. In a digital signature scheme, receiver of a message-signature pair gets assurance about the fact that the message belongs to the sender and neither receiver nor any third party can manipulate the message. In the current state of art, most of the existing digital signatures' security relies on classical cryptographic assumption based hard problems, such as discrete log, integer factorization, etc. However, rapid development of quantum computing creates a security threat to these classical digital signature schemes. It indicates the recruitment of an alternative solution which can prevent quantum attacks. We focus on this concern by implementing a post-quantum secure isogeny based digital signature scheme without making use of SIDH and CSIDH. Our scheme achieves uf-cma security under a hard problem in isogeny. The proposed signature scheme incurs 256 byte public key size and 128 byte signature size to achieve 128-bit security level (NIST-1 level of security). In particular, the size of signature of our design is smaller than all other IBC based signature schemes at the 128-bit security level.
Expand
Wenshuo Guo, Fang-Wei Fu
ePrint Report ePrint Report
This paper presents a brand-new idea of masking the algebraic structure of linear codes used in code-based cryptography. Specially, we introduce the so-called semilinear transformations in coding theory, make a thorough study on their algebraic properties and then creatively apply them to the construction of code-based cryptosystems. Note that $\mathbb{F}_{q^m}$ can be viewed as an $\mathbb{F}_q$-linear space of dimension $m$, a semilinear transformation $\varphi$ is therefore defined to be an $\mathbb{F}_q$-linear automorphism of $\mathbb{F}_{q^m}$. After that, we impose this transformation to a linear code $\mathcal{C}$ over $\mathbb{F}_{q^m}$. Apparently $\varphi(\mathcal{C})$ forms an $\mathbb{F}_q$-linear space, but generally does not preserve the $\mathbb{F}_{q^m}$-linearity according to our analysis. Inspired by this observation, a new technique for masking the structure of linear codes is developed in this paper. Meanwhile, we endow the secret code with the so-called partial cyclic structure to make a reduction in public-key size. Compared to some other code-based cryptosystems, our proposal admits a much more compact representation of public keys. For instance, 1058 bytes are enough to reach the security of 256 bits, almost 1000 times smaller than that of the Classic McEliece entering the third round of the NIST PQC project.
Expand
◄ Previous Next ►