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:
10 August 2023
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.
Sunyeop Kim, Myoungsu Shin, Seonkyu Kim, Hanbeom Shin, Insung Kim, Donggeun Kwon, Dongjae Lee, Seonggyeom Kim, Deukjo Hong, Jaechul Sung, Seokhie Hong
Shadow is a lightweight block cipher proposed at IEEE IoT journal 2021. Shadow’s main design principle is adopting a variant 4- branch Feistel structure in order to provide a fast diffusion rate. We define such a structure as Shadow structure and prove that it is al- most identical to the Generalized Feistel Network, which invalidates the design principle. Moreover, we give a structural distinguisher that can distinguish Shadow structure from random permutation with only two plaintext/ciphertext pairs. By exploiting the key schedule, the distin- guisher can be extended to key recovery attack with only one plain- text/ciphertext pair. Furthermore, by considering Shadow’s round func- tion, only certain forms of monomials can appear in the ciphertext, re- sulting in an integral distinguisher of four plaintext/ciphertext pairs. Even more, the algebraic degree does not increase more than 12 for Shadow-32 and 20 for Shadow-64 regardless of rounds used. Our results show that Shadow is highly vulnerable to algebraic attacks, and that algebraic attacks should be carefully considered when designing ciphers with AND, rotation, and XOR operations.
Ghous Amjad, Kevin Yeo, Moti Yung
Anonymous tokens are digital signature schemes that enable an issuer to provider users with signatures without learning the input message or the resulting signature received by the user. These primitives allow applications to propagate trust while simultaneously protecting the identity of the user. Anonymous tokens have become a core component for improving the privacy of several real-world applications including ad measurements, authorization protocols, spam detection and VPNs.
In certain applications, it is natural to associate signatures with specific public metadata ensuring that signatures only propagate trust with respect to only a certain set of scenarios. To solve this, we study the notion of anonymous tokens with public metadata in this work. We present a variant of RSA blind signatures with public metadata such that issuers may only generate signatures that verify for a certain choice of public metadata. We prove the security of our protocol under one-more RSA assumptions with multiple exponents that we introduce. Furthermore, we provide evidence that the concrete security bounds should be nearly identical to standard RSA blind signatures. The protocols in this paper have been proposed as a technical specification in an IRTF internet draft.
In certain applications, it is natural to associate signatures with specific public metadata ensuring that signatures only propagate trust with respect to only a certain set of scenarios. To solve this, we study the notion of anonymous tokens with public metadata in this work. We present a variant of RSA blind signatures with public metadata such that issuers may only generate signatures that verify for a certain choice of public metadata. We prove the security of our protocol under one-more RSA assumptions with multiple exponents that we introduce. Furthermore, we provide evidence that the concrete security bounds should be nearly identical to standard RSA blind signatures. The protocols in this paper have been proposed as a technical specification in an IRTF internet draft.
09 August 2023
We are proud to announce the winners of the 2023 IACR Test-of-Time Award for Crypto.
The IACR Test-of-Time Award honors papers published at the 3 IACR flagship conferences 15 years ago which have had a lasting impact on the field. This year, we are announcing the winners for each conference separately.
The Test-of-Time award for Crypto 2008 is awarded to:
A Framework for Efficient and Composable Oblivious Transfer, by Chris Peikert, Vinod Vaikuntanathan and Brent Waters, for the creation of a simple framework for achieving efficient UC composable protocols that can be realized under a variety of concrete assumptions, introducing a powerful notion of dual-mode encryption and allowing for the first time to create bandwidth efficient Regev encryption.
For more information, see https://www.iacr.org/testoftime.
Congratulations to the winners!
The Test-of-Time award for Crypto 2008 is awarded to:
A Framework for Efficient and Composable Oblivious Transfer, by Chris Peikert, Vinod Vaikuntanathan and Brent Waters, for the creation of a simple framework for achieving efficient UC composable protocols that can be realized under a variety of concrete assumptions, introducing a powerful notion of dual-mode encryption and allowing for the first time to create bandwidth efficient Regev encryption.
For more information, see https://www.iacr.org/testoftime.
Congratulations to the winners!
08 August 2023
Roorkee, India, 14 December - 17 December 2023
Event date: 14 December to 17 December 2023
Submission deadline: 1 September 2023
Notification: 15 October 2023
Submission deadline: 1 September 2023
Notification: 15 October 2023
Sydney, Australia, 15 April - 17 April 2024
Event date: 15 April to 17 April 2024
Submission deadline: 1 October 2023
Notification: 15 December 2023
Submission deadline: 1 October 2023
Notification: 15 December 2023
07 August 2023
Sonia Belaïd, Gaëtan Cassiers, Camille Mutschler, Matthieu Rivain, Thomas Roche, François-Xavier Standaert, Abdul Rahman Taleb
Physical side-channel attacks are powerful attacks that exploit a device's physical emanations to break the security of cryptographic implementations. Many countermeasures have been proposed against these attacks, especially the widely-used and efficient masking countermeasure. Nevertheless, proving the security of masked implementations is challenging. Current techniques rely on empirical approaches to validate the security of such implementations. On the other hand, the theoretical community introduced leakage models to provide formal proofs of the security of masked implementations. Meanwhile, these leakage models rely on physical assumptions that are difficult to satisfy in practice, and the literature lacks a clear framework to implement proven secure constructions on a physical device while preserving the proven security.
In this paper, we present a complete methodology describing the steps to turn an abstract masking scheme proven secure in a theoretical leakage model into a physical implementation satisfying provable security against side-channel attacks in practice. We propose new tools to enforce or relax the physical assumptions the indeal noisy leakage model rely on and provide novel ways of including them in a physical implementation. We also highlight the design goals for an embedded device to reach high levels of proven security, discussing the limitations and open problems of the practical usability of the leakage models. Our goal is to show that it is possible to bridge theory and practice and to motivate further research to fully close the gap and get practical implementations proven secure against side-channel attacks on a physical device without any ideal assumption about the leakage.
In this paper, we present a complete methodology describing the steps to turn an abstract masking scheme proven secure in a theoretical leakage model into a physical implementation satisfying provable security against side-channel attacks in practice. We propose new tools to enforce or relax the physical assumptions the indeal noisy leakage model rely on and provide novel ways of including them in a physical implementation. We also highlight the design goals for an embedded device to reach high levels of proven security, discussing the limitations and open problems of the practical usability of the leakage models. Our goal is to show that it is possible to bridge theory and practice and to motivate further research to fully close the gap and get practical implementations proven secure against side-channel attacks on a physical device without any ideal assumption about the leakage.
Thomas Decru, Luciano Maino, Antonio Sanso
In this paper, we present a new quantum-resistant weak Verifiable Delay Function based on a purely algebraic construction. Its delay depends on computing a large-degree isogeny between elliptic curves, whereas its verification relies on the computation of isogenies between products of two elliptic curves. One of its major advantages is its expected fast verification time. However, it is important to note that the practical implementation of our theoretical framework poses significant challenges. We examine the strengths and weaknesses of our construction, analyze its security and provide a proof-of-concept implementation.
Sourav Das, Zhuolun Xiang, Alin Tomescu, Alexander Spiegelman, Benny Pinkas, Ling Ren
Verifiable Secret Sharing (VSS) is a fundamental building block in cryptography. Despite its importance and extensive studies, existing VSS protocols are often complex and inefficient. Many of them do not support dual threads, are not publicly verifiable, or do not properly terminate in asynchronous networks. In this paper, we present a new and simple paradigm for designing VSS protocols in synchronous and asynchronous networks. Our VSS protocols are optimally fault-tolerant, i.e., they tolerate a 1/2 and a 1/3 fraction of malicious nodes in synchronous and asynchronous networks, respectively. They only require a public key infrastructure and the hardness of discrete logarithms. Our protocols support dual thresholds and their transcripts are publicly verifiable. We implement our VSS protocols and measure their computation and communication costs with up to 1024 nodes. Our evaluation illustrates that our VSS protocols provide asynchronous termination and public verifiability with minimum performance overhead. Compared to the existing VSS protocol with similar guarantees, our protocols are 5-15× and 8-13× better in computation and communication cost, respectively.
Colin O'Flynn
Electromagnetic Fault Injection (EMFI) has been demonstrated to be useful for both academic and industrial research. Due to the dangerous voltages involved, most work is done with commercial tools. This paper introduces a safety-focused low-cost and open-source design that can be built for less than \$50 using only off-the-shelf parts.
The paper also introduces an iCE40 based Time-to-Digital Converter (TDC), which is used to visualize the glitch inserted by the EMFI tool. This demonstrates the internal voltage perturbations between voltage, body biasing injection (BBI), and EMFI all result in similar waveforms. In addition, a link between an easy-to-measure external voltage measurement and the internal measurement is made. Attacks are also made on a hardware AES engine, and a soft-core RISC-V processor, all running on the same iCE40 FPGA.
The platform is used to demonstrate several aspects of fault injection, including that the spatial positioning of the EMFI probe can impact the glitch strength, and that the same physical device may require widely different glitch parameters when running different designs.
The paper also introduces an iCE40 based Time-to-Digital Converter (TDC), which is used to visualize the glitch inserted by the EMFI tool. This demonstrates the internal voltage perturbations between voltage, body biasing injection (BBI), and EMFI all result in similar waveforms. In addition, a link between an easy-to-measure external voltage measurement and the internal measurement is made. Attacks are also made on a hardware AES engine, and a soft-core RISC-V processor, all running on the same iCE40 FPGA.
The platform is used to demonstrate several aspects of fault injection, including that the spatial positioning of the EMFI probe can impact the glitch strength, and that the same physical device may require widely different glitch parameters when running different designs.
Xinyi Ji, Jiankuo Dong, Pinchang Zhang, Deng Tonggui, Hua Jiafeng, Fu Xiao
CRYSTALS-Kyber, as the only public key encryption (PKE) algorithm selected by the National Institute of Standards and Technology (NIST) in the third round, is considered one of the most promising post-quantum cryptography (PQC) schemes. Lattice-based cryptography uses complex discrete alogarithm problems on lattices to build secure encryption and decryption systems to resist attacks from quantum computing. Performance is an important bottleneck affecting the promotion of post quantum cryptography. In this paper, we present a High-performance Implementation of Kyber (named HI-Kyber) on the NVIDIA GPUs, which can increase the key-exchange performance of Kyber to the million-level. Firstly, we propose a lattice-based PQC implementation architecture based on kernel fusion, which can avoid redundant global-memory access operations. Secondly, We optimize and implement the core operations of CRYSTALS-Kyber, including Number Theoretic Transform (NTT), inverse NTT (INTT), pointwise multiplication, etc. Especially for the calculation bottleneck NTT operation, three novel methods are proposed to explore extreme performance: the sliced layer merging (SLM), the sliced depth-first search (SDFS-NTT) and the entire depth-first search (EDFS-NTT), which achieve a speedup of 7.5%, 28.5%, and 41.6% compared to the native implementation. Thirdly, we conduct comprehensive performance experiments with different parallel dimensions based on the above optimization. Finally, our key exchange performance reaches 1,664 kops/s. Specifically, based on the same platform, our HI-Kyber is 3.52$\times$ that of the GPU implementation based on the same instruction set and 1.78$\times$ that of the state-of-the-art one based on AI-accelerated tensor core.
Inam ul Haq, Jian Wang, Youwen Zhu, Sheharyar Nasir
The accelerated advances in information communication technologies have made it possible for enterprises to deploy large scale applications in a multi-server architecture (also known as cloud computing environment). In this architecture, a mobile user can remotely obtain desired services over the Internet from multiple servers by initially executing a single registration on a trusted registration server (RS). Due to the hazardous nature of the Internet, to protect user privacy and online communication, a lot of multi-server authenticated-key-agreement (MSAKA) schemes have been furnished. However, all such designs lack in two very vital aspects, i.e., 1) no security under the partially trusted RS and 2) RS cannot control a user to access only a wanted combination of service-providing servers. To address these shortcomings, we present a new MSAKA protocol using self-certified public-key cryptography (SCPKC). We confirm the security of the proposed scheme by utilizing the well-known automated verification tool AVISPA and also provide a formal security proof in the random oracle model. Moreover, the software implementation of the proposed scheme, and a performance and security metrics comparison shows that it portrays a better security performance trade-off, and hence is more appropriate for real-life applications having resource constraint devices.