International Association
for Cryptologic Research

The Tower variant of the Number Field Sieve (TNFS) is known to be asymptotically the most efficient algorithm to solve the discrete logarithm problem in finite fields of medium characteristics, when the extension degree is composite. A major obstacle to an efficient implementation of TNFS is the collection of algebraic relations, as it happens in dimension greater than 2. This requires the construction of new sieving algorithms which remain efficient as the dimension grows. In this article, we overcome this difficulty by considering a lattice enumeration algorithm which we adapt to this specific context. We also consider a new sieving area, a high-dimensional sphere, whereas previous sieving algorithms for the classical NFS considered an orthotope. Our new sieving technique leads to a much smaller running time, despite the larger dimension of the search space, and even when considering a larger target, as demonstrated by a record computation we performed in a 521-bit finite field GF(p^6). The target finite field is of the same form than finite fields used in recent zero-knowledge proofs in some blockchains. This is the first reported implementation of TNFS.

We cryptanalyse the SIDH-based oblivious pseudorandom function from supersingular isogenies proposed at Asiacrypt'20 by Boneh, Kogan and Woo. To this end, we give an attack on an assumption, the auxiliary one-more assumption, that was introduced by Boneh et al. and we show that this leads to an attack on the oblivious PRF itself. The attack breaks the pseudorandomness as it allows adversaries to evaluate the OPRF without further interactions with the server after some initial OPRF evaluations and some offline computations. More specifically, we first propose a polynomial-time attack. Then, we argue it is easy to change the OPRF protocol to include some countermeasures, and present a second subexponential attack that succeeds in the presence of said countermeasures. Both attacks break the security parameters suggested by Boneh et al. Furthermore, we provide a proof of concept implementation as well as some timings of our attack. Finally, we examine the generation of one of the OPRF parameters and argue that a trusted third party is needed to guarantee provable security.

Machine learning aided cryptanalysis is an interesting but challenging research topic. At CRYPTO'19, Gohr proposed a Neural Distinguisher (ND) based on a plaintext difference. The ND takes a ciphertext pair as input and outputs its class (a real or random ciphertext pair). At EUROCRYPTO'20, Benamira et al proposed a deeper analysis of how two specific NDs against Speck32/64 work. However, there are still three research gaps that researchers are eager to fill in. (1) what features related to a ciphertext pair are learned by the ND? (2) how to explain various phenomena related to NDs? (3) what else can machine learning do in conventional cryptanalysis?

In this paper, we filled in the three research gaps: (1) we first propose the Extended Differential-Linear Connectivity Table (EDLCT) which is a generic tool describing a cipher. Features corresponding to the EDLCT are designed to describe a ciphertext pair. Based on these features, various machine learning-based distinguishers including the ND are built. To explore various NDs from the EDLCT view, we propose a Feature Set Sensitivity Test (FSST) to identify which features may have a significant influence on NDs. Features identified by FSST share the same characteristic related to the cipher's round function. Surrogate models of NDs are also built based on identified features. Experiments on Speck32/64 and DES confirm that features corresponding to the EDLCT are learned by NDs. (2) We explain phenomena related to NDs via EDLCT. (3) We show how to use machine learning to search differential-linear propagations ∆ → λ with a high correlation, which is a tough task in the differential-linear attack. Applications in Chaskey and DES demonstrate the advantages of machine learning. Furthermore, we provide some optional inputs to improve ND

IBM Digital Health Pass (IDHP) is a technology developed by IBM offering the technical infrastructure to allow individuals to prove their COVID19-related health status (e.g., whether that individual was tested negative for COVID19, has been partially/fully vaccinated, or recovered from COVID19) to third parties in a secure and privacy-respectful way.

In a nutshell, IBM Digital Health Pass technology enables issuers, i.e., authorised healthcare providers onboarded to the system by health authorities of a given country or jurisdiction, to produce digital attestations about individuals’ health status. These attestations, called Health Certificates are issued to individuals, called subjects or holders, and are stored on a piece of paper or within subjects’ mobile phone wallets. Subjects can then demonstrate the authenticity of one or more of their Health Certificates to third parties of their choice called verifiers, when the necessity of demonstrating COVID19 related health status arises. Subjects can also demonstrate their association with each of their Health Certificates.

IBM Digital Health Pass is built around preserving individuals’ privacy as a first-class requirement, based on established public key cryptography concepts in a way that can easily scale to millions of Health Certificates.

In EUROCRYPT~2020, Hosoyamada and Sasaki find differential paths with probability $2^{-2n/3}$ can be useful in quantum collision attacks, v.s. $2^{-n/2}$ for classical collision attacks. This observation led to attacks for more rounds on some AES-like hash functions. In this paper, we quantize the multi-collision distinguisher proposed by Biryukov, Khovratovich, and Nikoli{\'c} at CRYPTO~2009, and propose quantum multi-collision distinguishers. Compared against the tight bound $2^{\frac{n}{2} \cdot(1-\frac{1}{2^{q}-1})}$ for quantum multi-collision on ideal functions by Liu and Zhang in EUROCRYPT~2019, we find the probability of useful differential paths can be as low as $2^{-n}$. This leads to even more attacked rounds than both classical multi-collision distinguishers and quantum collision attacks. To demonstrate the effectiveness, we applied the attack model to AES, Rijndael, and the post-quantum block cipher design Saturnin. Distinguishing attacks are found on the full version of AES-192, AES-256, Rijndael-128-160, and Rijndael-128-224. Other results include 8-round AES-128, 11-round Rijndael-160-192, 12-round Rijndael-160-256, and 10-round Saturnin-256.

We construct lightweight authenticated key exchange protocols based on pre-shared keys, which achieve full forward security and rely only on simple and efficient symmetric-key primitives. All of our protocols have rigorous security proofs in a strong security model, all have low communication complexity, and are particularly suitable for resource-constrained devices. We describe three protocols that apply linear key evolution to provide different performance and security properties. Correctness in parallel and concurrent protocol sessions is difficult to achieve for linearly key-evolving protocols, emphasizing the need for assurance of availability alongside the usual confidentiality and authentication security goals. We introduce synchronization robustness as a new formal security goal, which essentially guarantees that parties can re-synchronize efficiently. All of our new protocols achieve this property. Since protocols based on linear key evolution cannot guarantee that all concurrently initiated sessions successfully derive a key, we also propose two constructions with non-linear key evolution based on puncturable PRFs. These are instantiable from standard hash functions and require O( C log(|CTR|)) memory, where C is the number of concurrent sessions and |CTR| is an upper bound on the total number of sessions per party. These are the first protocols to simultaneously achieve full forward security, synchronization robustness, and concurrent correctness.

This paper presents Multidimentional Moddiv public key cryptosystem which is based on an instance of LWR problem consisting on finding a secret vector $ X $ in $\mathbb{Z}_{r}^{n}$ knowing vectors $A$ and $B$ respectively in $\mathbb{Z}_{s}^{m}$ and $\mathbb{Z}_{t}^{l}$ , where elements of vector B are defined as follows : $B(i)$ =( ($\sum_{j=1}^{j=n} X(j) *A(j+i) $) $ Mod(2^ p)Div(2^ q)$ . Mod is integer modulo operation, Div is integer division operation, p and q are known integers satisfying $ p > 2 \times q $ . Size in bits of s equals p, size of bits of r equals q, and size in bits of t equals $p-q$, $ m >2 \times n $ and $ l = m - n $.

Delegating heavy computations to auxiliary servers, while keeping the inputs secret, presents a practical solution for computationally limited devices to use resource-intense cryptographic protocols, such as those based on isogenies, and thus allows the deployment of post-quantum security on mobile devices and in the internet of things. We propose two algorithms for the secure and verifiable delegation of isogeny computations in the CSIDH setting. We then apply these algorithms to different instances of CSIDH and to the signing algorithms SeaSign and CSI-FiSh. Our algorithms present a communication-cost trade-off. Asymptotically (for high communication), the cost for the delegator is reduced by a factor $9$ for the original CSIDH-512 parameter set and a factor $20$ for SQALE'd CSIDH-4096, while the relative cost of SeaSign vanishes. Even for much lower communication cost, we come close to these asymptotic results. Using the knowledge of the class group, the delegation of CSI-FiSh is basically free (up to element generation in $\mathbb{Z}_{\#\text{Cl}(\mathcal{O})}$) already at a very low communication cost.

We work on some open problems in radical isogenies. Radical isogenies are formulas to compute chains of $N$-isogenies for small $N$ and proposed by Castryck, Decru, and Vercauteren in Asisacrypt 2020. These formulas do not need to generate a point of order $N$ generating the kernel and accelerate some isogeny-based cryptosystems like CSIDH. On the other hand, since these formulas use Tate normal forms, these need to transform Tate normal forms to curves with efficient arithmetic, e.g., Montgomery curves. In this paper, we propose radical-isogeny formulas of degrees 3 and 4 on Montgomery curves. Our formulas have simple formulas to recover Montgomery coefficients and are more efficient for some cryptosystems than the original radical isogenies. In addition, we prove a conjecture left open by Castryck et al. that relates to radical isogenies of degree 4.

In time-specific signatures (TSS) [Paterson \& Quaglia, SCN'10] [Ishizaka \& Kiyomoto, ISC'20] with $T$ numerical values, each signer is given a secret-key associated with a numerical value $t\in[0,T-1]$ and each signature on a message is generated under a numerical range $[L,R]$ s.t. $0\leq L\leq R\leq T-1$. A signer with $t$ can correctly generate a signature under $[L,R]$ if $t$ is truly included in $[L,R]$, i.e., $t\in[L,R]$.

As a generalized primitive of TSS, we propose multi-dimensional \textit{sub}-range signatures (MDSBRS). As a related primitive, we also propose multi-dimensional \textit{super}-range signatures (MDSPRS). In MDSBRS (resp. MDSPRS) with $D\in\mathbb{N}$ dimensions, each secret-key is associated with a set of $D$ ranges $\{[l_i,r_i]\mid i\in[1,D]\}$ s.t. $0 \leq l_i\leq r_i\leq T_i-1$ and a threshold value $d\in[1,D]$, and it correctly produces a signature on any message under a set of $D$ ranges $\{[L_i,R_i]\mid i\in[1,D]\}$ s.t. $0 \leq L_i\leq R_i\leq T_i-1$, if and only if total number of key-ranges every one $[l_i,r_i]$ of which is a \textit{sub}-range (resp. \textit{super}-range) of the corresponded signature-range $[L_i,R_i]$, i.e., $L_i\leq l_i\leq r_i\leq R_i$ (resp. $l_i\leq L_i\leq R_i\leq r_i$), is more than $d-1$. We show that, by extending (or generalizing) an existing TSS scheme, we obtain MDSBRS and MDSPRS schemes each one of which is secure, i.e., existentially unforgeable and perfectly (signer-)private, under standard assumption and asymptotically efficient.

Blockchain systems are rapidly gaining traction. Decentralized storage systems like Filecoin are a crucial component of this ecosystem that aim to provide robust file storage through a Proof of Replication (PoRep) or its variants.

However, a PoRep actually offers limited robustness. Indeed if all the file replicas are stored on a single hard disk, a single catastrophic event is enough to lose the file.

We introduce a new primitive, Proof of Geo-Retrievability or in short "GeoPoRet", that enables proving that a file is located within a strict geographic boundary. Using GeoPoRet, one can trivially construct a PoRep by proving that a file is in several distinct geographic regions. We define what it means for a GeoPoRet scheme to be complete and sound, in the process making important extensions to prior formalism.

We propose GoAT, a practical GeoPoRet scheme to prove file geolocation. Unlike previous geolocation systems that rely on trusted-verifiers, GoAT bootstraps using public timestamping servers on the internet that serve as geolocation anchors, tolerating a local threshold of dishonest anchors. GoAT internally uses a communication-efficient Proof-of-Retrievability (PoRet) scheme in a novel way to achieve constant-size PoRet-component in its proofs.

We validate GoAT's practicality by conducting an initial measurement study to find usable anchors and also perform a real-world experiment. The results show that a significant fraction of the internet can be used as GoAT anchors. Furthermore, GoAT achieves geolocation radii as little as 1000km.

During the Crypto Forum Research Group (CFRG)'s standardization of password-authenticated key exchange (PAKE) protocols, a novel property emerged: a PAKE scheme is said to be ``quantum-annoying'' if a quantum computer can compromise the security of the scheme, but only by solving one discrete logarithm for each guess of a password. Considering that early quantum computers will likely take quite long to solve even a single discrete logarithm, a quantum-annoying PAKE, combined with a large password space, could delay the need for a post-quantum replacement by years, or even decades.

In this paper, we make the first steps towards formalizing the quantum-annoying property. We consider a classical adversary in an extension of the generic group model in which the adversary has access to an oracle that solves discrete logarithms. While this idealized model does not fully capture the range of operations available to an adversary with a general-purpose quantum computer, this model does allow us to quantify security in terms of the number of discrete logarithms solved. We apply this approach to the CPace protocol, a balanced PAKE advancing through the CFRG standardization process, and show that the CPaceBase variant is secure in the generic group model with a discrete logarithm oracle.

Revocable identity-based encryption (RIBE) is an extension of IBE that satisfies a key revocation mechanism to manage a number of users dynamically and efficiently. To resist quantum attacks, two adaptively secure lattice-based RIBE schemes are known in the (quantum) random oracle model ((Q)ROM). Wang et al.'s scheme that is secure in the ROM has large secret keys depending on the depth of a binary tree and its security reduction is not tight. Ma and Lin's scheme that is secure in the QROM has large ciphertexts depending on the length of identities and is not anonymous. In this paper, we propose an adaptively secure lattice-based RIBE scheme that is secure in the QROM. Our scheme has compact parameters, where the ciphertext-size is smaller than Wang et al.'s scheme and the secret key size is the same as Ma and Lin's scheme. Moreover, our scheme is anonymous and its security reduction is completely tight. We design the proposed scheme by modifying Ma-Lin's scheme instantiated by the Gentry-Peikert-Vaikuntanathan (GPV) IBE. We can obtain the advantages of our scheme by making use of Katsumata et al.'s proof technique of the GPV IBE in the QROM.

The framework of interactive oracle proofs (IOP) has been used with great success to construct a number of efficient transparent zk-SNARKs in recent years. However, these constructions are based on Reed-Solomon codes and can only be applied directly to statements given in the form of arithmetic circuits or R1CS over large fields $\mathbb{F}$ since their soundness error is at least $1/|\mathbb{F}|$.

This motivates the question of what is the best way to apply these IOPs to statements that are naturally written as R1CS over small fields, and more concretely, the binary field $\mathbb{F}_2$. While one can just see the system as one over an extension field $\mathbb{F}_{2^e}$ containing $\mathbb{F}_2$, this seems wasteful, as it uses $e$ bits to encode just one ``information'' bit. In fact, the recent BooLigero has devised a way to apply the well-known Ligero while being able to encode $\sqrt{e}$ bits into one element of $\mathbb{F}_{2^e}$.

In this paper, we introduce a new protocol for $\mathbb{F}_2$-R1CS which among other things relies on a more efficient embedding which (for practical parameters) allows to encode $\geq e/4$ bits into an element of $\mathbb{F}_{2^e}$. Our protocol makes then black box use of lincheck and rowcheck protocols for the larger field. Using the lincheck and rowcheck introduced in Aurora and Ligero respectively we obtain $1.31 - 1.65 \times$ smaller proofs for Aurora and $3.71 \times$ for Ligero. We also estimate the reduction of prover time by a factor of $24.7 \times$ for Aurora and between $6.9 - 32.5 \times$ for Ligero without interactive repetitions.

Our methodology uses the notion of reverse multiplication friendly embeddings introduced in the area of secure multiparty computation, combined with a new IOPP to test linear statements modulo a subspace $V \leq \mathbb{F}_{2^e}$ which may be of independent interest.

Today’s society depends on interconnected electronic devices, which handle various sensitive information. Due to the knowledge needed to develop these devices and the economic advantage of reusable solutions, most of these systems contain Third-Party Intellectual Property (3PIP) cores that might not be trustworthy. If one of these 3PIP cores is vulnerable, the security of the entire device is potentially affected. As a result, sensitive data that is processed by the device can be leaked to an attacker. Competitions like Hack@DAC serve as a playground to develop and examine novel approaches and computer-aided tools that identify security vulnerabilities in System-on-Chip (SoC) Register-Transfer-Level (RTL) designs. In this paper, we present a successful divide and conquer approach to test SoC security which is illustrated by exemplary RTL vulnerabilities in the competition’s SoC design. Additionally, we craft real-world software attacks that exploit these vulnerabilities.

So far, signature schemes based on the MPC-in-the-head approach (MPCitH) have either been designed by taking a proof system and selecting a suitable symmetric-key primitive (Picnic, CCS16), or starting with an existing primitive such as AES and trying to find the most suitable proof system (BBQ, SAC19 or Banquet, PKC21). In this work we do both: we improve certain symmetric-key primitives to better fit signature schemes, and we also propose a new signature scheme by co-designing a proof system and a new block cipher. Our concrete results are as follows.

First, we show how to provably remove the need to include the key schedule of block ciphers. This simplifies schemes like Picnic and it also leads to the fastest and smallest AES-based signatures. For example, we achieve signature sizes of around 10.8 to 14.2 KB for the 128-bit security level, on average 10% shorter than Banquet and 15% faster.

Second, we investigate a variant of AES with larger S-boxes we call LSAES, for which we can argue that it is very likely at least as strong as AES, further reducing the size of AES-based signatures to 9.9 KB.

Finally, we present a new signature scheme, Rainier, based on a new block cipher called Rain combined with a Banquet-like proof system. To the best of our knowledge, it is the first MPCitH-based signature scheme which can produce signatures that are less than 5 KB in size; it also outperforms previous Picnic and Banquet instances in all performance metrics.

An approximate homomorphic encryption scheme called CKKS (Cheon-Kim-Kim-Song) is considered one of the most promising fully homomorphic encryption (FHE) schemes since it enables computations on real and complex numbers in encrypted form. Several bootstrapping approaches were proposed for CKKS to refresh the modulus in a ciphertext. However all the existing bootstrapping approaches for CKKS rely on polynomial approximation of modulus reduction function and consequently, the quality of the message deteriorates due to polynomial approximation errors. We propose the first bootstrapping approach for the CKKS scheme without polynomial approximation of the modulus reduction function. Instead, our procedure adopts blind rotation technique from FHEW-type schemes and as a result, our approach introduces only an error that is comparable to a rescaling error. We also present several optimizations including compact representation of public keys required for bootstrapping and modified blind rotation technique for the case of sparse secret key. We demonstrate that our bootstrapping procedure can be generalized to the BGV and BFV schemes with minor modifications in the proposed algorithms.

Recently, a sequence of works have made strong advances in two-round (i.e., round-optimal) secure multi-party computation (MPC). In the honest-majority setting -- the focus of this work -- Ananth et al. [CRYPTO'18, EC'19], Applebaum et al. [TCC'18, EC'19] and Garg et al. [TCC'18] have established the feasibility of general two-round MPC in standard communication models involving broadcast (BC) and private point-to-point (P2P) channels.

In this work, we set out to understand what features of the communication model are necessary for these results, and more broadly the design of two-round MPC. Focusing our study on the plain model -- the most natural model for honest-majority MPC -- we obtain the following results:

1. Dishonest majority from Honest majority: In the two round setting, honest-majority MPC and dishonest-majority MPC are surprisingly close, and often equivalent. This follows from our results that the former implies 2-message oblivious transfer, in many settings. (i) We show that without private point-to-point (P2P) channels, i.e., when we use only broadcast (BC) channels, honest-majority MPC implies 2-message oblivious transfer. (ii) Furthermore, this implication holds even when we use both P2P and BC, provided that the MPC protocol is robust against ``fail-stop'' adversaries.

2. The curious case of Identifiable Abort: While security with guaranteed output delivery (and even fairness) against malicious adversaries is impossible in two rounds, nothing is known with regards to the ``next best'' security notion, namely, security with identifiable abort (IA). We show that IA is impossible to achieve with honest-majority even if we use both P2P and BC channels. However, surprisingly, this lower bound can be overcome by replacing P2P channels with a ``bare'' (i.e., untrusted) public-key infrastructure (PKI).

These results ``explain'' that the reliance on P2P channels (together with BC) in the recent two-round protocols was in fact necessary, and that these protocols couldn't have achieved a stronger security guarantee, namely, IA. Overall, our results (put together with prior works) fully determine the best-achievable security for honest-majority MPC in different communication models in two rounds. As a consequence, they yield the following hierarchy of communication models:

BC < PTP < BC+PTP < BC+PKI

This shows that contrary to common perception, BC channel is the weakest communication model, and that a bare PKI setup is strictly stronger than P2P channels.

Secure hash functions are widely used cryptographic algorithms to secure diverse attacks. A one-way secure hash function is used in the various cryptographic area, for instance, password protection. However, most of the hash functions provide security based on static parameters and publicly known operations. Therefore, it becomes easier to attack by the attackers because all parameters and operations are predefined. The publicly known parameters and predefined operations make the oracle regenerate the key even though it is a one-way secure hash function. Moreover, the key (sensitive data) is mixed with the predefined constant where an oracle may find a way to discover the key. To address the above issues of the secure hash functions, we propose a novel and one-way secure hash algorithm, OSHA for short, to protect sensitive data against attackers. OSHA depends on a pseudo-random number generator to generate a private key. Moreover, OSHA mixes multiple private keys to generate a hash value. Furthermore, OSHA uses dynamic parameters, which is difficult for adversaries to guess. Unlike conventional secure hash algorithms, OSHA does not depend on fixed constants. It replaces the fixed constant with the private keys. Also, the key is not mixed with the private keys; hence, there is no way to recover and reverse the process for the adversaries.

We put forth a template for constructing statistical ZAPs for NP. Our template compiles NIZKs for NP in the hidden bit model (which exist unconditionally) into statistical ZAPs using a new notion of interactive hidden-bit generator (IHBG), which adapts the notion of hidden-bit generator to the plain model by building upon the recent notion of statistically-hiding extractable commitments. We provide a construction of IHBG from the explicit hardness of the decision Diffie-Hellman assumption (where explicit refers to requiring an explicit upper bound on the advantage of any polynomial-time adversary against the assumption) and the existence of statistical ZAPs for a specific simple language, building upon the recent construction of dual-mode hidden-bit generator from (Libert et al., EUROCRYPT 2020). We provide two instantiations of the underlying simple ZAP: 1. Using the recent statistical ZAP for the Diffie-Hellman language of (Couteau and Hartmann, CRYPTO 2020), we obtain statistical ZAPs for NP assuming (the explicit hardness of) DDH in $G_1$ and kernel-DH in $G_2$ (a search assumption which is weaker than DDH), where $(G_1,G_2)$ are groups equipped with an asymmetric pairing. This improves over the recent work of (Lombardi et al., EUROCRYPT 2020) which achieved a relaxed variant of statistical ZAP for NP, under a stronger assumption. 2. Using the recent work of (Couteau et al., EUROCRYPT 2020), we obtain statistical ZAPs for NP assuming the explicit hardness of DDH, together with the assumption that no efficient adversary can break the key-dependent message one-wayness of ElGamal with respect to efficient functions over groups of size $2^\secpar$ with probability better than $\poly(\secpar)/2^{(c + o(1)) \cdot \secpar}$, denoted $2^{-c\secpar}$-\OWKDM, for a constant c = 1/2, in pairing-free groups. Note that the latter is a search discrete-log-style falsifiable assumption, incomparable to DDH (in particular, it is not known to imply public-key encryption).