International Association
for Cryptologic Research

The Learning With Errors (LWE) problem is one of the major hard problems in post-quantum cryptography. For example, 1) the only Key Exchange Mechanism KEM standardized by NIST [14] is based on LWE; and 2) current publicly available Homomorphic Encryption (HE) libraries are based on LWE. NIST KEM schemes use random secrets, but homomorphic encryption schemes use binary or ternary secrets, for efficiency reasons. In particular, sparse binary secrets have been proposed, but not standardized [2], for HE. Prior work SALSA [49] demonstrated a new machine learning attack on sparse binary secrets for the LWE problem in small dimensions (up to n = 128) and low Hamming weights (up to h = 4). However, this attack assumed access to millions of LWE samples, and was not scaled to higher Hamming weights or dimensions. Our attack, PICANTE, reduces the number of samples required to just m = 4n samples. Moreover, it can recover secrets with much larger dimensions (up to 350) and Hamming weights (roughly n/10, or h = 33 for n = 300). To achieve this, we introduce a preprocessing step which allows us to generate the training data from a linear number of samples and changes the distribution of the training data to improve transformer training. We also improve the distinguisher/secret recovery methods of SALSA and introduce a novel cross-attention recovery mechanism which allows us to read-off the secret directly from the trained models.

Grover’s algorithm is a quantum searching algorithm that poses a threat to symmetric cryptography. Due to their smaller key sizes, lightweight cryptographic algorithms such as Simplified-AES face a much more immediate threat from Grover’s algorithm than traditional cryptographic algorithms. By analyzing different S-boxes, it was discovered that the S-box 946C753AE8FBD012 may be more quantum resistant than the S-box that Simplified-AES uses, 94ABD1856203CEF7. In addition to this, 16x4 S-boxes (or 4 4x4 S-boxes) showed to be significantly more quantum secure than 4x4 S-boxes. This is because the number of gates needed to model a $2^n$x4 S-box increases at an exponential rate. It was also found that this property extends to $2^n$x8 S-boxes, implying the existence of a more quantum secure 8x8 S-box that AES could use. However, an increase in quantum security does not equate to an increase in classical security, as some of the least quantum secure S-boxes analyzed displayed some of the best classical security. Finally, an alteration of Simplified-AES that used a 16x4 S-box was found that displayed better classical and quantum security than Simplified-AES and did not require an increase in key size.

The rising issues of harassment, exploitation, corruption, and other forms of abuse have led victims to seek comfort by acting in unison against common perpetrators (e.g., #MeToo movement). One way to curb these issues is to install allegation escrow systems that allow victims to report such incidents. The escrows are responsible for identifying victims of a common perpetrator and taking the necessary action to bring justice to them. However, users hesitate to participate in these systems due to the fear of such sensitive reports being leaked to perpetrators, who may further misuse them. Thus, to increase trust in the system, cryptographic solutions are being designed to realize secure allegation escrow (SAE) systems.

In the work of Arun et al. (NDSS'20), which presents the state-of-the-art solution, we identify attacks that can leak sensitive information and compromise victim privacy. We also report issues present in prior works that were left unidentified. To arrest all these breaches, we put forth an SAE system that prevents the identified attacks and retains the salient features from all prior works. The cryptographic technique of secure multi-party computation (MPC) serves as the primary underlying tool in designing our system. At the heart of our system lies a new duplicity check protocol and an improved matching protocol. We also provide additional features such as allegation modification and deletion, which were absent in the state of the art. To demonstrate feasibility, we benchmark the proposed system with state-of-the-art MPC protocols and report the cost of processing an allegation. Different settings that affect system performance are analyzed, and the reported values showcase the practicality of our solution.

Security vulnerabilities in the symmetric-key primitives of a cipher can undermine the overall security claims of the cipher. With the rapid advancement of quantum computing in recent years, there is an increasing effort to evaluate the security of symmetric-key cryptography against potential quantum attacks. This paper focuses on analyzing the quantum attack resistance of AIM, a symmetric-key primitive used in the AIMer digital signature scheme. We presents the first quantum circuit implementation of AIM and estimates its complexity (such as qubit count, gate count, and circuit depth) with respect to Grover's search algorithm. For Grover's key search, the most important optimization metric is the depth, especially when considering parallel search. Our implementation gathers multiple methods for a low-depth quantum circuit of AIM in order to reduce the Toffoli depth and full depth.

Electronic voting (e-voting) aims to provide a sustainable and accessible environment for voters while preserving anonymity and trust. In this paper, we present a novel e-voting scheme that combines Group Identity-based Identification (GIBI) scheme with Homomorphic Encryption (HE) based on the Distributed ElGamal (DE) cryptosystem. Our scheme allows for efficient voter authentication through the use of a Discrete Logarithm (DL)-based identification protocol and enables encrypted vote counting without the need for decryption. Additionally, our scheme allows for individual and universal verifiability through the use of Zero-Knowledge (ZK) proofs. We also propose some future work to enhance the scheme for more secure or practical use.

Due to recent cryptanalytical breakthroughs, the multivariate signature schemes that seemed to be most promising in the past years are no longer in the focus of the research community. Hence, the cryptographically mature UOV scheme is of great interest again. Since it has not been part of the NIST process for standardizing post-quantum cryptography so far, it has not been studied intensively for its physical security.

In this work, we present a side-channel attack on the latest implementation of UOV. In the first part of the attack, a single side-channel trace of the signing process is used to learn all vinegar variables used in the computation. Then, we employ the reconciliation attack to reveal the complete secret key. Our attack, unlike previous work, targets the inversion of the central map and not the subsequent linear transformation. It further does not require the attacker to control the message to be signed.

We have verified the practicality of our attack on a ChipWhisperer-Lite board with a 32-bit STM32F3 ARM Cortex-M4 target mounted on a CW308 UFO board. We publicly provide the code and both reference and target traces. Additionally, we discuss several countermeasures that can at least make our attack less efficient.

We present a new generic transform that takes a multi-round interactive proof for the membership of a language $\mathcal{L}$ and outputs a non-interactive zero-knowledge proof (not of knowledge) in the common reference string model. Similar to the Fiat-Shamir transform, it requires a hash function $\mathsf{H}$. However, in our transform the zero-knowledge property is in the standard model, and the adaptive soundness is in the non-programmable random oracle model ($\mathsf{NPROM}$). Behind this new generic transform, we build a new generic OR-composition of two multi-round interactive proofs. Note that the two common techniques for building OR-proofs (parallel OR-proof and sequential OR-proof) cannot be naturally extended to the multi-round setting. We also give a proof of security for our OR-proof in the quantum oracle model ($\mathsf{QROM}$), surprisingly the security loss in $\\mathsf{QROM}$ is independent from the number of rounds.

In 1979, Shamir and Blakley introduced secret sharing schemes to provide both security and reliability. In this study, we construct two secret sharing schemes with perfect concealment. The first is an \((n,n)\)-threshold scheme by a group. Although the scheme itself is already known, we prove that its concealment is perfect. We propose the second as a new \((2,n)\)-threshold scheme by a quasigroup.

As online group communication scenarios become more and more common these years, malicious or unpleasant messages are much easier to spread on the internet. Message franking is a crucial cryptographic mechanism designed for content moderation in online end-to-end messaging systems, allowing the receiver of a malicious message to report the message to the moderator. Unfortunately, the existing message franking schemes only consider 1-1 communication scenarios.

In this paper, we systematically explore message franking in group communication scenarios. We introduce the notion of asymmetric group message franking (AGMF), and formalize its security requirements. Then, we provide a framework of constructing AGMF from a new primitive, called $\text{HPS-KEM}^{\rm{\Sigma}}$. We also give a construction of $\text{HPS-KEM}^{\rm{\Sigma}}$ based on the DDH assumption. Plugging the concrete $\text{HPS-KEM}^{\rm{\Sigma}}$ scheme into our AGMF framework, we obtain a DDH-based AGMF scheme, which supports message franking in group communication scenarios.

Are you fascinated by security? Are you willing to take on the challenge of securing the next generation of computer systems and networks? Do you like to work in a team of young researchers? We are seeking a PhD candidate who is interested in interdisciplinary research on side-channel attacks against quantum devices used in quantum networks.

Quantum technologies are being developed at a fast page. On the one hand, progress on the development of quantum computers poses a serious threat for our security infrastructure, especially for public-key cryptography. On the other hand, quantum components bring novel opportunities since they will be integrated in our networks and could bring novel security functionalities. However, quantum components are mostly experimental, and their security is yet to be studied and assessed in depth. In particular, little is known about their susceptibility against side-channel and physical attacks and, as a direct consequence, we do not know if and which countermeasures can be applied.

This PhD position will study the problem of side channels and physical attacks against quantum devices, understanding the extent to which they could be considered a threat and exploring potential methodologies to counteract and mitigate them. In collaboration with experimental physicists, experiments on real quantum devices are expected to be carried out to assess their robustness.

The fully funded PhD position will be at University of Amsterdam and QuSoft. The position is a part of the Quantum Delta NL Groeifonds project CAT-2, development of a national quantum network and will also involve collaboration with the experimental and theoretical partners of the CAT-2 project.

Closing date for applications:

Contact: Christian Schaffner

More information: https://vacatures.uva.nl/UvA/job/PhD/742058802/

Several fully-funded PhD student openings for Fall 2023 are available in cryptography, computer security, privacy, and blockchain-based systems at the University of Connecticut (UConn), Computer Science and Engineering department, led by Prof. Ghada Almashaqbeh.

The positions provide a great opportunity for students with interest in interdisciplinary projects that combine knowledge from various fields towards the design of secure systems and protocols. We target real-world and timely problems and aim to develop secure and practical solutions backed by rigorous foundations and efficient implementations/thorough performance testing. We are also interested in conceptual projects that contribute in bridging the gap between theory and practice of Cryptography.

For more information about our current and previous projects please check https://ghadaalmashaqbeh.github.io/research/. For interested students, please send your CV to ghada@uconn.edu and provide any relevant information about your research interests, and relevant skills and background.

Closing date for applications:

Contact: Ghada Almashaqbeh

More information: https://ghadaalmashaqbeh.github.io/research/

This paper describes a vulnerability in several implementations of the Secure Hash Algorithm 3 (SHA-3) that have been released by its designers. The vulnerability has been present since the final-round update of Keccak was submitted to the National Institute of Standards and Technology (NIST) SHA-3 hash function competition in January 2011, and is present in the eXtended Keccak Code Package (XKCP) of the Keccak team. It affects all software projects that have integrated this code, such as the scripting languages Python and PHP Hypertext Preprocessor (PHP). The vulnerability is a buffer overflow that allows attacker-controlled values to be eXclusive-ORed (XORed) into memory (without any restrictions on values to be XORed and even far beyond the location of the original buffer), thereby making many standard protection measures against buffer overflows (e.g., canary values) completely ineffective. First, we provide Python and PHP scripts that cause segmentation faults when vulnerable versions of the interpreters are used. Then, we show how this vulnerability can be used to construct second preimages and preimages for the implementation, and we provide a specially constructed file that, when hashed, allows the attacker to execute arbitrary code on the victim's device. The vulnerability applies to all hash value sizes, and all 64-bit Windows, Linux, and macOS operating systems, and may also impact cryptographic algorithms that require SHA-3 or its variants, such as the Edwards-curve Digital Signature Algorithm (EdDSA) when the Edwards448 curve is used. We introduce the Init-Update-Final Test (IUFT) to detect this vulnerability in implementations.

The classical "BGW protocol" (Ben-Or, Goldwasser and Wigderson, STOC 1988) shows that secure multiparty computation (MPC) among $n$ parties can be realized with perfect full security if $t < n/3$ parties are corrupted. This holds against malicious adversaries in the "standard" model for MPC, where a fixed set of $n$ parties is involved in the full execution of the protocol. However, the picture is less clear in the mobile adversary setting of Ostrovsky and Yung (PODC 1991), where the adversary may periodically "move" by uncorrupting parties and corrupting a new set of $t$ parties. In this setting, it is unclear if full security can be achieved against an adversary that is maximally mobile, i.e., moves after every round. The question is further motivated by the "You Only Speak Once" (YOSO) setting of Gentry et al. (Crypto 2021), where not only the adversary is mobile but also each round is executed by a disjoint set of parties. Previous positive results in this model do not achieve perfect security, and either assume probabilistic corruption and a nonstandard communication model, or only realize the weaker goal of security-with-abort. The question of matching the BGW result in these settings remained open.

In this work, we tackle the above two challenges simultaneously. We consider a layered MPC model, a simplified variant of the fluid MPC model of Choudhuri et al. (Crypto 2021). Layered MPC is an instance of standard MPC where the interaction pattern is defined by a layered graph of width $n$, allowing each party to send secret messages and broadcast messages only to parties in the next layer. We require perfect security against a malicious adversary who may corrupt at most $t$ parties in each layer. Our main result is a perfect, fully secure layered MPC protocol with an optimal corruption threshold of $t < n/3$, thus extending the BGW feasibility result to the layered setting. This implies perfectly secure MPC protocols against a maximally mobile adversary.

MEGA is a large-scale cloud storage and communication platform that aims to provide end-to-end encryption for stored data. A recent analysis by Backendal, Haller and Paterson (IEEE S&P 2023) invalidated these security claims by presenting practical attacks against MEGA that could be mounted by the MEGA service provider. In response, the MEGA developers added lightweight sanity checks on the user RSA private keys used in MEGA, sufficient to prevent the previous attacks.

We analyse these new sanity checks and show how they themselves can be exploited to mount novel attacks on MEGA that recover a target user's RSA private key with only slightly higher attack complexity than the original attacks. We identify the presence of an ECB encryption oracle under a target user's master key in the MEGA system; this oracle provides our adversary with the ability to partially overwrite a target user's RSA private key with chosen data, a powerful capability that we use in our attacks. We then present two distinct types of attack, each type exploiting different error conditions arising in the sanity checks and in subsequent cryptographic processing during MEGA's user authentication procedure. The first type appears to be novel and exploits the manner in which the MEGA code handles modular inversion when recomputing $u = q^{-1} \bmod p$. The second can be viewed as a small subgroup attack (van Oorschot and Wiener, EUROCRYPT 1996, Lim and Lee, CRYPTO 1998). We prototype the attacks and show that they work in practice.

As a side contribution, we show how to improve the RSA key recovery attack of Backendal-Haller-Paterson against the unpatched version of MEGA to require only 2 logins instead of the original 512.

We conclude by discussing wider lessons about secure implementation of cryptography that our work surfaces.

In symmetric cryptography, block ciphers, stream ciphers and permutations often make use of a round function and many round functions consist of a linear and a non-linear layer. One that is often used is based on the cellular automaton that is denoted by $\chi$ as a Boolean map on bi-infinite sequences, $\mathbb{F}^{\mathbb{Z}}$. It is defined by $\sigma \mapsto \nu$ where each $\nu_i = \sigma_i + (\sigma_{i+1}+1)\sigma_{i+2}$. A map $\chi_n$ is a map that operatos on $n$-bit arrays with periodic boundary conditions. This corresponds with $\chi$ restricted to periodic infinite sequences with period that divides $n$. This map $\chi_n$ is used in various permutations, e.g., Keccak-f (the permutation in SHA-3), ASCON (the NIST standard for lightweight cryptography), Xoodoo, Rasta and Subterranean (2.0).

In this paper, we characterize the graph of $\chi$ on periodic sequences. It turns out that $\chi$ is surjective on the set of \emph{all} periodic sequences. We will show what sequences will give collisions after one application of $\chi$. We prove that, for odd $n$, the order of $\chi_n$ (in the group of bijective maps on $\mathbb{F}^n$) is $2^{\lceil \operatorname{lg}(\frac{n+1}2)\rceil}$.

A given periodic sequence lies on a cycle in the graph of $\chi$, or it can be represented as a polynomial. By regarding the divisors of such a polynomial one can see whether it lies in a cycle, or after how many iterations of $\chi$ it will.

Furthermore, we can see, for a given $\sigma$, the length of the cycle in its component in the state diagram. Finally, we extend the surjectivity of $\chi$ to $\mathbb{F}^{\mathbb{Z}}$, thus to include non-periodic sequences.

It has been a long-standing viewpoint that doubling the length of key seeds in symmetric cipher can resist the quantum search attacks. This paper establishes a quantum key search model to deal with the post-quantum security of symmetric ciphers. The quantum search is performed in the punctured keystream/ciphertext space instead of the key space. On inputting the punctured keystreams/ciphertexts, we rule out the fake keys and find out the real key via the iterative use of the quantum singular value search algorithm. We find out several parameters, such as the length and min-entropy of the punctured keystream, the iterations, and the error in the search algorithm, and all of them can influence the resulting complexity. When these parameters are chosen properly, a better complexity can be obtained than Grover algorithm. Our search model can apply to any typical symmetric cipher. To demonstrate the power, we apply our model to analyze block cipher AES family, stream ciphers Grain-128 and ZUC-128. The resulting complexity of AES-128 is $\tilde{\mathcal O}(2^{30.8})$, $\tilde{\mathcal O}(2^{32.0})$ of AES-192, $\tilde{\mathcal O}(2^{32.7})$ of AES-256, $\tilde{\mathcal O}(2^{27.5})$ of Grain-128, and $\tilde{\mathcal O}(2^{39.8})$ of ZUC-128.

Our results show that increasing the length of key seeds is not an effective way anymore to resist the quantum search attacks, and it is necessary to propose new measures to ensure the post-quantum security of symmetric ciphers.

OCB3 is a mature and provably secure authenticated encryption mode of operation which allows for associated data (AEAD). This note reports a small flaw in the security proof of OCB3 that may cause a loss of security in practice, even if OCB3 is correctly implemented in a trustworthy and nonce-respecting module. The flaw is present when OCB3 is used with short nonces. It has security implications that are worse than nonce-repetition as confidentiality and authenticity are lost until the key is changed. The flaw is due to an implicit condition in the security proof and to the way OCB3 processes nonce. Different ways to fix the mode are presented.

Quantum cryptography leverages many unique features of quantum information in order to construct cryptographic primitives that are oftentimes impossible classically. In this work, we build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.

We define and construct several fundamental cryptographic primitives with key-revocation capabilities, namely pseudorandom functions, secret-key and public-key encryption, and even fully homomorphic encryption, assuming the quantum subexponential hardness of the learning with errors problem. Central to all our constructions is our approach for making the Dual-Regev encryption scheme (Gentry, Peikert and Vaikuntanathan, STOC 2008) revocable.

In a recent work, Cremers, Naor, Paz, and Ronen (CRYPTO '22) point out the problem of catastrophic impersonation in balanced password authenticated key exchange protocols (PAKEs). Namely, in a balanced PAKE, when a single party is compromised, the attacker learns the password and can subsequently impersonate anyone to anyone using the same password. The authors of the work present two solutions to this issue: CHIP, an identity-binding PAKE (iPAKE), and CRISP, a strong identity-binding PAKE (siPAKE). These constructions prevent the impersonation attack by generating a secret key on setup that is inextricably tied to the party's identity, and then deleting the password. Thus, upon compromise, all an attacker can immediately do is impersonate the victim. The strong variant goes further, preventing attackers from performing any precomputation before the compromise occurs.

In this work we present LATKE, an iPAKE from lattice assumptions in the random oracle model. In order to achieve security and correctness, we must make changes to CHIP's primitives, security models, and protocol structure.

Zero-knowledge proof systems for computational integrity have seen a rise in popularity in the last couple of years. One of the results of this development is the ongoing effort in designing so-called arithmetization-friendly hash functions in order to make these proofs more efficient. One of these new hash functions, Poseidon, is extensively used in this context, also thanks to being one of the first constructions tailored towards this use case. Many of the design principles of Poseidon have proven to be efficient and were later used in other primitives, yet parts of the construction have shown to be expensive in real-word scenarios.

In this paper, we propose an optimized version of Poseidon, called Poseidon2. The two versions differ in two crucial points. First, Poseidon is a sponge hash function, while Poseidon2 can be either a sponge or a compression function depending on the use case. Secondly, Poseidon2 is instantiated by new and more efficient linear layers with respect to Poseidon. These changes allow to decrease the number of multiplications in the linear layer by up to 90% and the number of constraints in Plonk circuits by up to 70%. This makes Poseidon2 the currently fastest arithmetization-oriented hash function without lookups.

Besides that, we address a recently proposed algebraic attack and propose a simple modification that makes both Poseidon and Poseidon2 secure against this approach.