International Association for Cryptologic Research

International Association
for Cryptologic Research

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:

RSS symbol icon
via RSS feed
Twitter bird icon
via Twitter
Weibo icon
via Weibo
Facebook icon
via Facebook

15 December 2023

Victor Shoup
ePrint Report ePrint Report
In this brief note, we flesh out some details of the recently proposed Simplex atomic broadcast protocol, and modify it so that leaders disperse blocks in a more communication efficient fashion, while maintaining the simplicity and excellent latency characteristics of the protocol.
Expand
Poulami Das, Andreas Erwig, Michael Meyer, Patrick Struck
ePrint Report ePrint Report
Cryptocurrency networks crucially rely on digital signature schemes, which are used as an authentication mechanism for transactions. Unfortunately, most major cryptocurrencies today, including Bitcoin and Ethereum, employ signature schemes that are susceptible to quantum adversaries, i.e., an adversary with access to a quantum computer can forge signatures and thereby spend coins of honest users. In cryptocurrency networks, signature schemes are typically not executed in isolation, but within a so-called cryptographic wallet. In order to achieve security against quantum adversaries, the signature scheme and the cryptographic wallet must withstand quantum attacks.

In this work, we advance the study on post-quantum secure signature and wallet schemes. That is, we provide the first formal model for deterministic threshold wallets and we show a generic post-quantum secure construction from any post-quantum secure threshold signature scheme with rerandomizable keys. We then instantiate our construction from the isogeny-based signature scheme CSI-FiSh and we show that our instantiation significantly improves over prior work.
Expand
Srinidhi Hari Prasad, Florian Mendel, Martin Schläffer, Rishub Nagpal
ePrint Report ePrint Report
In this work, we present the first low-latency, second-order masked hardware implementation of Ascon that requires no fresh randomness using only $d+1$ shares. Our results significantly outperform any publicly known second-order masked implementations of AES and Ascon in terms of combined area, latency and randomness requirements. Ascon is a family of lightweight authenticated encryption and hashing schemes selected by NIST for standardization. Ascon is tailored for small form factors. It requires less power and energy while attaining the same or even better performance than current NIST standards. We achieve the reduction of latency by rearranging the linear layers of the Ascon permutation in a round-based implementation. We provide an improved technique to achieve implementations without the need for fresh randomness. It is based on the concept of changing of the guards extended to the second-order case. Together with the reduction of latency, we need to consider a large set of additional conditions which we propose to solve using a SAT solver. We have formally verified both, our first- and second-order implementations of Ascon using CocoAlma for the first two rounds. Additionally, we have performed a leakage assessment using t-tests on all 12 rounds of the initial permutation. Finally, we provide a comparison of our second-order masked Ascon implementation with other results.
Expand
Prasanna Ravi, Arpan Jati, Shivam Bhasin
ePrint Report ePrint Report
In this report, we perform an in-depth analysis of the RSA authentication feature used in the secure boot procedure of Xilinx Zynq-7000 SoC device. The First Stage Boot Loader (FSBL) is a critical piece of software executed during secure boot, which utilizes the RSA authentication feature to validate all the hardware and software partitions to be mounted on the device. We analyzed the implementation of FSBL (provided by Xilinx) for the Zynq-7000 SoC and identified a critical security flaw, whose exploitation makes it possible to load an unauthenticated application onto the Zynq device, thereby bypassing RSA authentication. We also experimentally validated the presence of the vulnerability through a Proof of Concept (PoC) attack to successfully mount an unauthenticated software application on an RSA authenticated Zynq device. The identified flaw is only present in the FSBL software and thus can be easily fixed through appropriate modification of the FSBL software. Thus, the first contribution of our work is the identification of a critical security flaw in the FSBL software to bypass RSA authentication.

Upon bypassing RSA authentication, an attacker can mount any unauthenticated software application on the target device to mount a variety of attacks. Among the several possible attacks, we are interested to perform recovery of the encrypted bitstream in the target boot image of the Zynq-7000 device. To the best of our knowledge, there does not exist any prior work that has reported a practical bitstream recovery attack on the Zynq-7000 device. In the context of bitstream recovery, Ender et al. in 2020 proposed the Starbleed attack that is applicable to standalone Virtex-6 and 7-series Xilinx FPGAs. The design advisory provided by Xilinx as a response to the Starbleed attack claims that the Zynq-7000 SoC is resistant “due to the use of asymmetric and/or symmetric authentication in the boot/configuration process that ensures configuration is authenticated prior to use". Due to the security flaw found in the FSBL, we managed to identify a novel approach to mount the Starbleed attack on the Zynq-7000 device for full bitstream recovery. Thus, as a second contribution of our work, we present the first practical demonstration of the Starbleed attack on the Zynq-7000 SoC. We perform experimental validation of our proposed attacks on the PYNQ-Z1 platform based on the Zynq-7000 SoC.
Expand
Hongqing Liu, Chaoping Xing, Chen Yuan, Taoxu Zou
ePrint Report ePrint Report
The privacy-preserving machine learning (PPML) has gained growing importance over the last few years. One of the biggest challenges is to improve the efficiency of PPML so that the communication and computation costs of PPML are affordable for large machine learning models such as deep learning. As we know, linear algebra such as matrix multiplication occupies a significant part of the computation in the deep learning such as deep convolutional neural networks (CNN). Thus, it is desirable to propose the MPC protocol specialized for the matrix operations. In this work, we propose a dishonest majority MPC protocol over matrix rings which supports matrix multiplication and addition. Our MPC protocol can be seen as a variant of SPDZ protocol, i.e., the MAC and global key of our protocol are vectors of length $m$ and the secret of our protocol is an $m\times m$ matrix. Compared to the classic SPDZ protocol, our MPC protocol reduces the communication complexity by at least $m$ times. We also show that our MPC protocol is as efficient as [11] which also presented a dishonest majority MPC protocol specialized for matrix operations. The MPC protocol [11] resorts to the homomorphic encryption scheme (BFV scheme) to produce the matrix triples in the preprocessing phase. This implies that their protocol only supports the matrix operations over integer rings or prime fields of large size. On the contrary, we resort to vector oblivious linear evaluations and random vector oblivious linear evaluations to generate correlated randomness in the preprocessing phase. Thus, the matrices of our MPC protocol can be defined over any finite field or integer ring. Due to the small size of our MAC, the communication complexity of our MPC protocol remains almost the same regardless of the size of the field or the ring.
Expand
Nai-Hui Chia, Shih-Han Hung
ePrint Report ePrint Report
We introduce protocols for classical verification of quantum depth (CVQD). These protocols enable a classical verifier to differentiate between devices of varying quantum circuit depths, even in the presence of classical computation. The goal is to demonstrate that a classical verifier can reject a device with a quantum circuit depth of no more than $d$, even if the prover employs additional polynomial-time classical computation to deceive. Conversely, the verifier accepts a device with a quantum circuit depth of $d'>d$.

Previous results for separating hybrid quantum-classical computers with various quantum depths require either quantum access to oracles or interactions between the classical verifier and the quantum prover. However, instantiating oracle separations can significantly increase the quantum depth in general, and interaction challenges the quantum device to keep the qubits coherent while waiting for the verifier's messages. These requirements pose barriers to implementing the protocols on near-term devices.

In this work, we present a two-message protocol under the quantum hardness of learning with errors and the random oracle heuristic. An honest prover only needs classical access to the random oracle, and therefore any instantiation of the oracle does not increase the quantum depth. To our knowledge, our protocol is the first non-interactive CVQD, the instantiation of which using concrete hash functions, e.g., SHA-3, does not require additional quantum depth.

Our second protocol seeks to explore the minimality of cryptographic assumptions and the tightness of the separations. To accomplish this, we introduce an untrusted quantum machine that shares entanglements with the target machine. Utilizing a robust self-test, our protocol certifies the depth of the target machine with information-theoretic security and nearly optimal separation.
Expand
Daniel R. L. Brown
ePrint Report ePrint Report
A failed hypothesis is reported here. The hope was that large matrices over small non-standard arithmetic are likely to have infeasible division, and furthermore be secure for use in Rabi–Sherman associative cryptography.
Expand
Yunqi Li, Kyle Soska, Zhen Huang, Sylvain Bellemare, Mikerah Quintyne-Collins, Lun Wang, Xiaoyuan Liu, Dawn Song, Andrew Miller
ePrint Report ePrint Report
Enhancing privacy on smart contract-enabled blockchains has garnered much attention in recent research. Zero-knowledge proofs (ZKPs) is one of the most popular approaches, however, they fail to provide full expressiveness and fine-grained privacy. To illustrate this, we underscore an underexplored type of Miner Extractable Value (MEV), called Residual Bids Extractable Value (RBEV). Residual bids highlight the vulnerability where unfulfilled bids inadvertently reveal traders’ unmet demands and prospective trading strategies, thus exposing them to exploitation. ZKP-based approaches failed to ad- dress RBEV as they cannot provide post-execution privacy without some level of information disclosure. Other MEV mitigations like fair-ordering protocols also failed to address RBEV. We introduce Ratel, an innovative framework bridging a multi-party computation (MPC) prototyping framework (MP-SPDZ) and a smart contract language (Solidity), harmonizing the privacy with full expressiveness of MPC with Solidity ’s on-chain programmability. This synergy empowers developers to effortlessly craft privacy-preserving decentralized applications (DApps). We demonstrate Ratel’s efficacy through two distinguished decentralized finance (DeFi) applications: a decentralized exchange and a collateral auction, effectively mitigating the potential RBEV issue. Furthermore, Ratel is equipped with a lightweight crash-reset mechanism, enabling the seamless recovery of transiently benign faulty nodes. To prevent the crash-reset mechanism abused by malicious entities and ward off DoS attacks, we incorporate a cost-utility analysis anchored in the Bayesian approach. Our performance evaluation of the applications developed under the Ratel framework underscores their competency in managing real-world peak-time workloads.
Expand
Amirreza Sarencheh, Aggelos Kiayias, Markulf Kohlweiss
ePrint Report ePrint Report
Stablecoins are digital assets designed to maintain a consistent value relative to a reference point, serving as a vital component in Blockchain, and Decentralized Finance (DeFi) ecosystem. Typical implementations of stablecoins via smart contracts come with important downsides such as a questionable level of privacy, potentially high fees, and lack of scalability. We put forth a new design, PARScoin, for a Privacy-preserving, Auditable, and Regulation-friendly Stablecoin that mitigates these issues while enabling high performance both in terms of speed of settlement and for scaling to large numbers of users. Our construction is blockchain-agnostic and is analyzed in the Universal Composition (UC) framework, offering a secure and modular approach for its integration into the broader blockchain ecosystem.
Expand
Tim Beyne, Michiel Verbauwhede
ePrint Report ePrint Report
In this work we introduce algebraic transition matrices as the basis for a new approach to integral cryptanalysis that unifies monomial trails (Hu et al., Asiacrypt 2020) and parity sets (Boura and Canteaut, Crypto 2016). Algebraic transition matrices allow for the computation of the algebraic normal form of a primitive based on the algebraic normal forms of its components by means of well-understood operations from linear algebra. The theory of algebraic transition matrices leads to better insight into the relation between integral properties of $F$ and $F^{−1}$. In addition, we show that the link between invariants and eigenvectors of correlation matrices (Beyne, Asiacrypt 2018) carries over to algebraic transition matrices. Finally, algebraic transition matrices suggest a generalized definition of integral properties that subsumes previous notions such as extended division properties (Lambin, Derbez and Fouque, DCC 2020). On the practical side, a new algorithm is described to search for these generalized properties and applied to Present, resulting in new properties. The algorithm can be instantiated with any existing automated search method for integral cryptanalysis.
Expand
Andrea Basso, Mingjie Chen, Tako Boris Fouotsa, Péter Kutas, Abel Laval, Laurane Marco, Gustave Tchoffo Saah
ePrint Report ePrint Report
Isogeny-based cryptography is an instance of post-quantum cryptography whose fundamental problem consists of finding an isogeny between two (isogenous) elliptic curves $E$ and $E'$. This problem is closely related to that of computing the endomorphism ring of an elliptic curve. Therefore, many isogeny-based protocols require the endomorphism ring of at least one of the curves involved to be unknown. In this paper, we explore the design of isogeny based protocols in a scenario where one assumes that the endomorphism ring of all the curves are public. In particular, we identify digital signatures based on proof of isogeny knowledge from SIDH squares as such a candidate. We explore the design choices for such constructions and propose two variants with practical instantiations. We analyze their security according to three lines, the first consists of attacks based on KLPT with both polynomial and superpolynomial adversary, the second consists of attacks derived from the SIDH attacks and finally we study the zero-knowledge property of the underlying proof of knowledge.
Expand

12 December 2023

Scott Fluhrer
ePrint Report ePrint Report
In "Oops, I did it again" - Security of One-Time Signatures under Two-Message Attacks, Bruinderink and Hülsing analyzed the effect of key reuse for several one time signature systems. When they analyzed the Winternitz system, they assumed certain probabilities were independent when they weren't, leading to invalid conclusions. This paper does a more correct characterization of the Winternitz scheme, and while their ultimate conclusion (that key reuse allows for practical forgeries) is correct, the situation is both better and worse than what they concluded.
Expand
Sulaiman Alhussaini, Craig Collett, Serge˘ı Sergeev
ePrint Report ePrint Report
After the Kotov-Ushakov attack on the tropical implementation of Stickel protocol, various attempts have been made to create a secure variant of such implementation. Some of these attempts used a special class of commuting matrices resembling tropical circulants, and they have been proposed with claims of resilience against the Kotov-Ushakov attack, and even being potential post-quantum candidates. This paper, however, reveals that a form of the Kotov-Ushakov attack remains applicable and, moreover, there is a heuristic implementation of that attack which has a polynomial time complexity and shows an overwhelmingly good success rate.
Expand
Céline Chevalier, Guirec Lebrun, Ange Martinelli
ePrint Report ePrint Report
The recently standardized secure group messaging protocol “Messaging Layer Security” (MLS) is designed to ensure asynchronous communications within large groups, with an almost-optimal communication cost and the same security level as point-to-point secure messaging protocols such as “Signal”. In particular, the core sub-protocol of MLS, a Continuous Group Key Agreement (CGKA) called TreeKEM, must generate a common group key that respects the fundamental security properties of “post-compromise security” and “forward secrecy” which mitigate the effects of user corruption over time.

Most research on CGKAs has focused on how to improve these two security properties. However, post-compromise security and forward secrecy require the active participation of respectively all compromised users and all users within the group. Inactive users – who remain offline for long periods – do not update anymore their encryption keys and therefore represent a vulnerability for the entire group. This issue has already been identified in the MLS standard, but no solution, other than expelling these inactive users after some disconnection time, has been found.

We propose here a CGKA protocol based on TreeKEM and fully compatible with the MLS standard, that implements a “quarantine” mechanism for the inactive users in order to mitigate the risk induced by these users without removing them from the group. That mechanism indeed updates the inactive users’ encryption keys on their behalf and secures these keys with a secret sharing scheme. If some of the inactive users eventually reconnect, their quarantine stops and they are able to recover all the messages that were exchanged during their offline period. Our “Quarantined-TreeKEM” protocol thus offers a good trade-off between security and functionality, with a very limited – and sometimes negative – communication overhead.
Expand
François-Xavier Wicht, Zhipeng Wang, Duc V. Le, Christian Cachin
ePrint Report ePrint Report
Considerable work explores blockchain privacy notions. Yet, it usually employs entirely different models and notations, complicating potential comparisons. In this work, we use the Transaction Directed Acyclic Graph (TDAG) and extend it to capture blockchain privacy notions (PDAG). We give consistent definitions for untraceability and unlinkability. Moreover, we specify conditions on a blockchain system to achieve each aforementioned privacy notion. Thus, we can compare the two most prominent privacy-preserving blockchains -- Monero and Zcash, in terms of privacy guarantees. Finally, we unify linking heuristics from the literature with our graph notation and review a good portion of research on blockchain privacy.
Expand
Cong Ling, Andrew Mendelsohn
ePrint Report ePrint Report
We extend the middle product to skew polynomials, which we use to define a skew middle-product Learning with Errors (LWE) variant. We also define a skew polynomial LWE problem, which we connect to Cyclic LWE (CLWE), a variant of LWE in cyclic division algebras. We then reduce a family of skew polynomial LWE problems to skew middle-product LWE, for a family which includes the structures found in CLWE. Finally, we give an encryption scheme and demonstrate its IND-CPA security, assuming the hardness of skew middle-product LWE.
Expand

11 December 2023

Technical University of Denmark, Dept. of Applied Mathematics and Computer Science, Copenagen Area
Job Posting Job Posting
Are you excited about post-quantum cryptography, provable security or secure end-to-end encrypted messaging? Or maybe more than one of these? Then we have a great PhD opportunity for you!

The goal of the project is to explore different routes towards providing a fully quantum-secure replacement for X3DH, the key exchange protocol used by Signal, WhatsApp and the likes. It is an excellent opportunity to be involved in advanced research on cryptographic systems secure against quantum computing.

For more information click the title of this job listing. If you are interested feel free to reach out to Christian Majenz (chmaj@dtu.dk).

Closing date for applications:

Contact: Christian Majenz, Associate Professor at DTU Compute, Cyber Security Engineering Section

More information: https://efzu.fa.em2.oraclecloud.com/hcmUI/CandidateExperience/en/sites/CX_1/job/2851/?utm_medium=jobshare

Expand
University of Kassel, Germany
Job Posting Job Posting

The Information Security group is looking for a strong candidate to fill an open PhD position. The PhD will be supervised by Jiaxin Pan and will work on provable security, for instance, key exchange protocols and digital signature schemes. We will also work on the post-quantum security of them.

We hope that the PhD can publish at major venues, such as Crypto, Eurocrypt, Asiacrypt, PKC, etc., under the supervision. In the past, this has been successfully realized.

The position is paid according to EG13 TV-H (full-time). It is initially limited for 3 years with the possibility of extension for a further 2 years. The position comes with teaching load of 4 hours per week during the semester teaching period. This is usually manageable and can be done in the forms of tutorials, labs, seminars, or thesis co-supervision.

We encourage strong candidates with a Master degree and those who are close to finish to apply. Knowledge in post-quantum cryptography, digital signatures, or key exchange is highly desirable.

More information can be found in:

  • https://stellen.uni-kassel.de/jobposting/9023eb9d3fd3366877c376079417eb1d088ded3c0 (English), or
  • https://stellen.uni-kassel.de/jobposting/0870f187f0392f19987735519cbe2b5778a3eb910 (German)

Closing date for applications:

Contact: Jiaxin Pan: https://sites.google.com/view/jiaxinpan

More information: https://stellen.uni-kassel.de/jobposting/9023eb9d3fd3366877c376079417eb1d088ded3c0

Expand
University of Birmingham, UK
Job Posting Job Posting
The Center for Cyber Security and Privacy of the University of Birmingham is looking for a postdoctoral researcher in cryptography. We invite applications from candidates with research records in applied probability and security reductions/analysis of cryptographic schemes. The position is for 1 year. For informal enquiries, please contact Rishiraj Bhattacharyya.

Closing date for applications:

Contact: Rishiraj Bhattacharyya (r.bhattacharyya@bham.ac.uk)

More information: https://edzz.fa.em3.oraclecloud.com/hcmUI/CandidateExperience/en/sites/CX_6001/job/3750/

Expand
Limitless Labs, Ukraine or Remote
Job Posting Job Posting
Limitless Labs is an R&D collective advancing gaming, distributed systems & computing. Our team has extensive expertise in fields like cryptography, crypto networks, game development, ML, product growth & startups. In the past, our founding team has been 2x backed by a16z, built an AI app company with 250M downloads, a prominent web3 gaming title and reached half a million people around the world with blockchain-powered humanitarian relief.

This role is dedicated to applied research. In our initial phases, we are committed to understanding and leveraging the state-of-the-art, while in future phases, we will advance it. Primarily, the researcher will contribute to the design of new architectural solutions.

Responsibilities

- Design, specify and verify distributed systems by leveraging formal and experimental techniques.

- Build proof of concepts and prepare executable specifications for the development team.

- Regularly going through papers, bringing new ideas and staying up-to-date.

- Conducting theoretical and practical analysis of the performance of distributed systems.

- Collaborating with both internal and external contributors.

Closing date for applications:

Contact: Ira | Head of People @ Limitless Labs

More information: https://apply.workable.com/limitless-labs-network/j/EF6246F619/

Expand
◄ Previous Next ►