International Association
for Cryptologic Research

In 2019, Gu Chunsheng introduced Integer-RLWE, a variant of RLWE devoid of some of its efficiency flaws. Most notably, he proposes a setting where $n$ can be an arbitrary positive integer, contrarily to the typical construction $n = 2^k$. In this paper, we analyze the new problem and implement the classical meet-in-the-middle and lattice-based attacks. We then use the peculiarity of the construction of $n$ to build an improved lattice-based attack in cases where $n$ is composite with an odd divisor. For example, for parameters $n = 2000$ and $q = 2^{33}$, we reduce the estimated complexity of the attack from $2^{288}$ to $2^{164}$. We also present reproducible experiments confirming our theoretical results.

CSIDH is an isogeny-based post-quantum key establishment protocol proposed in 2018. In this work, we analyze attacking implementations of CSIDH which use dummy isogeny operations using fault injections from a mathematical perspective. We detail an attack by which the private key can be learned by the attacker up to sign with absolute certainty using $\sum \lceil \log_2(b_i) + 1 \rceil$ fault attacks on pairwise distinct group action evaluations under the same private key under ideal conditions using a binary search approach, where $\vec{b}$ is the bound vector defining the keyspace. As a countermeasure to this attack, we propose randomly mixing the real degree $\ell_j$ isogenies together with the dummy ones by means of a binary decision vector. To evaluate the efficacy of this countermeasure, we formulate a probability-based attack on this randomized scheme using a maximum likelihood approach and simulate the attack using 6 bound vectors used in previous CSIDH implementations. We found that the number of attacks required under our model to reach just 1% certainty about the key increased by a factor between 8--12 over the standard approach in the setting of signed private keys and a factor between 28--45 using non-negative private keys, depending on $\vec{b}$. We derive theoretical upper bounds on the number of attacks required to reach a specified certainty threshold about the key under our model. Based on our data and the minimal additional overhead required, we recommend all future implementations of CSIDH to employ a randomized decision vector approach. Finally since our model assumes fault attacks provide no information on the sign of the key, we use a technique based on Gray codes to optimize the standard meet-in-the-middle attack for learning the sign of the key values once their magnitudes have been learned through fault attacks. We estimate that, on average, this optimized technique uses approximately 88% fewer field-multiplication-equivalent operations over the standard approach.

Event date: 3 May to 6 May 2021
Submission deadline: 4 December 2020
Notification: 19 February 2021

Event date: 5 November to 6 November 2020
Submission deadline: 10 September 2020
Notification: 26 October 2020

Event date: 3 September to 4 September 2020

DFINITY is reimagining the Internet as a public network that hosts secure software and services. The Internet Computer is a new technology stack that is unhackable, fast, scales to billions of users around the world, and supports a new kind of autonomous software that promises to reverse Big Tech’s monopolization of the internet.

DFINITY is looking for a full-time Cryptography Researcher, specialized in practical and provably secure cryptographic protocols for blockchains. The main task will be to design, develop, and prove secure, efficient cryptographic protocols for a distributed system and you will contribute in creating a high-performance blockchain computer. We offer a flexible work environment and an opportunity to collaborate with a dynamic and talented team of researchers and developers from around the world.

Requirements:

PhD in Cryptography, emphasis on efficient and provably secure protocols

Excellent record of peer-reviewed publications, in particular at IACR, ACM, and IEEE conferences

Experience in the implementation of cryptographic protocols in C or Rust

Good understanding of practical systems and their security

Responsibilities:

Identify functional and security requirements of cryptographic protocols for the DFINITY platform

Design provably secure, scalable and practical cryptographic protocols

Design security models, capturing requirements and adversarial models

Provide full implementation specification of cryptographic protocols

Collaborate with a team of Researchers and Developers across our global research centers

Participate in software architecture decisions, providing necessary information in a clear fashion

Collaborate with engineers to implement cryptographic protocols

Write high-quality research papers targeted at top conferences and journals

Represent the company in academic and industry conferences and share technical information with the public

Closing date for applications:

Contact: Jan Camenisch - please submit via https://dfinity.org/careers/

More information: https://dfinity.org/careers/

The isogeny-based scheme CSIDH is a promising candidate for quantum-resistant static-static key exchanges with very small public keys, but is inherently difficult to implement in constant time. In the current literature, there are two directions for constant-time implementations: algorithms containing dummy computations and dummy-free algorithms. While the dummy-free implementations come with a 2x slowdown, they offer by design more resistance against fault attacks. In this work, we evaluate how practical fault injection attacks are on the constant-time implementations containing dummy calculations. We present three different fault attacker models. We evaluate our fault models both in simulations and in practical attacks. We then present novel countermeasures to protect the dummy isogeny computations against fault injections. The implemented countermeasures result in an overhead of 7% on the Cortex-M4 target, falling well short of the 2x slowdown for dummy-less variants.

WebAuthn, forming part of FIDO2, is a W3C standard for strong authentication, which employs digital signatures to authenticate web users whilst preserving their privacy. Owned by users, WebAuthn authenticators generate attested and unlinkable public-key credentials for each web service to authenticate users. Since the loss of authenticators prevents users from accessing web services, usable recovery solutions preserving the original WebAuthn design choices and security objectives are urgently needed.

We examine Yubico's recent proposal for recovering from the loss of a WebAuthn authenticator by using a secondary backup authenticator. We analyse the cryptographic core of their proposal by modelling a new primitive, called Asynchronous Remote Key Generation (ARKG), which allows some primary authenticator to generate unlinkable public keys for which the backup authenticator may later recover corresponding private keys. Both processes occur asynchronously without the need for authenticators to export or share secrets, adhering to WebAuthn's attestation requirements. We prove that Yubico's proposal achieves our ARKG security properties under the discrete logarithm and PRF-ODH assumptions in the random oracle model. To prove that recovered private keys can be used securely by other cryptographic schemes, such as digital signatures or encryption schemes, we model compositional security of ARKG using composable games by Brzuska et al. (ACM CCS 2011), extended to the case of arbitrary public-key protocols.

As well as being more general, our results show that private keys generated by ARKG may be used securely to produce unforgeable signatures for challenge-response protocols, as used in WebAuthn. We conclude our analysis by discussing concrete instantiations behind Yubico's ARKG protocol, its integration with the WebAuthn standard, performance, and usability aspects.

In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove: Let $\tau \in (0,\infty), \delta \in (0,1), \epsilon \in (0,1)$ be arbitrary constants. Assume sub-exponential security of the following assumptions, where $\lambda$ is a security parameter, and the parameters $\ell,k,n$ below are large enough polynomials in $\lambda$:

- The SXDH assumption on asymmetric bilinear groups of a prime order $p = O(2^\lambda)$,

- The LWE assumption over $\mathbb{Z}_{p}$ with subexponential modulus-to-noise ratio $2^{k^\epsilon}$, where $k$ is the dimension of the LWE secret,

- The LPN assumption over $\mathbb{Z}_p$ with polynomially many LPN samples and error rate $1/\ell^\delta$, where $\ell$ is the dimension of the LPN secret,

- The existence of a Boolean PRG in $\mathsf{NC}^0$ with stretch $n^{1+\tau}$,

Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists.

We present CrypTFlow2, a cryptographic framework for secure inference over realistic Deep Neural Networks (DNNs) using secure 2-party computation. CrypTFlow2 protocols are both correct -- i.e., their outputs are bitwise equivalent to the cleartext execution -- and efficient -- they outperform the state-of-the-art protocols in both latency and scale. At the core of CrypTFlow2, we have new 2PC protocols for secure comparison and division, designed carefully to balance round and communication complexity for secure inference tasks. Using CrypTFlow2, we present the first secure inference over ImageNet-scale DNNs like ResNet50 and DenseNet121. These DNNs are at least an order of magnitude larger than those considered in the prior work of 2-party DNN inference. Even on the benchmarks considered by prior work, CrypTFlow2 requires an order of magnitude less communication and 20x-30x less time than the state-of-the-art.

In distributed symmetric-key encryption (DiSE), a set of n distributed servers share a key (or key set) and any t, t <= n, servers can collectively use the shared key (or key set) in a DiSE transaction to encrypt a message or decrypt a ciphertext without reconstructing the shared key (or key set). Each participating server contributes one or more partial results and one participating server called the initiator combines all partial results into a final result. An adversary who has compromised up to (t-1) servers will not be able to access the shared key (or key set).

Due to the distributed nature of DiSE, a DiSE server that has been compromised by an adversary may return wrong partial results to the initiator. Worse, multiple DiSE servers compromised by the same adversary may collude to send back wrong partial results. In this article we developed a robust DiSE that allows an honest initiator to detect wrong partial results by an adversary. The robustness of our DiSE is built through redundant computation. Our robust DiSE can detect wrong partial results by an adversary who has compromised up to min(t-1, n-t) servers. Next, the honest-initiator assumption is removed by rotating the initiator role among active servers across multiple DiSE transactions. A scalable, industry-level implementation for the robust DiSE has been developed and two cases, (t=3, n=5) and (t=16, n=24), have been tested to show the feasibility of robust DiSE. Our robust DiSE can be used to build intrusion-tolerant applications, such as intrusion-tolerant database encryption.

Distance-bounding protocols provide a means for a verifier (e.g., an RFID reader) to estimate his relative distance to a prover (e.g., a bankcard), in order to counteract relay attacks. We propose FlexiDB, a new cryptographic model for DB, parameterised over fine-grained corruptions. It allows to consider trivial cases, classical cases but also new, generalised scenarios in which we show manipulating differently-corrupt provers at once leads to new attacks. We propose a proof-of-concept mechanisation of FlexiDB in the interactive cryptographic prover EasyCrypt, and use it to prove a flavour of man-in-the-middle security on a variant of MasterCard's contactless-payment protocol.

Symmetric Searchable Encryption (SSE) is an encryption technique that allows users to search directly on their outsourced encrypted data while preserving the privacy of both the files and the queries. Unfortunately, majority of the SSE schemes allows users to either decrypt the whole ciphertext or nothing at all. In this paper, we propose a novel scheme based on traditional symmetric primitives, that allows data owners to bind parts of their ciphertexts with specific policies. Inspired by the concept of Attribute-Based Encryption (ABE) in the public setting, we design a scheme through which users can recover only certain parts of an encrypted document if and only if they retain a set of attributes that satisfy a policy. Our construction satisfies the important notion of forward privacy while at the same time supports the multi-client model by leveraging SGX functionality for the synchronization of users. To prove the correctness of our approach, we provide a detailed simulation-based security analysis coupled with an extensive experimental evaluation that shows the effectiveness of our scheme.

Blockchain systems have severe scalability limitations e.g., long confirmation delays. Layer-2 protocols are designed to address such limitations. The most prominent class of such protocols are payment channel networks e.g., the Lightning Network for Bitcoin where pairs of participants create channels that can be concatenated into networks. These allow payments across the network without interaction with the blockchain. A drawback is that all intermediary nodes within a payment path must be online. Virtual Channels, as recently proposed by Dziembowski et al. (CCS'18), allow payments without this limitation. However, these can only be implemented on blockchains with smart contract capability therefore limiting its applicability. Our work proposes the notion of --Lightweight-- Virtual Payment Channels, i.e. only requiring timelocks and multisignatures, enabling Virtual Channels on a larger range of blockchain systems of which a prime example is Bitcoin. More concretely, other contributions of this work are (1) to introduce a fully-fledged formalization of our construction, and (2) to present a simulation based proof of security in Canetti's UC Framework.

There once was a table of hashes That held extra items in stashes It all seemed like bliss But things went amiss When the stashes were stored in the caches

The first Oblivious RAM protocols introduced the ``hierarchical solution,'' (STOC '90) where the servers store a series of hash tables of geometrically increasing capacities. Each ORAM query would read a small number of locations from each level of the hierarchy, and each level of the hierarchy would be reshuffled and rebuilt at geometrically increasing intervals to ensure that no single query was ever repeated twice at the same level. This yielded an ORAM protocol with polylogarithmic (amortized) overhead.

Future works extended and improved the hierarchical solution, replacing traditional hashing with cuckoo hashing (ICALP '11) and cuckoo hashing with a combined stash (Goodrich et al. SODA '12). In this work, we identify a subtle flaw in the protocol of Goodrich et al. (SODA '12) that uses cuckoo hashing with a stash in the hierarchical ORAM solution.

We give a concrete distinguishing attack against this type of hierarchical ORAM that uses cuckoo hashing with a \emph{combined} stash. This security flaw has propagated to at least 5 subsequent hierarchical ORAM protocols, including the recent optimal ORAM scheme, OptORAMa (Eurocrypt '20).

In addition to our attack, we identify a simple fix that does not increase the asymptotic complexity.

We note, however, that our attack only affects more recent \emph{hierarchical ORAMs}, but does not affect the early protocols that predate the use of cuckoo hashing, or other types of ORAM solutions (e.g. Path ORAM or Circuit ORAM).

To prove computational complexity lower bounds in cryp- tography, one often resorts to so-called generic models of computation. For example, a generic algorithm for the discrete logarithm is one which works independently from the group representation—and thus works generically for all group representations. There are a multitude of dif- ferent models in the literature making comparing different results—and even matching lower and upper bounds proven in different models— rather difficult. In this work we view a model as a set of games with the same type of interactions. Using a standard notion of reduction between two games, we establish a hierarchy between models. Different models may now be classified as weaker and stronger if a reduction between them exists. We propose different extensions of the generic group model with different queries, explicitly capturing different information that an algorithm may need to exploit. Finally, we use the hierarchy between these models to systematically compare and improve the results in the literature. First we strengthen the model in which the baby-step giant-step algorithm is proven and weaken the model in which the matching lower bound is proven. We then analyse the discrete logarithm with preprocessing. Upper and lower bounds have been proven in the literature in mismatching models. We weaken the model of the lower bound and strengthen the model of the upper bound to close the gap between the two.

One can bootstrap (R)LWE-based fully homomorphic encryption (FHE) schemes in less than one second, but bootstrapping AGCD-based FHE schemes, also known as FHE over the integers, is still very slow. In this work we propose fast bootstrapping methods for FHE over the integers, closing thus this gap between these two types of schemes. We use a variant of the AGCD problem to construct a new GSW-like scheme that can natively encrypt polynomials, then, we show how the single-gate bootstrapping method proposed by Ducas and Micciancio (EUROCRYPT 2015) can be adapted to FHE over the integers using our scheme, and we implement a bootstrapping that runs in less than one second in a common personal computer. We also perform multi-value bootstrapping on non-binary message spaces achieving running times close to one second with modest memory requirements.

We introduce the notion of a Succinct Parallelizable Argument of Knowledge (SPARK). This is an argument of knowledge with the following three efficiency properties for computing and proving a (non-deterministic, polynomial time) parallel RAM computation that can be computed in parallel time T with at most p processors: (1) The prover’s (parallel) running time is T + polylog(T * p). (In other words, the prover’s running time is essentially T for large computation times!) (2) The prover uses at most p * polylog(T * p) processors, and (3) the communication and verifier complexity are both polylog(T * p). The combination of all three is desirable as it gives a way to leverage a moderate increase in parallelism in favor of near-optimal running time. We emphasize that even a factor two overhead in the prover’s parallel running time is not allowed.

Our main contribution is a generic construction of SPARKs from any succinct argument of knowledge where the prover’s parallel running time is T * polylog(T * p) when using p processors, assuming collision-resistant hash functions. When suitably instantiating our construction, we achieve a four-round SPARK for any parallel RAM computation assuming only collision resistance. Additionally assuming the existence of a succinct non-interactive argument of knowledge (SNARK), we construct a non-interactive SPARK that also preserves the space complexity of the underlying computation up to polylog(T * p) factors.

We also show the following applications of non-interactive SPARKs. First, they immediately imply delegation protocols with near optimal prover (parallel) running time. This, in turn, gives a way to construct verifiable delay functions (VDFs) from any sequential function. When the sequential function is also memory-hard, this yields the first construction of a memory-hard VDF.

A new approach to the security analysis of hardware-oriented masked ciphers against second-order side-channel attacks is developed. By relying on techniques from symmetric-key cryptanalysis, concrete security bounds are obtained in a variant of the probing model that allows the adversary to make only a bounded, but possibly very large, number of measurements. Specifically, it is formally shown how a bounded-query variant of robust probing security can be reduced to the linear cryptanalysis of masked ciphers. As a result, the compositional issues of higher-order threshold implementations can be overcome without relying on fresh randomness. From a practical point of view, the aforementioned approach makes it possible to transfer many of the desirable properties of first-order threshold implementations, such as their low randomness usage, to the second-order setting. For example, a straightforward application to the block cipher LED results in a masking using less than 700 random bits including the initial sharing. In addition, the cryptanalytic approach introduced in this paper provides additional insight into the design of masked ciphers and allows for a quantifiable trade-off between security and performance.

We propose single-trace side-channel attacks against lattice-based KEMs, the current candidates of the NIST's standardization project. More specifically, we analyze the message encoding in the encapsulation of lattice-based KEMs to obtain the ephemeral session keys, concluding that a single trace leakage allows a whole key recovery: our implementation on a ChipWhisperer UFO STM32F3 target board shows 100% success rates for Crystals-Kyber and Saber regardless of optimization level, and more than a 79% success rate for FrodoKEM. We further show that our attack methodologies are not restricted to the above algorithms but widely applicable to other NIST PQC candidates, including LAC, NewHope, NTRU Prime, and NTRU.