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:
14 November 2023
Andrea Coladangelo, Sam Gunn
Quantum copy protection, introduced by Aaronson, enables giving out a quantum program-description that cannot be meaningfully duplicated. Despite over a decade of study, copy protection is only known to be possible for a very limited class of programs.
As our first contribution, we show how to achieve "best-possible" copy protection for all programs. We do this by introducing quantum state indistinguishability obfuscation (qsiO), a notion of obfuscation for quantum descriptions of classical programs. We show that applying qsiO to a program immediately achieves best-possible copy protection.
Our second contribution is to show that, assuming injective one-way functions exist, qsiO is concrete copy protection for a large family of puncturable programs --- significantly expanding the class of copy-protectable programs. A key tool in our proof is a new variant of unclonable encryption (UE) that we call coupled unclonable encryption (cUE). While constructing UE in the standard model remains an important open problem, we are able to build cUE from one-way functions. If we additionally assume the existence of UE, then we can further expand the class of puncturable programs for which qsiO is copy protection.
Finally, we construct qsiO relative to an efficient quantum oracle.
As our first contribution, we show how to achieve "best-possible" copy protection for all programs. We do this by introducing quantum state indistinguishability obfuscation (qsiO), a notion of obfuscation for quantum descriptions of classical programs. We show that applying qsiO to a program immediately achieves best-possible copy protection.
Our second contribution is to show that, assuming injective one-way functions exist, qsiO is concrete copy protection for a large family of puncturable programs --- significantly expanding the class of copy-protectable programs. A key tool in our proof is a new variant of unclonable encryption (UE) that we call coupled unclonable encryption (cUE). While constructing UE in the standard model remains an important open problem, we are able to build cUE from one-way functions. If we additionally assume the existence of UE, then we can further expand the class of puncturable programs for which qsiO is copy protection.
Finally, we construct qsiO relative to an efficient quantum oracle.
Akhil Bandarupalli, Adithya Bhat, Saurabh Bagchi, Aniket Kate, Michael Reiter
Regular access to unpredictable and bias-resistant randomness is important for applications such as blockchains, voting, and secure distributed computing. Distributed random beacon protocols address this need by distributing trust across multiple nodes, with the majority of them assumed to be honest. These protocols have found applications in blockchain technology, leading to the proposal of several distributed random beacon protocols, with some already implemented. However, many current random beacon systems rely on threshold cryptographic setups or exhibit high computational costs, while others assume partial or bounded synchronous networks. To overcome these limitations, we propose HashRand, a computation and communication-efficient asynchronous random beacon protocol that uses a secure Hash function to generate beacons and pairwise secure channels. HashRand has a per-node communication complexity of $\mathcal{O}(\lambda n \log(n))$ bits per beacon. The computational efficiency of HashRand is attributed to the two orders of magnitude lower time of a one-way Hash computation compared to discrete log exponentiation. Interestingly, besides reduced overhead, HashRand achieves Post-Quantum security by leveraging the secure Hash function against quantum adversaries, setting it apart from other random beacon protocols that use discrete log cryptography. In a geo-distributed testbed of $n=160$ nodes, HashRand produces 1 beacon every second, which is at least 4x higher than Spurt. We also demonstrate the practical utility of HashRand by implementing a Post-Quantum secure Asynchronous SMR protocol, which has a response rate of over 122k txns per second over a WAN at $n=40$ nodes.
Cecilia Boschini, Hila Dahari, Moni Naor, Eyal Ronen
The Snowden's revelations kick-started a community-wide effort to develop cryptographic tools against mass surveillance.
In this work, we propose to add another primitive to that toolbox: Fail-Stop Signatures (FSS) [EC'89].
FSS are digital signatures enhanced with a forgery-detection mechanism that can protect a PPT signer from more powerful attackers.
Despite the fascinating concept, research in this area stalled after the '90s. However, the ongoing transition to post-quantum cryptography, with its hiccups due to the novelty of underlying assumptions, has become the perfect use case for FSS.
This paper aims to reboot research on FSS with practical use in mind: Our framework for FSS includes ``fine-grained'' security definitions (that assume a powerful, but bounded adversary e.g: can break $128$-bit of security, but not $256$-bit).
As an application, we show new FSS constructions for the post-quantum setting.
We show that FSS are equivalent to standard, provably secure digital signatures that do not require rewinding or programming random oracles, and that this implies lattice-based FSS.
Our main construction is an FSS version of SPHINCS, which required building FSS versions of all its building blocks: WOTS, XMSS, and FORS.
In the process, we identify and provide generic solutions for two fundamental issues arising when deriving a large number of private keys from a single seed, and when building FSS for Hash-and-Sign-based signatures.
Sophie Stevens
The Internet Key Exchange version 2 (IKEv2) (RFC 7296) is a component of IPsec used to authenticate two parties (the initiator and responder) to each other and to establish a set of security parameters for the communications. The security parameters include secret keys to encrypt and authenticate data as well as the negotiation of a set of cryptographic algorithms. The core documentation uses exclusively Diffie-Hellman exchanges to agree the security information. However, this is not a quantum-secure option due to the ability of Shor's algorithm to break the security assumption underlying the Diffie-Hellman. A post-quantum solution is to include a preshared key in the exchange, as proposed by the extension RFC 8784; assuming that this preshared key has sufficient entropy, the keys created in the IKEv2 exchange will be resistant to a quantum computer. In this paper, we investigate the security claims of RFC 8784 using formal verification methods. We find that keys created using the preshared key are secret from an adversary. However, certain authentication properties of the protocol that are weakened under the assumption that Diffie-Hellman is insecure are not recovered using the preshared key.
Raja Adhithan Radhakrishnan
This paper introduces a novel approach to enhancing cryp-
tographic security. It proposes the use of one-time message sharing com-
bined with Physically Unclonable Functions (PUF) to securely exchange
keys and generate an S-subbyte-box for encryption. This innovative tech-
nique aims to elevate the security standards of cryptographic applica-
tions.
Pierrick Dartois, Luciano Maino, Giacomo Pope, Damien Robert
In this paper, we describe an algorithm to compute chains of $(2,2)$-isogenies between products of elliptic curves in the theta model. The description of the algorithm is split into various subroutines to allow for a precise field operation counting.
We present a constant time implementation of our algorithm in Rust and an alternative implementation in SageMath. Our work in SageMath runs ten times faster than a comparable implementation of an isogeny chain using the Richelot correspondence. The Rust implementation runs up to forty times faster than the equivalent isogeny in SageMath and has been designed to be portable for future research in higher-dimensional isogeny-based cryptography.
We present a constant time implementation of our algorithm in Rust and an alternative implementation in SageMath. Our work in SageMath runs ten times faster than a comparable implementation of an isogeny chain using the Richelot correspondence. The Rust implementation runs up to forty times faster than the equivalent isogeny in SageMath and has been designed to be portable for future research in higher-dimensional isogeny-based cryptography.
Paderborn University, Department of Computer Science, Paderborn, Germany
With the Institute for Photonic Quantum Systems (PhoQS), Paderborn University wants to establish an international research centre in the field of photonic quantum technologies. The aim is to develop new technologies for photon-based quantum applications as well as new theoretical and experimental concepts and research approaches. Ultimately, the focus is on understanding and controlling photonic quantum simulators and quantum computers.
In the Faculty of Electrical Engineering, Computer Science and Mathematics, the Institute of Computer Science - Department "Codes and Cryptography" - has a vacancy for a
Postdoc (m/f/d)
(salary is according to 13 TV-L)
position with 100% of the regular working hours within the framework of the MKW (Ministry of Culture and Science of the State of North Rhine-Westphalia) NRW project "Photonic Quantum Computing (PhoQC)". The employment is initially limited to three years and is based on the legal regulations of the WissZeitVG.
Your duties and responsibilities:
- Complexity-theoretical analysis of boson sampling-like experiments
- Development of quantum algorithms using boson sampling for practical applications
- Development and analysis of theoretical frameworks for universal quantum computing based on quantum photonics
Hiring requirements:
- Completed PhD in computer science, mathematics or physics or comparable qualification
It is expected that the applicant has experience in at least one of the following areas:
- Quantum algorithms
- Quantum complexity
- Theoretical quantum photonics
- Quantum information theory
Postdoc (m/f/d)
(salary is according to 13 TV-L)
position with 100% of the regular working hours within the framework of the MKW (Ministry of Culture and Science of the State of North Rhine-Westphalia) NRW project "Photonic Quantum Computing (PhoQC)". The employment is initially limited to three years and is based on the legal regulations of the WissZeitVG.
Your duties and responsibilities:
- Complexity-theoretical analysis of boson sampling-like experiments
- Development of quantum algorithms using boson sampling for practical applications
- Development and analysis of theoretical frameworks for universal quantum computing based on quantum photonics
Hiring requirements:
- Completed PhD in computer science, mathematics or physics or comparable qualification
It is expected that the applicant has experience in at least one of the following areas:
- Quantum algorithms
- Quantum complexity
- Theoretical quantum photonics
- Quantum information theory
Closing date for applications:
Contact: Please send your application including a CV (preferably in a single pdf file) using the Ref. No. 6207 by bloemer@upb.de. Information regarding the processing of your person data can be located at: https://www.uni-paderborn.de/en/zv/personaldatenschutz.
More information: https://cs.uni-paderborn.de/en/cuk/?cHash=8829d72369c94558f8571cc307314a2c
Luxembourg Institute of Science and Technology (LIST), Luxembourg
LIST is looking for a highly motivated candidate with proven skills in federated data processing such as applying simple statistics or advanced machine learning tools, to improve the utility of the obtained information. For example, collaborative cyberthreat intelligence systems that use advanced analytics solutions can offer significant advantages over the local systems by detecting cyberattacks early and promptly responding to them. While recent developments in cryptography and the rise of homomorphic encryption and secure multi-party computation allow operations without revealing the underlying data in cleartext, these technologies still suffer from a noticeable overhead in terms of computation and communication. The main mission of the candidate, together with local and international collaborators, is to continue research on these technologies to address scalability and performance requirements.
Closing date for applications:
Contact: Dr. Qiang Tang (qiang.tang@list.lu)
Abu Dhabi, United Arab Emirates, 5 March - 8 March 2024
Event date: 5 March to 8 March 2024
13 November 2023
Jong-Yeon Park, Jang-Won Ju, Wonil Lee, Bo-Gyeong Kang, Yasuyuki Kachi, Kouichi Sakurai
As NIST is putting the final touches on the standardization of PQC (Post Quantum Cryptography) public key algorithms, it is a racing certainty that peskier cryptographic attacks undeterred by those new PQC algorithms will surface. Such a trend in turn will prompt more follow-up studies of attacks and countermeasures. As things stand, from the attackers’ perspective, one viable form of attack that can be implemented thereupon is the so-called “side-channel attack”. Two best-known countermeasures heralded to be durable against side-channel attacks are: “masking” and “hiding”. In that dichotomous picture, of particular note are successful single-trace attacks on some of the NIST’s PQC then-candidates, which worked to the detriment of the former: “masking”. In this paper, we cast an eye over the latter: “hiding”. Hiding proves to be durable against both side-channel attacks and another equally robust type of attacks called “fault injection attacks”, and hence is deemed an auspicious countermeasure to be implemented. Mathematically, the hiding method is fundamentally based on random permutations. There has been a cornucopia of studies on generating random permutations. However, those are not tied to implementation of the hiding method. In this paper, we propose a reliable and efficient verification of permutation implementation, through employing Fisher–Yates’ shuffling method. We introduce the concept of an ?-th order permutation and explain how it can be used to verify that our implementation is more efficient than its previous-gen counterparts for hiding countermeasures.
Aarushi Goel, Mathias Hall-Andersen, Gabriel Kaptchuk
Existing protocols for proving the correct execution of a RAM program in zero-knowledge are plagued by a processor expressiveness trade-off : supporting fewer instructions results in smaller processor circuits (which improves performance), but may result in more program execution steps because non-supported instruction must be emulated over multiple processor steps (which diminishes performance).
We present Dora, a concretely efficient zero-knowledge protocol for RAM programs that sidesteps this tension by making it (nearly) free to add additional instructions to the processor. The computational and communication complexity of proving each step of a computation in Dora, is constant in the number of supported instructions. Dora is also highly generic and only assumes the existence of linearly homomorphic commitments. We implement Dora and demonstrate that on commodity hardware it can prove the correct execution of a processor with thousands of instruction, each of which has thousands of gates, in just a few milliseconds per step.
We present Dora, a concretely efficient zero-knowledge protocol for RAM programs that sidesteps this tension by making it (nearly) free to add additional instructions to the processor. The computational and communication complexity of proving each step of a computation in Dora, is constant in the number of supported instructions. Dora is also highly generic and only assumes the existence of linearly homomorphic commitments. We implement Dora and demonstrate that on commodity hardware it can prove the correct execution of a processor with thousands of instruction, each of which has thousands of gates, in just a few milliseconds per step.
Lorenz Panny
A recent preprint [ePrint 2023/1475] suggests the use of polynomials over a tropical algebra to construct a digital signature scheme "based on" the problem of factoring such polynomials, which is known to be NP‑hard.
This short note presents two very efficient forgery attacks on the scheme, bypassing the need to factorize tropical polynomials and thus demonstrating that security in fact rests on a different, empirically easier problem.
Pierrick Dartois, Luciano Maino, Giacomo Pope, Damien Robert
In this paper, we describe an algorithm to compute chains of $(2,2)$-isogenies between products of elliptic curves in the theta model. The description of the algorithm is split into various subroutines to allow for a precise field operation counting.
We present a constant time implementation of our algorithm in Rust and an alternative implementation in SageMath. Our work in SageMath runs ten times faster than a comparable implementation of an isogeny chain using the Richelot correspondence. The Rust implementation runs up to forty times faster than the equivalent isogeny in SageMath and has been designed to be portable for future research in higher-dimensional isogeny-based cryptography.
We present a constant time implementation of our algorithm in Rust and an alternative implementation in SageMath. Our work in SageMath runs ten times faster than a comparable implementation of an isogeny chain using the Richelot correspondence. The Rust implementation runs up to forty times faster than the equivalent isogeny in SageMath and has been designed to be portable for future research in higher-dimensional isogeny-based cryptography.
Claude Carlet, Abderrahman Daif, Sylvain Guilley, Cédric Tavernier
In the attacker models of Side-Channel Attacks (SCA) and Fault Injection Attacks (FIA), the opponent has access to a noisy version of the internal behavior of the hardware. Since the end of the nineties, many works have shown that this type of attacks constitutes a serious threat to cryptosystems implemented in embedded devices. In the state-of-the-art, there exist several countermeasures to protect symmetric encryption (especially AES-128). Most of them protect only against one of these two attacks (either SCA or FIA). The main known counter-measure against SCA is masking; it makes the complexity of SCA growing exponentially with its order d. The most general version of masking is based on error correcting codes. It has the advantage of offering in principle a protection against both types of attacks (SCA and FIA), but all the functions implemented in the algorithm need to be masked accordingly, and this is not a simple task in general. We propose a particular version of such construction that has several advantages: it has a very low computation complexity, it offers a concrete protection against both SCA and FIA, and finally it allows flexibility: being not specifically dedicated to AES, it can be applied to any block cipher with any S-boxes. In the state-of-art, masking schemes all come with pros and cons concerning the different types of complexity (time, memory, amount of randomness). Our masking scheme concretely achieves the complexity of the best known scheme, for each complexity type
Remi Geraud-Stewart, David Naccache
Given a set of matrices $\mathbf{A} := \{A_0, \dotsc, A_{k-1}\}$, and a matrix $M$ guaranteed to be the product of some ordered subset of $\mathbf{L}\subset\mathbf{A}$, can $\mathbf{L}$ be efficiently recovered? We begin by observing that the answer is positive under some assumptions on $\mathbf{A}$.
Noting that appropriate transformations seem to make $\mathbf{L}$'s recovery difficult we provide the blueprint of two new public-key cryptosystems based upon this problem.
We term those constructions "blueprints because, given their novelty, we are still uncertain of their exact security. Yet, we daringly conjecture that even if attacks are found on the proposed constructions, these attacks could be thwarted by adjustments in the key generation, key size or the encryption mechanism, thereby resulting on the long run in fully-fledged public-key cryptosystems that do not seem to belong to any of the mainstream public-key encryption paradigms known to date.
Noting that appropriate transformations seem to make $\mathbf{L}$'s recovery difficult we provide the blueprint of two new public-key cryptosystems based upon this problem.
We term those constructions "blueprints because, given their novelty, we are still uncertain of their exact security. Yet, we daringly conjecture that even if attacks are found on the proposed constructions, these attacks could be thwarted by adjustments in the key generation, key size or the encryption mechanism, thereby resulting on the long run in fully-fledged public-key cryptosystems that do not seem to belong to any of the mainstream public-key encryption paradigms known to date.
Andreas Brüggemann, Oliver Schick, Thomas Schneider, Ajith Suresh, Hossein Yalame
Secure multi-party computation (MPC) enables (joint) computations on sensitive data while maintaining privacy. In real-world scenarios, asymmetric trust assumptions are often most realistic, where one somewhat trustworthy entity interacts with smaller clients. We generalize previous two-party computation (2PC) protocols like MUSE (USENIX Security'21) and SIMC (USENIX Security'22) to the three-party setting (3PC) with one malicious party, avoiding the performance limitations of dishonest-majority inherent to 2PC.
We introduce two protocols, Auxiliator and Socium, in a machine learning (ML) friendly design with a fast online phase and novel verification techniques in the setup phase. These protocols bridge the gap between prior 3PC approaches that considered either fully semi-honest or malicious settings. Auxiliator enhances the semi-honest two-party setting with a malicious helper, significantly improving communication by at least two orders of magnitude. Socium extends the client-malicious setting with one malicious client and a semi-honest server, achieving substantial communication improvement by at least one order of magnitude compared to SIMC.
Besides an implementation of our new protocols, we provide the first open-source implementation of the semi-honest 3PC protocol ASTRA (CCSW'19) and a variant of the malicious 3PC protocol SWIFT (USENIX Security'21).
We introduce two protocols, Auxiliator and Socium, in a machine learning (ML) friendly design with a fast online phase and novel verification techniques in the setup phase. These protocols bridge the gap between prior 3PC approaches that considered either fully semi-honest or malicious settings. Auxiliator enhances the semi-honest two-party setting with a malicious helper, significantly improving communication by at least two orders of magnitude. Socium extends the client-malicious setting with one malicious client and a semi-honest server, achieving substantial communication improvement by at least one order of magnitude compared to SIMC.
Besides an implementation of our new protocols, we provide the first open-source implementation of the semi-honest 3PC protocol ASTRA (CCSW'19) and a variant of the malicious 3PC protocol SWIFT (USENIX Security'21).
Kazumasa Shinagawa, Koji Nuida
Private Simultaneous Messages (PSM) is a minimal model of secure computation, where the input players with shared randomness send messages to the output player simultaneously and only once. In this field, finding upper and lower bounds on communication complexity of PSM protocols is important, and in particular, identifying the optimal one where the upper and lower bounds coincide is the ultimate goal. However, up until now, functions for which the optimal communication complexity has been determined are few: An example of such a function is the two-input AND function where $(2\log_2 3)$-bit communication is optimal. In this paper, we provide new upper and lower bounds for several concrete functions. For lower bounds, we introduce a novel approach using combinatorial objects called abstract simplicial complexes to represent PSM protocols. Our method is suitable for obtaining non-asymptotic explicit lower bounds for concrete functions. By deriving lower bounds and constructing concrete protocols, we show that the optimal communication complexity for the equality and majority functions with three input bits are $3\log_2 3$ bits and $6$ bits, respectively. We also derive new lower bounds for the $n$-input AND function, three-valued comparison function, and multiplication over finite rings.
Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Hendrik Waldner
A central direction of research in secure multiparty computation with dishonest majority
has been to achieve three main goals:
1. reduce the total number of rounds of communication (to four, which is optimal); 2. use only polynomial-time hardness assumptions, and 3. rely solely on cryptographic assumptions in a black-box manner.
This is especially challenging when we do not allow a trusted setup assumption of any kind. While protocols achieving two out of three goals in this setting have been designed in recent literature, achieving all three simultaneously remained an elusive open question. Specifically, it was answered positively only for a restricted class of functionalities. In this paper, we completely resolve this long-standing open question. Specifically, we present a protocol for all polynomial-time computable functions that does not require any trusted setup assumptions and achieves all three of the above goals simultaneously.
1. reduce the total number of rounds of communication (to four, which is optimal); 2. use only polynomial-time hardness assumptions, and 3. rely solely on cryptographic assumptions in a black-box manner.
This is especially challenging when we do not allow a trusted setup assumption of any kind. While protocols achieving two out of three goals in this setting have been designed in recent literature, achieving all three simultaneously remained an elusive open question. Specifically, it was answered positively only for a restricted class of functionalities. In this paper, we completely resolve this long-standing open question. Specifically, we present a protocol for all polynomial-time computable functions that does not require any trusted setup assumptions and achieves all three of the above goals simultaneously.
Prabhanjan Ananth, Aditya Gulati, Fatih Kaleoglu, Yao-Ting Lin
We introduce a new notion called ${\cal Q}$-secure pseudorandom isometries (PRI). A pseudorandom isometry is an efficient quantum circuit that maps an $n$-qubit state to an $(n+m)$-qubit state in an isometric manner. In terms of security, we require that the output of a $q$-fold PRI on $\rho$, for $ \rho \in {\cal Q}$, for any polynomial $q$, should be computationally indistinguishable from the output of a $q$-fold Haar isometry on $\rho$.
By fine-tuning ${\cal Q}$, we recover many existing notions of pseudorandomness. We present a construction of PRIs and assuming post-quantum one-way functions, we prove the security of ${\cal Q}$-secure pseudorandom isometries (PRI) for different interesting settings of ${\cal Q}$.
We also demonstrate many cryptographic applications of PRIs, including, length extension theorems for quantum pseudorandomness notions, message authentication schemes for quantum states, multi-copy secure public and private encryption schemes, and succinct quantum commitments.
By fine-tuning ${\cal Q}$, we recover many existing notions of pseudorandomness. We present a construction of PRIs and assuming post-quantum one-way functions, we prove the security of ${\cal Q}$-secure pseudorandom isometries (PRI) for different interesting settings of ${\cal Q}$.
We also demonstrate many cryptographic applications of PRIs, including, length extension theorems for quantum pseudorandomness notions, message authentication schemes for quantum states, multi-copy secure public and private encryption schemes, and succinct quantum commitments.
Miguel de Vega, Andrei Lapets, Stanislaw Jarecki, Wicher Malten, Mehmet Ugurbil, Wyatt Howe
Among secure multi-party computation protocols, linear secret sharing schemes often do not rely on cryptographic assumptions and are among the most straightforward to explain and to implement correctly in software. However, basic versions of such schemes either limit participants to evaluating linear operations involving private values or require those participants to communicate synchronously during a computation phase. A straightforward, information-theoretically secure extension to such schemes is presented that can evaluate arithmetic sum-of-products expressions that contain multiplication operations involving non-zero private values. Notably, this extension does not require that participants communicate during the computation phase. Instead, a preprocessing phase is required that is independent of the private input values (but is dependent on the number of factors and terms in the sum-of-products expression).