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

18 August 2019

Gilles Barthe, Sandrine Blazy, Benjamin Grégoire, Rémi Hutin, Vincent Laporte, David Pichardie, Alix Trieu
ePrint Report ePrint Report
Timing side-channels are arguably one of the main sources of vulnerabilities in cryptographic implementations. One effective mitigation against timing side-channels is to write programs that do not perform secret-dependent branches and memory accesses. This mitigation, known as ''cryptographic constant-time'', is adopted by several popular cryptographic libraries.

This paper focuses on compilation of cryptographic constant-time programs, and more specifically on the following question: is the code generated by a realistic compiler for a constant-time source program itself provably constant-time? Surprisingly, we answer the question positively for a mildly modified version of the CompCert compiler, a formally verified and moderately optimizing compiler for C. Concretely, we modify the CompCert compiler to eliminate sources of potential leakage. Then, we instrument the operational semantics of CompCert intermediate languages so as to be able to capture cryptographic constant-time. Finally, we prove that the modified CompCert compiler preserves constant-time. Our mechanization maximizes reuse of the CompCert correctness proof, through the use of new proof techniques for proving preservation of constant-time. These techniques achieve complementary trade-offs between generality and tractability of proof effort, and are of independent interest.
Expand
Wulu Li, Lei Chen, Xin Lai, Xiao Zhang, Jiajun Xin
ePrint Report ePrint Report
Privacy protection has been extensively studied in the current blockchain research field. As representations, Monero and Zerocash have realized completely anonymous and amount-hiding transactions. However, nonregulation can lead to abuse of privacy, which brings about serious risks of breaking laws and committing crimes. Therefore, it is crucial to study the privacy-preserving blockchain systems with regulatory functions. In this paper, we discuss the regulatory model (regulator behavior, user behavior) on the privacy-preserving blockchains from application scenarios and finally select unconditional regulation, static regulation, and self-participation of users as the core principles, which is currently the closest approach to the "decentralization" of regulatable privacy-preserving blockchains. On the basis of the established regulatory model, we first propose a traceable and linkable ring signature scheme (TLRS) by use of classic ring signatures, one-time signatures and zero-knowledge proofs, which realizes the unforgeability, anonymity, linkability, nonslanderability and traceability of users' identities. Moreover, we first propose traceable Borromean range proof (TBoRP) and traceable Bulletproofs range proof (TBuRP) by use of Fiat-Shamir transform and DH assumptions, which realize the completeness, soundness, zero-knowledge and traceability of the transaction amounts. We also apply the newly designed schemes and other zero-knowledge proof protocols to achieve richer regulatory functions.
Expand
Dirk Achenbach, Roland Gröll, Timon Hackenjos, Alexander Koch, Bernhard Löwe, Jeremias Mechler, Jörn Müller-Quade, Jochen Rill
ePrint Report ePrint Report
EMV, also known as Chip and PIN, is the world-wide standard for card-based electronic payment. Its security wavers: over the past years, researchers have demonstrated various practical attacks, ranging from using stolen cards by disabling PIN verification to cloning cards by pre-computing transaction data. Most of these attacks rely on violating certain unjustified and not explicitly stated core assumptions upon which EMV is built, namely that the input device (e.g. the ATM) is trusted and all communication channels are non-interceptable. In addition, EMV lacks a comprehensive formal description of its security. In this work we give a formal model for the security of electronic payment protocols in the Universal Composability (UC) framework. A particular challenge for electronic payment is that one participant of a transaction is a human who cannot perform cryptographic operations. Our goal is twofold. First, we want to enable a transition from the iterative engineering of such protocols to using cryptographic security models to argue about a protocol’s security. Second, we establish a more realistic adversarial model for payment protocols in the presence of insecure devices and channels. We prove a set of necessary requirements for secure electronic payment with regards to our model. We then discuss the security of current payment protocols based on these results and find that most are insecure or require unrealistically strong assumptions. Finally, we give a simple payment protocol inspired by chipTAN and photoTAN and prove its security. Our model captures the security properties of electronic payment protocols with human interaction. We show how to use this to reason about necessary requirements for secure electronic payment and how to develop a protocol based on the resulting guidelines. We hope that this will facilitate the development of new protocols with well-understood security properties.
Expand

13 August 2019

Bastian Richter, Alexander Wild, Amir Moradi
ePrint Report ePrint Report
In side-channel analysis attacks, on-die localized EM monitoring enable high bandwidth measurements of only a relevant part of the Integrated Circuit (IC). This can lead to improved attacks compared to cases where only power consumption is measured. Combined with profiled attacks which utilize a training phase to create precise models of the information leakage, the attacks can become even more powerful. In contrast, localized EM measurements can cause difficulties in applying the learned models as the probe should be identically positioned for both the training and the attack even when the setup was used otherwise in between. Even small differences in the probe position can lead to significant differences in the recorded signals. In this paper we present an automated system to precisely and efficiently reposition the probe when performing repeated measurements. Based on the training IC, we train a machine learning system to return the position of the probe for a given measurement. By taking a small number of measurements on the IC under attack, we can then obtain the coordinates of the measurements and map it to correct the coordinate system. As the target for our practical analyses, we use an STM32L0 ARMM0+ microcontroller with integrated hardware AES.
Expand
Karim Eldefrawy, Vitor Pereira
ePrint Report ePrint Report
Secure Multi-Party Computation (MPC) enables a group of $n$ distrusting parties to jointly compute a function using private inputs. MPC guarantees correctness of computation and confidentiality of inputs if no more than a threshold $t$ of the parties are corrupted. Proactive MPC (PMPC) addresses the stronger threat model of a mobile adversary that controls a changing set of parties (but only up to $t$ at any instant), and may eventually corrupt all $n$ parties over a long time.

This paper takes a first stab at developing high-assurance implementations of (P)MPC. We present high-assurance implementations of (P)MPC protocols. We formalize in EasyCrypt, a tool-assisted framework for building high-confidence cryptographic proofs, several abstract and reusable variations of secret sharing and of (P)MPC protocols building on top of them. Using those, we prove a series of abstract theorems for the proactive setting. We implement and perform computer-checked security proofs of concrete instantiations of all required (abstract) protocols in EasyCrypt.

We also develop a new tool-chain to extract high-assurance executable implementations of protocols implemented and verified in EasyCrypt that uses Why3 as an intermediate tool. Using this new tool, we were able to extract code from our (P)MPC formalizations and to conduct a practical evaluation of it by comparing the performance obtained using our approach to the performance of manually implemented versions using Python-based Charm framework for prototyping cryptographic schemes. We argue that the small overhead of our high-assurance executables is a reasonable price to pay for the increased confidence about their correctness and security.
Expand
Pavol Zajac
ePrint Report ePrint Report
Public key algorithms based on QC-MPDC and QC-LDPC codes for key encapsulation/encryption submitted to NIST post-quantum competition (BIKE, QC-MDPC KEM, LEDA) are vulnerable against reaction attacks based on decoding failures. To protect algorithms, authors propose to limit the key usage, in the extreme (BIKE) to only use ephemeral public keys. In some authenticated protocols, we need to combine each key with a signature, which can lead to increased traffic overhead, especially given large signature sizes of some of the proposed post-quantum signature schemes. We propose to combine ephemeral public keys with a simple Merkle-tree to obtain a server authenticated key encapsulation/transport suitable for TLS-like handshake protocols.
Expand
Raluca Posteuca
ePrint Report ePrint Report
The stream cipher FOUNTAIN was introduced in April 2019 as one of the candidates in the NIST lightweight crypto standardization process. In this paper we introduce a slide attack that leads to the construction of 32 relations on key bits, with time complexity around $17\times 2^{80}$. The success of the attack is around 98%. We also present some properties of the internal state transitions that allow the identification of (key-iv-ad) input data that produce identical ciphertexts, with probability of $2^{-32}$.
Expand
Wei Cheng, Claude Carlet, Kouassi Goli, Sylvain Guilley, Jean-Luc Danger
ePrint Report ePrint Report
Side-channel analysis and fault injection attacks are two typical threats to cryptographic implementations, especially in modern embedded devices. Thus there is an insistent demand for dual side-channel and fault injection protections. As it is known, masking is a kind of provable countermeasure against side-channel attacks. Recently, inner product masking (IPM) was proposed as a promising higher-order masking scheme against side-channel analysis, but not for fault injection attacks. In this paper, we devise a new masking scheme named IPM-FD. It is built on IPM, which enables fault detection. This novel masking scheme has three properties: the security orders in the word-level probing model, bit-level probing model, and the number of detected faults. IPM-FD is proven secure both in the word-level and in the bit-level probing models, and allows for end-to-end fault detection against fault injection attacks.

Furthermore, we illustrate its security order by interpreting IPM-FD as a coding problem then linking it to one defining parameters of linear code, and show its implementation cost by applying IPM-FD to AES-128.
Expand
Hai Zhou, Amin Rezaei, Yuanqi Shen
ePrint Report ePrint Report
Logic encryption, a method to lock a circuit from unauthorized use unless the correct key is provided, is the most important technique in hardware IP protection. However, with the discovery of the SAT attack, all traditional logic encryption algorithms are broken. New algorithms after the SAT attack are all vulnerable to structural analysis unless a provable obfuscation is applied to the locked circuit. But there is no provable logic obfuscation available, in spite of some vague resorting to logic resynthesis. In this paper, we formulate and discuss a trilemma in logic encryption among locking robustness, structural security, and encryption efficiency, showing that pre-SAT approaches achieve only structural security and encryption efficiency, and post-SAT approaches achieve only locking robustness and encryption efficiency. There is also a dilemma between query complexity and error number in locking. We first develop a theory and solution to the dilemma in locking between query complexity and error number. Then, we provide a provable obfuscation solution to the dilemma between structural security and locking robustness. We finally present and discuss some results towards the resolution of the trilemma in logic encryption.
Expand
Shixiong Wang, Juanyang Zhang, Jingnan He, Huaxiong Wang, Chao Li
ePrint Report ePrint Report
As an extension of identity-based encryption (IBE), revocable hierarchical IBE (RHIBE) supports both key revocation and key delegation simultaneously, which are two important functionalities for cryptographic use in practice. Recently in PKC 2019, Katsumata et al. constructed the first lattice-based RHIBE scheme with decryption key exposure resistance (DKER). Such constructions are all based on bilinear or multilinear maps before their work. In this paper, we simplify the construction of RHIBE scheme with DKER provided by Katsumata et al. With our new treatment of the identity spaces and the time period space, there is only one short trapdoor base in the master secret key and in the secret key of each identity. In addition, we claim that some items in the keys can also be removed due to the DKER setting. Our first RHIBE scheme in the standard model is presented as a result of the above simplification. Furthermore, based on the technique for lattice basis delegation in fixed dimension, we construct our second RHIBE scheme in the random oracle model. It has much shorter items in keys and ciphertexts than before, and also achieves the adaptive-identity security under the learning with errors (LWE) assumption.
Expand
Kai Chen; Zhongrui Lin; Jian Wan; Lei Xu; Chungen Xu.
ePrint Report ePrint Report
Searchable symmetric encryption (SSE) for multi-owner model draws much attention as it enables data users to perform searches over encrypted cloud data outsourced by data owners. However, implementing secure and precise query, efficient search and flexible dynamic system maintenance at the same time in SSE remains a challenge. To address this, this paper proposes secure and efficient multi-keyword ranked search over encrypted cloud data for multi-owner model based on searching adversarial networks. We exploit searching adversarial networks to achieve optimal pseudo-keyword padding, and obtain the optimal game equilibrium for query precision and privacy protection strength. Maximum likelihood search balanced tree is generated by probabilistic learning, which achieves efficient search and brings the computational complexity close to $\mathcal{O}(\log N)$. In addition, we enable flexible dynamic system maintenance with balanced index forest that makes full use of distributed computing. Compared with previous works, our solution maintains query precision above 95% while ensuring adequate privacy protection, and introduces low overhead on computation, communication and storage.
Expand
Lynn Margaret Batten, Hugh Cowie Williams
ePrint Report ePrint Report
Abstract. The extremely efficient Rabin-Williams signature scheme relies on decryption of a quadratic equation in order to retrieve the original message. Customarily, square roots are found using the Chinese Remainder Theorem. This can be done in polynomial time, but generally produces four options for the correct message which must be analyzed to determine the correct one. This paper resolves the problem of efficient deterministic decryption to the correct message modulo $p^2q$ by establishing conditions on the primes $p$ and $q$ as well as on any legitimate message. We do this using the CRT modulo pq to find four roots. We show that the correct root (initial message) is the only one of these four which is in our allowed message set (it is in fact the smallest of the four integers) and which satisfies a quadratic equation modulo $p^2q$; no additional work is required to eliminate the others. As a result, we propose what we believe is now the most efficient version of R-W signature scheme decryption.
Expand
Fabio Banfi, Ueli Maurer, Christopher Portmann, Jiamin Zh
ePrint Report ePrint Report
Recent research in quantum cryptography has led to the development of schemes that encrypt and authenticate quantum messages with computational security. The security definitions used so far in the literature are asymptotic, game-based, and not known to be composable. We show how to define finite, composable, computational security for secure quantum message transmission. The new definitions do not involve any games or oracles, they are directly operational: a scheme is secure if it transforms an insecure channel and a shared key into an ideal secure channel from Alice to Bob, i.e., one which only allows Eve to block messages and learn their size, but not change them or read them. By modifying the ideal channel to provide Eve with more or less capabilities, one gets an array of different security notions. By design these transformations are composable, resulting in composable security.

Crucially, the new definitions are finite. Security does not rely on the asymptotic hardness of a computational problem. Instead, one proves a finite reduction: if an adversary can distinguish the constructed (real) channel from the ideal one (for some fixed security parameters), then she can solve a finite instance of some computational problem. Such a finite statement is needed to make security claims about concrete implementations.

We then prove that (slightly modified versions of) protocols proposed in the literature satisfy these composable definitions. And finally, we study the relations between some game-based definitions and our composable ones. In particular, we look at notions of quantum authenticated encryption and QCCA2, and show that they suffer from the same issues as their classical counterparts: they exclude certain protocols which are arguably secure.
Expand
Wen-Ran Zhang
ePrint Report ePrint Report
Whereas it is widely deemed impossible to overcome the optimality of the one-time pad (OTP) cipher in pre- and post-quantum cryptography, this work shows that the optimality of information theoretic security of OTP is paradoxical from the perspective of information conservational computing and cryptography. To prove this point, information theoretic security of OTP is extended to information conservational security of scalable one-time pad (S-OTP) where total key length can be compressed to a condensed tiny minimum through “black hole” keypad compression coupled with “big bang” data recovery. Thus, S-OTP makes it possible for secure transmission of long messages that used to be impossible with OTP. It is proven that if the security of OTP is optimal, S-OTP would be impossible; on the other hand, if S-OTP is not information theoretically secure, OTP would not be secure either. Thus, we have a proof by contradiction on the paradoxical nature of OTP optimality. It is further proven that a summation with percentage distribution is a special case of equilibrium-based bipolar quantum cellular automata. This proof bridges a classical world with a quantum world and makes it possible to combine the advantages of both approaches for pre- and post-quantum cryptography. It is suggested that the findings of this work form an analytical paradigm of quantum intelligence machinery toward perfect information conservational security. Some mysteries in nature and science are identified and discussed. In particular, the question is posted: Could modern science have been like a well-founded building with a floor of observable being and truth but missing its roof for equilibrium, harmony, information conservation, and logically definable causality?
Expand
David Derler, Sebastian Ramacher, Daniel Slamanig, Christoph Striecks
ePrint Report ePrint Report
Managing sensitive data in highly-distributed environments is gaining a lot of attention recently. Often, once data is presented to such environments, this data is persistent there. Being able to "forget" in such environments constitutes a very desired feature due to data security and privacy issues. In particular, applying the European General Data Protection Regulation (GDPR), the "Right to be Forgotten" essentially became a data owner right.

In this work, we seek for cryptographic solutions that offer the possibility to willfully lose access to data in distributed environments (which can be seen equivalent to removing that data). We argue that simple encryption mechanisms do not suffice to cover all desired requirements and provide a solution that offers several strong security and privacy features. In particular, our solution achieves forward secrecy for all participants in the system (i.e., even when user keys leak), ensures strong privacy against public observers of the system (i.e., key anonymity against tracking), and enables fine-grained access control. Having those features in parallel was unknown from the cryptographic literature.

We base our solution on a novel cryptographic primitive we dub Identity-Based Puncturable Encryption (IBPE) which significantly enhances previous ideas on Puncturable Encryption (PE) due to Green and Miers (IEEE S&P 2015) and Günther et al. (EUROCRYPT 2017). We argue that black-box constructions from Hierarchical Identity-Based Encryption (HIBE) do not seem to work, albeit we do know how to construct PE from HIBE. We further introduce an important feature being crucial in the setting of always-accessible and public data, namely that of key-anonymity for IBPE such that an IBPE ciphertext reveals nothing about the encryption key. We demonstrate the feasibility of our IBPE construction with a practical prototype implementation. Finally, we show that IBPE is a very versatile tool by using it to generically instantiate forward-secret IBE and forward-secret digital signatures, latter also being of importance in a distributed setting.
Expand

12 August 2019

Gildas Avoine, Sébastien Canard, Loïc Ferreira
ePrint Report ePrint Report
With the rise of the Internet of Things and the growing popularity of constrained end-devices, several security protocols are widely deployed or strongly promoted (e.g., Sigfox, LoRaWAN, NB-IoT). Based on symmetric-key functions, these protocols lack in providing security properties usually ensured by asymmetric schemes, in particular forward secrecy. We describe a 3-party authenticated key exchange protocol solely based on symmetric-key functions (regarding the computations done between the end-device and the back-end network) which guarantees forward secrecy. Our protocol enables session resumption (without impairing security). This allows saving communication and computation cost, and is particularly advantageous for low-resource end-devices. Our 3-party protocol can be applied in a real-case IoT deployment (i.e., involving numerous end-devices and servers) such that the latter inherits from the security properties of the protocol. We give a concrete instantiation of our key exchange protocol, and formally prove its security.
Expand

11 August 2019

Zurich, Switzerland, 23 November - 24 November 2019
Event Calendar Event Calendar
Event date: 23 November to 24 November 2019
Submission deadline: 3 August 2019
Notification: 18 September 2019
Expand

08 August 2019

Tobias Schneider, Clara Paglialonga, Tobias Oder, Tim Güneysu
ePrint Report ePrint Report
With the rising popularity of lattice-based cryptography, the Learning with Errors (LWE) problem has emerged as a fundamental core of numerous encryption and key exchange schemes. Many LWE-based schemes have in common that they require sampling from a discrete Gaussian distribution which comes with a number of challenges for the practical instantiation of those schemes. One of these is the inclusion of countermeasures against a physical side-channel adversary. While several works discuss the protection of samplers against timing leaks, only few publications explore resistance against other side-channels, e.g., power. The most recent example of a protected binomial sampler (as used in key encapsulation mechanisms to sufficiently approximate Gaussian distributions) from CHES 2018 is restricted to a first-order adversary and cannot be easily extended to higher protection orders. In this work, we present the first protected binomial sampler which provides provable security against a side-channel adversary at arbitrary orders. Our construction relies on a new conversion between Boolean and arithmetic (B2A) masking schemes for prime moduli which outperforms previous algorithms significantly for the relevant parameters, and is paired with a new masked bitsliced sampler allowing secure and efficient sampling even at larger protection orders. Since our proposed solution supports arbitrary moduli, it can be utilized in a large variety of lattice-based constructions, like NewHope, LIMA, Saber, Kyber, HILA5, or Ding Key Exchange.
Expand
Guillaume Wafo-Tapa, Slim Bettaieb, Loic Bidoux, Philippe Gaborit
ePrint Report ePrint Report
In this paper, we present a practicable chosen ciphertext timing attack retrieving the secret key of HQC. The attack exploits a correlation between the weight of the error to be decoded and the running time of the decoding algorithm of BCH codes. For the 128-bit security parameters of HQC, the attack runs in less than a minute on a desktop computer using 5441 decoding requests and has a success probability of approximately 93 percent. To prevent this attack, we propose a constant time algorithm for the decoding of BCH codes. Our implementation of the countermeasure achieves a constant time execution of the decoding process without a significant performance penalty.
Expand
Benoît Libert, Khoa Nguyen, Alain Passelègue, Radu Titiu
ePrint Report ePrint Report
The Naor-Yung paradigm is a well-known technique that constructs IND-CCA2-secure encryption schemes by means of non-interactive zero-knowledge proofs satisfying a notion of simulation-soundness. Until recently, it was an open problem to instantiate it under the sole Learning-With-Errors (LWE) assumption without relying on random oracles. While the recent results of Canetti et al. (STOC'19) and Peikert-Shiehian (Crypto'19) provide a solution to this problem by applying the Fiat-Shamir transform in the standard model, the resulting constructions are extremely inefficient as they proceed via a reduction to an NP-complete problem. In this paper, we give a direct, non-generic method for instantiating Naor-Yung under the LWE assumption outside the random oracle model. Specifically, we give a direct construction of an unbounded simulation-sound NIZK proof system for the LWE relation. In turn, this relation makes it possible to express the equality of plaintexts encrypted under different keys in the dual Regev cryptosystem. As an application, we obtain an LWE-based public-key encryption scheme for which we can prove key-dependent message (KDM-CCA2) security under chosen-ciphertext attacks in the standard model.
Expand
◄ Previous Next ►