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:
02 December 2022
Vasyl Ustimenko
Symbolic computations with usage of algebraic graphs A(n; F_q)
and A(n;,F_q[x_1, x_2,..., x_n]) were used for the development of various
cryptographic algorithms because the length of their minimal cycle (the
girth) tends to infinity when n is growing. It was announced recently that
for each commutative integrity ring the girth of A(n, K) is ≥ 2n. In this
paper we present essentially shorter closed proof of this statement and
evaluate the girth of some induced subgraphs of A(n; K[x_1, x_2, ..., x_n]).
30 November 2022
Jesús-Javier Chi-Domínguez
This paper illustrates that masking the torsion point images does not guarantee Castryck-Decru attack does not apply.
Our experiments over SIDH primes hint that any square root concerning the Weil pairing on the masked public key helps to recover Bob's private key via the Castryck-Decru attack.
Kirill Vedenev, Yury Kosolapov
Recently, F.Ivanov, E.Krouk and V.Zyablov proposed new cryptosystem based of Generalized Reed--Solomon (GRS) codes over field extensions. In their approach, the subfield images of GRS codes are masked by a special transform, so that the resulting public codes are not equivalent to subfield images of GRS code but burst errors still can be decoded. In this paper, we show that the complexity of message-recovery attack on this cryptosystem can be reduced due to using burst errors, and the secret key of Ivanov-Krouk-Zyablov cryptosystem can successfully recovered in polynomial time with a linear-algebra based attack and a square-based attack.
Joo Woo, Kwangsu Lee, Jong Hwan Park
In 2009, Lyubashevsky proposed a lattice-based signature scheme by applying the Fiat-Shamir transformation and proved its security under the generalized compact knapsack (GCK) problem. This scheme has a simple structure but has large signature and key sizes due to the security requirement of their security reduction. Dilithium, which was submitted to the NIST Post-Quantum Cryptography standardization and selected as one of the final candidates, is an improvement of the Lyubashevsky's signature scheme and decreases key and signature sizes by modifying the form of a public key and including additional steps in key generation, signing, and verification algorithms. Thus, Dilithium has a more complex structure to implement compared to the Lyubashevsky's scheme. To combine the strength of both signature schemes, we modify the Lyubashevsky's signature scheme and present a new security proof that removes their security requirement. As a result, we propose a simple and practical GCKSign signature scheme based on the hardness of a new GCK assumption, called target-modified one-wayness of GCK function. The signature size of our signature scheme decreases 40 percent, the sum of signature and public key sizes decreases 25 percent, and the secret key size decreases 90 percent for the NIST security level III, compared to Dilithium. Furthermore, by the simplicity of our structure, the key generation, signing, and verification algorithms of our scheme run 2.4$\times$, 1.7$\times$, and 2.0$\times$ faster than those of Dilithium, respectively.
Jonghyun Kim, Jong Hwan Park
NTRU was the first practical public-key encryption scheme constructed on a lattice over a polynomial-based ring, and has been still considered secure against significant cryptanalytic attacks in a few decades. Despite such a long history, NTRU and its variants proposed to date suffer from several drawbacks, such as the difficulty of achieving worst-case correctness error in a moderate modulus, inconvenient sampling distributions for messages, and relatively slower algorithms than other lattice-based schemes.
In this work, we suggest a new NTRU-based key encapsulation mechanism (KEM), called NTRU+, which overcomes almost all existing drawbacks. NTRU+ is constructed based on two new generic transformations called $\mathsf{ACWC}_{2}$ and $\overline{\mathsf{FO}}^{\perp}$. $\mathsf{ACWC}_{2}$ is used for easily achieving a worst-case correctness error, and $\overline{\mathsf{FO}}^{\perp}$ (as a variant of the Fujisaki-Okamoto transform) is used for achieving chosen-ciphertext security without re-encryption. $\mathsf{ACWC}_{2}$ and $\overline{\mathsf{FO}}^{\perp}$ are all defined using a randomness-recovery algorithm and an encoding method. Especially, our simple encoding method, called $\mathsf{SOTP}$, allows us to sample a message from a natural bit-sting space with an arbitrary distribution. We provide four parameter sets for NTRU+ and give implementation results, using NTT-friendly rings over cyclotomic trinomials.
In this work, we suggest a new NTRU-based key encapsulation mechanism (KEM), called NTRU+, which overcomes almost all existing drawbacks. NTRU+ is constructed based on two new generic transformations called $\mathsf{ACWC}_{2}$ and $\overline{\mathsf{FO}}^{\perp}$. $\mathsf{ACWC}_{2}$ is used for easily achieving a worst-case correctness error, and $\overline{\mathsf{FO}}^{\perp}$ (as a variant of the Fujisaki-Okamoto transform) is used for achieving chosen-ciphertext security without re-encryption. $\mathsf{ACWC}_{2}$ and $\overline{\mathsf{FO}}^{\perp}$ are all defined using a randomness-recovery algorithm and an encoding method. Especially, our simple encoding method, called $\mathsf{SOTP}$, allows us to sample a message from a natural bit-sting space with an arbitrary distribution. We provide four parameter sets for NTRU+ and give implementation results, using NTT-friendly rings over cyclotomic trinomials.
Jon-Lark Kim, Jihoon Hong, Terry Shue Chien Lau, YounJae Lim, Chik How Tan, Theo Fanuela Prabowo, Byung-Sun Won
We propose a REinforced modified Dual-Ouroboros based on Gabidulin codes, shortly called REDOG.
This is a code-based cryptosystem based on the well-known rank metric codes, Gabidulin codes.
The public key sizes of REDOG are 14KB, 33KB, 63KB at the security levels of 128, 192, 256 bits respectively.
There is no decoding failure in decryption. REDOG is IND-CPA. As a new result, we give the performance results of implementing REDOG including the time for Key generation, encryption, and decryption for each security level.
Marta Bellés-Muñoz, Jorge Jiménez Urroz, Javier Silva
A recent area of interest in cryptography is recursive composition of proof systems. One of the approaches to make recursive composition efficient involves cycles of pairing-friendly elliptic curves of prime order. However, known constructions have very low embedding degrees. This entails large parameter sizes, which makes the overall system inefficient.
In this paper, we explore $2$-cycles composed of curves from families parameterized by polynomials, and show that such cycles do not exist unless a strong condition holds. As a consequence, we prove that no $2$-cycles can arise from the known families, except for those cycles already known. Additionally, we show some general properties about cycles, and provide a detailed computation on the density of pairing-friendly cycles among all cycles.
In this paper, we explore $2$-cycles composed of curves from families parameterized by polynomials, and show that such cycles do not exist unless a strong condition holds. As a consequence, we prove that no $2$-cycles can arise from the known families, except for those cycles already known. Additionally, we show some general properties about cycles, and provide a detailed computation on the density of pairing-friendly cycles among all cycles.
Han Wu, Guangwu Xu
Primal attack, BKW attack, and dual attack are three well-known attacks to LWE. To build efficient post-quantum cryptosystems in practice, the structured variants of LWE (i.e. MLWE/RLWE) are often used. Some efforts have been spent on addressing concerns about additional vulnerabilities introduced by algebraic structures and no effective attack method based on ideal lattices or module lattices has been proposed so far; these include refining primal attack and BKW attack to MLWE/RLWE. It is thus an interesting problem to consider how to enhance the dual attack against LWE with the rich algebraic structure of MLWE (including RLWE). In this paper, we present the first attempt to this problem by observing that each short vector found by BKZ generates another n − 1 vectors of the same length automatically and all of these short vectors can be used to distinguish. To this end, an interesting property which indicates the rotations are consistent with certain linear transformations is proved, and a new kind of intersection lattice is constructed with some tricks. Moreover, we notice that coefficient vectors of different rotations of the same polynomial are near-orthogonal in high-dimensional spaces. This is validated by extensive experiments and is treated as an extension to the assumption under the original dual attack against LWE. Taking Newhope512 as an example, we show that by our enhanced dual attack method, the required blocksize and time complexity (in both classical and quantum cases) all decrease. It is remarked that our improvement is not significant and its limitation is also touched on. Our results do not reveal a severe security problem for MLWE/RLWE compared to that of a general LWE, this is consistent with the findings by the previous work for using primal and BKW attacks to MLWE/RLWE.
Mashrukh Zayed, Adnan Anwar, Ziaur Rahman, Sk. Shezan Arefin, Rafiqul Islam
On the Internet of Connected Vehicles, a vehicle has to communicate bi-directionally with several devices for establishing a shared network for inter-vehicle and intra-vehicle connectivity. These connection protocols are commonly structured to connect all the individual components with an implicit degree of trust, which is supposed to protect the whole system from unauthorized users. Technologies like Automotive Ethernet tend to increase security by reducing the implicit trust within the local network devices. However, the lack of individual security protocols in vehicle-to-vehicle communication still keeps the possession of vulnerability to hacks, external attacks, and further disruption. This is where Zero Trust Architecture can become a reliable technology for the exchange of information in between vehicles. Zero trust is a security system that means no one is trusted by default and verification is required from anyone or any device willing to get connected to the intra-vehicle network. In this paper, we have scoped the preliminary and most vital step of this system: verifying the owner identity of a vehicle with zero trust manner. Our approach involves recognizing vehicle license plates and utilizing the license information for retrieving the vehicle owner details to establish trust before allowing connection to the network. Our proposed methodology operates with 85\% to 99\% accuracy on the license recognition part within recognizable distances using PyTesseract OCR. Reliability to the zero trust solution is gained through necessary information retrieved using GET and POST requests to and from the corresponding driving license information databases.
Yi Chen, Zhenzhen Bao, Yantian Shen, Hongbo Yu
In the seminal work published by Gohr in CRYPTO 2019, neural networks were successfully exploited to perform differential attacks on Speck32/64, the smallest member in the block cipher family Speck. The deep learning aided key-recovery attack by Gohr achieves considerable improvement in terms of time complexity upon the state-of-the-art result from the conventional cryptanalysis method. A further question is whether the advantage of deep learning aided attacks can be kept on large-state members of Speck and other primitives. Since there are several key points in Gohr’s key-recovery frameworks that seem not fit for large-state ciphers, this question stays open for years.
This work provides an answer to this question by proposing a deep learning aided multi-stage key-recovery framework. To apply this key-recovery framework on large-state members of Speck, multiple neural distinguishers (NDs) are trained and carefully combined into groups. Employing the groups of NDs under the multi-stage key-recovery framework, practical attacks are designed and trialed. Experimental results show the effectiveness of the framework. The practical attacks are then extended into theoretical attacks that cover more rounds. To do that, multi-round classical differentials (CDs) are used together with the NDs. To find the CDs’ neutral bits to boost signals from the distinguishers, an efficient algorithm is proposed.
As a result, considerable improvement in terms of both time and data complexity of differential key-recovery attacks on round-reduced Speck with the largest, i.e., the 128-bit state, is obtained. Besides, efficient differential attacks are achieved on round-reduced Speck with 96-bit and 64-bit states. Since most real-world block ciphers have a state size of no less than 64 bits, this work paves the way for performing cryptanalysis using deep learning on more block ciphers. The code is available at https://github.com/AI-Lab-Y/NAAF.
This work provides an answer to this question by proposing a deep learning aided multi-stage key-recovery framework. To apply this key-recovery framework on large-state members of Speck, multiple neural distinguishers (NDs) are trained and carefully combined into groups. Employing the groups of NDs under the multi-stage key-recovery framework, practical attacks are designed and trialed. Experimental results show the effectiveness of the framework. The practical attacks are then extended into theoretical attacks that cover more rounds. To do that, multi-round classical differentials (CDs) are used together with the NDs. To find the CDs’ neutral bits to boost signals from the distinguishers, an efficient algorithm is proposed.
As a result, considerable improvement in terms of both time and data complexity of differential key-recovery attacks on round-reduced Speck with the largest, i.e., the 128-bit state, is obtained. Besides, efficient differential attacks are achieved on round-reduced Speck with 96-bit and 64-bit states. Since most real-world block ciphers have a state size of no less than 64 bits, this work paves the way for performing cryptanalysis using deep learning on more block ciphers. The code is available at https://github.com/AI-Lab-Y/NAAF.
Andreas Freitag
Digital Identities are playing an essential role in our digital lives. Today, most Digital Identities are based on central architectures. Central Digital Identity providers control and know our data and thereby our Identity. Self Sovereign Identities are based on decentralized data storage and data exchange architecture, where the user is in sole control of his data and identity. Most of the issued credentials need the possibility of revocation. For a centrally managed Digital Identity system, revocation is not a problem. In decentral architectures, revocation is more challenging. Revocation can be done with different methods e.g. list based, cryptographic accumulators and with credential updates. A revocation method must be privacy preserving and must scale. This paper gives an overview of the available revocation methods, including a survey to define requirements, assess revocation groups against the requirements, highlights shortcomings of the methods and introduces a new revocation method called Linked Validity Verifiable Credentials.
Microsoft Research, Redmond, WA
The Cryptography, Security, and Privacy research group at Microsoft Research, Redmond, is looking for interns to work on multiple topics, including privacy-preserving protocols, post-quantum cryptography, privacy in AI, digital identities, and usable security and privacy. The scope of our work is broad, so even if you are unsure of whether your skills are relevant, we recommend applying in any case.
Please apply as soon as possible at https://careers.microsoft.com/us/en/job/1483268/Research-Intern-Privacy-and-Cryptography.
Please apply as soon as possible at https://careers.microsoft.com/us/en/job/1483268/Research-Intern-Privacy-and-Cryptography.
Closing date for applications:
Contact: Kim Laine
More information: https://careers.microsoft.com/us/en/job/1483268/Research-Intern-Privacy-and-Cryptography
NTT Research, Sunnyvale, CA, USA
The CIS Lab continually seeks the top minds and rising stars in cryptography research, with internship, postdoctoral, and fulltime scientist research positions available starting in 2023. All positions will be in-person at our Sunnyvale office. Applications should be submitted by December 20 to guarantee full consideration.
Internships. Internships typically are for about 12 weeks during the summer. For the duration of their internship, interns will be matched with one of our research scientists as a mentor. Summer housing assistance is available. Interested individuals should have demonstrated strong mathematical ability and be enrolled in a PhD program with a focus on cryptography, computer security, or theoretical computer science.
Postoctoral research positions. Postdoctoral research positions are available with an initial duration of one year, and the possibility of extension to two years. Postdocs will be matched with a host from the lab, but are welcome to collaborate with any of our world-class scientists. Applicants should have or expect to have a PhD degree relating to cryptography, computer security, or theoretical computer science by summer 2023.
Fulltime Scientist. We are looking to hire Scientists in both foundational and applied cryptography to join our permanent team. For further information, please visit https://careers.ntt-research.com/cis
Closing date for applications: Dec 20, 2022.
Internships. Internships typically are for about 12 weeks during the summer. For the duration of their internship, interns will be matched with one of our research scientists as a mentor. Summer housing assistance is available. Interested individuals should have demonstrated strong mathematical ability and be enrolled in a PhD program with a focus on cryptography, computer security, or theoretical computer science.
Postoctoral research positions. Postdoctoral research positions are available with an initial duration of one year, and the possibility of extension to two years. Postdocs will be matched with a host from the lab, but are welcome to collaborate with any of our world-class scientists. Applicants should have or expect to have a PhD degree relating to cryptography, computer security, or theoretical computer science by summer 2023.
Fulltime Scientist. We are looking to hire Scientists in both foundational and applied cryptography to join our permanent team. For further information, please visit https://careers.ntt-research.com/cis
Closing date for applications: Dec 20, 2022.
Closing date for applications:
Contact: cis.careers@ntt-research.com
More information: https://careers.ntt-research.com/cis
Lund University, Department of Electrical and Information Technology
The main duties of doctoral students are to devote themselves to their research studies which includes participating in research projects and third cycle courses. Especially, the doctral student shall perform research on attacks of resource allocation functions in dynamic networks such as 5G/6G. This means to investigate how machine learning based resource allocation functions might be influence by different types of attacks. In the next step, the stuent will investigate how to detect and/or prevent such attaks. The research method will be a combination of system studies, simulations and experiemental research.
The research project is funded by ELLIT and a research project which is a collaboration between Lund and Linköping universities.
The main duties of doctoral students are to devote themselves to their research studies which includes participating in research projects and third cycle courses. The work duties will also include teaching and other departmental duties (no more than 20%).
Closing date for applications:
Contact: Christian Gehrmann
More information: https://lu.varbi.com/what:job/jobID:569632/
Copper (www.copper.co)
Copper is transforming how institutional investors engage with digital assets, providing market-leading infrastructure in addition to custody, trading and prime brokerage services.
Conduct cryptography literature review, select relevant papers, and produce a specification and pseudocode from the paper(s).
Implement cryptography specifications into secure, production-level code.
Interact with auditors and academia, as well as client-side cryptographers.
Provide cryptography support for other Copper development teams.
Integrate cryptography primitives into Copper’s internal MPC framework.
Participate in the design and implementation of Copper’s next generation MPC framework.
Your Experience Skills and Knowledge:
Essential
5+ years engineering experience in the implementation of cryptography primitives, preferably in MPC, Threshold cryptography, Zero Knowledge Proofs or similar.
3+ years R&D experience specializing in MPC and Threshold cryptography, gained within academia or industry.
Proficiency in programming with Rust, or significant programming experience using C, C++ or Golang
Deep knowledge of common signature schemes of blockchains e.g., ECDSA, EdDSA, BLS
Experience with containerisation and DevOps practices.
Desirable
Masters/PhD in Cryptography/Mathematics
Prior experience with HSMs, Intel SGX, iPhone secure enclaves etc.
Prior experience with Scala, Kotlin or Java.
Prior experience working on a cryptocurrency wallet, or a similar system engineering problem
Familiarity with the digital asset custody space
Our award-winning custody application leverages the genius of multi-party computation (MPC) and can be configured to support cold, warm, and hot wallet solutions. Our culture is based on innovation, enthusiasm and above all else collaboration. Key Responsibilities:
Closing date for applications:
Contact: Alan Brophy (alan.brophy@copper.co)
More information: https://grnh.se/da97a862teu
The University of Manchester, Department of Computer Science
The Systems and Software Security group (S3) at the University of Manchester is looking for a PhD student interested in the topics of cryptographic protocols, blockchains, subversion-resilient cryptography, multi-party computation, or a mix of these.
We are seeking a highly motivated person with a MS.c. degree in computer science or related areas. Excellent final year BS.c. students are also welcome to apply. Interested candidates should enquire about the position to Bernardo Magri (email below). The official application typically requires a CV, cover letter, transcripts, and references (more information about the official application process can be found at https://www.manchester.ac.uk/study/postgraduate-research/admissions/how-to-apply/).
The PhD studentship comes with a stipend of around £17.5K per annum plus tuition fees covered for the duration of 3.5 years. The starting date is flexible and can be for January, May or September 2023.
Closing date for applications:
Contact: Bernardo Magri (bernardo dot magri at manchester.ac.uk)
28 November 2022
Kaveh Aasaraai, Emanuele Cesena, Rahul Maganti, Nicolas Stalder, Javier Varela, Kevin Bowers
Number-Theoretic-Transform (NTT) is a variation of Fast-Fourier-Transform (FFT) on finite fields. NTT is being increasingly used in blockchain and zero-knowledge proof applications. Although FFT and NTT are widely studied for FPGA implementation, we believe CycloneNTT is the first to solve this problem for large data sets ($\ge2^{24}$, 64-bit numbers) that would not fit in the on-chip RAM. CycloneNTT uses a state-of-the-art butterfly network and maps the dataflow to hybrid FIFOs composed of on-chip SRAM and external memory. This manifests into a quasi-streaming data access pattern minimizing external memory access latency and maximizing throughput. We implement two variants of CycloneNTT optimized for DDR and HBM external memories. Although historically this problem has been shown to be memory-bound, CycloneNTT's quasi-streaming access pattern is optimized to the point that when using HBM (Xilinx C1100), the architecture becomes compute-bound. On the DDR-based platform (AWS F1), the latency of the application is equal to the streaming of the entire dataset $\log N$ times to/from external memory. Moreover, exploiting HBM's larger number of channels, and following a series of additional optimizations, CycloneNTT only requires $\frac{1}{6}\log N$ passes.
Dan Boneh, Aditi Partap, Lior Rotem
An accountable threshold signature (ATS) is a threshold signature scheme where every signature identifies the quorum of signers who generated that signature. They are widely used in financial settings where signers need to be held accountable for threshold signatures they generate. In this paper we initiate the study of proactive refresh for accountable threshold signatures. Proactive refresh is a protocol that lets the group of signers refresh their shares of the secret key, without changing the public key or the threshold. We give several definitions for this notion achieving different levels of security. We observe that certain natural constructions for an ATS cannot be proactively refreshed because the secret key generated at setup is needed for accountability. We then construct three types of ATS schemes with proactive refresh. The first is a generic construction that is efficient when the number of signers is small. The second is a hybrid construction that performs well for a large number of signers and satisfies a strong security definition. The third is a collection of very practical constructions derived from ATS versions of the Schnorr and BLS signature schemes; however these practical constructions only satisfy our weaker notion of security.
Srinivasan Raghuraman, Yibin Yang
Fitzi, Garay, Maurer, and Ostrovsky (J. Cryptology 2005) showed that in the presence of a dishonest majority, no primitive of cardinality $n - 1$ is complete for realizing an arbitrary $n$-party functionality with guaranteed output delivery. In this work, we show that in the presence of $n - 1$ corrupt parties, no unreactive primitive of cardinality $n - 1$ is complete for realizing an arbitrary $n$-party functionality with fairness. We show more generally that for $t > \frac{n}{2}$, in the presence of $t$ malicious parties, no unreactive primitive of cardinality $t$ is complete for realizing an arbitrary $n$-party functionality with fairness. We complement this result by noting that $(t+1)$-wise fair exchange is complete for realizing an arbitrary $n$-party functionality with fairness. In order to prove our results, we utilize the primitive of fair coin tossing and introduce the notion of predictability in coin tossing protocols, which we believe is of independent interest.
Daniele Friolo, Matteo Salvino, Daniele Venturi
The Fujisaki-Okamoto (FO) transform (CRYPTO 1999 and JoC 2013) turns any weakly (i.e., IND-CPA) secure public-key encryption (PKE) scheme into a strongly (i.e., IND-CCA) secure key encapsulation method (KEM) in the random oracle model (ROM). Recently, the FO transform re-gained momentum as part of CRISTAL-Kyber, selected by the NIST as the PKE winner of the post-quantum cryptography standardization project.
Following Fischlin (ICALP 2005), we study the complete non-malleability of KEMs obtained via the FO transform. Intuitively, a KEM is completely non-malleable if no adversary can maul a given public key and ciphertext into a new public key and ciphertext encapsulating a related key for the underlying blockcipher.
On the negative side, we find that KEMs derived via FO are not completely non-malleable in general. On the positive side, we show that complete non-malleability holds in the ROM by assuming the underlying PKE scheme meets an additional property, or by a slight tweak of the transformation.
Following Fischlin (ICALP 2005), we study the complete non-malleability of KEMs obtained via the FO transform. Intuitively, a KEM is completely non-malleable if no adversary can maul a given public key and ciphertext into a new public key and ciphertext encapsulating a related key for the underlying blockcipher.
On the negative side, we find that KEMs derived via FO are not completely non-malleable in general. On the positive side, we show that complete non-malleability holds in the ROM by assuming the underlying PKE scheme meets an additional property, or by a slight tweak of the transformation.