International Association
for Cryptologic Research

The CIS Lab continually seeks the top minds and rising stars in cryptography research, with internship and postdoctoral research positions available starting in 2022. All positions will be in-person at our Sunnyvale office. Applications should be submitted by December 20 to guarantee full consideration.

Postdoctoral research positions are available with an initial duration of one year, and the possibility of extension to two years. Postdocs will be matched with a host from the lab, but are welcome to collaborate with any of our world-class scientists. Applicants should have or expect to have a PhD degree relating to cryptography, computer security, or theoretical computer science by summer 2022.

For further information and to apply, please visit https://careers.ntt-research.com/cis

Closing date for applications:

Contact: cis.careers@ntt-research.com

More information: https://careers.ntt-research.com/cis

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.

Trading goods lies at the backbone of the modern economy and the recent advent of cryptocurrencies has opened the door for trading decentralized (digital) assets: A large fraction of the value of cryptocurrencies comes from the inter-currency exchange and trading, which has been arguably the most successful application of decentralized money. The security issues observed with centralized, custodial cryptocurrency exchanges have motivated the design of atomic swaps, a protocol for coin exchanges between any two users. Yet, somewhat surprisingly, no atomic swap protocol exists that simultaneously satisfies the following simple but desired properties: (i) non-custodial, departing from a third party trusted holding the coins from users during the exchange; (ii) universal, that is, compatible with all (current and future) cryptocurrencies; (iii) multi-asset, supporting the exchange of multiple coins in a single atomic swap.

From a theoretical standpoint, in this work we show a generic protocol to securely swap $n$ coins from any (possible multiple) currencies for $\tilde{n}$ coins of any other currencies, for any $n$ and $\tilde{n}$. We do not require any custom scripting language supported by the corresponding blockchains, besides the bare minimum ability to verify signatures on transactions. For the special case when the blockchains use ECDSA or Schnorr signatures, we design a practically efficient protocol based on adaptor signatures and time-lock puzzles. As a byproduct of our approach, atomic swaps transactions no longer include custom scripts and are identical to standard one-to-one transactions. We also show that our protocol naturally generalizes to any cycle of users, i.e., atomic swaps with more than two participants. To demonstrate the practicality of our approach, we have evaluated a prototypical implementation of our protocol for Schnorr/ECDSA signatures and observed that an atomic swap requires below one second on commodity machines. Even on blockchains with expressive smart contract support (e.g., Ethereum), our approach reduces the on-chain cost both in terms of transaction size and gas cost.

In this paper we study and relate several invariants connected to the solving degree of a polynomial system. This provides a rigorous framework for estimating the complexity of solving a system of polynomial equations via Groebner bases methods. Our main results include a connection between the solving degree and the last fall degree and one between the degree of regularity and the Castelnuovo--Mumford regularity.

We describe a technique to backdoor a prime factor of a composite odd integer $N$, so that an attacker knowing a possibly secret factor base $\mathcal{B}$, can efficiently retrieve it from $N$. Such method builds upon Complex Multiplication theory for elliptic curves, by generating primes $p$ associated to $\mathcal{B}$-smooth order elliptic curves over $\mathbb{F}_p$. When such primes $p$ divide an integer $N$, the latter can be efficiently factored using a generalization of Lenstra's Factorization Method over rings bigger than $\mathbb{Z}_N$, and with no knowledge other than $N$ and $\mathcal{B}$. We then formalize semiprimality certificates that, based on a result by Goldwasser and Kilian, allow to prove semiprimality of an integer with no need to reveal any of its factors. We show how our prime generation procedure can be used to efficiently produce semiprimality certificates, ultimately allowing us to sketch a multi-party distributed protocol to generate semiprimes with unknown factorisation, particularly relevant in the setting of distributed RSA modulus generation. We provide and discuss implementations of all proposed protocols and we address security of semiprimality certificates by showing that semiprimes generated within our methods result at least as secure as random semiprimes of same size.

Solving a system of $m$ multivariate quadratic equations in $n$ variables (the $\mathcal MQ$ problem) is one of the main challenges of algebraic cryptanalysis. The XL algorithm (XL for short) is a major approach for solving the $\mathcal MQ$ problem with linearization over a coefficient field. Furthermore, the hybrid approach with XL (h-XL) is a variant of XL guessing some variables beforehand. In this paper, we present a variant of h-XL, which we call the polynomial XL (PXL). In PXL, the whole $n$ variables are divided into $k$ variables to be fixed and the remaining $n-k$ variables as ``main variables'', and we generate the Macaulay matrix with respect to the $n-k$ main variables over a polynomial ring of the $k$ variables. By eliminating some columns of the Macaulay matrix over the polynomial ring before guessing $k$ variables, the amount of manipulations required for each guessed value can be reduced. Our complexity analysis indicates that PXL is efficient on the system with $n \approx m$. For example, on systems over ${\mathbb F}_{2^8}$ with $n=m=80$, the number of manipulations required by the hybrid approaches with XL and Wiedemann XL and PXL is estimated as $2^{252}$, $2^{234}$, and $2^{220}$, respectively.

The security of code based constructions is usually assessed by Information Set Decoding (ISD) algorithms. In the quantum setting, amplitude amplification yields an asymptotic square root gain over the classical analogue. However, it is still unclear whether a real quantum circuit could yield actual improvements or suffer an enormous overhead due to its implementation. This leads to different considerations of these quantum attacks in the security analysis of code based proposals. In this work we clarify this doubt by giving the first quantum circuit design of the fully-fledged ISD procedure, an implementation in the quantum simulation library Qibo as well as precise estimates of its complexities. We show that against common belief, Prange's ISD algorithm can be implemented rather efficiently on a quantum computer, namely with only a logarithmic overhead in circuit depth compared to a classical implementation.

As another major contribution, we leverage the idea of classical co-processors to design hybrid classical-quantum trade-offs, that allow to tailor the necessary qubits to any available amount, while still providing quantum speedups. Interestingly, when constraining the width of the circuit instead of its depth we are able to overcome previous optimality results on constraint quantum search.

SNOW-V is a stream cipher recently designed for 5G communication system. In this paper, we propose two efficient algorithms to evaluate the precise correlation of SNOW-V's two main nonlinear components with linear hull effects fully considered. Based on these algorithms, we could efficiently and extensively search much more linear masks than before. The ideas of these algorithms can be generalized to other similar nonlinear components in symmetric cipher. We apply our algorithms to full SNOW-V to search different types of linear approximations with high correlations. Our results depict more linear approximations with higher correlations than those proposed for full SNOW-V and SNOW-$\text{V}_{\boxplus_{32},\boxplus_8}$ recently. The best linear approximation we found has absolute correlation $2^{-47.567}$. There are at least 8, 135 and 1092 linear approximations with absolute correlation greater than $2^{-47.851}$, $2^{-49}$ and $2^{-50}$ respectively, which would derive a fast correlation attack with time/memory/data complexities $2^{240.86}$, $2^{240.37}$ and $2^{236.87}$. It is better than all the previous results of fast correlation attack against full SNOW-V. Moreover, we propose some properties for linear trails with 3 active S-boxes, which give a theoretical explanation that automatic search method lacks of. Our work provides a more comprehensive description for the linear approximation properties of full SNOW-V.

Blockchain is a decentralized ledger applying the peer-to-peer (P2P) network, cryptography and consensus mechanism over distributed network. Especially, the underlying cryptographic algorithms protect the blockchain integrity and data authenticity. However, it is well-known that every single algorithm is associated with a limited lifespan due to the increasing computational power of attackers. The compromise of algorithms directly leads to the compromise of blockchain validity. There are two existing long-term blockchain schemes dealing with this problem, but we observe that in these schemes: 1) the calculation of block hash values is not compatible with existing blockchains; 2) the hash transition procedure is only specified from the first algorithm to the second one, there are multiple possibilities to implement the scheme for a longer time, some of them may lead to the failure of the scheme; 3) the security of their schemes are not formally analyzed and proved. In this paper, we propose an enhanced long-term blockchain scheme as a solution to issue 1 and 2, and we formally prove that our scheme is secure without the limitation of cryptographic algorithms. Besides, we implement our scheme, the results show that our hash transition procedure can be completed between 20 minutes (best case) and several hours (worst case) for a current Bitcoin and Ethereum blockchain, which is very efficient.

Event date: 12 September to 16 September 2022