International Association
for Cryptologic Research

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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 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.

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."

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.

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.

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.

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:

• 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)