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:
19 January 2023
Nicu Neculache, Vlad-Andrei Petcu, Emil Simion
Voting mechanisms allow the expression of the elections by a democratic approach. Any voting scheme must ensure, preferably in an efficient way, a series of safety measures such as confidentiality, integrity and anonymity. Since the 1980s, the concept of electronic voting became more and more of interest, being an advantageous or even necessary alternative for the organization of secure elections. In this paper, we give an overview for the e-voting mechanisms together with the security features they must fulfill. Then we focus on the blind signature paradigm, specifically on the Pairing Free Identity-Based Blind Signature Scheme with Message Recovery (PF-IDBS-MR). Our goal is to give a better understanding on the PF-IDBS-MR scheme by offering an adaptation on the standard voting protocol’s phases. More important, we analyze if the general security requirements and the recommendations proposed by the Council of Europe are met by the scheme.
Ashley Fraser, Lydia Garms, Elizabeth A. Quaglia
We introduce incoercible digital signature schemes, a variant of a standard digital signature. Incoercible signatures enable signers, when coerced to produce a signature for a message chosen by an attacker, to generate fake signatures that are indistinguishable from real signatures, even if the signer is compelled to reveal their full history (including their secret signing keys and any randomness used to produce keys/signatures) to the attacker. Additionally, we introduce an authenticator that can detect fake signatures, which ensures that coercion is identified. We present a formal security model for incoercible signature schemes that comprises an established definition of unforgeability and captures new notions of weak receipt-freeness, strong receipt-freeness and coercion-resistance. We demonstrate that an incoercible signature scheme can be viewed as a transformation of any generic signature scheme. Indeed, we present two incoercible signature scheme constructions that are built from a standard signature scheme and a sender-deniable encryption scheme. We prove that our first construction satisfies coercion-resistance, and our second satisfies strong receipt-freeness. We conclude by presenting an extension to our security model: we show that our security model can be extended to the designated verifier signature scheme setting in an intuitive way as the designated verifier can assume the role of the authenticator and detect coercion during the verification process.
Weizhao Jin, Erik Kline, T. K. Satish Kumar, Lincoln Thurlow, Srivatsan Ravi
In practical operational networks, it is essential to validate path integrity, especially when untrusted intermediate nodes are from numerous network infrastructures operated by several network authorities. Current solutions often reveal the entire path to all parties involved, which may potentially expose the network structures to malicious intermediate attackers. Additionally, there is no prior work done to provide a systematic approach combining the complete lifecycle of packet delivery, i.e., path slicing, path validation and path rerouting, leaving these highly-intertwined modules completely separated. In this work, we present a decentralized privacy-preserving path validation system ?3? that integrates our novel path validation protocol with an efficient path slicing algorithm and a malice-resilient path rerouting mechanism. Specifically, leveraging Non-Interactive Zero-Knowledge proofs, our path validation protocol XOR-Hash-NIZK protects the packet delivery tasks against information leakage about multi-hop paths and potentially the underlying network infrastructures. We implemented and evaluated our system on a state-of-the-art 5G Dispersed Computing Testbed simulating a multi-authority network. Our results show that while preserving the privacy of paths and nodes and enhancing the security of network service, our system optimizes the performance trade-off between network service quality and security/privacy.
Sebastian Faust, Carmit Hazay, David Kretzler, Benjamin Schlosser
An important research direction in secure multi-party computation (MPC) is to improve the efficiency of the protocol. One idea that has recently received attention is to consider a slightly weaker security model than full malicious security -- the so-called setting of $\textit{covert security}$. In covert security, the adversary may cheat but only is detected with certain probability. Several works in covert security consider the offline/online approach, where during a costly offline phase correlated randomness is computed, which is consumed in a fast online phase. State-of-the-art protocols focus on improving the efficiency by using a covert offline phase, but ignore the online phase. In particular, the online phase is usually assumed to guarantee security against malicious adversaries. In this work, we take a fresh look at the offline/online paradigm in the covert security setting. Our main insight is that by weakening the security of the online phase from malicious to covert, we can gain significant efficiency improvements during the offline phase. Concretely, we demonstrate our technique by applying it to the online phase of the well-known TinyOT protocol (Nielsen et al., CRYPTO '12). The main observation is that by reducing the MAC length in the online phase of TinyOT to $t$ bits, we can guarantee covert security with a detection probability of $1- \frac{1}{2^t}$. Since the computation carried out by the offline phase depends on the MAC length, shorter MACs result in a more efficient offline phase and thus speed up the overall computation. Our evaluation shows that our approach reduces the communication complexity of the offline protocol by at least 35% for a detection rate up to $\frac{7}{8}$. In addition, we present a new generic composition result for analyzing the security of online/offline protocols in terms of concrete security.
Theophilus Agama
Applying the pothole method on the factors of numbers of the form $2^n-1$, we prove the inequality $$\iota(2^n-1)\leq n-1+\iota(n)$$ where $\iota(n)$ denotes the length of the shortest addition chain producing $n$.
Alexandre Berzati, Andersson Calle Viera, Maya Chartouni, Steven Madec, Damien Vergnaud, David Vigilant
This paper presents a new profiling side-channel attack on the signature scheme CRYSTALS-Dilithium, which has been selected by the NIST as the new primary standard for quantum-safe digital signatures. This algorithm has a constant-time implementation with consideration for side-channel resilience. However, it does not protect against attacks that exploit intermediate data leakage. We exploit such a leakage on a vector generated during the signing process and whose costly protection by masking is a matter of debate. We design a template attack that enables us to efficiently predict whether a given coefficient in one coordinate of this vector is zero or not. Once this value has been completely reconstructed, one can recover, using linear algebra methods, part of the secret key that is sufficient to produce universal forgeries. While our paper deeply discusses the theoretical attack path, it also demonstrates the validity of the assumption regarding the required leakage model, from practical experiments with the reference implementation on an ARM Cortex-M4.
Hao Yang, Shiyu Shen, Wangchen Dai, Lu Zhou, Zhe Liu, Yunlei Zhao
Homomorphic encryption (HE) is one of the most promising techniques for privacy-preserving computations, especially the word-wise HE schemes that allow batched computations over ciphertexts. However, the high computational overhead hinders the deployment of HE in real-word applications. The GPUs are often used to accelerate the execution in such scenarios, while the performance of different HE schemes on the same GPU platform is still absent.
In this work, we implement three word-wise HE schemes BGV, BFV, and CKKS on GPU, with both theoretical and engineering optimizations. We optimize the hybrid key-switching technique, reducing the computational and memory overhead of this procedure. We explore several kernel fusing strategies to reuse data, which reduces the memory access and IO latency, and improves the overall performance. By comparing with the state-of-the-art works, we demonstrate the effectiveness of our implementation.
Meanwhile, we present a framework that finely integrates our implementation of the three schemes, covering almost all scheme functions and homomorphic operations. We optimize the management of pre-computation, RNS bases and memory in the framework, to provide efficient and low-latency data access and transfer. Based on this framework, we provide a thorough benchmark of the three schemes, which can serve as a reference for scheme selection and implementation in constructing privacy-preserving applications.
Marc Joye
On-line/off-line encryption schemes enable the fast encryption of a message from a pre-computed coupon. The paradigm was put forward in the case of digital signatures.
This work introduces a compact public-key additively homomorphic encryption scheme. The scheme is semantically secure under the decisional composite residuosity (DCR) assumption. Compared to Paillier cryptosystem, it merely requires one or two integer additions in the on-line phase and no increase in the ciphertext size. This work also introduces a compact on-line/off-line trapdoor commitment scheme featuring the same fast on-line phase. Finally, applications to chameleon signatures are presented.
Raja Adhithan RadhaKrishnan
The goals of cryptography are achieved using mathematically strong crypto-algorithms, which are adopted for securing data and
communication. Even though the algorithms are mathematically
secure, the implementation of these algorithms may be vulnerable to
side-channel attacks such as timing and power analysis attacks. One
of the effective countermeasures against such attacks is Threshold Implementation(TI). However, TI realization in crypto-device introduces
hardware complexity, so it shall not be suitable for resource-constrained
devices. Therefore, there is a need for efficient and effective countermeasure techniques for resource-constrained devices. In this work, we propose a lightweight countermeasure using an Arbiter Physical Unclonable Function (A-PUF) to obfuscate intermediate values in the register for rolled and unrolled implementation of Advanced Encryption Standard (AES). The countermeasure is realized in rolled (iterative) implementation of AES in a 65nm Field Programmable Gate Array (FPGA). We have analyzed the security strength and area of the obfuscated AES using A-PUF and compared it with conventional (rolled AES) and masked TI of AES. Further, we have illustrated the effectiveness of pre-charge and neutralizing countermeasures to strengthen the side channel resistance. We have discussed the complexity of mounting a side channel and modeling attacks on obfuscated AES using A-PUF.
Jose Contreras
This study presents a proof-of-concept for a cognitive-based authentication system that uses an individual's writing style as a unique identifier to grant access to a system. A machine learning SVM model was trained on these features to distinguish between texts generated by each user. The stylometric feature vector was then used as an input to a key derivation function to generate a unique key for each user. The experiment results showed that the developed system achieved up to 87.42\% accuracy in classifying texts as written, and the generated keys were found to be secure and unique. We explore the intersection between natural intelligence, cognitive science, and cryptography, intending to develop a cognitive cryptography system. The proposed system utilizes behavioral features from linguistic-biometric data to detect and classify users through stylometry. This information is then used to generate a cryptographic key for authentication, providing a new level of security in access control. The field of cognitive cryptography is relatively new and has yet to be fully explored, making this research particularly relevant and essential. Through our study, we aim to contribute to understanding the potential of cognitive cryptography and its potential applications in securing access to sensitive information.
Manuela Horduna, Simona-Maria Lăzărescu, Emil Simion
Ransomware is a malware that employs encryption to hold a victim's data, causing irreparable loss and monetary incentives to individuals or business organizations.
The occurrence of ransomware attacks has been increasing significantly and as the attackers are investing more creativity and inventiveness into their threats, the struggle of fighting against ill-themed activities has become more difficult and even time and energy-draining.
Therefore, recent researches try to shed some light on combining machine learning with defense mechanisms for detecting this type of malware.
Machine learning allows anti-ransomware systems to become more accurate at predicting outcomes or behaviors of the attacks and is vastly used in the advanced research of cybersecurity.
In this paper we analyze how machine learning can improve malware recognition in order to stand against critical security issues, giving a brief, yet comprehensive overview of this thriving topic in order to facilitate future research. We also briefly present the most important events of 2022 in terms of ransomware attacks, providing details about the ransoms demanded.
Mahimna Kelkar, Kushal Babel, Philip Daian, James Austgen, Vitalik Buterin, Ari Juels
Most cryptographic protocols model a player’s knowledge of secrets in a simple way. Informally, the player knows a secret in the sense that she can directly furnish it as a (private) input to a protocol, e.g., to digitally sign a message.
The growing availability of Trusted Execution Environments (TEEs) and secure multiparty computation, however, undermines this model of knowledge. Such tools can encumber a secret sk and permit a chosen player to access sk conditionally, without actually knowing sk. By permitting selective access to sk by an adversary, encumbrance of secrets can enable vote-selling in cryptographic voting schemes, illegal sale of credentials for online services, and erosion of deniability in anonymous messaging systems.
Unfortunately, existing proof-of-knowledge protocols fail to demonstrate that a secret is unencumbered. We therefore introduce and formalize a new notion called complete knowledge (CK). A proof (or argument) of CK shows that a prover does not just know a secret, but also has fully unencumbered knowledge, i.e., unrestricted ability to use the secret.
We introduce two practical CK schemes that use special-purpose hardware, specifically TEEs and off-the-shelf mining ASICs. We prove the security of these schemes and explore their practical deployment with a complete, end-to-end prototype that supports both. We show how CK can address encumbrance attacks identified in previous work. Finally, we introduce two new applications enabled by CK that involve proving ownership of blockchain assets.
The growing availability of Trusted Execution Environments (TEEs) and secure multiparty computation, however, undermines this model of knowledge. Such tools can encumber a secret sk and permit a chosen player to access sk conditionally, without actually knowing sk. By permitting selective access to sk by an adversary, encumbrance of secrets can enable vote-selling in cryptographic voting schemes, illegal sale of credentials for online services, and erosion of deniability in anonymous messaging systems.
Unfortunately, existing proof-of-knowledge protocols fail to demonstrate that a secret is unencumbered. We therefore introduce and formalize a new notion called complete knowledge (CK). A proof (or argument) of CK shows that a prover does not just know a secret, but also has fully unencumbered knowledge, i.e., unrestricted ability to use the secret.
We introduce two practical CK schemes that use special-purpose hardware, specifically TEEs and off-the-shelf mining ASICs. We prove the security of these schemes and explore their practical deployment with a complete, end-to-end prototype that supports both. We show how CK can address encumbrance attacks identified in previous work. Finally, we introduce two new applications enabled by CK that involve proving ownership of blockchain assets.
David Spielmann, Ognjen Glamocanin, Mirjana Stojilovic
State-of-the-art sensors for measuring FPGA voltage fluctuations are time-to-digital converters (TDCs). They allow detecting voltage fluctuations in the order of a few nanoseconds. The key building component of a TDC is a delay line, typically implemented as a chain of fast carry propagation multiplexers. In FPGAs, the fast carry chains are constrained to dedicated logic and routing, and need to be routed strictly vertically. In this work, we present an alternative approach to designing on-chip voltage sensors, in which the FPGA routing resources replace the carry logic. We present three variants of what we name a routing delay sensor (RDS): one vertically constrained, one horizontally constrained, and one free of any constraints. We perform a thorough experimental evaluation on both the Sakura-X side-channel evaluation board and the Alveo U200 datacenter card, to evaluate the performance of the RDS sensors in the context of a remote power side-channel analysis attack. The results show that our best RDS implementation in most cases outperforms the TDC. On average, for breaking the full 128-bit key of an AES-128 cryptographic core, an adversary requires 35% fewer side-channel traces when using the RDS than when using the TDC. Besides making the attack more effective, given the absence of the placement and routing constraint, the RDS sensor is also easier to deploy.
Aymeric Genêt
SPHINCS+ is a hash-based digital signature scheme that was selected by NIST in their post-quantum cryptography standardization process. The establishment of a universal forgery on the seminal scheme SPHINCS was shown to be feasible in practice by injecting a fault when the signing device constructs any non-top subtree. Ever since the attack has been made public, little effort was spent to protect the SPHINCS family against attacks by faults. This paper works in this direction in the context of SPHINCS+ and analyzes the current algorithms that aim to prevent fault-based forgeries.
First, the paper adapts the original attack to SPHINCS+ reinforced with randomized signing and extends the applicability of the attack to any combination of faulty and valid signatures. Considering the adaptation, the paper then presents a thorough analysis of the attack. In particular, the analysis shows that, with high probability, the security guarantees of SPHINCS+ significantly drop when a single random bit flip occurs anywhere in the signing procedure and that the resulting faulty signature cannot be detected with the verification procedure. The paper shows both in theory and experimentally that the countermeasures based on caching the intermediate W-OTS+s offer a marginally greater protection against unintentional faults, and that such countermeasures are circumvented with a tolerable number of queries in an active attack. Based on these results, the paper recommends real-world deployments of SPHINCS+ to implement redundancy checks.
First, the paper adapts the original attack to SPHINCS+ reinforced with randomized signing and extends the applicability of the attack to any combination of faulty and valid signatures. Considering the adaptation, the paper then presents a thorough analysis of the attack. In particular, the analysis shows that, with high probability, the security guarantees of SPHINCS+ significantly drop when a single random bit flip occurs anywhere in the signing procedure and that the resulting faulty signature cannot be detected with the verification procedure. The paper shows both in theory and experimentally that the countermeasures based on caching the intermediate W-OTS+s offer a marginally greater protection against unintentional faults, and that such countermeasures are circumvented with a tolerable number of queries in an active attack. Based on these results, the paper recommends real-world deployments of SPHINCS+ to implement redundancy checks.
Adrian-Daniel Stefan, Ionut-Petrisor Anghel, Emil Simion
The use of traditional cryptography based on symmetric keys has been replaced with the revolutionary idea discovered by Diffie and Hellman in 1976 that fundamentally changed communication systems by ensuring a secure transmission of information over an insecure channel. Nowadays public key cryptography is frequently used for authentication in e-commerce, digital signatures and encrypted communication. Most of the public key cryptosystems used in practice are based on integer factorization (the famous RSA cryptosystem proposed by Rivest, Shamir and Adlemann), respectively on the discrete logarithm (in finite curves or elliptic curves). However these systems suffer from two potential drawbacks like efficiency because they must use large keys to maintain security and of course security breach with the advent of the quantum computer as a result of Peter Shor's discovery in 1999 of the polynomial algorithm for solving problems such factorization of integers and discrete logarithm.
Shuqin Su, Bohan Yang, Vladimir Rožić, Mingyuan Yang, Min Zhu, Shaojun Wei, Leibo Liu
TRNG is an essential component for security applications. A vulnerable TRNG could be exploited to facilitate potential attacks or be related to a reduced key space, and eventually results in a compromised cryptographic system. A digital FIRO-/GARO-based TRNG with high throughput and high entropy rate was introduced by Jovan Dj. Golić (TC’06). However, the fact that periodic oscillation is a main failure of FIRO-/GARO-based TRNGs is noticed in the paper (Markus Dichtl, ePrint’15). We verify this problem and estimate the consequential entropy loss using Lyapunov exponents and the test suite of the NIST SP 800-90B standard. To address the problem of periodic oscillations, we propose several implementation guidelines based on a gate-level model, a design methodology to build a reliable GARO-based TRNG, and an online test to improve the robustness of FIRO-/GARO-based TRNGs. The gate-level implementation guidelines illustrate the causes of periodic oscillations, which are verified by actual implementation and bifurcation diagram. Based on the design methodology, a suitable feedback polynomial can be selected by evaluating the feedback polynomials. The analysis and understanding of periodic oscillation and FIRO-/GARO-based TRNGs are deepened by delay adjustment. A TRNG with the selected feedback polynomial may occasionally enter periodic oscillations, due to active attacks and the delay inconstancy of implementations. This inconstancy might be caused by self-heating, temperature and voltage fluctuation, and the process variation among different silicon chips. Thus, an online test module, as one indispensable component of TRNGs, is proposed to detect periodic oscillations. The detected periodic oscillation can be eliminated by adjusting feedback polynomial or delays to improve the robustness. The online test module is composed of a lightweight and responsive detector with a high detection rate, outperforming the existing detector design and statistical tests. The areas, power consumptions and frequencies are evaluated based on the ASIC implementations of a GARO, the sampling circuit and the online test module. The gate-level implementation guidelines promote the future establishment of the stochastic model of FIRO-/GARO-based TRNGs with a deeper understanding.
Johanna Maria Kirss, Peeter Laud, Nikita Snetkov, Jelizaveta Vakarjuk
We propose a threshold encryption scheme with two-party decryption, where one of the keyshares may be stored and used in a device that is able to provide only weak security for it. We state the security properties the scheme needs to have to support such use-cases, and construct a scheme with these properties.
Atsuki Momose, Ling Ren, Elaine Shi, Jun Wan, Zhuolun Xiang
Designing an efficient solution for Byzantine broadcast is an important problem for many distributed computing and cryptographic tasks. There have been many attempts to achieve sub-quadratic communication complexity in several directions, both in theory and practice, all with pros and cons. This paper initiates the study of another attempt: improving the amortized communication complexity of multi-shot Byzantine broadcast. Namely, we try to improve the average cost when we have sequential multiple broadcast instances. We present a protocol that achieves optimal amortized linear complexity under an honest majority. Our core technique is to efficiently form a network for disseminating the sender's message by keeping track of dishonest behaviors over multiple instances. We also generalize the technique for the dishonest majority to achieve amortized quadratic communication complexity.
Kelong Cong, Yi-Fu Lai, Shai Levin
Generating supersingular elliptic curves of unknown endomorphism ring has been a problem vexing isogeny-based cryptographers for several years. A recent development has proposed a trusted setup protocol to generate such a curve, where each participant generates and proves knowledge of an isogeny. Thus, the construction of efficient proofs of knowledge of isogeny has developed new interest.
Historically, the isogeny community has assumed that obtaining isogeny proofs of knowledge from generic proof systems, such as zkSNARKs, was not a practical approach. We contribute the first concrete result in this area by applying Aurora (EUROCRYPT'19), Ligero (CCS'17) and Limbo (CCS'21) to an isogeny path relation, and comparing their performance to a state-of-the-art, tailor-made protocol for the same relation. In doing so, we show that modern generic proof systems are competitive when applied to isogeny assumptions, and provide an order of magnitude ($10\textrm{-}30\times$) improvement to proof and verification times, with similar proof sizes. In addition, these proofs provide a stronger notion of soundness, and statistical zero-knowledge; a property that has only recently been achieved in isogeny PoKs. Independently, this technique shows promise as a component in the design of future isogeny-based or other post-quantum protocols.
Historically, the isogeny community has assumed that obtaining isogeny proofs of knowledge from generic proof systems, such as zkSNARKs, was not a practical approach. We contribute the first concrete result in this area by applying Aurora (EUROCRYPT'19), Ligero (CCS'17) and Limbo (CCS'21) to an isogeny path relation, and comparing their performance to a state-of-the-art, tailor-made protocol for the same relation. In doing so, we show that modern generic proof systems are competitive when applied to isogeny assumptions, and provide an order of magnitude ($10\textrm{-}30\times$) improvement to proof and verification times, with similar proof sizes. In addition, these proofs provide a stronger notion of soundness, and statistical zero-knowledge; a property that has only recently been achieved in isogeny PoKs. Independently, this technique shows promise as a component in the design of future isogeny-based or other post-quantum protocols.
Christina Boura, Margot Funk, Yann Rotella
Troika is a sponge-based hash function designed by Kölbl, Tischhauser, Bogdanov and Derbez in 2019. Its specificity is that it is defined over $\mathbb{F}_3$ in order to be used inside IOTA’s distributed ledger but could also serve in all settings requiring the generation of ternary randomness. To be used in practice, Troika needs to be proven secure against state-of-the-art cryptanalysis. However, there are today almost no analysis tools for ternary designs. In this article we take a step in this direction by analyzing the propagation of differential trails of Troika and by providing bounds on the weight of its trails. For this, we adapt a well-known framework for trail search designed for KECCAK and provide new advanced techniques to handle the search on $\mathbb{F}_3$. Our work demonstrates that providing analysis tools for non-binary designs is a highly non-trivial research direction that needs to be enhanced in order to better understand the real security offered by such non-conventional primitives.