International Association
for Cryptologic Research

We consider four variants of the RSA cryptosystem with an RSA modulus $N=pq$ where the public exponent $e$ and the private exponent $d$ satisfy an equation of the form $ed-k\left(p^2-1\right)\left(q^2-1\right)=1$. We show that, if the prime numbers $p$ and $q$ share most significant bits, that is, if the prime difference $|p-q|$ is sufficiently small, then one can solve the equation for larger values of $d$, and factor the RSA modulus, which makes the systems insecure.

The pseudo-random sampling of constant weight word, as it is currently implemented in schemes like BIKE or HQC, is prone to the leakage of information on the seed being used. This creates a vulnerability when the semantic security conversion requires a deterministic re-encryption. This observation was first made in [HLS21] about HQC, and a timing attack was presented to recover the secret key. As suggested in [HLS21] a similar attack applies to BIKE and an instance of such an attack is presented here, as well as countermeasures similar to those suggested in [HLS21] for HQC. A new approach for fixing the issue is also proposed. It is first remarked that, contrary to what is done currently, the sampling of constant weight words doesn’t need to produce a uniformly distributed output. If the distribution is close to uniform in the appropriate metric, the impact on security is negligible. Also, a new variant of Fisher-Yates shuffle is proposed which is (1) very well suited for secure implementations against timing and cache attacks, and (2) produces constant weight words with a distribution close enough to uniform.

The RSA cryptosystem comprises of two important features that are needed for encryption process known as the public parameter $e$ and the modulus $N$. In 1999, a cryptanalysis on RSA which was described by Boneh and Durfee focused on the key equation $ed-k\phi(N)=1$ and $e$ of the same magnitude to $N$. Their method was applicable for the case of $d

The public parameters of the RSA cryptosystem are represented by the pair of integers $N$ and $e$. In this work, first we show that if $e$ satisfies the Diophantine equation of the form $ex^2-\phi(N)y^2=z$ for appropriate values of $x, y$ and $z$ under certain specified conditions, then one is able to factor $N$. That is, the unknown $\frac{y}{x}$ can be found amongst the convergents of $\frac{\sqrt{e}}{\sqrt{N}}$ via continued fractions algorithm. Consequently, Coppersmith's theorem is applied to solve for prime factors $p$ and $q$ in polynomial time. We also report a second weakness that enabled us to factor $k$ instances of RSA moduli simultaneously from the given $(N_i,e_i)$ for $i=1,2,\cdots,k$ and a fixed $x$ that fulfills the Diophantine equation $e_{i}x^{2}-y_{i}^{2}\phi(N_{i})=z_{i}$. This weakness was identified by solving the simultaneous Diophantine approximations using the lattice basis reduction technique. We note that this work extends the bound of insecure RSA decryption exponents.

Front-running is the malicious, and often illegal, act of both manipulating the order of pending trades and injecting additional trades to make a profit at the cost of other users. In decentralized finance (DeFi), front-running strategies exploit both public knowledge of user trades from transactions pending on the network and the miner's ability to determine the final transaction order. Given the financial loss and increased transaction load resulting from adversarial front-running in decentralized finance, novel cryptographic protocols have been proposed to mitigate such attacks in the permission-less blockchain setting. We systematize and discuss the state-of-the-art of front-running mitigation in decentralized finance, and illustrate remaining attacks and open challenges.

The Transport Layer Security (TLS) protocol is a fundamental building block for ensuring security on Internet. It provides an easy to use framework for the purposes of establishing an authenticated and secure channel between two parties that have never physically met. Nevertheless, TLS only provides a simple cryptographic functionality compared to more advanced protocols such as protocols for secure multiparty computation (MPC).

In this work, we provide a framework for efficiently establishing channels for MPC over the Internet. We focus on MPC protocols in the oblivious transfer (OT) hybrid model such that it is sufficient to establish OT correlations for such a channel. We revisit and combine different notions of UC security proposed in both the MPC and authenticated key exchange settings. Through this work, we show how an OT protocol can be composed with a secure authenticator to ensure the authenticity of messages sent during the OT.

In addition, we adapt and analyse non-interactive OTs based on dense key encapsulation mechanisms (KEMs) in the random oracle model, where the first message, i.e. public key, can be reused. These KEMs can be instantiated based on CDH, RSA and LWE and after a performance and security evaluation, it turns out that the resulting OT protocols are very competitive with the state of the art and are able to leverage existing PKIs.

We present the application of a known subfield lattice attack on a fully homomorphic encryption scheme based on NTRU. We show that the scheme is vulnerable to the attack due to a particular parameter having to satisfy a derived lower bound. We also show that, due to the structure of the scheme, the attack is successful in all practical instantiations of the scheme.

Quantum computers provide a new way of solving problems even in cryptography in which digital signature make an important role. In this paper, we describe a comparison between the spectral test in classical mode and quantum mode through Fourier Transform. A comparison of the results in the two cases was made. Applications of the proposed techniques are from the field of statistical testing of the pseudorandom bit generators used for cryptographic applications. The proposed statistical test is an extension of the Discrete Fourier Transform statistical test proposed in NIST SP 800-22.

Fully homomorphic encryption (FHE) is a powerful tool in cryptography that allows one to perform arbitrary computations on encrypted material without having to decrypt it first. There are numerous FHE schemes, all of which are expanded from somewhat homomorphic encryption (SHE) schemes, and some of which are considered viable in practice. However, while these FHE schemes are semantically (IND-CPA) secure, the question of their IND-CCA1 security is much less studied. In this paper, we group SHE schemes into broad categories based on their similarities and underlying hardness problems. For each category, we show that the SHE schemes are susceptible to either known adaptive key recovery attacks, a natural extension of known attacks, or our proposed attacks. Finally, we discuss the known techniques to achieve IND-CCA1 secure FHE and SHE schemes.

Several cryptosystems using structured lattices have been believed to be quantum resistant. Their security can be linked to the hardness of solving the Shortest Vector Problem over module or ideal lattices. During the past few years it has been shown that the related problem of finding a short generator of a principal ideal can be solved in quantum polynomial time over cyclotomic fields, and classical polynomial time over a range of multiquadratic and multicubic fields. Hence, it is important to study as many as possible other number fields, to improve our knowledge of the aformentioned problems. In this paper we generalise the work done over multiquadratic and multicubic fields to a larger range of real Kummer extensions of prime exponent p. Moreover, we extend the analysis by studying the Log-unit lattice over these number fields, in comparison to already studied fields.

At Indocrypt 2021, Hermelink, Pessl, and Pöppelmann presented a fault injection attack against Kyber’s decapsulation module. The attack can thwart countermeasures such as masking, shuffling, and double executions, but is not overly easy to perform. In this work, we extend and facilitate the attack in two ways, thereby admitting a larger variety of fault injection setups. Firstly, the attack surface is enlarged: originally, the two input operands of the polynomial comparison are covered, and we additionally cover encryption modules such as binomial sampling, butterflies in the last layer of the inverse number-theoretic transform (NTT), modular reduction, and ciphertext compression. Secondly, the fault model is relaxed: originally, precise bit flips are required, and we additionally support set-to-0 faults, set-to-1 faults, random faults, arbitrary bit flips, instruction skips, etc. A notable feature of our attack is that masking and certain forms of blinding help the attack. If finite field elements are visualized in a circular manner, our attack is analogous to the casino game roulette: randomization-based countermeasures spin the wheel, and the attacker only needs to wait for a certain set of pockets.

In this paper we provide technical details on two new attack vectors, relevant to implementations of [GG18] and [GG20] threshold ECDSA protocols. Both attacks lead to a complete secret key extraction by exploiting different parts of the Multiplicative-to-Additive (MtA) sub-protocol the parties run during signing. Our first attack applies to the setting of ”fast” MtA, which runs the protocol with no range proofs. We leverage a powerful oracle, much stronger than originally anticipated in [GG18], to reveal a part of the secret key with each signature we run. The number of required signatures depends on the implementation under attack and the number of parties controlled by the attacker. Our proof of concept demonstrates a full key extraction by a single malicious party using eight signatures. Our second attack deals with the more common setting of “full” MtA, that is, including ZK proofs. The only requirement for mounting a successful attack is to use a small Paillier encryption key. The key size check was not specified in the protocol and therefore missing from most existing threshold ECDSA implementations, making them vulnerable. As we show, choosing a small key completely eliminates a specific hiding property in one of the values sent from the victim to the attacker during one of ZK proofs. This allows a single malicious party to extract the full secret key after a single valid signature. We provide a proof of concept for this attack as well.

In December 2020, David Oranchak, Jarl Van Eycke, and Sam Blake solved a 51-year old mystery: the Zodiac cipher of 340 symbols. Blake (2021) explains their solution. The correctness of their solution has not been seriously doubted, and here we give a further argument in its favor: the unicity distance of the cipher's system is at most 152.

Code-based cryptography plays an important role in post-quantum cryptography. While many crypto-primitives such as public-key encryption, digital signature have been proposed from codes, there is no non-interactive code-based key exchange protocol. We solve the opening problem of constructing a non-interactive key exchange protocol from coding theory in this work. To prove the security of this protocol, we propose a new hard problem called sub-LE problem, which is a sub-problem of code equivalence problem. We prove its hardness by reducing the well-known code linearly equivalence problem to the sub-LE problem. This new hard problem provides many good properties such as partly commutativity. This excites us most because it allows not only the construction of key exchange protocol, but also many other primitives such as a new public-key encryption scheme.

We study zero-knowledge arguments where proofs are: of knowledge, short, publicly-verifiable and produced without interaction. While zkSNARKs satisfy these requirements, we build such proofs in a constrained theoretical setting: in the standard-model---i.e., without a random oracle---and without assuming public-verifiable SNARKs (or even NIZKs, for some of our constructions) or primitives currently known to imply them.

We model and construct a new primitive, SPuC (Succinct Publicly-Certifiable System), where: a party can prove knowledge of a witness $w$ by publishing a proof $\pi_0$; the latter can then be certified non-interactively by a committee sharing a secret; any party in the system can now verify the proof through its certificates; the total communication complexity should be sublinear in $|w|$. We construct SPuCs generally from (leveled) Threshold FHE, homomorphic signatures and linear-only encryption, all instantiatable from lattices and thus plausibly quantum-resistant. We also construct them in the two-party case replacing TFHE with the simpler primitive of homomorphic secret-sharing.

Our model has practical applications in blockchains and in other protocols where there exist committees sharing a secret and it is necessary for parties to prove knowledge of a solution to some puzzle.

We show that one can construct a version of SPuCs with robust proactive security from similar assumptions. In a proactively secure model the committee reshares its secret from time to time. Such a model is robust if the committee members can prove they performed this resharing step correctly. Along the way to our goal we define and build Proactive Universal Thresholdizers, a proactive version of the Universal Thresholdizer defined in Boneh et al. [Crypto 2018].

Isogeny-based cryptosystem from elliptic curves has been well studied for several years, but there are fewer works about isogenies on hyperelliptic curves to this date. In this work, we make the first step to explore isogenies and pairings on generic squared Kummer surfaces, which is believed to be a better type of Kummer surfaces. The core of our work is the Richelot isogeny having two kernels together with each dual onto the squared Kummer surfaces, then a chain of Richelot isogenies is constructed simply. Besides, with the coordinate system on the Kummer surface, we modify the squared pairings, so as to propose a self-contained pairing named squared symmetric pairing, which can be evaluated with arithmetic on the same squared Kummer surface. In the end, as applications, we present a Verifiable Delay Function and a Delay Encryption on squared Kummer surfaces.

This work revisits the security of classical signatures and ring signatures in a quantum world. For (ordinary) signatures, we focus on the arguably preferable security notion of blind-unforgeability recently proposed by Alagic et al. (Eurocrypt'20). We present two short signature schemes achieving this notion: one is in the quantum random oracle model, assuming quantum hardness of SIS; and the other is in the plain model, assuming quantum hardness of LWE with super-polynomial modulus. Prior to this work, the only known blind-unforgeable schemes are Lamport's one-time signature and the Winternitz one-time signature, and both of them are in the quantum random oracle model. For ring signatures, the recent work by Chatterjee et al. (Crypto'21) proposes a definition trying to capture adversaries with quantum access to the signer. However, it is unclear if their definition, when restricted to the classical world, is as strong as the standard security notion for ring signatures. They also present a construction that only partially achieves (even) this seeming weak definition, in the sense that the adversary can only conduct superposition attacks over the messages, but not the rings. We propose a new definition that does not suffer from the above issue. Our definition is an analog to the blind-unforgeability in the ring signature setting. Moreover, assuming the quantum hardness of LWE, we construct a compiler converting any blind-unforgeable (ordinary) signatures to a ring signature satisfying our definition.

The main protection against side-channel attacks consists in computing every function with multiple shares via the masking countermeasure. For IND-CCA secure lattice-based encryption schemes, the masking of the decryption algorithm requires the high-order computation of a polynomial comparison. In this paper, we describe and evaluate a number of different techniques for such high-order comparison, always with a security proof in the ISW probing model. As an application, we describe the full high-order masking of the NIST finalists Kyber and Saber, with a concrete implementation.

As an emerging joint learning model, federated deep learning is a promising way to combine model parameters of different users for training and inference without collecting users’ original data. However, a practical and efficient solution has not been established in previous work due to the absence of effcient matrix computation and cryptography schemes in the privacy-preserving federated learning model, especially in partially homomorphic cryptosystems. In this paper, we propose a practical and efficient privacy-preserving federated learning framework (PEPFL). First, we present a lifted distributed ElGamal cryptosystem that can be applied to federated learning and solve the multi-key problem in federated learning. Secondly, we develop a practical partially single instruction multiple data (PSIMD) parallelism scheme that can encode a plaintext matrix into single plaintext to conduct the encryption, improving effectiveness and reducing communication cost in partially homomorphic cryptosystems. In addition, a novel privacy-preserving federated learning framework is designed by using momentum gradient descent (MGD) with a convolutional neural network (CNN) and the designed cryptosystem. Finally, we evaluate the security and performance of PEPFL. The experiment results demonstrate that the scheme is practicable, effective, and secure with low communication and computational costs.

Federated learning (FL), as an emerging distributed learning framework, can combine training from different users without collecting users’ original data, protecting privacy to a certain extent. However, there are no efficient privacy protection technologies applicable to IoT. One challenge in IoT is to reduce the client-server communication cost and solve communication failure questions. Another challenge is how to utilize highquality data to guarantee training performance. To solve these challenges, we present a privacy-preserving and optimal fraction FL framework based on elliptic curve cryptosystem (ECC) and k-nearest neighbor (KNN) method in an ad-hoc network. Firstly, we propose an improved multiple key EC-ElGamal cryptosystem (MEEC), which can reduce computation overhead and improve the encryption efficiency owing to the lightweight EC-ElGamal cryptosystem with shorter keys and ciphertext. Secondly, we propose the first ad-hoc FL framework with an ad-hoc quit and join algorithm, solving the communication failure questions, guaranteeing the optimal power computation. Thirdly, we raise a Euclidean fraction scheme based on an improved KNN method, which can quickly obtain the optimal training data from the heterogeneity data, avoiding low-quality data or malicious data to join the training. Finally, security analysis and performance evaluation have been performed. Compared with the existing solutions, our scheme is secure, practicable, efficient with low communication and computational costs in IoT.