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:
27 March 2021
Subhadeep Banik, Andrea Caforio, Takanori Isobe, Fukang Liu, Willi Meier, Kosei Sakamoto, Santanu Sarkar
It has been common knowledge that for a stream cipher to be secure against generic TMD tradeoff attacks, the size of its internal state in bits needs to be at least twice the size of the length of its secret key. In FSE 2015, Armknecht and Mikhalev however proposed the stream cipher Sprout with a Grain-like architecture, whose internal state was equal in size with its secret key and yet resistant against TMD attacks. Although Sprout had other weaknesses, it germinated a sequence of stream cipher designs like Lizard and Plantlet with short internal states. Both these designs have had cryptanalytic results reported against them. In this paper, we propose the stream cipher Atom that has an internal state of 159 bits and offers a security of 128 bits. Atom uses two key filters simultaneously to thwart certain cryptanalytic attacks that have been recently reported against keystream generators. In addition, we found that our design is one of the smallest stream ciphers that offers this security level, and we prove in this paper that Atom resists all the attacks that have been proposed against stream ciphers so far in literature. On the face of it, Atom also builds on the basic structure of the Grain family of stream ciphers. However, we try to prove that by including the additional key filter in the architecture of Atom we can make it immune to all cryptanalytic advances proposed against stream ciphers in recent cryptographic literature.
Christoph Dobraunig, Bart Mennink
Side-channel attacks are a threat to secrets stored on a device, especially if an adversary has physical access to the device. As an effect of this, countermeasures against such attacks for cryptographic algorithms are a well-researched topic. In this work, we deviate from the study of cryptographic algorithms and instead focus on the side-channel protection of a much more basic operation, the comparison of a known attacker-controlled value with a secret one. Comparisons sensitive to side-channel leakage occur in tag comparisons during the verification of message authentication codes (MACs) or authenticated encryption, but are typically omitted in security analyses. Besides, also comparisons performed as part of fault countermeasures might be sensitive to side-channel attacks. In this work, we present a formal analysis on comparing values in a leakage resilient manner by utilizing cryptographic building blocks that are typically part of an implementation anyway. Our results indicate that there is no need to invest additional resources into implementing a protected comparison operation itself if a sufficiently protected implementation of a public cryptographic permutation, or a (tweakable) block cipher, is already available. We complement our contribution by applying our findings to the SuKS message authentication code used by lightweight authenticated encryption scheme ISAP, and to the classical Hash-then-PRF construction.
Hayato Kimura, Keita Emura, Takanori Isobe, Ryoma Ito, Kazuto Ogawa, Toshihiro Ohigashi
Cryptanalysis of symmetric-key ciphers, e.g., linear/differential cryptanalysis, requires an adversary to know the internal structures of the targeted ciphers. On the other hand, deep learning-based cryptanalysis has attracted significant attention because the adversary is not assumed to have knowledge of the targeted ciphers except the interfaces of algorithms. Such a blackbox attack is extremely strong; thus we must design symmetric-key ciphers that are secure against deep learning-based cryptanalysis. However, previous attacks do not clarify what features or internal structures affect success probabilities; therefore it is difficult to employ the results of such attacks to design deep learning-resistant symmetric-key ciphers. In this paper, we focus on toy SPN block ciphers (small PRESENT and small AES) and propose deep learning-based output prediction attacks. Due to its small internal structures, we can build learning models by employing the maximum number of plaintext/ciphertext pairs, and we can precisely calculate the rounds in which full diffusion occurs. We demonstrate the following: (1) our attacks work against a similar number of rounds attacked by linear/differential cryptanalysis, (2) our attacks realize output predictions (precisely plaintext recovery and ciphertext prediction) that are much stronger than distinguishing attacks, and (3) swapping the order of components or replacement components affects the success probabilities of the attacks. It is particularly worth noting that swapping/replacement does not affect the success probabilities of linear/differential cryptanalysis. We expect that our results will be an important stepping stone in the design of deep learning-resistant symmetric key ciphers.
Yupu Hu, Xingting Dong, Baocang Wang
Branching program is an important component of indistinguishability obfuscation (IO) schemes, its size greatly influences the efficiencies of corresponding IO schemes. There are two major candidates of branching programs, Bar86 branching program and IK00 branching program. Bar86 branching program was shown to efficiently recognize NC$^1$ circuits. In specific, a Boolean circuit of depth $d$ can be recognized by a Bar86 branching program of length not larger than $4^d$ (Therefore of size not larger than $5^2 \times 4^d$).
In this short paper we present similar result about IK00 branching program. We show that IK00 branching program efficiently recognizes NC$^1$ circuits, that is, a Boolean circuit of depth $d$ can be recognized by an IK00 branching program of size not larger than $(n+1) \times 4^d$, where $n$ is input length.
Our result may be a negative evidence for IK00 branching program to efficiently recognize polynomial-time computable functions.
Alberto Garoffolo, Dmytro Kaidalov, Roman Oliynykov
In our previous paper we introduced a novel SNARK-based construction, called Zendoo, that allows Bitcoin-like blockchains to create and communicate with sidechains of different types without knowing their internal structure. We also introduced a specific construction, called Latus, allowing creation of fully verifiable sidechains. But in there we omitted a detailed description of an incentive scheme for Latus that is an essential element of a real decentralized system. This paper fills the gap by introducing details of the incentive scheme for the Latus sidechain. Represented ideas can also be adopted by other SNARK-based blockchains to incentivize decentralized proofs creation.
Thales Bandiera Paiva, Routo Terada
In 1989, Shamir presented an efficient identification scheme (IDS) based on the permuted kernel problem (PKP). After 21 years, PKP was generalized by Lampe and Patarin, who were able to build an IDS similar to Shamir's one, but using the binary field. This binary variant presented some interesting advantages over Shamir's original IDS, such as reduced number of operations and inherently resistance against side-channel attacks. In the security analysis, considering the best attacks against the original PKP, the authors concluded that none of these existing attacks appeared to have a significant advantage when attacking the binary variant. In this paper, we propose the first attack that targets the binary PKP. The attack is analyzed in detail, and its practical performance is compared with our theoretical models. For the proposed parameters originally targeting 79 and 98 bits of security, our attack can recover about 100% of all keys using less than $2^{63}$ and $2^{77}$ operations, respectively.
Carmine Abate, Philipp G. Haselwarter, Exequiel Rivas, Antoine Van Muylder, Théo Winterhalter, Catalin Hritcu, Kenji Maillard, Bas Spitters
State-separating proofs (SSP) is a recent methodology for structuring game-based cryptographic proofs in a modular way. While very promising, this methodology was previously not fully formalized and came with little tool support. We address this by introducing SSProve, the first general verification framework for machine-checked state-separating proofs. SSProve combines high-level modular proofs about composed protocols, as proposed in SSP, with a probabilistic relational program logic for formalizing the lower-level details, which together enable constructing fully machine-checked crypto proofs in the Coq proof assistant. Moreover, SSProve is itself formalized in Coq, including the algebraic laws of SSP, the soundness of the program logic, and the connection between these two verification styles.
Alessandro Barenghi, Jean-Francois Biasse, Edoardo Persichetti, Paolo Santini
Code-based cryptographic schemes are highly regarded among the quantum-safe alternatives to current standards. Yet, designing code-based signatures using traditional methods has always been a challenging task, and current proposals are still far from the target set by other post-quantum primitives (e.g. lattice-based). In this paper, we revisit a recent work using an innovative approach for signing, based on the hardness of the code equivalence problem. We introduce some optimizations and provide a security analysis for all variants considered. We then show that the new parameters produce instances of practical interest.
Harishma Boyapally, Urbi Chatterjee, Debdeep Mukhopadhyay
Recently, a light-weight authenticated key-exchange (AKE) scheme has been proposed. The scheme provides mutual authentication. It is asymmetric in nature by delegating complex cryptographic operations to resource-equipped servers, and carefully managing the workload on resource-constrained Smart meter nodes by using Physically Unclonable Functions. The prototype Smart meter built using commercial-off-the-shelf products is enabled with a low-cost countermeasure against load-modification attacks, which goes side-by-side with the proposed protocol. An attack against this AKE scheme has been recently proposed claiming that the server can be breached to mount spoofing attacks. It relies on the assumption that the result of an attack against authenticated key-exchange protocol is determined before the attacker learns the session key. In this short paper, we discuss the attacks validity and describe the misinterpretation of the AKE protocols security definition.
Ryo Nishimaki, Takashi Yamakawa
Broadbent and Islam (TCC '20) proposed a quantum cryptographic primitive called quantum encryption with certified deletion. In this primitive, a receiver in possession of a quantum ciphertext can generate a classical certificate that the encrypted message is deleted. Though they proved that their construction is information theoretically secure, a drawback is that the construction is limited to the setting of one-time symmetric key encryption (SKE) where a sender and receiver have to share a common key in advance and the key can be used only once.
In this paper, we construct a (reusable-key) public key encryption (PKE) and attribute-based encryption (ABE) with certified deletion. Our PKE with certified deletion is constructed assuming the existence of IND-CPA secure PKE, and our ABE with certified deletion is constructed assuming the existence of indistinguishability obfuscation and one-way function.
Onur Gunlu
We extend a basic key agreement model with a hidden identifier source to a multi-user model with joint secrecy and privacy constraints over all entities that do not trust each other. Different entities that use different measurements of the same remote source through broadcast channels (BCs) to agree on mutually-independent local secret keys are considered. This model is the proper multi-user extension of the basic model since the encoder and decoder pairs are not assumed to trust other pairs, unlike assumed in the literature. Strong secrecy constraints imposed jointly on all secret keys, which is more stringent than separate secrecy leakage constraints for each secret key considered in the literature, are satisfied. Inner bounds for maximum key rate, and minimum privacy-leakage and storage rates are proposed for any finite number of entities. Inner and outer bounds for degraded and less-noisy BCs are given to illustrate cases with strong privacy. A multi-enrollment model that is used for common physical unclonable functions (PUFs) is also considered to establish inner and outer bounds for key-leakage-storage regions that differ only in the Markov chains imposed. For this special case, the encoder and decoder measurement channels have the same channel transition matrix and secrecy leakage is measured for each secret key separately. We illustrate cases for which it is useful to have multiple enrollments as compared to a single enrollment and vice versa.
Ao Liu, Yun Lu, Lirong Xia, Vassilis Zikas
Differential privacy has been widely applied to provide privacy guarantees by adding random noise to the function output. However, it inevitably fails in many high-stakes voting scenarios, where voting rules are required to be deterministic.
In this work, we present the first framework for answering the question: ``How private are commonly-used voting rules?" Our answers are two-fold. First, we show that deterministic voting rules provide sufficient privacy in the sense of distributional differential privacy (DDP). We show that assuming the adversarial observer has uncertainty about individual votes, even publishing the histogram of votes achieves good DDP.
Second, we introduce the notion of exact privacy to compare the privacy preserved in various commonly-studied voting rules, and obtain dichotomy theorems of exact DDP within a large subset of voting rules called generalized scoring rules.
Thomas Haines, Peter Roenne
There is a difference between a system having no known attacks and the system being secure---as cryptographers know all too well. Once we begin talking about the implementations of systems this issue becomes even more prominent since the amount of material which needs to be scrutinised skyrockets. Historically, lack of transparency and low standards for e-voting system implementations have resulted in a culture where open source code is seen as a gold standard; however, this ignores the issue of the comprehensibility of that code.
In this work we make concrete empirical recommendations based on our, and others, experiences and findings from examining the source code of e-voting systems. We highlight that any solution used for significant elections should be well designed, carefully analysed, deftly built, accurately documented and expertly maintained. Until e-voting system implementations are clear, comprehensible, and open to public scrutiny security standards are unlikely to improve.
In this work we make concrete empirical recommendations based on our, and others, experiences and findings from examining the source code of e-voting systems. We highlight that any solution used for significant elections should be well designed, carefully analysed, deftly built, accurately documented and expertly maintained. Until e-voting system implementations are clear, comprehensible, and open to public scrutiny security standards are unlikely to improve.
Subhadeep Banik, Takanori Isobe, Fukang Liu, Kazuhiko Minematsu, Kosei Sakamoto
We present Orthros, a 128-bit block pseudorandom function.
It is designed with primary focus on latency of fully unrolled circuits. For this purpose, we adopt a parallel structure comprising two keyed permutations.
The round function of each permutation is similar to Midori, a low-energy block cipher, however we thoroughly revise it to reduce latency, and introduce different rounds to significantly improve cryptographic strength in a small number of rounds.
We provide a comprehensive, dedicated security analysis.
For hardware implementation, Orthros achieves the lowest latency among the state-of-the-art low-latency primitives.
For example, using the STM 90nm library, Orthros achieves a minimum latency of around 2.4 ns, while other constructions like PRINCE, Midori-128 and QARMA_{9}-128-\sigma_{0} achieve 2.56 ns, 4.10 ns, 4.38 ns respectively.
Durba Chatterjee, Harishma Boyapally, Sikhar Patranabis, Urbi Chatterjee, Debdeep Mukhopadhyay, Aritra Hazra
In this paper, we propose a novel primitive named Physically Related Function (PReF) which are devices with hardware roots of trust. It enables secure key-exchange with no pre-established/embedded secret keys. This work is motivated by the need to perform key-exchange between lightweight resource-constrained devices. We present a proof-of-concept realization of our contributions in hardware using FPGAs.
Marshall Ball, Elette Boyle, Ran Cohen, Lisa Kohl, Tal Malkin, Pierre Meyer, Tal Moran
Topology-hiding broadcast (THB) enables parties communicating over an incomplete network to broadcast messages while hiding the topology from within a given class of graphs. THB is a central tool underlying general topology-hiding secure computation (THC) (Moran et al. TCC15). Although broadcast is a privacy-free task, it was recently shown that THB for certain graph classes necessitates computational assumptions, even in the semi-honest setting, and even given a single corrupted party.
In this work we investigate the minimal assumptions required for topology-hiding communication: both Broadcast or Anonymous Broadcast (where the broadcasters identity is hidden). We develop new techniques that yield a variety of necessary and sufficient conditions for the feasibility of THB/THAB in different cryptographic settings: information theoretic, given existence of key agreement, and given existence of oblivious transfer. Our results show that feasibility can depend on various properties of the graph class, such as connectivity, and highlight the role of different properties of topology when kept hidden, including direction, distance, and/or distance-of-neighbors to the broadcaster.
An interesting corollary of our results is a dichotomy for THC with a public number of at least three parties, secure against one corruption: information-theoretic feasibility if all graphs are 2-connected; necessity and sufficiency of key agreement otherwise.
In this work we investigate the minimal assumptions required for topology-hiding communication: both Broadcast or Anonymous Broadcast (where the broadcasters identity is hidden). We develop new techniques that yield a variety of necessary and sufficient conditions for the feasibility of THB/THAB in different cryptographic settings: information theoretic, given existence of key agreement, and given existence of oblivious transfer. Our results show that feasibility can depend on various properties of the graph class, such as connectivity, and highlight the role of different properties of topology when kept hidden, including direction, distance, and/or distance-of-neighbors to the broadcaster.
An interesting corollary of our results is a dichotomy for THC with a public number of at least three parties, secure against one corruption: information-theoretic feasibility if all graphs are 2-connected; necessity and sufficiency of key agreement otherwise.
Christian Majenz, Chanelle Matadah Manfouo, Maris Ozols
Quantum-access security, where an attacker is granted superposition access to secret-keyed functionalities, is a fundamental security model and its study has inspired results in post-quantum security. We revisit, and fill a gap in, the quantum-access security analysis of the Lamport one-time signature scheme (OTS) in the quantum random oracle model (QROM) by Alagic et al.~(Eurocrypt 2020). We then go on to generalize the technique to the Winternitz OTS. Along the way, we develop a tool for the analysis of hash chains in the QROM based on the superposition oracle technique by Zhandry (Crypto 2019) which might be of independent interest.
Hossein Fereidooni, Samuel Marchal, Markus Miettinen, Azalia Mirhoseini, Helen Möllering, Thien Duc Nguyen, Phillip Rieger, Ahmad Reza Sadeghi, Thomas Schneider, Hossein Yalame, Shaza Zeitouni
Federated learning (FL) is an emerging distributed machine learning paradigm which addresses critical data privacy issues in machine learning by enabling clients, using an aggregation server (aggregator), to jointly train a global model without revealing their training data. Thereby, it improves not only privacy but is also efficient as it uses the computation power and data of potentially millions of clients for training in parallel.
However, FL is vulnerable to so-called inference attacks by malicious aggregators which can infer information about clients data from their model updates. Secure aggregation restricts the central aggregator to only learn the summation or average of the updates of clients. Unfortunately, existing protocols for secure aggregation for FL suffer from high communication, computation, and many communication rounds.
In this work, we present SAFELearn, a generic design for efficient private FL systems that protects against inference attacks that have to analyze individual clients' model updates using secure aggregation. It is flexibly adaptable to the efficiency and security requirements of various FL applications and can be instantiated with MPC or FHE. In contrast to previous works, we only need 2 rounds of communication in each training iteration, do not use any expensive cryptographic primitives on clients, tolerate dropouts, and do not rely on a trusted third party. We implement and benchmark an instantiation of our generic design with secure two-party computation. Our implementation aggregates 500~models with more than 300K parameters in less than 0.5 seconds.
However, FL is vulnerable to so-called inference attacks by malicious aggregators which can infer information about clients data from their model updates. Secure aggregation restricts the central aggregator to only learn the summation or average of the updates of clients. Unfortunately, existing protocols for secure aggregation for FL suffer from high communication, computation, and many communication rounds.
In this work, we present SAFELearn, a generic design for efficient private FL systems that protects against inference attacks that have to analyze individual clients' model updates using secure aggregation. It is flexibly adaptable to the efficiency and security requirements of various FL applications and can be instantiated with MPC or FHE. In contrast to previous works, we only need 2 rounds of communication in each training iteration, do not use any expensive cryptographic primitives on clients, tolerate dropouts, and do not rely on a trusted third party. We implement and benchmark an instantiation of our generic design with secure two-party computation. Our implementation aggregates 500~models with more than 300K parameters in less than 0.5 seconds.
Yasufumi Hashimoto
The problem of Blockwise Isomorphism of Polynomials was introduced by Santoso at PQCrypto 2020 as a generalization of the problem of Isomorphism of Polynomials. In the present paper, we describe how to solve this problem with circulant matrices, used in Santoso's Diffie-Hellman type encryption scheme.
Alex Biryukov, Gleb Naumenko, Sergei Tikhomirov
The Lightning Network (LN) is a prominent scalability solution for Bitcoin that allows for low-latency off-chain payments through a network of payment channels. LN users lock bitcoins into collaboratively owned addresses and redistribute the ownership of these funds without confirming each transfer on-chain. The LN introduces new privacy challenges.
In this paper, we focus on channel balance probing. We propose a new model of the LN that accounts for parallel and unidirectional channels, which has not been done in prior work. We describe a probing algorithm that accurately updates the attacker's balance estimates without the need to directly connect to victims. We introduce an uncertainty-based metric to measure the attacker's information gain.
We implement the first probing-focused LN simulator and suggest several countermeasures against general probing (implemented considering parallel channels). We evaluate these techniques using the simulator, as well as experiments on the real network.
According to our simulations, an attacker can infer up to $80\%$~information regarding channel balances spending $\approx 20$~seconds per channel. The suggested countermeasures limit the attacker's gain at $30\%$, while also increasing the attack time by 2-4x.
In addition, we describe sophisticated attack techniques that combine fee-probing and channel jamming to get precise access to individual channel balances inside a hop, and test them against the real network.
Finally, we discuss payment flows and their concealment.
In this paper, we focus on channel balance probing. We propose a new model of the LN that accounts for parallel and unidirectional channels, which has not been done in prior work. We describe a probing algorithm that accurately updates the attacker's balance estimates without the need to directly connect to victims. We introduce an uncertainty-based metric to measure the attacker's information gain.
We implement the first probing-focused LN simulator and suggest several countermeasures against general probing (implemented considering parallel channels). We evaluate these techniques using the simulator, as well as experiments on the real network.
According to our simulations, an attacker can infer up to $80\%$~information regarding channel balances spending $\approx 20$~seconds per channel. The suggested countermeasures limit the attacker's gain at $30\%$, while also increasing the attack time by 2-4x.
In addition, we describe sophisticated attack techniques that combine fee-probing and channel jamming to get precise access to individual channel balances inside a hop, and test them against the real network.
Finally, we discuss payment flows and their concealment.