International Association
for Cryptologic Research

Traditional fully homomorphic encryption (FHE) schemes support computation on data encrypted under a single key. In STOC 2012, L\'opez-Alt et al. introduced the notion of multi-key FHE (MKFHE), which allows homomorphic computation on ciphertexts encrypted under different keys. In this work, we focus on MKFHE constructions from standard assumptions and propose a new construction of ring-LWE-based multi-hop MKFHE scheme. Our work is based on Brakerski-Gentry-Vaikuntanathan (BGV) FHE scheme where, in contrast, all the previous works on multi-key FHE with standard assumptions were based on Gentry-Sahai-Waters (GSW) FHE scheme. Therefore, our construction can encrypt ring elements rather than a single bit and naturally inherits the advantages in aspects of the ciphertext/plaintext ratio and the complexity of homomorphic operations. Moveover, the proposed MKFHE scheme supports the Chinese Remainder Theorem (CRT)-based ciphertexts packing technique, achieves $poly\left(k,L,\log n\right)$ computation overhead for $k$ users, circuits with depth at most $L$ and an $n$ dimensional lattice, and gives the first batched MKFHE scheme based on standard assumptions to our knowledge. Furthermore, the ciphertext extension algorithms of previous schemes need to perform complex computation on each ciphertext, while our extension algorithm just needs to generate evaluation keys for the extended scheme. So the complexity of ciphertext extension is only dependent on the number of associated parities but not on the number of ciphertexts. Besides, our scheme also admits a threshold decryption protocol from which a generalized two-round MPC protocol can be similarly obtained as prior works.

Zero knowledge proof systems have been widely studied in cryptography. In the statistical setting, two classes of proof systems studied are Statistical Zero Knowledge (SZK) and Non-Interactive Statistical Zero Knowledge (NISZK), where the difference is that in NISZK only very limited communication is allowed between the verifier and the prover. It is an open problem whether these two classes are in fact equal. In this paper, we rule out efficient black box reductions between SZK and NISZK.

We achieve this by studying algorithms which can reverse the entropy of a function. The problem of estimating the entropy of a circuit is complete for NISZK. Hence, reversing the entropy of a function is equivalent to a black box reduction of NISZK to its complement, which is known to be equivalent to a black box reduction of SZK to NISZK [Goldreich et al, CRYPTO 1999]. We show that any such black box algorithm incurs an exponential loss of parameters, and hence cannot be implemented efficiently.

In this work, we initially study the necessary properties and security requirements of Ring Confidential Transaction (RingCT) protocol deployed in the popular anonymous cryptocurrency Monero. Firstly, we formalize the syntax of RingCT protocol and present several formal security definitions according to its application in Monero. Based on our observations on the underlying (linkable) ring signature and commitment schemes, we then put forward a new efficient RingCT protocol (RingCT 2.0), which is built upon the well-known Pedersen commitment, accumulator with one-way domain and signature of knowledge (which altogether perform the functions of a linkable ring signature). Besides, we show that it satisfies the security requirements if the underlying building blocks are secure in the random oracle model. In comparison with the original RingCT protocol, our RingCT 2.0 protocol presents a significant space saving, namely, the transaction size is independent of the number of groups of input accounts included in the generalized ring while the original RingCT suffers a linear growth with the number of groups, which would allow each block to process more transactions.

In this work we continue the study on the round complexity of secure two-party computation with black-box simulation. Katz and Ostrovsky in CRYPTO 2004 showed a 5 (optimal) round construction assuming trapdoor permutations for the general case where both players receive the output. They also proved that their result is round optimal. This lower bound has been recently revisited by Garg et al. in Eurocrypt 2016 where a 4 (optimal) round protocol is showed assuming a simultaneous message exchange channel. Unfortunately there is no instantiation of the protocol of Garg et al. under standard polynomial-time hardness assumptions. In this work we close the above gap by showing a 4 (optimal) round construction for secure two-party computation in the simultaneous message channel model with black-box simulation, assuming trapdoor permutations against polynomial-time adversaries. Our construction for secure two-party computation relies on a special 4-round protocol for oblivious transfer that nicely composes with other protocols in parallel. We define and construct such special oblivious transfer protocol from trapdoor permutations. This building block is clearly interesting on its own. Our construction also makes use of a recent advance on non-malleability: a delayed-input 4-round non-malleable zero knowledge argument.

We present a new improvement in the Linear Programming technique to derive bounds on information theoretic problems. In our case, we deal with the search for lower bounds on the information ratio of secret sharing schemes. We obtain non-Shannon-type bounds without using information inequalities explicitly. Our new techniques makes it possible to determine the optimal information ratio of linear secret sharing schemes for all access structures on $5$ participants. New lower bounds are presented also for graph-based access structures on six participants and for some small matroidal access structures. In particular, we determine the optimal information ratio of the linear secret sharing schemes for the ports of the Vamos matroid.

To strengthen the resistance of countermeasures based on secret sharing, several works have suggested to use the scheme introduced by Shamir in 1978, which proposes to use the evaluation of a random d-degree polynomial into n > d public points to share the sensitive data. Applying the same principles used against the classical Boolean sharing, all these works have assumed that the most efficient attack strategy was to exploit the minimum number of shares required to rebuild the sensitive value; which is d+1 if the reconstruction is made with Lagrange's interpolation. In this paper, we highlight first an important difference between Boolean and Shamir's sharings which implies that, for some signal-to-noise ratio, it is more advantageous for the adversary to observe strictly more than d+1 shares. We argue that this difference is related to the existence of so-called exact linear repairing codes, which themselves come with reconstruction formulae that need (much) less information (counted in bits) than Lagrange's interpolation. In particular, this result implies that, contrary to what was believed, the choice of the public points in Shamir's sharing has an impact on the countermeasure strength. As another contribution, we exhibit a positive impact of the existence of linear exact repairing schemes; we indeed propose to use them to improve the state-of-the-art multiplication algorithms dedicated to Shamir's sharing. We argue that the improvement can be effective when the multiplication operation in the base field is at least two times smaller than in its sub-fields.

In this paper, we present a practical password scheme due to Spilman, which is perfectly secure in the bounded retrieval model, assuming ideal hash functions. The construction is based on a hash-like function com- puted by a third party “facilitator”. The facilitator is trusted, and security derives from the facilitator’s long random secret, although the adversary is assumed to be able to retrieve a large fraction of that secret.

Unlike the traditional “salted and hashed password” approach, this scheme is secure against an adversary capable of performing brute force dictionary attacks offline. The key security property for the facilitator function is a form of uncloneability, that prevents the adversary from calculating function values offline.

The Fiat-Shamir transform is a technique for combining a hash function and an identification scheme to produce a digital signature scheme. The resulting scheme is known to be secure in the random oracle model (ROM), which does not, however, imply security in the scenario where the adversary also has quantum access to the oracle. Due to the announced eventual change-over to cryptographic schemes that should resist attacks by quantum adversaries, the problem of constructing secure Fiat-Shamir signature schemes in the quantum random oracle model (QROM) has received increased interest. There have been recent results that proved the security of specific schemes (e.g., Alkim et al. PQC 2017) constructed via the Fiat-Shamir transform, as well as those that gave more general constructions (e.g., Unruh, ASIACRYPT 2017), but only with asymptotic security proofs. The goal of this current paper is to create a generic framework for constructing tight reductions in the QROM from underlying hard problems to Fiat-Shamir signatures. Our generic reduction is composed of two results whose proofs, we believe, are simple and natural. We first consider a security notion (UF-NMA) in which the adversary obtains the public key and attempts to create a valid signature without accessing a signing oracle. We give a tight reduction showing that deterministic signatures (i.e., ones in which the randomness is derived from the message and the secret key) that are UF-NMA secure are also secure under the standard chosen message attack (UF-CMA) security definition. Our second result is showing that if the identification scheme is “lossy”, as defined in (Abdalla et al. Eurocrypt 2012), then the security of the UF-NMA scheme is tightly based on the hardness of distinguishing regular and lossy public keys of the identification scheme. This latter distinguishing problem is normally exactly the definition of some presumably-hard mathematical problem. The combination of these components gives our main result. As a concrete instantiation of our framework, we modify the recent lattice-based Dilithium digital signature scheme (Ducas et al., EPRINT 2017) so that its underlying identification scheme admits lossy public keys. The original Dilithium scheme, which is proven secure in the classical ROM based on standard lattice assumptions, has 1.5KB public keys and 2.7KB signatures. The new scheme, which is tightly based on the hardness of the Module-LWE problem in the QROM using our generic reductions, has 7.7KB public keys and 5.7KB signatures for the same security level. Furthermore, due to our proof of equivalence between the UF-NMA and UF-CMA security notions of deterministic signature schemes, we can formulate a new non-interactive assumption under which the original Dilithium signature scheme is also tightly secure in the QROM.

Inspired by the astonishing success of cryptocurrencies, most notably the Bitcoin system, several recent works have focused on the design of robust blockchain-style protocols that work in a peer-to-peer setting such as the Internet. In contrast to the setting traditionally considered in multiparty computation (MPC), in these systems, honesty is measured by computing power instead of requiring that only a certain fraction of parties is controlled by the adversary. This provides a potential countermeasure against the so-called Sybil attack, where an adversary creates fake identities, thereby easily taking over the majority of parties in the system. In this work we design protocols for Broadcast and Byzantine agreement that are secure under the assumption that the majority of computing power is controlled by the honest parties and for the first time have expected constant round complexity. This is in contrast to earlier works (Crypto'15, ePrint'14) which have round complexities that scale linearly with the number n of parties; an undesirable feature in a P2P environment with potentially thousands of users. In addition, our main protocol which runs in quasi-constant rounds, introduces novel ideas that significantly decrease communication complexity. Concretely, this is achieved by using an appropriate time-locked encryption scheme and by structuring the parties into a network of so-called cliques.

Although external-memory sorting has been a classical algorithms abstraction and has been heavily studied in the literature, perhaps somewhat surprisingly, when data-obliviousness is a requirement, even very rudimentary questions remain open. Prior to our work, it is not even known how to construct a comparison-based, external-memory oblivious sorting algorithm that is optimal in IO-cost.

We make a significant step forward in our understanding of external-memory, oblivious sorting algorithms. Not only do we construct a comparison-based, external-memory oblivious sorting algorithm that is optimal in IO-cost, our algorithm is also cache-agnostic in that the algorithm need not know the storage hierarchy's internal parameters such as the cache and cache-line sizes. Our result immediately implies a cache-agnostic ORAM construction whose asymptotical IO-cost matches the best known cache-aware scheme.

Last but not the least, we propose and adopt a new and stronger security notion for external-memory, oblivious algorithms and argue that this new notion is desirable for resisting possible cache-timing attacks. Thus our work also lays a foundation for the study of oblivious algorithms in the cache-agnostic model.

State machine replication, or “consensus”, is a central abstraction for distributed systems where a set of nodes seek to agree on an ever-growing, linearly-ordered log. In this paper, we propose a practical new paradigm called Thunderella for achieving state machine replication by combining a fast, asynchronous path with a (slow) synchronous “fall-back” path (which only gets executed if something goes wrong); as a consequence, we get simple state machine replications that essentially are as robust as the best synchronous protocols, yet “optimistically” (if a super majority of the players are honest), the protocol “instantly” confirms transactions. We provide instantiations of this paradigm in both permissionless (using proof-of-work) and permissioned settings. Most notably, this yields a new blockchain protocol (for the permissionless setting) that remains resilient assuming only that a majority of the computing power is controlled by honest players, yet optimistically—if 3/4 of the computing power is controlled by honest players, and a special player called the “accelerator”, is honest—transactions are confirmed as fast as the actual message delay in the network. We additionally show the 3/4 optimistic bound is tight for protocols that are resilient assuming only an honest majority.

Two-rounds are minimal for all MPC protocols in the absence of a trusted PKI, however certain protocols allow the reuse of inputs for different functions, or the re-evaluation of the same function on different inputs without the re-distribution of public key information. These can achieve an amortised round complexity of below two rounds per computation. Function rerunnable MPC has been achieved using FHE, while additive homomorphic properties of DH-based cryptosystems have been used to allow input rerunnable protocols. These differ in properties such as computational cost per execution, collusion tolerance and number of rounds supported. We discuss the characteristics of some rerunnable protocols, and present a proof of the rerunnable aggregation protocol of Kursawe, Danezis and Katz from the Decisional Bilinear Diffie Hellman Assumption.

Device-specific physical characteristics provide the foundation for PUFs, a hardware primitive for secure storage of cryptographic keys. So far, they have been implemented by either directly evaluating a binary output or by mapping outputs from a higher-order alphabet to a fixed-length bit sequence. However, the latter causes a significant bias in the derived key when combined with an equidistant quantization.

To overcome this limitation, we propose a variable-length bit mapping that reflects the properties of a Gray code in a different metric, namely the Levenshtein metric instead of the classical Hamming metric. Subsequent error-correction is therefore based on a custom insertion/deletion correcting code. This new approach effectively counteracts the bias in the derived key already at the input side.

We present the concept for our scheme and demonstrate its feasibility based on an empirical PUF distribution. As a result, we increase the effective output bit length of the secret by over 40% compared to state-of-the-art approaches while at the same time obtaining additional advantages, e.g., an improved tamper-sensitivity. This opens up a new direction of Error-Correcting Codes (ECCs) for PUFs that output responses with symbols of higher-order output alphabets.

A growing number of connected objects, with their high performance and low-resources constraints, are embedding lightweight ciphers for protecting the confidentiality of the data they manipulate or store. Since those objects are easily accessible, they are prone to a whole range of physical attacks, one of which are fault attacks against for which countermeasures are usually expensive to implement, especially on off-the-shelf devices. For such devices, we propose a new generic software countermeasure, called the Internal Redundancy Countermeasure (IRC), to thwart most fault attacks while preserving the performances of the targeted cipher. We report practical experiments showing that IRC successfully thwarts fault attacks on the block cipher PRIDE and on the stream cipher TRIVIUM for which we protect both the initialization and the keystream generation.

We investigate the subset-resilience problem, defined in 2002 by Reyzin and Reyzin to analyze their HORS signature scheme. We show that textbook HORS is insecure against adaptive attacks, and present a practical attack based on a greedy algorithm. We also describe weak messages for HORS, that map to smaller subsets than expected, and are thus easier to cover. This leads to an improved attack against HORS and to an improved classical attack against the signature scheme SPHINCS, of complexity $2^{270}$ instead of $2^{277}$. We pro- pose the PRNG to obtain a random subset construction (PORS), which avoids weak messages, for a tiny computational overhead. We adapt PORS to SPHINCS to also deterministically select the HORST instance that is used to sign the input message. This new construction reduces the attack surface and increases the security level, improving the security of SPHINCS by 67 bits against classical attacks and 33 bits against quantum attacks. A version of SPHINCS using our PORS construction can work with smaller parameters that reduce the signature size by 4616 bytes and speed up signature and verification, for the same 128-bit post-quantum security as the original SPHINCS.

We present a very simple yet very powerful idea for turning any semi-honestly secure MPC protocol into an actively secure one, at the price of reducing the threshold of tolerated corruptions.

Our compiler leads to a very efficient MPC protocols for the important case of secure evaluation of arithmetic circuits over arbitrary rings (e.g., the natural case of $\mathbb{Z}_{2^{\ell}}\!$) for small number of parties. We show this by giving a concrete protocol in the preprocessing model for the popular setting with three parties and one corruption. This is the first protocol for secure computation over rings that achieves active security with constant overhead.

For a given vectorial Boolean function $F$ from $\mathbb{F}_2^n$ to itself it was defined an associated Boolean function $\gamma_F(a,b)$ in $2n$ variables by C.~Carlet, P.~Charpin, V.~Zinoviev in 1998 that takes value~$1$ iff $a\neq{\bf 0}$ and equation $F(x)+F(x+a)=b$ has solutions. In this paper we introduce the notion of differentially equivalent functions as vectorial functions that have equal associated Boolean functions. To describe differential equivalence class of a given APN function is an open problem of great interest. We obtained that each quadratic APN function $G$ in $n$ variables, $n\leq 6$, that is differentially equivalent to a given quadratic APN function $F$, is represented as $G = F + A$, where $A$ is an affine function. For the APN Gold function $F(x)=x^{2^k+1}$, where gcd$(k,n)=1$, we completely described all affine functions $A$ such that $F$ and $F+A$ are differentially equivalent. This result implies that APN Gold functions $F$ with $k=n/2 - 1$ for $n=4t$ form the first infinitive family of functions up to EA-equivalence having non-trivial differential equivalence class consisting of more that $2^{2n}$ trivial functions $F_{c,d}(x) = F(x+c)+d$, $c,d\in\mathbb{F}_2^n$.

We investigate the merits of altering the Garg, Gentry and Halevi (GGH13) graded encoding scheme to remove the presence of the ideal \(\langle g \rangle\). In particular, we show that we can alter the form of encodings so that effectively a new \(g_i\) is used for each source group \(\mathbb{G}_i\), while retaining correctness. This would appear to prevent all known attacks on IO candidates instantiated using GGH13. However, when analysing security in a simplified branching program model, we present an IO distinguishing attack that does not use \(\langle g \rangle\). This result opens a counterpoint with the work of Halevi (EPRINT 2015) which stated that the core computational hardness problem underpinning GGH13 is computing a basis of this ideal. Our attempts seem to suggest that there is a structural vulnerability in the way that GGH13 encodings are constructed that lies deeper than the presence of \(\langle g \rangle\). Tangentially, we observe that our attack is prevented when considering all the added machinery of IO candidates.

Ring signatures, introduced by Rivest, Shamir and Tauman (ASIACRYPT 2001), allows to sign a message on behalf of a set of users (called a ring) while guaranteeing authenticity, i.e.~only members of the ring can produce valid signatures, and anomimity, i.e.~the signatures hides the actual signer. In terms of efficiency, in all constructions the size of the signature depends on the number of members of the ring. Indeed, the most efficient constructions require signatures of size $O(\log n)$, where $n$ is the size of the ring (Groth and Kohlweiss EUROCYPT 2015, Libert et al.~EUROCRYPT 2016). However, both constructions are proven secure in the random oracle model. Without random oracles the most efficient construction remains the one of Chandran et al. (ICALP 2007) with a signatgure of size $O(\sqrt{n})$.

In this work we construct a ring signature of size $O(\sqrt[3]{n})$ without random oracles. Our construction uses bilinear groups and we prove its security under the permutation pairing assumption, introduced by Groth and Lu (ASIACRYPT 2007), which is a non-falsifiable assumption in bilinear groups.

Iterative collision search procedures play a key role in developing combinatorial algorithms for the subset sum and learning parity with noise (LPN) problems. In both scenarios, the single-list pair-wise iterative collision search finds the most solutions and offers the best efficiency. However, due to its complex probabilistic structure, no rigorous analysis for it appears to be available to the best of our knowledge. As a result, theoretical works often resort to overly constrained and sub-optimal iterative collision search variants in exchange for analytic simplicity. In this paper, we present rigorous analysis for the single-list pair-wise iterative collision search method and its applications in subset sum and LPN. In the subset sum direction, it outperforms Wagner's algorithm for attacking knapsack-based cryptosystems. In the LPN literature, the single-list pair-wise iterative collision search method is known as the LF2 heuristic. Besides LF2, we also present rigorous analysis of other LPN solving heuristics and show that they work well when combined with LF2. Putting it together, we significantly narrow the gap between theoretical and heuristic algorithms for LPN.