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:
08 March 2024
Charlotte Lefevre, Bart Mennink
It is known that the sponge construction is tightly indifferentiable from a random oracle up to around $2^{c/2}$ queries, where $c$ is the capacity. In particular, it cannot provide generic security better than half of the underlying permutation size. In this paper, we aim to achieve hash function security beating this barrier. We present a hashing mode based on two $b$-bit permutations named the double sponge. The double sponge can be seen as the sponge embedded within the double block length hashing paradigm, making two permutation calls in parallel interleaved with an efficient mixing function. Similarly to the sponge, the permutation size is split as $b = r+c$, and the underlying compression function absorbs $r$ bits at a time. We prove that the double sponge is indifferentiable from a random oracle up to around $2^{2c/3}$ queries. This means that the double sponge achieves security beyond the birthday bound in the capacity. In addition, if $c>3b/4$, the double sponge beats the birthday bound in the primitive size, to our knowledge being the first hashing mode based on a permutation that accomplices this feature.
Damien Robert
A compilation of various notes written over the years on some algorithms on abelian varieties.
Dan Boneh, Aditi Partap, Lior Rotem
Suppose Alice uses a $t$-out-of-$n$ secret sharing to store her secret key on $n$ servers. Her secret key is protected as long as $t$ of them do not collude. However, what if a less-than-$t$ subset of the servers decides to offer the shares they have for sale? In this case, Alice should be able to hold them accountable, or else nothing prevents them from selling her shares. With this motivation in mind, Goyal, Song, and Srinivasan (CRYPTO 21) introduced the concept of {\em traceable secret sharing}. In such schemes, it is possible to provably trace the leaked secret shares back to the servers who leaked them. Goyal et al.~presented the first construction of a traceable secret sharing scheme. However, secret shares in their construction are quadratic in the secret size, and their tracing algorithm is quite involved as it relies on Goldreich-Levin decoding.
In this work, we put forth new definitions and practical constructions for traceable secret sharing. In our model, some $f < t$ servers output a reconstruction box~$R$ that may arbitrarily depend on their shares. Given additional $t-f$ shares, $R$ reconstructs and outputs the secret. The task is to trace $R$ back to the corrupted servers given black-box access to $R$. Unlike Goyal et al., we do not assume that the tracing algorithm has any information on how the corrupted servers constructed~$R$ from the shares in their possession.
We then present two very efficient constructions of traceable secret sharing based on two classic secret sharing schemes. In both of our schemes, shares are only twice as large as the secret, improving over the quadratic overhead of Goyal et al. Our first scheme is obtained by presenting a new practical tracing algorithm for the widely-used Shamir secret sharing scheme. Our second construction is based on an extension of Blakley's secret sharing scheme. Tracing in this scheme is optimally efficient, and requires just one successful query to $R$. We believe that our constructions are an important step towards bringing traceable secret-sharing schemes to practice. This work also raises several interesting open problems that we describe in the paper.
In this work, we put forth new definitions and practical constructions for traceable secret sharing. In our model, some $f < t$ servers output a reconstruction box~$R$ that may arbitrarily depend on their shares. Given additional $t-f$ shares, $R$ reconstructs and outputs the secret. The task is to trace $R$ back to the corrupted servers given black-box access to $R$. Unlike Goyal et al., we do not assume that the tracing algorithm has any information on how the corrupted servers constructed~$R$ from the shares in their possession.
We then present two very efficient constructions of traceable secret sharing based on two classic secret sharing schemes. In both of our schemes, shares are only twice as large as the secret, improving over the quadratic overhead of Goyal et al. Our first scheme is obtained by presenting a new practical tracing algorithm for the widely-used Shamir secret sharing scheme. Our second construction is based on an extension of Blakley's secret sharing scheme. Tracing in this scheme is optimally efficient, and requires just one successful query to $R$. We believe that our constructions are an important step towards bringing traceable secret-sharing schemes to practice. This work also raises several interesting open problems that we describe in the paper.
Lin Ding, Zhengting Li, Ziyu Guan, Xinhai Wang, Zheng Wu
The DECT Standard Cipher (DSC) is a proprietary stream cipher used for encryption in the Digital Enhanced Cordless Telecommunications (DECT), which is a standard for short range cordless communication and widely deployed worldwide both in residential and enterprise environments. New weaknesses of the DSC stream cipher which are not discovered in previous works are explored and analyzed in this paper. Based on these weaknesses, new practical key recovery attacks and distinguishing attack on DSC with lower time cost are proposed. The first cryptanalytic result show that DSC can be broken in about 13.12 seconds in the known IV setting, when an offline phase that takes about 58.33 minutes is completed. After then, a distinguishing attack on DSC in the related key chosen IV setting is given, which has a time complexity of only 2 encryptions and a success probability of almost 1. Finally, based on the slide property, a key recovery attack on DSC with practical complexities is proposed. The experimental result shows that DSC can be broken on a common PC within about 44.97 seconds in the multiple related key setting. The attacks on DSC proposed in this paper clearly show that a well-designed initialization is absolutely necessary to design a secure stream cipher.
Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, Manuel Vidigueira
Byzantine Agreement (BA) enables $n$ processes to reach consensus on a common valid $L_o$-bit value, even in the presence of up to $tn/3$. Different instantiations of ADA-DARE achieve near-optimal adaptive bit complexity of $O(nL_o + n(f + 1) \kappa)$ for both strong multi-valued validated BA (SMVBA) and interactive consistency (IC). By definition, for IC, $L_o = nL_{in}$, with $L_{in}$ representing the size of an input value.
These results achieve optimal $O(n(L_o+f))$ word complexity and significantly improve the previous best results by up to a linear factor, depending on $L_o$ and $f$.
Xinpeng Yang, Liang Cai, Yinghao Wang, Yinghao Wang, Lu Sun, Jingwei Hu
Multiparty private set intersection (mPSI) protocol is capable of finding the intersection of multiple sets securely without revealing any other information. However, its limitation lies in processing only those elements present in every participant's set, which proves inadequate in scenarios where certain elements are common to several, but not all, sets.
In this paper, we introduce an innovative variant of the mPSI protocol named unbalanced quorum PSI to fill in the gaps of the mPSI protocol. Unlike the previous quorum-PSI proposals which detect elements present in at least $k$ out of $n$ equal sets, our protocol is particularly tailored for unbalanced cases where the size of the receiver's set is much smaller than the size of the senders' sets. Our work achieves logarithmic communication complexity in the semi-honest setting, significantly surpassing previous work in efficiency.
The benchmarks show that it takes 22.7 seconds in WAN and 14.7 seconds in LAN for online computation, and only 87.8 MB of total communication to intersect 5535 elements across 15 sets, each containing $2^{24}$ elements. Compared to prior work, this is roughly an 87$\times$ reduction in communication and a 31$\times$ reduction in online time. Our protocols can be easily extended to the larger set with $2^{28}$ elements which is nearly impractical for prior work.
Muhammed F. Esgin, Thomas Espitau, Guilhem Niot, Thomas Prest, Amin Sakzad, Ron Steinfeld
We introduce a toolkit for transforming lattice-based hash-and-sign signature schemes into masking-friendly signatures secure in the t-probing model. Until now, efficiently masking lattice-based hash-and-sign schemes has been an open problem, with unsuccessful attempts such as Mitaka. A first breakthrough was made in 2023 with the NIST PQC submission Raccoon, although it was not formally proven.
Our main conceptual contribution is to realize that the same principles underlying Raccoon are very generic, and to find a systematic way to apply them within the hash-and-sign paradigm. Our main technical contribution is to formalize, prove, instantiate and implement a hash-and-sign scheme based on these techniques. Our toolkit includes noise flooding to mitigate statistical leaks, and an extended Strong Non-Interfering probing security (SNIu) property to handle masked gadgets with unshared inputs.
We showcase the efficiency of our techniques in a signature scheme, Plover, based on (hint) Ring-LWE. It is the first lattice-based masked hash-and-sign scheme with quasi-linear complexity O(d log d) in the number of shares d. Our performances are competitive with the state-of-the-art masking-friendly signature, the Fiat-Shamir scheme Raccoon.
We showcase the efficiency of our techniques in a signature scheme, Plover, based on (hint) Ring-LWE. It is the first lattice-based masked hash-and-sign scheme with quasi-linear complexity O(d log d) in the number of shares d. Our performances are competitive with the state-of-the-art masking-friendly signature, the Fiat-Shamir scheme Raccoon.
07 March 2024
Corsica, France, 9 September - 13 September 2024
Event date: 9 September to 13 September 2024
Submission deadline: 15 March 2024
Submission deadline: 15 March 2024
Kyoto, Japan, 17 September - 19 September 2024
Event date: 17 September to 19 September 2024
Submission deadline: 16 April 2024
Notification: 20 June 2024
Submission deadline: 16 April 2024
Notification: 20 June 2024
Robert Bosch GmbH, Renningen, Germany
Bosch Research is developing an open source cloud platform (https://carbynestack.io) for computing on encrypted data using Secure Multi-party Computation (MPC). Potential use cases include, but are not limited to, Privacy-Preserving Machine Learning and Privacy-Preserving Data Analytics. For such large computations on big data, active secure MPC becomes quite expensive. Bosch Research is therefore trying to reduce the computational and communication costs of MPC by optimizing the underlying cryptographic primitives and protocols.
Thus, we are looking for a highly motivated PhD candidate with a strong background in applied cryptography and preferably also MPC.
The candidates should meet the following requirements:
Thus, we are looking for a highly motivated PhD candidate with a strong background in applied cryptography and preferably also MPC.
The candidates should meet the following requirements:
- Education: Hold an M.Sc. degree (or equivalent) with excellent grades in IT security or computer science.
- Experience and Knowledge: Strong background in (applied) cryptography with a particular focus on cryptographic protocols/MPC, including security models and basic security proof techniques. Good software development/programming skills.
- Personality and Working Practice: Self-motivated and enthusiastic, independent, reliable, creative, and able to work in an international team with diverse background.
- Language: Fluent English language skills
- become a part of the team and advance research on MPC,
- develop novel approaches to improve the practical efficiency of actively secure MPC protocols,
- design efficient MPC protocols for diverse use-cases, and
- publish and present your results in top-tier journals and at conferences.
Closing date for applications:
Contact: Please submit your application, including your CV, transcripts of records from your Master studies, and a cover letter including your research background and research interest, via: https://smrtr.io/hmG3C
More information: https://smrtr.io/hmG3C
Brandenburg University of Technology Cottbus-Senftenberg, Chair of IT Security
The Young Investigator Group “COSYS - Control Systems and Cyber Security Lab” at the Chair of IT Security at the Brandenburg University of Technology Cottbus-Senftenberg has an open PhD/Postdoc position in the following areas:
- Privacy-Enhancing Technologies in Cyber-Physical Systems.
- AI-based Network Attack Detection and Simulation.
- AI-enabled Penetration Testing.
Closing date for applications:
Contact: Ivan Pryvalov (ivan.pryvalov@b-tu.de)
The University of Edinburgh
The successful candidate will contribute to the formal security specification and design of cryptographic protocols in the Open Finance area. In Open Finance we envision multiple entities, each holding private data, that want to perform joint computation over this data to offer to customers the best possible financial products. The main goal of the project is to investigate what are the security requirements for Open Finance, and then provide a formal security specification (e.g., in the Universal Composable framework) of such a system. The successful candidate will then work on designing a protocol that matches this security definition, and in the final stage of the project, will implement part of the system, focusing on a specific use case. The candidate will be supported by members of the Business School to successfully complete the first phase of the project related to understanding the basic security requirements of an Open Finance system. The majority of the project will be related to the formal design of the system that will be supported by members of the School of Informatics. The project is funded by Input-Output Global. Candidates must have a Ph.D. (or nearing completion) in cryptography or related fields. Evidence of strong research experience as demonstrated through publications at top-tier conferences or high-impact journals is essential. We are looking for a highly motivated candidate with strong initiative and commitment to excellence, and an ability to conduct world-class research. The successful candidate will have the opportunity to work remotely if they require that (as long as they are in the UK). For more info, we refer to the application page.
Application deadline 12/03/2024, 23:59GMT
Closing date for applications:
Contact: Michele Ciampi michele.ciampi@ed.ac.uk
More information: https://elxw.fa.em3.oraclecloud.com/hcmUI/CandidateExperience/en/sites/CX_1001/job/9810
05 March 2024
Max Duparc, Tako Boris Fouotsa, Serge Vaudenay
We present a new post-quantum Public Key Encryption scheme (PKE) named Supersingular Isogeny Lollipop Based Encryption or SILBE. SILBE is obtained by leveraging the generalized lollipop attack of Castryck and Vercauteren on the M-SIDH Key exchange by Fouotsa, Moriya and Petit. Doing so, we can in fact make of SILBE a post-quantum secure Updatable Public Key Encryption scheme (UPKE). SILBE is the first isogeny-based UPKE which is not based on group actions. In its core, SILBE extensively uses both the Deuring Correspondence and Kani's Lemma, two central concepts in Isogeny-Based Cryptography.
Yanyi Liu, Rafael Pass
While classic result in the 1980s establish that one-way functions (OWFs) imply the existence of pseudorandom generators (PRGs) which in turn imply pseudorandom functions (PRFs), the constructions (most notably the one from OWFs to PRGs) is complicated and inefficient.
Consequently, researchers have developed alternative \emph{direct} constructions of PRFs from various different concrete hardness assumptions. In this work, we continue this thread of work and demonstrate the first direct constructions of PRFs from average-case hardness of the time-bounded Kolmogorov complexity problem $\mktp[s]$, where given a threshold, $s(\cdot)$, and a polynomial time-bound, $t(\cdot)$, $\mktp[s]$ denotes the language consisting of strings $x$ with $t$-bounded Kolmogorov complexity, $K^t(x)$, bounded by $s(|x|)$.
In more detail, we demonstrate a direct PRF construction with quasi-polynomial security from mild average-case of hardness of $\mktp[2^{O(\sqrt{\log n})}]$ w.r.t the uniform distribution. We note that by earlier results, this assumption is known to be equivalent to the existence of quasi-polynomially secure OWFs; as such, our results yield the first direct (quasi-polynomially secure) PRF constructions from a natural hardness assumptions that also is known to be implied by (quasi-polynomially secure) PRFs.
Perhaps surprisingly, we show how to make use of the Nisan-Wigderson PRG construction to get a cryptographic, as opposed to a complexity-theoretic, PRG.
Consequently, researchers have developed alternative \emph{direct} constructions of PRFs from various different concrete hardness assumptions. In this work, we continue this thread of work and demonstrate the first direct constructions of PRFs from average-case hardness of the time-bounded Kolmogorov complexity problem $\mktp[s]$, where given a threshold, $s(\cdot)$, and a polynomial time-bound, $t(\cdot)$, $\mktp[s]$ denotes the language consisting of strings $x$ with $t$-bounded Kolmogorov complexity, $K^t(x)$, bounded by $s(|x|)$.
In more detail, we demonstrate a direct PRF construction with quasi-polynomial security from mild average-case of hardness of $\mktp[2^{O(\sqrt{\log n})}]$ w.r.t the uniform distribution. We note that by earlier results, this assumption is known to be equivalent to the existence of quasi-polynomially secure OWFs; as such, our results yield the first direct (quasi-polynomially secure) PRF constructions from a natural hardness assumptions that also is known to be implied by (quasi-polynomially secure) PRFs.
Perhaps surprisingly, we show how to make use of the Nisan-Wigderson PRG construction to get a cryptographic, as opposed to a complexity-theoretic, PRG.
Oana Ciobotaru, Vesselin Velichkov, Maxim Peter
The Fiat-Shamir transform [1] is a well-known and widely employed technique for converting sound public-coin interactive protocols into sound non-interactive protocols. Even though the transformation itself is relatively clear and simple, some implementations choose to deviate from the specifications, for example for performance reasons. In this short note, we present a vulnerability arising from such a deviation in a KZG-based PLONK verifier implementation. This deviation stemmed from the incorrect computation of the last challenge of the PLONK protocol [2], where the KZG batching proof challenge was computed before, and, hence, independently from the KZG evaluation proofs. More generally, such a vulnerability may affect any KZG [3] implementation where one uses batched KZG proof evaluations for at least two distinct evaluation points. We call an attack enabled by such a deviation a Last Challenge Attack. For concreteness, we show that when a PLONK verifier implementation presents such a deviation, a malicious PLONK prover can mount a Last Challenge Attack to construct verifiable proofs of false statements. The described vulnerability was initially discovered as part of an audit, and has been responsibly disclosed to the developers and fixed. A proof of concept of the vulnerability, in which a proof is forged for an arbitrary public input, is made available.
In addition to the above, in this work we also provide a security proof of the knowledge-soundness of the batched KZG scheme with evaluations for at least two distinct values.
In addition to the above, in this work we also provide a security proof of the knowledge-soundness of the batched KZG scheme with evaluations for at least two distinct values.
Dan Boneh, Iftach Haitner, Yehuda Lindell
Verifiable random functions (VRFs) are pseudorandom functions with the addition that the function owner can prove that a generated output is correct, with respect to a committed key. In this paper we introduce the notion of an exponent-VRF, or eVRF, which is a VRF that does not provide its output $y$ explicitly, but instead provides $Y = y \cdot G$, where $G$ is a generator of some finite cyclic group (or $Y = g^y$ in multiplicative notation). We construct eVRFs from DDH and from the Paillier encryption scheme (both in the random-oracle model). We then show that an eVRF can be used to solve several long-standing open problems in threshold cryptography. In particular, we construct (1) a one-round fully simulatable distributed key-generation protocols (after a single two-round initialization phase), (2) a two-round fully simulatable signing protocols for multiparty Schnorr with a deterministic variant, (3) a two-party ECDSA protocol that has a deterministic variant, (4) a threshold Schnorr signing where the parties can later prove that they signed without being able to frame another group, (5) an MPC-friendly and verifiable HD-derivation. Efficient simulatable protocols of this round complexity were not known prior to this work. All of our protocols are concretely efficient.
Theresa Krüger
The possible effects of irradiation on security controllers implemented in CMOS technology are studied. First, the decrease of the effectiveness of a light sensor/detector as countermeasure against laser fault injection is analysed. Second, the use of irradiation as fault injection method is proposed.
Jiajun Xin, Arman Haghighi, Xiangan Tian, Dimitrios Papadopoulos
Proofs of Liabilities (PoL) allow an untrusted prover to commit to its liabilities towards a set of users and then prove independent users' amounts or the total sum of liabilities, upon queries by users or third-party auditors. This application setting is highly dynamic. User liabilities may increase/decrease arbitrarily and the prover needs to update proofs in epoch increments (e.g., once a day for a crypto-asset exchange platform). However, prior works mostly focus on the static case and trivial extensions to the dynamic setting open the system to windows of opportunity for the prover to under-report its liabilities and rectify its books in time for the next check, unless all users check their liabilities at all epochs. In this work, we develop Notus, the first dynamic PoL system for general liability updates that avoids this issue. Moreover, it achieves $O(1)$ query proof size, verification time, and auditor overhead-per-epoch.
The core building blocks underlying Notus are a novel zero-knowledge (and SNARK-friendly) RSA accumulator and a corresponding zero-knowledge MultiSwap protocol, which may be of independent interest. We then propose optimizations to reduce the prover's update overhead and make Notus scale to large numbers of users ($10^6$ in our experiments). Our results are very encouraging, e.g., it takes less than $2$ms to verify a user's liability and the proof size is $256$ Bytes. On the prover side, deploying Notus on a cloud-based testbed with eight 32-core machines and exploiting parallelism, it takes ${\sim}3$ minutes to perform the complete epoch update, after which all proofs have already been computed.
Shuhan Zeng, Yongjian Liao, Chuanhao Zhou, Jinlin He, Hongwei Wang
Confidentiality and authentication are two main security goals in secure electronic mail (e-mail). Furthermore, deniability is also a significant security property for some e-mail applications to protect the privacy of the sender. Although searchable encryption solves the keyword searching problem in a secure e-mail system, it also breaks the deniability of the system. Because the adversary can obtain the information of the data sender and data user from the trapdoor as well as ciphertext used for keyword searching. At the same time, efficiency is another problem in mobile computing. To overcome the issues, we put forward deniably authenticated searchable public key encryption (DA-SPKE) which can apply to the deniable e-mail system. We first define the DA-SPKE model and propose the DA-SPKE scheme. Then we prove its security in the random oracle model and evaluate its efficiency. Finally, we use it in a deniably secure e-mail system to protect both data senders’ and data users' privacy.
04 March 2024
Shintaro Narisada, Shusaku Uemura, Hiroki Okada, Hiroki Furue, Yusuke Aikawa, Kazuhide Fukushima
As post-quantum cryptography transitions toward practical deployment, the significance of extensive cryptanalysis is on the rise. Three out of the four NIST-PQC round 4 candidates are forms of code-based cryptography. Analyses of asymptotic complexity in information set decoding (ISD) algorithms have been a central focus in the field of code-based cryptography. Recently, Esser, May and Zweydinger (Eurocrypt '22) demonstrate the practicality of the May--Meurer--Thomae (MMT) algorithm by decoding McEliece-1284. Esser and Zweydinger (Eurocrypt '23) propose the time-memory trade-off variant of Becker--Joux--May--Meurer (BJMM) decoding, which solves QC-3138. These works have paved the way for the cryptanalysis of ISD in real-world scenarios.
In this work, we further advance the progress of the abovementioned studies by performing a concrete analysis of MMT decoding. We improve the list construction in MMT so that the number of both candidates and representations in the enumeration phase is increased without the need for additional time and memory. Our new algorithm is theoretically 5.1 times faster than the BJMM algorithm for Classic McEliece I instance. We achieve the minimum time complexity across all categories of Classic McEliece among all ISD algorithms. Moreover, compared with the BJMM algorithm, our MMT algorithm reduces the bit security by 1 to 3 bits for all code based NIST-PQC round 4 candidates. Practical security estimates confirm that all the candidates have sufficiently strong bit security, except for Classic McEliece III, with a 1-bit deficiency.
In addition, we implement our new MMT algorithm in a GPU environment and provide the new record of the McEliece-1409 instance, along with implementation details and experimental analyses. Our study verifies the practical reliability of the code-based candidates against current ISD algorithms.
In this work, we further advance the progress of the abovementioned studies by performing a concrete analysis of MMT decoding. We improve the list construction in MMT so that the number of both candidates and representations in the enumeration phase is increased without the need for additional time and memory. Our new algorithm is theoretically 5.1 times faster than the BJMM algorithm for Classic McEliece I instance. We achieve the minimum time complexity across all categories of Classic McEliece among all ISD algorithms. Moreover, compared with the BJMM algorithm, our MMT algorithm reduces the bit security by 1 to 3 bits for all code based NIST-PQC round 4 candidates. Practical security estimates confirm that all the candidates have sufficiently strong bit security, except for Classic McEliece III, with a 1-bit deficiency.
In addition, we implement our new MMT algorithm in a GPU environment and provide the new record of the McEliece-1409 instance, along with implementation details and experimental analyses. Our study verifies the practical reliability of the code-based candidates against current ISD algorithms.