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:
25 May 2023
Artem Grigor, Vincenzo Iovino, Giuseppe Visconti
A natural approach to anonymous voting over Ethereum assumes that there is an off-chain aggregator that performs the following task. The aggregator receives valid signatures of YES/NO preferences from eligible voters and uses them to compute a zk-SNARK proof of the fact that the majority of voters have cast a preference for YES or NO. Then, the aggregator sends to the smart contract the zk-SNARK proof, the smart contract verifies the proof and can trigger an action (e.g., a transfer of funds). It is believed that as the zk-SNARK proof guarantees anonymity, the privacy of the voters is preserved by attackers not colluding with the aggregator. Moreover, if the SNARK proof verification is efficient the GAS cost will be independent on the number of participating voters and signatures submitted by voters to the aggregator.
In this paper we show that this naive approach to run referenda over Ethereum can incur severe security problems. We propose both mitigations and hardness results for achieving voting procedures in
which the proofs submitted on-chain are either ZK or succinct.
Shahla Atapoor, Karim Baghery, Daniele Cozzo, Robi Pedersen
A Distributed Key Generation (DKG) protocol is an essential component of threshold cryptography. DKGs enable a group of parties to generate a secret and public key pair in a distributed manner so that the secret key is protected from being exposed, even if a certain number of parties are compromised. Robustness further guarantees that the construction of the key pair is always successful, even if malicious parties try to sabotage the computation. In this paper, we construct two efficient robust DKG protocols in the CSIDH setting that work with Shamir secret sharing. Both the proposed protocols are proven to be actively secure in the quantum random oracle model and use an Information Theoretically (IT) secure Verifiable Secret Sharing (VSS) scheme that is built using bivariate polynomials. As a tool, we construct a new piecewise verifiable proof system for structured public keys, that could be of independent interest. In terms of isogeny computations, our protocols outperform the previously proposed DKG protocols CSI-RAShi and Structured CSI-RAShi. As an instance, using our DKG protocols, 4 parties can sample a PK of size 4kB, for CSI-FiSh and CSI-SharK, respectively, 3.4 and 1.7 times faster than the current alternatives. On the other hand, since we use an IT-secure VSS, the fraction of corrupted parties is limited to less than a third and the communication cost of our schemes scales slightly worse with an increasing number of parties. For a low number of parties, our scheme still outperforms the alternatives in terms of communication.
Jung Hee Cheon, Hyeongmin Choe, Dongyeon Hong, MinJune Yi
Recently, NIST has announced Kyber, a lattice-based key encapsulation mechanism (KEM), as a post-quantum standard.
However, it is not the most efficient scheme among the NIST's KEM finalists.
Saber enjoys more compact sizes and faster performance, and Mera et al. (TCHES '21) further pushed its efficiency, proposing a shorter KEM, Sable.
As KEM are frequently used on the Internet, such as in TLS protocols, it is essential to achieve high efficiency while maintaining sufficient security.
In this paper, we further push the efficiency limit of lattice-based KEMs by proposing SMAUG, a new post-quantum KEM scheme submitted to the Korean Post-Quantum Cryptography (KPQC) competition, whose IND-CCA2 security is based on the combination of MLWE and MLWR problems. We adopt several recent developments in lattice-based cryptography, targeting the textit{smallest} and the \textit{fastest} KEM while maintaining high enough security against various attacks, with a full-fledged use of sparse secrets. Our design choices allow SMAUG to balance the decryption failure probability and ciphertext sizes without utilizing error correction codes, whose side-channel resistance remains open.
With a constant-time C reference implementation, SMAUG achieves ciphertext sizes up to 12% and 9% smaller than Kyber and Saber, with much faster running time, up to 103% and 58%, respectively. Compared to Sable, SMAUG has the same ciphertext sizes but a larger public key, which gives a trade-off between the public key size versus performance; SMAUG has 39%-55% faster encapsulation and decapsulation speed in the parameter sets having comparable security.
In this paper, we further push the efficiency limit of lattice-based KEMs by proposing SMAUG, a new post-quantum KEM scheme submitted to the Korean Post-Quantum Cryptography (KPQC) competition, whose IND-CCA2 security is based on the combination of MLWE and MLWR problems. We adopt several recent developments in lattice-based cryptography, targeting the textit{smallest} and the \textit{fastest} KEM while maintaining high enough security against various attacks, with a full-fledged use of sparse secrets. Our design choices allow SMAUG to balance the decryption failure probability and ciphertext sizes without utilizing error correction codes, whose side-channel resistance remains open.
With a constant-time C reference implementation, SMAUG achieves ciphertext sizes up to 12% and 9% smaller than Kyber and Saber, with much faster running time, up to 103% and 58%, respectively. Compared to Sable, SMAUG has the same ciphertext sizes but a larger public key, which gives a trade-off between the public key size versus performance; SMAUG has 39%-55% faster encapsulation and decapsulation speed in the parameter sets having comparable security.
Vasyl Ustimenko, Aneta Wróblewska
We introduce large groups of quadratic transformations of a vector space over the finite fields defined via symbolic computations with the usage of
algebraic constructions of Extremal Graph Theory. They can serve as platforms for the protocols of Noncommutative Cryptography with security based on the complexity of word decomposition problem in noncommutative polynomial transformation group.
The modifications of these symbolic computations in the case of large fields of characteristic two allow us to define quadratic bijective multivariate public keys such that the inverses of public maps has a large polynomial degree. Another family of public keys is defined over arbitrary commutative ring with unity.
We suggest the usage of constructed protocols for the private delivery of quadratic encryption maps instead of the public usage of these transformations, i.e. the idea of temporal multivariate rules with their periodical change.
Koustabh Ghosh, Joan Daemen
In this paper, we study the differential properties of integer multiplication between two $w$-bit integers, resulting in a $2w$-bit integer. Our objective is to gain insights into its resistance against differential cryptanalysis and asses its suitability as a source of non-linearity in symmetric key primitives.
Julie Ha, Chloe Cachet, Luke Demarest, Sohaib Ahmad, Benjamin Fuller
Biometric databases are being deployed with few cryptographic protections. Because of the nature of biometrics, privacy breaches affect users for their entire life.
This work introduces Private Eyes, the first zero-leakage biometric database. The only leakage of the system is unavoidable: 1) the log of the dataset size and 2) the fact that a query occurred. Private Eyes is built from symmetric searchable encryption. Proximity queries are the required functionality: given a noisy reading of a biometric, the goal is to retrieve all stored records that are close enough according to a distance metric.
Private Eyes combines locality sensitive-hashing or LSHs (Indyk and Motwani, STOC 1998) and encrypted maps. One searches for the disjunction of the LSHs of a noisy biometric reading. The underlying encrypted map needs to efficiently answer disjunction queries.
We focus on the iris biometric. Iris biometric data requires a large number of LSHs, approximately 1000. The most relevant prior work is in zero-leakage k-nearest-neighbor search (Boldyreva and Tang, PoPETS 2021), but that work is designed for a small number of LSHs.
Our main cryptographic tool is a zero-leakage disjunctive map designed for the setting when most clauses do not match any records. For the iris, on average at most 6% of LSHs match any stored value.
To aid in evaluation, we produce a synthetic iris generation tool to evaluate sizes beyond available iris datasets. This generation tool is a simple generative adversarial network. Accurate statistics are crucial to optimizing the cryptographic primitives so this tool may be of independent interest.
Our scheme is implemented and open-sourced. For the largest tested parameters of 5000 stored irises, search requires 26 rounds of communication and 26 minutes of single-threaded computation.
Ghada Arfaoui, Thibaut Jacques, Marc Lacoste, Cristina Onete, Léo Robert
In multi-tenant cloud environments, physical resources are shared between various parties (called tenants) through the use of virtual machines (VMs). Tenants can verify the state of their VMs by means of deep-attestation: a process by which a (physical or virtual) Trusted Platform Module --TPM -- generates attestation quotes about the integrity state of the VMs. Unfortunately, most existing deep-attestation solutions are either: limited to single-tenant environments, in which tenant {privacy is irrelevant; are inefficient in terms of {linking VM attestations to hypervisor attestations; or provide privacy and/or linking, but at the cost of modifying the TPM hardware.
In this paper, we propose a privacy preserving TPM-based deep-attestation solution in multi-tenant environments, which provably guarantees: (i) Inter-tenant privacy: a tenant is unaware of whether or not the physical machine hosting its VMs also contains other VMs (belonging to other tenants); (ii) Configuration privacy: the hypervisor's configuration, used in the attestation process, remains private with respect to the tenants requiring a hypervisor attestation; and (iii) Layer linking: our protocol enables tenants to link hypervisors with the VMs, thus obtaining a guarantee that their VMs are running on specific physical machines.
Our solution relies on vector commitments and ZK-SNARKs. We build on the security model of Arfaoui et al. and provide both formalizations of the properties we require and proofs that our scheme does, in fact attain them. Our protocol is scalable, and our implementation results prove that it is viable, even for a large number of VMs hosted on a single platform.
In this paper, we propose a privacy preserving TPM-based deep-attestation solution in multi-tenant environments, which provably guarantees: (i) Inter-tenant privacy: a tenant is unaware of whether or not the physical machine hosting its VMs also contains other VMs (belonging to other tenants); (ii) Configuration privacy: the hypervisor's configuration, used in the attestation process, remains private with respect to the tenants requiring a hypervisor attestation; and (iii) Layer linking: our protocol enables tenants to link hypervisors with the VMs, thus obtaining a guarantee that their VMs are running on specific physical machines.
Our solution relies on vector commitments and ZK-SNARKs. We build on the security model of Arfaoui et al. and provide both formalizations of the properties we require and proofs that our scheme does, in fact attain them. Our protocol is scalable, and our implementation results prove that it is viable, even for a large number of VMs hosted on a single platform.
Dimitri Mankowski, Thom Wiggers, Veelasha Moonsamy
The ubiquitous use of smartphones has contributed to more and more users conducting their online browsing activities through apps, rather than web browsers. In order to provide a seamless browsing experience to the users, apps rely on a variety of HTTP-based APIs and third-party libraries, and make use of the TLS protocol to secure the underlying communication. With NIST's recent announcement of the first standards for post-quantum algorithms, there is a need to better understand the constraints and requirements of TLS usage by Android apps in order to make an informed decision for migration to the post-quantum world.
In this paper, we performed an analysis of TLS usage by highest-ranked apps from Google Play Store to assess the resulting overhead for adoption of post-quantum algorithms. Our results show that apps set up large numbers of TLS connections with a median of 94, often to the same hosts. At the same time, many apps make little use of resumption to reduce the overhead of the TLS handshake. This will greatly magnify the impact of the transition to post-quantum cryptography, and we make recommendations for developers, server operators and the mobile operating systems to invest in making more use of these mitigating features or improving their accessibility. Finally, we briefly discuss how alternative proposals for post-quantum TLS handshakes might reduce the overhead.
In this paper, we performed an analysis of TLS usage by highest-ranked apps from Google Play Store to assess the resulting overhead for adoption of post-quantum algorithms. Our results show that apps set up large numbers of TLS connections with a median of 94, often to the same hosts. At the same time, many apps make little use of resumption to reduce the overhead of the TLS handshake. This will greatly magnify the impact of the transition to post-quantum cryptography, and we make recommendations for developers, server operators and the mobile operating systems to invest in making more use of these mitigating features or improving their accessibility. Finally, we briefly discuss how alternative proposals for post-quantum TLS handshakes might reduce the overhead.
Vasyl Ustimenko, Tymoteusz Chojecki
Classical Multivariate Cryptography (MP) is searching for special families of functions of kind ^nF=T_1FTT_2 on the vector space V= (F_q)^n where F is a quadratic or cubical polynomial map of the space to itself, T_1 and T^2 are affine transformations and T is the piece of information such that the knowledge of the triple T_1, T_2, T allows the computation of reimage x of given nF(x) in polynomial time O(n^ᾳ). Traditionally F is given by the list of coefficients C(^nF) of its monomial terms ordered lexicographically. We consider the Inverse Problem of MP of finding T_1, T_2, T for F given in its standard form. The solution of inverse problem is harder than finding the procedure to compute the reimage of ^nF in time O(n^ᾳ). For general quadratic or cubic maps nF this is NP hard problem. In the case of special family some arguments on its inclusion to class NP has to be given.
Quentin L. Meunier, Abdul Rahman Taleb
Side-Channel Attacks are powerful attacks which can recover secret information in a cryptographic device by analysing physical quantities such as power consumption. Masking is a common countermeasure to these attacks which can be applied in software and hardware, and consists in splitting the secrets in several parts. Masking schemes and their implementations are often not trivial, and require the use of automated tools to check for their correctness.
In this work, we propose a new practical tool named VerifMSI which extends an existing verification tool called LeakageVerif targeting software schemes. Compared to LeakageVerif, VerifMSI includes hardware constructs, namely gates and registers, what allows to take glitch propagation into account. Moreover, it includes a new representation of the inputs, making it possible to verify three existing security properties (Non-Interference, Strong Non-Interference, Probe Isolating Non-Interference) as well as a newly defined one called Relaxed Non-Interference, compared to the unique Threshold Probing Security verified in LeakageVerif. Finally, optimisations have been integrated in VerifMSI in order to speed up the verification.
We evaluate VerifMSI on a set of 9 benchmarks from the literature, focusing on the hardware descriptions, and show that it performs well both in terms of accuracy and scalability.
Bo-Yin Yang, Wei-Jeng Wang, Shang-Yi Yang, Char-Shin Miou, Chen-Mou Cheng
Solving multivariate polynomial systems over finite fields is an important
problem in cryptography. For random F2 low-degree systems with equally many
variables and equations, enumeration is more efficient than advanced solvers for all
practical problem sizes. Whether there are others remained an open problem.
We here study and propose an exhaustive-search algorithm for low degrees systems
over F3 which is suitable for parallelization. We implemented it on Graphic Processing
Units (GPUs) and commodity CPUs. Its optimizations and differences from the F2
case are also analyzed.
We can solve 30+ quadratic equations in 30 variables on an NVIDIA GeForce GTX
980 Ti in 14 minutes; a cubic system takes 36 minutes. This well outperforms
existing solvers. Using these results, we compare Gröbner Bases vs. enumeration for
polynomial systems over small fields as the sizes go up.
22 May 2023
Graz, Austria, 1 September - 4 September 2023
Event date: 1 September to 4 September 2023
Warszawa, Polska, 31 July - 3 August 2023
Event date: 31 July to 3 August 2023
Anubhab Baksi
In the design of GIFT, half round key XOR is used. This leads to the undesired consequence that the security against the differential/linear attacks are overestimated. This comes from the observation that; in the usual DDT/LAT based analysis of the differential/linear attacks, the inherent assumption is the full round key is XORed at each round.
Yang Yu, Huiwen Jia, Xiaoyun Wang
Lattice gadgets and the associated algorithms are the essential building blocks of lattice-based cryptography. In the past decade, they have been applied to build versatile and powerful cryptosystems. However, the practical optimizations and designs of gadget-based schemes generally lag their theoretical constructions.
For example, the gadget-based signatures have elegant design and capability of extending to more advanced primitives, but they are far less efficient than other lattice-based signatures.
This work aims to improve the practicality of gadget-based cryptosystems, with a focus on hash-and-sign signatures. To this end, we develop a compact gadget framework in which the used gadget is a square matrix instead of the short and fat one used in previous constructions. To work with this compact gadget, we devise a specialized gadget sampler, called semi-random sampler, to compute the approximate preimage. It first deterministically computes the error and then randomly samples the preimage. We show that for uniformly random targets, the preimage and error distributions are simulatable without knowing the trapdoor. This ensures the security of the signature applications. Compared to the Gaussian-distributed errors in previous algorithms, the deterministic errors have a smaller size, which lead to a substantial gain in security and enables a practically working instantiation.
As the applications, we present two practically efficient gadget-based signature schemes based on NTRU and Ring-LWE respectively. The NTRU-based scheme offers comparable efficiency to Falcon and Mitaka and a simple implementation without the need of generating the NTRU trapdoor. The LWE-based scheme also achieves a desirable overall performance. It not only greatly outperforms the state-of-the-art LWE-based hash-and-sign signatures, but also has an even smaller size than the LWE-based Fiat-Shamir signature scheme Dilithium. These results fill the long-term gap in practical gadget-based signatures.
This work aims to improve the practicality of gadget-based cryptosystems, with a focus on hash-and-sign signatures. To this end, we develop a compact gadget framework in which the used gadget is a square matrix instead of the short and fat one used in previous constructions. To work with this compact gadget, we devise a specialized gadget sampler, called semi-random sampler, to compute the approximate preimage. It first deterministically computes the error and then randomly samples the preimage. We show that for uniformly random targets, the preimage and error distributions are simulatable without knowing the trapdoor. This ensures the security of the signature applications. Compared to the Gaussian-distributed errors in previous algorithms, the deterministic errors have a smaller size, which lead to a substantial gain in security and enables a practically working instantiation.
As the applications, we present two practically efficient gadget-based signature schemes based on NTRU and Ring-LWE respectively. The NTRU-based scheme offers comparable efficiency to Falcon and Mitaka and a simple implementation without the need of generating the NTRU trapdoor. The LWE-based scheme also achieves a desirable overall performance. It not only greatly outperforms the state-of-the-art LWE-based hash-and-sign signatures, but also has an even smaller size than the LWE-based Fiat-Shamir signature scheme Dilithium. These results fill the long-term gap in practical gadget-based signatures.
Kevin Choi, Aathira Manoj, Joseph Bonneau
Motivated and inspired by the emergence of blockchains, many new protocols have recently been proposed for generating publicly verifiable randomness in a distributed yet secure fashion. These protocols work under different setups and assumptions, use various cryptographic tools, and entail unique trade-offs and characteristics. In this paper, we systematize the design of distributed randomness beacons (DRBs) as well as the cryptographic building blocks they rely on. We evaluate protocols on two key security properties, unbiasability and unpredictability, and discuss common attack vectors for predicting or biasing the beacon output and the countermeasures employed by protocols. We also compare protocols by communication and computational efficiency. Finally, we provide insights on the applicability of different protocols in various deployment scenarios and highlight possible directions for further research.
Marwan Zeggari, Aydin Abadi, Renaud Lambiotte, Mohamad Kassab
Sneakers were designated as the most counterfeited fashion item online, with three times more risk in a trade than any other fashion purchase. As the market expands, the current sneaker scene displays several vulnerabilities and trust flaws, mostly related to the legitimacy of assets or actors. In this paper, we investigate various blockchain-based mechanisms to address these large-scale trust issues. We argue that (i) pre-certified and tracked assets through the use of non-fungible tokens can ensure the genuine nature of an asset and authenticate its owner more effectively during peer-to-peer trading across a marketplace; (ii) a game-theoretic-based system with economic incentives for participating users can greatly reduce the rate of online fraud and address missed delivery deadlines; (iii) a decentralized dispute resolution system biased in favour of an honest party can solve potential conflicts more reliably.
Zhengjun Cao, Lihua Liu
We show that the key agreement scheme [Internet of Things, 2022(18): 100493] is flawed. (1) It neglects the structure of an elliptic curve and presents some false computations. (2) The scheme is insecure against key compromise impersonation attack.
Christof Beierle, Patrick Felke, Gregor Leander, Patrick Neumann, Lukas Stennes
Recent constructions of (tweakable) block ciphers with an embedded cryptographic backdoor relied on the existence of probability-one differentials or perfect (non-)linear approximations over a reduced-round version of the primitive. In this work, we study how the existence of probability-one differentials or perfect linear approximations over two rounds of a substitution-permutation network can be avoided by design. More precisely, we develop criteria on the s-box and the linear layer that guarantee the absence of probability-one differentials for all keys. We further present an algorithm that allows to efficiently exclude the existence of keys for which there exists a perfect linear approximation.
Lichao Wu, Guilherme Perin, Stjepan Picek
The ASCADv2 dataset ranks among the most secure publicly available datasets today. Two layers of countermeasures protect it: affine masking and shuffling, and the current attack approaches rely on strong assumptions. Specifically, besides having access to the source code, an adversary also requires prior knowledge of random shares. This paper forgoes reliance on such knowledge and proposes two attack approaches based on the vulnerabilities of the affine mask implementation. As a result, the first attack can retrieve all secret keys' reliance in less than a minute. Although the second attack is not entirely successful in recovering all keys, we believe more traces would help make such an attack fully functional.