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:
14 January 2022
Nadia Heninger
This book chapter outlines techniques for breaking cryptography by taking advantage of implementation mistakes made in practice, with a focus on those that exploit the mathematical structure of the most widely used public-key primitives.
Stefano Tessaro, Chenzhi Zhu
This paper proposes the first practical pairing-free three-move blind signature schemes that (1) are concurrently secure, (2) produce short signatures (i.e., three or four group elements/scalars), and (3) are provably secure either in the generic group model (GGM) or the algebraic group model (AGM) under the (plain or one-more) discrete logarithm assumption (beyond additionally assuming random oracles). We also propose a partially blind version of one of our schemes.
Our schemes do not rely on the hardness of the ROS problem (which can be broken in polynomial time) or of the mROS problem (which admits sub-exponential attacks). The only prior work with these properties is Abe’s signature scheme (EUROCRYPT ’02), which was recently proved to be secure in the AGM by Kastner et al. (PKC ’22), but which also produces signatures twice as long as those from our scheme.
The core of our proofs of security is a new problem, called weighted fractional ROS (WFROS), for which we prove (unconditional) exponential lower bounds.
Keita Emura, Kaisei Kajita, Ryo Nojima, Kazuto Ogawa, Go Ohtake
The Signal protocol is a secure messaging protocol providing end-to-end encrypted asynchronous communication. In this paper, we focus on a method capable of hiding membership information from the viewpoint of non group members in a secure group messaging (SGM) protocol, which we call "membership privacy''. Although Chase et al. (ACM CCS 2020) have considered the same notion, their proposal is an extension of Signal so called "Pairwise Signal'' where a group message is repeatedly sent over individual Signal channels. Thus their protocol is not scalable. In this work, we extend the Cohn-Gordon et al. SGM protocol (ACM CCS 2018), which we call the Asynchronous Ratcheting Trees (ART) protocol, to add membership privacy. We employ a key-private and robust public-key encryption (Abdalla et al., TCC2010/JoC2018) for hiding membership-related values in the setup phase. Furthermore, we concentrate on the fact that a group common key provides anonymity. This fact is used to encrypt membership information in the key update phase. Our extension does not affect the forward secrecy and post-compromise security of the original ART protocol. Although the efficiency of each user in the setup phase is worsened, the setup phase is run only once, and it seems to be acceptable. Any additional cost for key update does not depend on the number of group members (specifically, one encryption and decryption of a symmetric key-encryption scheme and one execution of a key-derivation function for each key update are employed). Therefore, the proposed protocol can add membership privacy to the ART protocol with a quite small overhead.
Dahmun Goudarzi, Thomas Prest, Matthieu Rivain, Damien Vergnaud
The probing security model is widely used to formally prove the security of masking schemes. Whenever a masked implementation can be proven secure in this model with a reasonable \emph{leakage rate}, it is also provably secure in a realistic leakage model known as the \emph{noisy leakage model}. This paper introduces a new framework for the composition of probing-secure circuits. We introduce the security notion of \emph{input-output separation} (IOS) for a refresh gadget. From this notion, one can easily compose gadgets satisfying the classical probing security notion --which does not ensure composability on its own-- to obtain a \emph{region probing secure} circuit. Such a circuit is secure against an adversary placing up to $t$ probes in each gadget composing the circuit, which ensures a tight reduction to the more realistic noisy leakage model. After introducing the notion and proving our composition theorem, we compare our approach to the composition approaches obtained with the (Strong) Non-Interference (S/NI) notions as well as the Probe-Isolating Non-Interference (PINI) notion. We further show that any uniform SNI gadget achieves the IOS security notion, while the converse is not true. We further describe a refresh gadget achieving the IOS property for any linear sharing with a quasilinear complexity $\Theta(n \log n)$ and a $O(1/\log n)$ leakage rate (for an $n$-size sharing). This refresh gadget is a simplified version of the quasilinear SNI refresh gadget proposed by Battistello, Coron, Prouff, and Zeitoun (ePrint~2016). As an application of our composition framework, we revisit the quasilinear-complexity masking scheme of Goudarzi, Joux and Rivain (Asiacrypt~2018). We improve this scheme by generalizing it to any base field (whereas the original proposal only applies to field with $n$th powers of unity) and by taking advantage of our composition approach. We further patch a flaw in the original security proof and extend it from the random probing model to the stronger region probing model. Finally, we present some application of this extended quasilinear masking scheme to AES and MiMC and compare the obtained performances.
Atakan Arslan, Muhammed Ali Bingöl
Elliptic Curve Cryptography (ECC) has been popularly used in RFID authentication protocols to efficiently overcome many security and privacy issues. Even if the strong cryptography primitives of ECC are utilised in the authentication protocols, the schemes are alas far from providing security and privacy properties as desired level. In this paper, we analyze four up-to-minute ECC based RFID authentication schemes proposed by Gasbi et al., Benssalah et al., Kumar et al., and Agrahari and Varma. The authors claim that their schemes provide prominent and important security and privacy requirements. However, we have shown some crucial vulnerabilities of the schemes against their allegations. We attack to Gasbi et al.'s protocol by using transmitted messages in insecure channel and exploiting the message relations which points a specific tag, and show that the scheme does not provide tag anonymity/untraceability, forward and backward security and the scheme has performance problems. Moreover, we demonstrate that Kumar et al., and Agrahari and Varma's schemes do not achieve forward and backward security because the schemes are not designed to eliminate the advantage of an adversary obtaining full knowledge of a tag from by attack definition. We also show that Benssalah et al.'s scheme suffers from tag anonymity/untraceability, forward and backward security when the pseudonym of a tag is transmitted in insecure channel somehow without updating.
Konstantinos Chalkias, Panagiotis Chatzigiannis, Yan Ji
Since the Mt. Gox Bitcoin exchange collapse in 2014, a number of custodial cryptocurrency wallets offer a form of financial solvency proofs to bolster their users' confidence. We identified that despite recent academic works that highlight potential security and privacy vulnerabilities in popular auditability protocols, a number of high-profile exchanges implement these proofs incorrectly, thus defeating their initial purpose. In this paper we provide an overview of \textit{broken} liability proof systems used in production today and suggest fixes, in the hope of closing the gap between theory and practice. Surprisingly, many of these exploitable attacks are due to a) weak cryptographic operations, for instance SHA1 hashing or hash-output truncation to 8 bytes, b) lack of data binding, such as wrong Merkle tree inputs and misuse of public bulletin boards, and c) lack of user-ID uniqueness guarantees.
AMBILI K N, JIMMY JOSE
Authenticated encryption (AE) schemes are a necessity to secure
the physical devices connected to the Internet. Two AE schemes,
TinyJambu and Elephant, are finalists of NIST lightweight
cryptography competition. Another AE scheme, ACORN v3, a
CAESAR competition finalist, has been shown to be particularly
vulnerable against Differential Fault Attack (DFA), even more
than its previous version ACORN v2. TinyJambu is also
susceptible to DFA. An optimized interpolation attack has been
proposed against one instance of Elephant, Delirium, recently.
We propose methods to strengthen these schemes using the
Cellular Automata (CA) and increase their resistance to these
attacks. The Programmable Cellular Automata (PCA) 90-150
is effectively deployed to make these ciphers robust against
DFA. We also provide mathematical analysis of the invigorated
schemes and show that significant improvement is achieved in all
the three enhanced schemes.
AMBILI K N, JIMMY JOSE
The increasing use of resource limited devices with less memory, less computing resource and less power supply, motivates
the adoption of lightweight cryptography to provide security solution. ASCON is a finalist and GIMLI is a round 2 candidate of NIST lightweight cryptography competition. ASCON is
a sponge function based authenticated encryption (AE) scheme
suitable for high performance applications. It is suitable for use
in environments like Internet of Things (IoT) where large number
of very constrained devices communicate with high-end servers.
The drawback is that fault analyses like Statistical Ineffective
fault attack (SIFA) and Sub-Set Fault Analysis (SSFA) are possible. GIMLI is also a sponge function based AE scheme which
is susceptible to SIFA. In this work, we modify ASCON 128a
and GIMLI exploiting the pseudo-random properties of Cellular
Automata (CA) to prevent these attacks. We analyse and show
that these attacks are inapplicable in the reinforced cipher.
AMBILI K N, JIMMY JOSE
Attribute based cryptography enhances the chances of secure communication on large scale. There are several features of attribute based
encryption which have been proposed as different protocols. Most of
these are suitable for access control in large systems like cloud services. Very few protocols focus on reducing the computational overhead
for lower end devices like Internet of Things sensors and actuators.
Hence, it is desirable to have a mix of features in protocols for IoT
architecture. Our protocol enforces accountability of different parties
involved while reducing the computational overhead during decryption
on miniature devices. We prove that our protocol is RCCA-secure in
selective security model and achieve accountability and unlinkability.
AMBILI K N, JIMMY JOSE
Cryptography based on identity and attributes enhances the chance of secure
communication on a large scale. Several attribute-based encryption schemes
achieve different objectives when used in various protocols. Most of these are
suitable for large systems like cloud services. There are a few protocols which
focus on reducing the computational overhead for lower end devices like Internet of
Things sensors and actuators. It is desirable to have a mix of features in protocols
for IoT security architecture. We first propose a scheme to ensure accountability
in CPABE scheme FAME. The protocol is proven CPA-secure with full security
in random oracle model. We also prove its accountability. We also propose a
hybrid protocol that enforces user accountability and outsourced decryption in IoT
systems and achieve full security in replayable chosen ciphertext attack (RCCA)
under random oracle model.
Antonio de la Piedra, Marloes Venema, Greg Alpár
Measuring efficiency is difficult. In the last decades, several works have contributed in the quest to successfully determine and compare the efficiency of pairing-based attribute-based encryption (ABE) schemes. However, many of these works are limited: they use little to no optimizations, or use underlying pairing-friendly elliptic curves that do not provide sufficient security anymore. Hence, using these works to benchmark ABE schemes does not yield accurate results. Furthermore, most ABE design papers focus on the efficiency of one important aspect. For instance, a new scheme may aim to have a fast decryption algorithm. Upon realizing this goal, the designer compares the new scheme with existing ones, demonstrating its dominance in this particular aspect. Although this approach is intuitive and might seem fair, the way in which this comparison is done might be biased. For instance, the schemes that are compared with the new scheme may be optimized with respect to another aspect, and appear in the comparison consequently inferior.
In this work, we present a framework for accurately benchmarking efficiency of ABE: ABE Squared. In particular, we focus on uncovering the multiple layers of optimization that are relevant to the implementation of ABE schemes. Moreover, we focus on making any comparison fairer by considering the influence of the potential design goals any optimizations. On the lowest layer, we consider the available optimized arithmetic provided by state-of-the-art cryptographic libraries. On the higher layers, we consider the choice of elliptic curve, the order of the computations, and the instantiation of the scheme on the chosen curves. In this latter aspect, the way in which a scheme is type converted plays an important role. Additionally, we show that especially the higher-level optimizations are dependent on the goal of the designer, e.g. optimization of the decryption algorithm. To compare schemes more transparently, we develop this framework, in which ABE schemes can be justifiably optimized and compared by taking into account the possible goals of a designer. To meet these goals, we also introduce manual, heuristic type-conversion techniques where existing techniques fall short. Finally, to illustrate the effectiveness of ABE Squared, we implement several schemes and provide all relevant benchmarks. These show that the design goal influences the optimization approaches, which in turn influence the overall efficiency of the implementations. Importantly, these show that the schemes also compare differently than existing works previously suggested.
In this work, we present a framework for accurately benchmarking efficiency of ABE: ABE Squared. In particular, we focus on uncovering the multiple layers of optimization that are relevant to the implementation of ABE schemes. Moreover, we focus on making any comparison fairer by considering the influence of the potential design goals any optimizations. On the lowest layer, we consider the available optimized arithmetic provided by state-of-the-art cryptographic libraries. On the higher layers, we consider the choice of elliptic curve, the order of the computations, and the instantiation of the scheme on the chosen curves. In this latter aspect, the way in which a scheme is type converted plays an important role. Additionally, we show that especially the higher-level optimizations are dependent on the goal of the designer, e.g. optimization of the decryption algorithm. To compare schemes more transparently, we develop this framework, in which ABE schemes can be justifiably optimized and compared by taking into account the possible goals of a designer. To meet these goals, we also introduce manual, heuristic type-conversion techniques where existing techniques fall short. Finally, to illustrate the effectiveness of ABE Squared, we implement several schemes and provide all relevant benchmarks. These show that the design goal influences the optimization approaches, which in turn influence the overall efficiency of the implementations. Importantly, these show that the schemes also compare differently than existing works previously suggested.
Dmitrii Koshelev
This note explains how to guarantee the membership of a point in the prime order subgroup of an elliptic curve (over a finite field) satisfying some moderate conditions. For this purpose, we apply the Tate pairing on the curve, however it is not required to be pairing-friendly. Whenever the cofactor is small, the given approach is more efficient than other known ones, because it needs to compute at most two $n$-th power residue symbols (with small $n$) in the basic field. In particular, we deal with two Legendre symbols for the curve Bandersnatch proposed by the Ethereum Foundation team. Due to recent improvements of Euclidean type constant-time algorithms for the Legendre symbol computation, the new subgroup check is almost free for that curve.
Melissa Azouaoui, Olivier Bronchain, Clément Hoffmann, Yulia Kuzovkova, Tobias Schneider, François-Xavier Standaert
The side-channel cryptanalysis of Post-Quantum (PQ) key encapsulation schemes has been a topic of intense activity over the last years. Many attacks have been put forward: Simple Power Analysis (SPAs) against the re-encryption of schemes using the Fujisaki-Okamoto (FO) transform are known to be very powerful; Differential Power Analysis (DPAs) against the decryption are also possible. Yet, to the best of our knowledge, a systematic and quantitative investigation of their impact for designers is still missing. In this paper, we propose to capture these attacks with shortcut formulas in order to compare their respective strength in function of the noise level. Taking the case of Kyber for illustration, we then evaluate the (high) cost of preventing them with masking and the extent to which different parts of an implementation could benefit from varying security levels. We finally
discuss tweaks to improve the situation and enable a better leveling of the countermeasures. Our conclusions confirm that current solutions for side-channel secure PQ key encapsulation schemes like Kyber are unlikely to be efficient in low-noise settings without (design or countermeasures) improvements.
Vipul Goyal, Justin Raizes, Pratik Soni
Blockchain technology has the potential of transforming cryptography. We study the problem of round-complexity of zero-knowledge, and more broadly, of secure computation in the blockchain-hybrid model, where all parties can access the blockchain as an oracle.
We study zero-knowledge and secure computation through the lens of a new security notion where the simulator is given the ability to ``time-travel” or more accurately, to look into the future states of the blockchain and use this information to perform simulation. Such a time-traveling simulator gives a novel security guarantee of the following form: whatever the adversary could have learnt from an interaction, it could have computed on its own shortly into the future (e.g., a few hours from now).
We exhibit the power of time-traveling simulators by constructing round-efficient protocols in the blockchain-hybrid model. In particular, we construct: 1. Three-round zero-knowledge (ZK) argument for NP with a polynomial-time black-box time-traveling simulator. 2. Three-round secure two-party computation (2PC) for any functionality with a polynomial-time black-box time-traveling simulator for both parties.
In addition to standard cryptographic assumptions, we rely on natural hardness assumptions for Proof-of-Work based blockchains. In comparison, in the plain model, three-round protocols with black-box simulation are impossible, and constructions with non-black-box simulation for ZK require novel cryptographic assumptions while no construction for three-round 2PC is known. Our three-round 2PC result relies on a new, two-round extractable commitment that admits a time-traveling extractor.
We study zero-knowledge and secure computation through the lens of a new security notion where the simulator is given the ability to ``time-travel” or more accurately, to look into the future states of the blockchain and use this information to perform simulation. Such a time-traveling simulator gives a novel security guarantee of the following form: whatever the adversary could have learnt from an interaction, it could have computed on its own shortly into the future (e.g., a few hours from now).
We exhibit the power of time-traveling simulators by constructing round-efficient protocols in the blockchain-hybrid model. In particular, we construct: 1. Three-round zero-knowledge (ZK) argument for NP with a polynomial-time black-box time-traveling simulator. 2. Three-round secure two-party computation (2PC) for any functionality with a polynomial-time black-box time-traveling simulator for both parties.
In addition to standard cryptographic assumptions, we rely on natural hardness assumptions for Proof-of-Work based blockchains. In comparison, in the plain model, three-round protocols with black-box simulation are impossible, and constructions with non-black-box simulation for ZK require novel cryptographic assumptions while no construction for three-round 2PC is known. Our three-round 2PC result relies on a new, two-round extractable commitment that admits a time-traveling extractor.
Varun Madathil, Chris Orsini, Alessandra Scafuro, Daniele Venturi
We present an information-theoretic transformation from any 2-round OT protocol with only game-based security in the presence of malicious adversaries into a 4-round (which is known to be optimal) OT protocol with simulation-based security in the presence of malicious adversaries.
Our transform is the first satisfying all of the following properties at the same time:
– It is in the plain model, without requiring any setup assumption.
– It only makes black-box usage of the underlying OT protocol.
– It is information-theoretic, as it does not require any further cryptographic assumption
(besides the existence of the underlying OT protocol).
Additionally, our transform yields a cubic improvement in communication complexity over the best previously known transformation.
Jonathan Godin, Philippe Lamontagne
Garg, Goldwasser and Vasudevan (Eurocrypt 2020) invented the notion of deletion-compliance to formally model the "right to be forgotten", a concept that confers individuals more control over their digital data. A requirement of deletion-compliance is strong privacy for the deletion requesters since no outside observer must be able to tell if deleted data was ever present in the first place. Naturally, many real world systems where information can flow across users are automatically ruled out.
The main thesis of this paper is that deletion-compliance is a standalone notion, distinct from privacy. We present an alternative definition that meaningfully captures deletion-compliance without any privacy implications. This allows broader class of data collectors to demonstrate compliance to deletion requests and to be paired with various notions of privacy. Our new definition has several appealing properties: - It is implied by the stronger definition of Garg et al. under natural conditions, and is equivalent when we add a privacy requirement. - It is naturally composable with minimal assumptions. - Its requirements are met by data structure implementations that do not reveal the order of operations, a concept known as history-independence.
Along the way, we discuss the many challenges that remain in providing a universal definition of compliance to the "right to be forgotten."
The main thesis of this paper is that deletion-compliance is a standalone notion, distinct from privacy. We present an alternative definition that meaningfully captures deletion-compliance without any privacy implications. This allows broader class of data collectors to demonstrate compliance to deletion requests and to be paired with various notions of privacy. Our new definition has several appealing properties: - It is implied by the stronger definition of Garg et al. under natural conditions, and is equivalent when we add a privacy requirement. - It is naturally composable with minimal assumptions. - Its requirements are met by data structure implementations that do not reveal the order of operations, a concept known as history-independence.
Along the way, we discuss the many challenges that remain in providing a universal definition of compliance to the "right to be forgotten."
Denis Firsov, Sven Laur, Ekaterina Zhuchko
In this work, we perform a formal analysis of definitions of
non-malleability for commitment schemes in the EasyCrypt theorem
prover. There are two distinct formulations of non-malleability found
in the literature: the comparison-based definition and the simulation-
based definition. In this paper, we do a formal analysis of both. We
start by formally proving that the comparison-based definition which was
originally introduced by Laur et al. is unsatisfiable. Also, we propose a
novel formulation of simulation-based non-malleability and show that it
is satisfiable in the Random Oracle Model. Moreover, we validate our
definition by proving that it implies hiding and binding of the commitment
scheme. Finally, we relate the novel definition to the existing definitions
of non-malleability.
Pierre-Alain Fouque, Paul Kirchner, Thomas Pornin, Yang Yu
We present $\BAT$ -- an IND-CCA secure key encapsulation mechanism (KEM) that is based on NTRU but follows an encryption/decryption paradigm distinct from classical NTRU KEMs. It demonstrates a new approach of decrypting NTRU ciphertext since its introduction 25 years ago. Instead of introducing an artificial masking parameter $p$ to decrypt the ciphertext, we use 2 linear equations in 2 unknowns to recover the message and the error. The encryption process is therefore close to the GGH scheme. However, since the secret key is now a short basis (not a vector), we need to modify the decryption algorithm and we present a new NTRU decoder. Thanks to the improved decoder, our scheme works with a smaller modulus and yields shorter ciphertexts, smaller than RSA-4096 for 128-bit classical security with comparable public-key size and much faster than RSA or even ECC. Meanwhile, the encryption and decryption are still simple and fast in spite of the complicated key generation. Overall, our KEM has more compact parameters than all current lattice-based schemes and a practical efficiency.
Moreover, due to the similar key pair structure, $\BAT$ can be of special interest in some applications using Falcon signature that is also the most compact signature in the round 3 of the NIST post-quantum cryptography standardization. However, different from Falcon, our KEM does not rely on floating-point arithmetic and can be fully implemented over the integers.
Jinyu Lu, Guoqiang Liu, Yunwen Liu, Bing Sun, Chao Li, Li Liu
In CRYPTO 2019, Gohr made a pioneering attempt, and successfully applied deep learning to the differential cryptanalysis against NSA block cipher SPECK32/64, achieving higher accuracy than the pure differential distinguishers. By its very nature, mining effective features in data plays a crucial role in data-driven deep learning. In this paper, in addition to considering the integrity of the information from the training data of the ciphertext pair, domain knowledge about the structure of differential cryptanalysis is also considered into the training process of deep learning to improve the performance. Besides, based on the SAT/SMT solvers, we find other high probability compatible differential characteristics which effectively improve the performance compared with previous work. We build neural distinguishers (NDs) and related-key neural distinguishers (RKNDs) against Simon and Simeck. The ND and RKND for SIMON32/64 reach 11-, 11-round with an accuracy of 59.55% and 97.90%, respectively. For SIMON64/128, the ND achieve an accuracy of 60.32% in 13-round, while it is 95.49% for the RKND. For SIMECK32/64, ND and RKND of 11-, 14-round are obtained, reaching an accuracy of 63.32% and 87.06%, respectively. And we build 17-round ND and 21-round RKND for SIMECK64/128 with an accuracy of 64.24% and 62.96%, respectively. Currently, these are the longest (related-key) neural distinguishers with higher accuracy for SIMON32/64, SIMON64/128, SIMECK32/64 and SIMECK64/128.
University of Tübingen, Department of Computer Science; Tübingen, Germany
Medical Data Privacy and Privacy-Preserving ML on Healthcare Data (MDPPML) group at the University of Tübingen is looking for motivated Ph.D. students and Postdocs in the area of Privacy Enhancing Technologies.
Research Topics: Development and analysis of cryptography-based privacy-preserving solutions for real-world healthcare problems. Topics of interest include (but are not limited to): privacy-preserving machine learning, genomic privacy, medical privacy as well as foundations for real-world cryptography.
Your profile:
Research Topics: Development and analysis of cryptography-based privacy-preserving solutions for real-world healthcare problems. Topics of interest include (but are not limited to): privacy-preserving machine learning, genomic privacy, medical privacy as well as foundations for real-world cryptography.
Your profile:
- Completed Master's degree (or equivalent) at a top university with excellent grades in computer science, or a similar area.
- Extensive knowledge in applied cryptography/security and machine learning.
- Very good software development skills.
- Knowledge of cryptographic protocols (ideally MPC).
- Knowledge of bioinformatics or genomics is plus.
- Self-motivated, reliable, creative, can work independently and want to do excellent research.
Closing date for applications:
Contact: Dr. Mete Akgün (mete.akguen@uni-tuebingen.de)