International Association
for Cryptologic Research

We initiate the study of encryption schemes where the decryption keys are unclonable quantum objects, which we call single decryptor encryption. We give a number of initial results in this area:

-We formalize the notion of single decryptor encryption. -We show that secret-key single decryptor encryption is possible unconditionally, in the setting where a limited number of ciphertexts are given. However, given an encryption oracle, we show that unconditional security is impossible. -We show how to use a very recent notion of one-shot signatures, together with sufficiently powerful witness encryption, to achieve public key single decryptor encryption. -We demonstrate several extensions of our scheme, achieving a number of interesting properties that are not possible classically.

Internet of Things is developing at a very fast rate. In order to ensure security and privacy, end-devices (e.g. smartphones, smart sensors, or any connected smartcards) shall be protected both against cyber attacks (coming down from the network) and against physical attacks (arising from attacker low-level interaction with the device). In this context, proactive protections shall be put in place to mitigate information theft from either side-channel monitoring or active computation/data corruption. Although both countermeasures have been developing fast and have become mature, there has surprisingly been little research to combine both.

In this article, we tackle this difficult topic and highlight a viable solution. It is shown to be more efficient than mere fault detection by repetition (which is anyway prone to repeated correlated faults). The presented solution leverages the fact that both side-channel protection and fault attack detection are coding techniques. We explain how to both prevent (higher-order) side-channel analyses and detect (higher-order) fault injection attacks. The specificity of this method is that it works ``end-to-end'', meaning that the detection can be delayed until the computation is finished. This simplifies considerably the error management logic as there is a single verification throughout the computation.

The final exponentiation, which is the exponentiation by a fixed large exponent, must be performed in the Tate and (optimal) Ate pairing computation to ensure output uniqueness, algorithmic correctness, and security for pairing-based cryptography. In this paper, we propose a new framework of efficient final exponentiation for pairings over families of elliptic curves. Our framework provides two methods: the first method supports families of elliptic curves with arbitrary embedding degrees, and the second method supports families with specific embedding degrees of providing even faster algorithms. Applying our framework to several Barreto-Lynn-Scott families, we obtain faster final exponentiation than the previous state-of-the-art constructions.

We put forward a new abstraction for achieving forward-secure signatures that are (1) short, (2) have fast update and signing and (3) have small private key size. Prior work that achieved these parameters was pioneered by the pebbling techniques of Itkis and Reyzin (CRYPTO 2001) which showed a process for generating a sequence of roots $h^{1/e_1}, h^{1/e_2}, \dots, h^{1/e_T}$ for a group element $h$ in $\mathbb{Z}_N^*$. However, the current state of the art has limitations.

First, while many works claim that Itkis-Reyzin pebbling can be applied, it is seldom shown how this non-trivial step is concretely done. Second, setting up the pebbling data structure takes $T$ time which makes key generation using this approach expensive. Third, many past works require either random oracles and/or the Strong RSA assumption; we will work in the standard model under the RSA assumption.

We introduce a new abstraction that we call an RSA sequencer. Informally, the job of an RSA sequencer is to store roots of a public key $U$, so that at time period $t$, it can provide $U^{1/e_t}$, where the value $e_t$ is an RSA exponent computed from a certain function. This separation allows us to focus on building a sequencer that efficiently stores such values, in a forward-secure manner and with better setup times than other comparable solutions. Our sequencer abstraction also has certain re-randomization properties that allow for constructing forward-secure signatures with a single trusted setup that takes $T$ time and individual key generation takes $\lg(T)$ time.

We demonstrate the utility of our abstraction by using it to provide concrete forward-secure signature schemes. We first give a random-oracle construction that closely matches the performance and structure of the Itkis-Reyzin scheme with the important exception that key generation is much faster (after the one-time setup). We then move on to designing a standard model scheme. This abstraction and illustration of how to use it may be useful for other future works.

We include a detailed performance evaluation of our constructions, with an emphasis on the time and space costs for large caps on the maximum number of time periods $T$ supported. Our philosophy is that frequently updating forward secure keys should be part of ``best practices'' in key maintenance. To make this practical, even for bounds as high as $T=2^{32}$, we show that after an initial global setup, it takes only seconds to generate a key pair, and only milliseconds to update keys, sign messages and verify signatures. The space requirements for the public parameters and private keys are also a modest number of kilobytes, with signatures being a single element in $\mathbb{Z}_N$ and one smaller value.

Progress in quantum technologies forces the development of new cryptographic primitives that are resistant to attacks of an adversary with a quantum computer. A large number of key establishment schemes have been proposed for two participants, but the area of group post-quantum key establishment schemes has not been studied a lot. Not so long ago, an isogeny-based key agreement scheme was proposed for three participants, based on a gradual increase in the degree of the key. We propose another principle for establishing a key for a group of participants using a tree-structure. The proposed key establishment scheme for four participants uses isogeny of elliptic curves as a mathematical tool.

The side-channel community recently investigated a new approach, based on deep learning, to significantly improve profiled attacks against embedded systems. Compared to template attacks, deep learning techniques can deal with protected implementations, such as masking or desynchronization, without substantial pre-processing. However, important issues are still open. One challenging problem is to adapt the methods classically used in the machine learning field (e.g. loss function, performance metrics) to the specific side-channel context in order to obtain optimal results. We propose a new loss function derived from the learning to rank approach that helps preventing approximation and estimation errors, induced by the classical cross-entropy loss. We theoretically demonstrate that this new function, called Ranking Loss (RkL), maximizes the success rate by minimizing the ranking error of the secret key in comparison with all other hypotheses. The resulting model converges towards the optimal distinguisher when considering the mutual information between the secret and the leakage. Consequently, the approximation error is prevented. Furthermore, the estimation error, induced by the cross-entropy, is reduced by up to 23%. When the ranking loss is used, the convergence towards the best solution is up to 23% faster than a model using the cross-entropy loss function. We validate our theoretical propositions on public datasets.

One-time memories (OTM) are the hardware version of oblivious transfer, and are useful for constructing objects that are impossible with software alone, such as one-time programs. In this work, we consider attacks on OTMs where a quantum adversary can leverage his physical access to the memory to mount quantum ``superposition attacks'' against the memory. Such attacks result in significantly weakened OTMs. For example, in the application to one-time programs, it may appear that such an adversary can always “quantumize” the classical protocol by running it on a superposition of inputs, and therefore learn superpositions of outputs of the protocol.

Perhaps surprisingly, we show that this intuition is false: we construct one-time programs from quantum-accessible one-time memories where the view of an adversary, despite making quantum queries, can be simulated by making only classical queries to the ideal functionality. At the heart of our work is a method of immunizing one-time memories against superposition attacks.

Learning parity with noise (LPN) is a notorious (average-case) hard problem that has been well studied in learning theory, coding theory and cryptography since the early 90's. It further inspires the Learning with Errors (LWE) problem [Regev, STOC 2005], which has become one of the central building blocks for post-quantum cryptography and advanced cryptographic primitives such as fully homomorphic encryption [Gentry, STOC 2009]. Unlike LWE whose hardness can be reducible from worst-case lattice problems, no corresponding worst-case hardness results were known for LPN until very recently. At Eurocrypt 2019, Brakerski et al. [BLVW19] established the first feasibility result that the worst-case hardness of nearest codeword problem (NCP) (on balanced linear code) at the extremely low noise rate $\frac{log^2 n}{n}$ implies the quasi-polynomial hardness of LPN at the extremely high noise rate $1/2-1/poly(n)$. It remained open whether a worst-case to average-case reduction can be established for standard (constant-noise) LPN, ideally with sub-exponential hardness.

In this paper, we carry on the worst-case to average-case reduction for LPN [BLVW19]. We first expand the underlying binary linear codes (of the worst-case NCP) to not only the balanced code considered in [BLVW19] but also to another code (in some sense dual to balanced code). At the core of our reduction is a new variant of smoothing lemma (for both binary codes) that circumvents the barriers (inherent in the underlying worst-case randomness extraction) and admits tradeoffs for a wider spectrum of parameter choices. In addition to the worst-case hardness result obtained in [BLVW19], we show that for any constant $0<c<1$ the constant-noise LPN problem is ($T=2^{\Omega(n^{1-c})},\epsilon=2^{-\Omega(n^{min(c,1-c)})},q=2^{\Omega(n^{min(c,1-c)})}$)-hard assuming that the NCP (on either code) at the low-noise rate $\tau=n^{-c}$ is ($T'={2^{\Omega(\tau n)}}$, $\epsilon'={2^{-\Omega(\tau n)}}$,$m={2^{\Omega(\tau n)}}$)-hard in the worst case, where $T$, $\epsilon$, $q$ and $m$ are time complexity, success rate, sample complexity, and codeword length respectively. Moreover, refuting the worst-case hardness assumption would imply arbitrary polynomial speedups over the current state-of-the-art algorithms for solving the NCP (and LPN), which is a win-win result. Unfortunately, public-key encryptions and collision resistant hash functions would need constant-noise LPN with ($T={2^{\omega(\sqrt{n})}}$, $\epsilon'={2^{-\omega(\sqrt{n})}}$,$q={2^{\sqrt{n}}}$)-hardness (Yu et al., CRYPTO 2016 \& ASIACRYPT 2019), which is almost (up to an arbitrary $\omega(1)$ factor in the exponent) what is reducible from the worst-case NCP when $c= 0.5$. We leave it as an open problem whether the gap can be closed or there is a separation in place.

In this article, we propose an adaptation of the algorithmic reduction theory of lattices to binary codes. This includes the celebrated LLL algorithm (Lenstra, Lenstra, Lovasz, 1982), as well as adaptations of associated algorithms such as the Nearest Plane Algorithm of Babai (1986). Interestingly, the adaptation of LLL to binary codes can be interpreted as an algorithmic version of the bound of Griesmer (1960) on the minimal distance of a code.

Using these algorithms, we demonstrate ---both with a heuristic analysis and in practice--- a small polynomial speed-up over the Information-Set Decoding algorithm of Lee and Brickell (1988) for random binary codes. This appears to be the first such speed-up that is not based on a time-memory trade-off.

The above speed-up should be read as a very preliminary example of the potential of a reduction theory for codes, for example in cryptanalysis. In constructive cryptography, this algorithmic reduction theory could for example also be helpful for designing trapdoor functions from codes.

The primary function of a cryptocurrency is money transfer between individuals. The wallet is the software that facilitates such transfers. Wallets are nowadays ubiquitous in the cryptocurrency space and a cryptocurrency is usually supported by many wallets. Despite that, the functionality of wallets has never been formally defined. Additionally, the mechanisms employed by the many wallets in the wild remain hidden in their respective codebases.

In this work we provide the first definition of a cryptocurrency wallet, which we model as a client to a server, or set of servers. We provide a distinction of wallets in various categories, based on whether they work for transparent or private cryptocurrencies, what trust assumptions they require, their performance and their communication overhead. For each type of wallet we provide a description of its client and server protocols. Additionally, we explore superlight wallets and describe their difference to superlight clients that have appeared in recent literature. We demonstrate how new wallet protocols can be produced by combining concepts from existing protocols. Finally we evaluate the performance and security characteristics of all wallet protocols and compare them.

Recently, many profiling side-channel attacks based on Machine Learning and Deep Learning have been proposed. Most of them focus on reducing the number of traces required for successful attacks by optimizing the modeling algorithms. In previous work, relatively sufficient traces need to be used for training a model. However, in the practical profiling phase, it is difficult or impossible to collect sufficient traces due to the constraint of various resources. In this case, the performance of profiling attacks is inefficient even if proper modeling algorithms are used. In this paper, the main problem we consider is how to conduct more efficient profiling attacks when sufficient profiling traces cannot be obtained. To deal with this problem, we first introduce the Conditional Generative Adversarial Network (CGAN) in the context of side-channel attacks. We show that CGAN can generate new traces to enlarge the size of the profiling set, which improves the performance of profiling attacks. For both unprotected and protected cryptographic algorithms, we find that CGAN can effectively learn the leakage of traces collected in their implementations. We also apply it to different modeling algorithms. In our experiments, the model constructed with the augmented profiling set can reduce the required attack traces by more than half, which means the generated traces can provide useful information as the real traces.

The currently proposed RISC-V True Random Number Generator (TRNG) architecture breaks with previous ISA TRNG practice by splitting the Entropy Source (ES) component away from cryptographic PRNGs into a separate interface, and in its use of polling. We describe the interface, its use in cryptography, and offer additional discussion, background, and rationale for various aspects of it. This design is informed by lessons learned from earlier mainstream ISAs, recently introduced SP 800-90B and FIPS 140-3 entropy audit requirements, AIS 31 and Common Criteria, current and emerging cryptographic needs such as post-quantum cryptography, and the goal of supporting a wide variety of RISC-V implementations and applications. Many of the architectural choices are a result of quantitative observations about random number generators in secure microcontrollers, the Linux kernel, and cryptographic libraries (OpenSSL). We further compare the architecture to some contemporary random number generators and describe a minimalistic TRNG reference implementation that uses the Entropy Source together with RISC-V AES instructions.

We propose Agora, the first blockchain-based data marketplace that enables multiple privacy-concerned parties to get compensated for contributing and exchanging data, without relying on a trusted third party during the exchange. Agora achieves data privacy, output verifiability, and atomicity of payments by leveraging cryptographic techniques, and is designed as a decentralized application via smart contracts. Particularly, data generators provide encrypted data to data brokers who use a functional secret key to learn nothing but the output of a specific, agreed upon, function over the raw data. Data consumers can purchase decrypted outputs from the brokers, accompanied by corresponding proofs of correctness. We implement a working prototype of Agora on Ethereum and experimentally evaluate its performance and deployment costs. As a core building block of Agora, we propose a new functional encryption scheme with additional public parameters that operate as a trust anchor for verifying decrypted results.

In this paper, we propose a new private set intersection (PSI) protocol that computes the following functionality. The two parties ($P_1$ and $P_2$) input two sets of items ($X$ and $Y$, respectively) and one of the parties outputs a function of the intersection ($f(X \cap Y)$). This functionality is generally required when the PSI protocol is used as a part of a larger secure two-party secure computation. Pinkas et al. presented a PSI protocol at Eurocrypt 2019 for this functionality, which has linear complexity only in communication. While there are PSI protocols with linear computation and communication complexities in the classical PSI setting where the intersection itself is revealed to one party, to the best of our knowledge, there is no PSI protocol, which outputs a function of the intersection and satisfies linear complexity in both communication and computation. We present the first PSI protocol that outputs only a function of the intersection with linear communication and computation complexities. While creating the protocol, as a side contribution, we provide a one-time oblivious programmable pseudo-random function based on garbled Bloom filters. We also implemented our protocol and provide performance results.

Contact tracing is an essential component of public health efforts to slow the spread of COVID-19 and other infectious diseases. Automating parts of the contact tracing process has the potential to significantly increase its scalability and efficacy, but also raises an array of privacy concerns, including the risk of unwanted identification of infected individuals and clandestine collection of privacy-invasive data about the population at large.

In this paper, we focus on automating the exposure notification part of contact tracing, which notifies people who have been in close proximity to infected people of their potential exposure to the virus. This work is among the first to focus on the privacy aspects of automated exposure notification. We introduce two privacy-preserving exposure notification schemes based on proximity detection. Both systems are decentralized -- no central entity has access to sensitive data. The first scheme is simple and highly efficient, and provides strong privacy for non-diagnosed individuals and some privacy for diagnosed individuals. The second scheme provides enhanced privacy guarantees for diagnosed individuals, at some cost to efficiency. We provide formal definitions for automated exposure notification and its security, and we prove the security of our constructions with respect to these definitions.

The information security community has devoted substantial effort to the design, development, and universal deployment of strong encryption schemes that withstand search and seizure by computationally-powerful nation-state adversaries. In response, governments are increasingly turning to a different tactic: issuing subpoenas that compel people to decrypt devices themselves, under the penalty of contempt of court if they do not comply. Compelled decryption subpoenas sidestep questions around government search powers that have dominated the Crypto Wars and instead touch upon a different (and still unsettled) area of the law: how encryption relates to a person's right to silence and against self-incrimination.

In this work, we provide a rigorous, composable definition of a critical piece of the law that determines whether cryptosystems are vulnerable to government compelled disclosure in the United States. We justify our definition by showing that it is consistent with prior court cases. We prove that decryption is often not compellable by the government under our definition. Conversely, we show that many techniques that bolster security overall can leave one more vulnerable to compelled disclosure.

As a result, we initiate the study of protecting cryptographic protocols against the threat of future compelled disclosure. We find that secure multi-party computation is particularly vulnerable to this threat, and we design and implement new schemes that are provably resilient in the face of government compelled disclosure. We believe this work should influence the design of future cryptographic primitives and contribute toward the legal debates over the constitutionality of compelled decryption.

Privacy guarantees are still insufficient for outsourced data processing in the cloud. While employing encryption is feasible for data at rest or in transit, it is not for computation without remarkable performance slowdown. Thus, handling data in plaintext during processing is still required, which creates vulnerabilities that can be exploited by malicious entities. Homomorphic encryption (HE) schemes are natural candidates for computation in the cloud since they enable processing of ciphertexts without any knowledge about the related plaintexts or the decryption key. This work focuses on the challenge of developing an efficient implementation of the BFV HE scheme on CUDA. This is done by combining and adapting different approaches from the literature, namely the double-CRT representation and the Discrete Galois Transform. Moreover, we propose and implement an improved formulation of the DGT inspired by classical algorithms, which computes the transform up to $2.6$ times faster than the state-of-the-art. By using these approaches, we obtain up to $3.6$ times faster homomorphic multiplication.

We construct a succinct non-interactive publicly-verifiable delegation scheme for any log-space uniform circuit under the sub-exponential $\mathsf{LWE}$ assumption, a standard assumption that is believed to be post-quantum secure. For a circuit of size $S$ and depth $D$, the prover runs in time poly$(S)$, and the verifier runs in time $(D + n) \cdot S^{o(1)}$, where $n$ is the input size. We obtain this result by slightly modifying the $\mathsf{GKR}$ protocol and proving that the Fiat-Shamir heuristic is sound when applied to this modified protocol. We build on the recent works of Canetti et al. (STOC 2019) and Peikert and Shiehian (Crypto 2020), which prove the soundness of the Fiat-Shamir heuristic when applied to a specific (non-succinct) zero-knowledge protocol. As a corollary, by the work of Choudhuri et al. (STOC 2019), this implies that the complexity class $\mathsf{PPAD}$ is hard (on average) under the sub-exponential $\mathsf{LWE}$ assumption, assuming that $\mathsf{\#SAT}$ with $o(\log n \cdot \log\log n)$ variables is hard (on average).

We give a taxonomy of computational assumptions in the algebraic group model (AGM). We first analyze Boyen's Uber assumption family for bilinear groups and then extend it in several ways to cover assumptions as diverse as Gap Diffie-Hellman and LRSW. We show that in the AGM every member of these families is implied by the $q$-discrete logarithm (DL) assumption, for some $q$ that depends on the degrees of the polynomials defining the Uber assumption.

Using the meta-reduction technique, we then separate $(q+1)$-DL from $q$-DL, which yields a classification of all members of the extended Uber-assumption families. We finally show that there are strong assumptions, such as one-more DL, that provably fall outside our classification, by proving that they cannot be reduced from $q$-DL even in the AGM.

Oblivious Parallel RAM (OPRAM) enables multiple clients to synchronously make read and write accesses to shared memory (more generally, any data-store) whilst hiding the access patterns from the owner/provider of that shared memory. Prior work is best suited to the setting of multiple processors (or cores) within a single client device, and consequently there are shortcomings when applying that work to the multi-client setting where distinct client devices may not trust each other, or may simply wish to minimise – for legal reasons or otherwise – the volume of data that is leaked to other client devices. In prior constructions, obliviousness from the storage provider is achieved by passing accesses between the clients in one or more sorting networks, both before and after the logical access is made to the shared memory: this process inherently leaks the contents of the accesses to those other clients. In this paper we address this issue by introducing the notion of client obliviousness for OPRAM, which asks that clients should only learn as much as is necessary for the scheme to function correctly. We provide an instantiation using established tools, with careful analysis to show that our new notion and regular OPRAM security are met. This introduces several subtleties which were not previously apparent, and we further discuss the implications of using the OPRAM model in the context of outsourced storage.