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:
11 August 2023
Pierre-Augustin BERTHET, Cédric Tavernier, Jean-Luc Danger, Laurent Sauvage
The recent technological advances in Post-Quantum Cryptography (PQC) rise the questions of robust implementations of new asymmetric cryptographic primitives in today’s technology. This is the case for the lattice-based CRYSTALS-Kyber algorithm which has been selected as the first NIST standard for Public Key Encryption (PKE) and Key Encapsulation Mechanisms (KEM). We have notably to make sure the Kyber implementation is resilient against physical attacks like Side-Channel Analysis (SCA) and Fault Injection Attacks (FIA). To reach this goal, we propose to use the masking countermeasure, more precisely the generic Direct Sum Masking method (DSM). By taking inspiration of a previous paper on AES, we extend the method to finite fields of characteristic prime other than 2 and even-length codes. In particular, we investigated its
application to Keccak, which is the hash-based function used in Kyber. We also provided the first masked implementation of Kyber providing both SCA and FIA resilience while not requiring any conversion between different masking methods.
Marcel Keller, Ke Sun
Keller and Sun (ICML'22) have found a gap in the accuracy between floating-point deep learning in cleartext and secure quantized deep learning using multi-party computation. We have discovered that this gap is caused by a bug in the implementation of max-pooling. In this note, we present updated figures to support this conclusion. We also add figures for another network on CIFAR-10.
Nicolas Mohnblatt, Alberto Sonnino, Kobi Gurkan, Philipp Jovanovic
Contact discovery is a crucial component of social applications, facilitating interactions between registered contacts. This work introduces Arke, a novel approach to contact discovery that addresses the limitations of existing solutions in terms of privacy, scalability, and reliance on trusted third parties. Arke ensures the unlinkability of user interactions, mitigates enumeration attacks, and operates without single points of failure or trust. Notably, Arke is the first contact discovery system whose performance is independent of the total number of users and the first that can operate in a Byzantine setting. It achieves its privacy goals through an unlinkable handshake mechanism built on top of an identity-based non-interactive key exchange. By leveraging a custom distributed architecture, Arke forgoes the expense of consensus to achieve scalability while maintaining consistency in a Byzantine fault tolerant environment. Performance evaluations demonstrate that Arke can support enough throughput to operate at a planetary scale while maintaining sub-second latencies in a large geo-distributed setting.
Arasu Arun, Srinath Setty, Justin Thaler
Succinct Non-interactive Arguments of Knowledge (SNARKs) allow an untrusted prover to establish that it correctly ran some "witness-checking procedure" on a witness. A zkVM (short for zero-knowledge Virtual Machine) is a SNARK that allows the witness-checking procedure to be specified as a computer program written in the assembly language of a specific instruction set architecture (ISA).
A $\textit{front-end}$ converts computer programs into a lower-level representation such as an arithmetic circuit or generalization thereof. A SNARK for circuit-satisfiability can then be applied to the resulting circuit.
We describe a new front-end technique called Jolt that applies to a variety of ISAs. Jolt arguably realizes a vision called the $\textit{lookup singularity}$, which seeks to produce circuits that only perform lookups into pre-determined lookup tables. The circuits output by Jolt primarily perform lookups into a gigantic lookup table, of size more than $2^{128}$, that depends only on the ISA. The validity of the lookups are proved via a new $\textit{lookup argument}$ called Lasso described in a companion work (Setty, Thaler, and Wahby, e-print 2023). Although size-$2^{128}$ tables are vastly too large to materialize in full, the tables arising in Jolt are structured, avoiding costs that grow linearly with the table size.
We describe performance and auditability benefits of Jolt compared to prior zkVMs, focusing on the popular RISC-V ISA as a concrete example. The dominant cost for the Jolt prover applied to this ISA (on $64$-bit data types) is cryptographically committing to about six $256$-bit field elements per step of the RISC-V CPU. This compares favorably to prior zkVM provers, even those focused on far simpler VMs.
A $\textit{front-end}$ converts computer programs into a lower-level representation such as an arithmetic circuit or generalization thereof. A SNARK for circuit-satisfiability can then be applied to the resulting circuit.
We describe a new front-end technique called Jolt that applies to a variety of ISAs. Jolt arguably realizes a vision called the $\textit{lookup singularity}$, which seeks to produce circuits that only perform lookups into pre-determined lookup tables. The circuits output by Jolt primarily perform lookups into a gigantic lookup table, of size more than $2^{128}$, that depends only on the ISA. The validity of the lookups are proved via a new $\textit{lookup argument}$ called Lasso described in a companion work (Setty, Thaler, and Wahby, e-print 2023). Although size-$2^{128}$ tables are vastly too large to materialize in full, the tables arising in Jolt are structured, avoiding costs that grow linearly with the table size.
We describe performance and auditability benefits of Jolt compared to prior zkVMs, focusing on the popular RISC-V ISA as a concrete example. The dominant cost for the Jolt prover applied to this ISA (on $64$-bit data types) is cryptographically committing to about six $256$-bit field elements per step of the RISC-V CPU. This compares favorably to prior zkVM provers, even those focused on far simpler VMs.
Srinath Setty, Justin Thaler, Riad Wahby
This paper introduces Lasso, a new family of lookup arguments, which allow an untrusted prover to commit to a vector $a \in \mathbb{F}^m$ and prove that all entries of a reside in some predetermined table $t \in \mathbb{F}^n$. Lasso’s performance characteristics unlock the so-called "lookup singularity". Lasso works with any multilinear polynomial commitment scheme, and provides the following efficiency properties.
For $m$ lookups into a table of size $n$, Lasso’s prover commits to just $m + n$ field elements. Moreover, the committed field elements are small, meaning that, no matter how big the field $\mathbb{F}$ is, they are all in the set $\{0, . . . , m\}$. When using a multiexponentiation-based commitment scheme, this results in the prover’s costs dominated by only $O(m + n)$ group operations (e.g., elliptic curve point additions), plus the cost to prove an evaluation of a multilinear polynomial whose evaluations over the Boolean hypercube are the table entries. This represents a significant improvement in prover costs over prior lookup arguments (e.g., plookup, Halo2’s lookups, lookup arguments based on logarithmic derivatives).
Unlike all prior lookup arguments, if the table $t$ is structured (in a precise sense that we define), then no party needs to commit to $t$, enabling the use of much larger tables than prior works (e.g., of size $2^{128}$ or larger). Moreover, Lasso’s prover only "pays" in runtime for table entries that are accessed by the lookup operations. This applies to tables commonly used to implement range checks, bitwise operations, big-number arithmetic, and even transitions of a full-fledged CPU such as RISC-V. Specifically, for any integer parameter $c > 1$, Lasso’s prover’s dominant cost is committing to $3 \cdot c \cdot m + c \cdot n^{1/c}$ field elements. Furthermore, all these field elements are “small”, meaning they are in the set $\{0, . . . , \max{(m, n^{1/c}, q)} − 1\}$, where $q$ is the maximum value in $a$.
Lasso’s starting point is Spark, a time-optimal polynomial commitment scheme for sparse polynomials in Spartan (CRYPTO 2020). We first provide a stronger security analysis for Spark. Spartan’s security analysis assumed that certain metadata associated with a sparse polynomial is committed by an honest party (this is acceptable for its purpose in Spartan, but not for Lasso). We prove that Spark remains secure even when that metadata is committed by a malicious party. This provides the first "standard" commitment scheme for sparse multilinear polynomials with optimal prover costs. We then generalize Spark to directly support a lookup argument for both structured and unstructured tables, with the efficiency characteristics noted above.
For $m$ lookups into a table of size $n$, Lasso’s prover commits to just $m + n$ field elements. Moreover, the committed field elements are small, meaning that, no matter how big the field $\mathbb{F}$ is, they are all in the set $\{0, . . . , m\}$. When using a multiexponentiation-based commitment scheme, this results in the prover’s costs dominated by only $O(m + n)$ group operations (e.g., elliptic curve point additions), plus the cost to prove an evaluation of a multilinear polynomial whose evaluations over the Boolean hypercube are the table entries. This represents a significant improvement in prover costs over prior lookup arguments (e.g., plookup, Halo2’s lookups, lookup arguments based on logarithmic derivatives).
Unlike all prior lookup arguments, if the table $t$ is structured (in a precise sense that we define), then no party needs to commit to $t$, enabling the use of much larger tables than prior works (e.g., of size $2^{128}$ or larger). Moreover, Lasso’s prover only "pays" in runtime for table entries that are accessed by the lookup operations. This applies to tables commonly used to implement range checks, bitwise operations, big-number arithmetic, and even transitions of a full-fledged CPU such as RISC-V. Specifically, for any integer parameter $c > 1$, Lasso’s prover’s dominant cost is committing to $3 \cdot c \cdot m + c \cdot n^{1/c}$ field elements. Furthermore, all these field elements are “small”, meaning they are in the set $\{0, . . . , \max{(m, n^{1/c}, q)} − 1\}$, where $q$ is the maximum value in $a$.
Lasso’s starting point is Spark, a time-optimal polynomial commitment scheme for sparse polynomials in Spartan (CRYPTO 2020). We first provide a stronger security analysis for Spark. Spartan’s security analysis assumed that certain metadata associated with a sparse polynomial is committed by an honest party (this is acceptable for its purpose in Spartan, but not for Lasso). We prove that Spark remains secure even when that metadata is committed by a malicious party. This provides the first "standard" commitment scheme for sparse multilinear polynomials with optimal prover costs. We then generalize Spark to directly support a lookup argument for both structured and unstructured tables, with the efficiency characteristics noted above.
Ripon Patgiri, Laiphrakpam Dolendro Singh
Password-based authentication is an extensively used method to authenticate users. It uses cryptography to communicate the authentication process. On the contrary, the physically unclonable function (PUF)-based authentication mechanism is also gaining popularity rapidly due to its usability in IoT devices. It is a lightweight authentication mechanism that does not use cryptography protocol. PUF-based authentication mechanisms cannot authenticate users. To overcome the drawback of PUF, we introduce a software-defined unclonable function (SUF, for short). Contrary to the PUF, the SUF is used to authenticate users, not devices. We use SUF to implement a lightweight password-based authentication mechanism termed Authentica. Authentica bridges the gap between the password-based and the PUF-based authentication mechanism. Authentica does not use cryptography for authentication. However, we establish challenge-response using cryptography during the registration phase, which is a one-time cost. Authentica addresses a) impersonation attacks, b) collision attacks, c) dictionary and rainbow table attacks, d) replay attacks, e) DDoS attacks, f) the domino effect issues, and g) the challenge-response database leakage issues.
Marc Fischlin, Felix Günther
Common verification steps in cryptographic protocols, such as signature or message authentication code checks or the validation of elliptic curve points, are crucial for the overall security of the protocol. Yet implementation errors omitting these steps easily remain unnoticed, as often the protocol will function perfectly anyways. One of the most prominent examples is Apple's goto fail bug where the erroneous certificate verification skipped over several of the required steps, marking invalid certificates as correctly verified. This vulnerability went undetected for at least 17 months.
We propose here a mechanism which supports the detection of such errors on a cryptographic level. Instead of merely returning the binary acceptance decision, we let the verification return more fine-grained information in form of what we call a confirmation code. The reader may think of the confirmation code as disposable information produced as part of the relevant verification steps. In case of an implementation error like the goto fail bug, the confirmation code would then miss essential elements.
The question arises now how to verify the confirmation code itself. We show how to use confirmation codes to tie security to basic functionality at the overall protocol level, making erroneous implementations be detected through the protocol not functioning properly. More concretely, we discuss the usage of confirmation codes in secure connections, established via a key exchange protocol and secured through the derived keys. If some verification steps in a key exchange protocol execution are faulty, then so will be the confirmation codes, and because we can let the confirmation codes enter key derivation, the connection of the two parties will eventually fail. In consequence, an implementation error like goto fail would now be detectable through a simple connection test.
We propose here a mechanism which supports the detection of such errors on a cryptographic level. Instead of merely returning the binary acceptance decision, we let the verification return more fine-grained information in form of what we call a confirmation code. The reader may think of the confirmation code as disposable information produced as part of the relevant verification steps. In case of an implementation error like the goto fail bug, the confirmation code would then miss essential elements.
The question arises now how to verify the confirmation code itself. We show how to use confirmation codes to tie security to basic functionality at the overall protocol level, making erroneous implementations be detected through the protocol not functioning properly. More concretely, we discuss the usage of confirmation codes in secure connections, established via a key exchange protocol and secured through the derived keys. If some verification steps in a key exchange protocol execution are faulty, then so will be the confirmation codes, and because we can let the confirmation codes enter key derivation, the connection of the two parties will eventually fail. In consequence, an implementation error like goto fail would now be detectable through a simple connection test.
10 August 2023
Rei Ueno, Naofumi Homma, Akiko Inoue, Kazuhiko Minematsu
This paper presents a provably secure, higher-order, and leakage-resilient
(LR) rekeying scheme named LR Rekeying with Random oracle Repetition (LR4), along with a quantitative security evaluation methodology. Many existing LR cryptographies are based on a concept of leveled implementation, which still essentially require a leak-free sanctuary (i.e., differential power analysis (DPA)-resistant component(s)) for some parts. In addition, although several LR pseudorandom functions (PRFs) based on only bounded DPA-resistant components have been developed, their validity and effectiveness for rekeying usage still need to be determined. In contrast, LR4 is formally proven under a leakage model that captures the practical goal of side-channel attack (SCA) protection (e.g., masking with a practical order) and assumes no unbounded DPA-resistant sanctuary. This proof suggests that LR4 resists exponential invocations (up to the birthday bound of key size) without using any unbounded leak-free component, which is the first of its kind. Moreover, we present a quantitative SCA success rate evaluation methodology for LR4 that combines the bounded leakage models for LR cryptography and a state-of-the-art information-theoretical SCA evaluation method. We validate its soundness and effectiveness as a DPA countermeasure through a numerical evaluation; that is, the number of secure calls of a symmetric primitive increases exponentially by increasing a security parameter under practical conditions.
Mustafa Khairallah
In this paper, we present a new distinguisher for the Tweak-aNd-Tweak (TNT) tweakable block cipher with $O(2^{n/2})$ complexity. The distinguisher is an adaptive chosen ciphertext distinguisher, unlike previous attacks that are only non-adaptive chosen plaintext attacks. However, the attack contradicts the security claims made by the designers. Given TNT can be seen as the three-round CLRW1 tweakable block cipher, our attack matches its more conservative bound. We provide the distinguisher description, a probabilistic analysis of its behaviour, experimental verification and an analysis of why the proof fails to capture the security of TNT. In summary, the distinguisher is based on collision counting and exploits non-uniformity in the statistical behaviour of random permutations. It reduces the goal of finding the collision to solving a difference equation defined over a random permutation. Due to this relation, the number of collisions observed by the distinguisher is twice as expected from an ideal tweakable block cipher.
Joachim Neu, Srivatsan Sridhar, Lei Yang, David Tse
Classic BFT consensus protocols guarantee safety and liveness for all clients if fewer than one-third of replicas are faulty. However, in applications such as high-value payments, some clients may want to prioritize safety over liveness. Flexible consensus allows each client to opt for a higher safety resilience, albeit at the expense of reduced liveness resilience. We present the first construction that allows optimal safety--liveness tradeoff for every client simultaneously. This construction is modular and is realized as an add-on applied on top of an existing consensus protocol. The add-on consists of an additional round of voting and permanent locking done by the replicas, to sidestep a sub-optimal quorum-intersection-based constraint present in previous solutions. We adapt our construction to the existing Ethereum protocol to derive optimal flexible confirmation rules that clients can adopt unilaterally without requiring system-wide changes. This is possible because existing Ethereum protocol features can double as the extra voting and locking. We demonstrate an implementation using Ethereum's consensus API.
Erya Jiang, Bo Qin, Qin Wang, Zhipeng Wang, Qianhong Wu, Jian Weng, Xinyu Li, Chenyang Wang, Yuhang Ding, Yanran Zhang
Decentralized Finance (DeFi) is a new paradigm in the creation, distribution, and utilization of financial services via the integration of blockchain technology. Our research conducts a comprehensive introduction and meticulous classification of various DeFi applications. Beyond that, we thoroughly analyze these risks from both technical and economic perspectives, spanning multiple layers. Lastly, we point out research directions in DeFi, encompassing areas of technological advancements, innovative economics, and privacy optimization.
Xiaoni Du, René Rodríguez, Hao Wu
Linear codes play a crucial role in various fields of engineering and mathematics, including data storage, communication, cryptography, and combinatorics. Minimal linear codes, a subset of linear codes, are particularly essential for designing effective secret sharing schemes. In this paper, we introduce several classes of minimal binary linear codes by carefully selecting appropriate Boolean functions. These functions belong to a renowned class of Boolean functions, the general Maiorana-McFarland class. We employ a method first proposed by Ding et al. [7] to construct minimal codes violating the Ashikhmin-Barg bound (wide minimal codes) by using Krawtchouk polynomials. The lengths, dimensions, and weight distributions of the obtained codes are determined using the Walsh spectrum distribution of the chosen Boolean functions. Our findings demonstrate that a vast majority of the newly constructed codes are wide minimal codes. Furthermore, our proposed codes exhibit a significantly larger minimum distance, in some cases, compared to some existing similar constructions. Finally, we address this method, based on Krawtchouk polynomials, more generally, and highlight certain generic properties related to it. This study provides insights into the scope of this method.
Alan Szepieniec, Thorkil Værge
A mutator set is a cryptographic data structure for authenticating operations on a changing set of data elements called items. Informally:
- There is a short commitment to the set. - There are succinct membership proofs for elements of the set. - It is possible to update the commitment as well as the membership proofs with minimal effort as new items are added to the set or as existing items are removed from it. - Items cannot be removed before they were added. - It is difficult to link an item's addition to the set to its removal from the set, except when using information available only to the party that generated it.
This paper formally defines the notion, motivates its existence with an application to scalable privacy in the context of cryptocurrencies, and proposes an instantiation inspired by Merkle mountain ranges and Bloom filters.
- There is a short commitment to the set. - There are succinct membership proofs for elements of the set. - It is possible to update the commitment as well as the membership proofs with minimal effort as new items are added to the set or as existing items are removed from it. - Items cannot be removed before they were added. - It is difficult to link an item's addition to the set to its removal from the set, except when using information available only to the party that generated it.
This paper formally defines the notion, motivates its existence with an application to scalable privacy in the context of cryptocurrencies, and proposes an instantiation inspired by Merkle mountain ranges and Bloom filters.
Ding Feng, Rupert Hitsch, Kaihua Qin, Arthur Gervais, Roger Wattenhofer, Yaxing Yao, Ye Wang
Decentralized Finance (DeFi), a blockchain-based financial ecosystem, suffers from smart contract vulnerabilities that led to a loss exceeding 3.24 billion USD by April 2022. To address this, blockchain firms audit DeFi applications, a process known as DeFi auditing. Our research aims to comprehend the mechanism and efficacy of DeFi auditing. We discovered its ability to detect vulnerabilities in smart contract logic and interactivity with other DeFi entities, but also noted its limitations in communication, transparency, remedial action implementation, and in preventing certain DeFi attacks. Moreover, our interview study delved into user perceptions of DeFi auditing, unmasking gaps in awareness, usage, and trust, and offering insights to address these issues.
Kwangsu Lee
Threshold signatures are digital signatures that support the multi-party signature generation such that a number of parties initially share a signing key and more than a threshold number of parties gather to generate a signature. In this paper, we propose a non-interactive decentralized threshold signature (NIDTS) scheme that supports the non-interactive and transparent key setup based on BLS signatures. Our NIDTS scheme has the following properties. 1) The key setup process is completely non-interactive and does not require message exchange between parties since the transfer of the register keys of parties is enough for a combiner to generate a compact verification key. 2) The register key of a party is compact since the size is independent of the number of group parties. 3) The signing process of parties is non-interactive. 4) The final threshold signature as well as partial signatures are succinct.
We prove the security of our NIDTS scheme under computational assumptions in the random oracle model. Furthermore, we implement our NIDTS scheme in Rust and compare its performance with other scheme to show that the key setup of our scheme is more efficient. For example, in the unweighted setting of 1000 parties, the key setup process of the NIDTS scheme takes 164 seconds, which is 5.9 times faster than the key setup process of the multiverse threshold signature (MTS) scheme.
Tanja Lange, Alex Pellegrini, Alberto Ravagnani
We analyze REDOG, a public-key encryption system submitted to the Korean
competition on post-quantum cryptography.
REDOG is based on rank-metric codes. We prove its incorrectness and attack its
implementation providing an efficient message recovery attack. Furthermore, we
show that the security of REDOG is much lower than claimed. We then
proceed to mitigate these issues and provide two approaches to fix the
decryption issue, one of which also leads to better security.
Daniel Escudero, Serge Fehr
Fully secure multiparty computation (or guaranteed output delivery) among $n$ parties can be achieved with perfect security if the number of corruptions $t$ is less than $n/3$, or with statistical security with the help of a broadcast channel if $t
In this work we make progress in this direction by taking the second route above: we present a fully secure protocol for $t
In this work we make progress in this direction by taking the second route above: we present a fully secure protocol for $t
Ravit Geva, Alexander Gusev, Yuriy Polyakov, Lior Liram, Oded Rosolio, Andreea Alexandru, Nicholas Genise, Marcelo Blatt, Zohar Duchin, Barliz Waissengrin, Dan Mirelman, Felix Bukstein, Deborah T ...
Real-world healthcare data sharing is instrumental in constructing broader-based and larger clinical data sets that may improve clinical decision-making research and outcomes. Stakeholders are frequently reluctant to share their data without guaranteed patient privacy, proper protection of their data sets, and control over the usage of their data. Fully homomorphic encryption (FHE) is a cryptographic capability that can address these issues by enabling computation on encrypted data without intermediate decryptions, so the analytics results are obtained without revealing the raw data. This work presents a toolset for collaborative privacy-preserving analysis of oncological data using multiparty FHE. Our toolset supports survival analysis, logistic regression training, and several common descriptive statistics. We demonstrate using oncological data sets that the toolset achieves high accuracy and practical performance, which scales well to larger data sets. As part of this work, we propose a novel cryptographic protocol for interactive bootstrapping in multiparty FHE, which is of independent interest. The toolset we develop is general-purpose and can be applied to other collaborative medical and healthcare application domains.
Karel BURDA
The paper extends Shannon's classical theory of ciphers. Here ciphers are modeled by Latin rectangles and their resistance to brute force attack is assessed through the valence of cryptograms. The valence of a cryptogram is defined as the number of all meaningful messages produced by decrypting the cryptogram with all possible keys. In this paper, the mean cryptogram valence of an arbitrary modern cipher with K keys, N outputs and N inputs, of which M inputs are messages, is derived. Furthermore, the lower bound on the valence of the cryptograms of entire ciphers is derived in this paper. The obtained parameters allow to assess the resistance of cryptograms, resp. ciphers against brute force attack. The model is general, illustrative and uses a simpler mathematical apparatus than existing theory. Therefore, it can also be used as an introduction to the theory of resistance of ciphers to brute force attack.
Hernán Darío Vanegas Madrigal, Daniel Cabarcas Jaramillo, Diego F. Aranha
The edit distance is a metric widely used in genomics to measure the similarity of two DNA chains. Motivated by privacy concerns, we propose a 2PC protocol to compute the edit distance while preserving the privacy of the inputs. Since the edit distance algorithm can be expressed as a mixed-circuit computation, our approach uses protocols based on secret-sharing schemes like Tinier and SPD$\mathbb{Z}_{2^k}$; and also daBits to perform domain conversion and edaBits to perform arithmetic comparisons. We modify the Wagner-Fischer edit distance algorithm, aiming at reducing the number of rounds of the protocol, and achieve a flexible protocol with a trade-off between rounds and multiplications. We implement our proposal in the MP-SPDZ framework, and our experiments show that it reduces the execution time respectively by 81\% and 54\% for passive and active security with respect to a baseline implementation in a LAN. The experiments also show that our protocol reduces traffic by two orders of magnitude compared to a BMR-MASCOT implementation.