International Association
for Cryptologic Research

We present a searchable encryption scheme for dynamic document collections in a multi-user scenario. Our scheme features fine-grained access control to search results, as well as access control to operations such as adding documents to the document collection, or changing individual documents. The scheme features verifiability of search results. Our scheme also satisfies the forward privacy notion crucial for the security of dynamic searchable encryption schemes.

Card-based cryptography provides simple and practicable protocols for performing secure multi-party computation (MPC) with just a deck of cards. For the sake of simplicity, this is often done using cards with only two symbols, e.g., clubs and hearts. Within this paper, we target the setting where all cards carry distinct symbols, catering for use-cases with commonly available standard decks and a weaker indistinguishability assumption. As of yet, the literature provides for only three protocols and no proofs for non-trivial lower bounds on the number of cards. As such complex proofs (handling very large combinatorial state spaces) tend to be involved and error-prone, we propose using formal verification for finding protocols and proving lower bounds. In this paper, we employ the technique of software bounded model checking (SBMC), which reduces the problem to a bounded state space, which is automatically searched exhaustively using a SAT solver as a backend.

Our contribution is twofold: (a) We identify two protocols for converting between different bit encodings with overlapping bases, and then show them to be card-minimal. This completes the picture of tight lower bounds on the number of cards with respect to runtime behavior and shuffle properties of conversion protocols. For computing AND, we show that there is no protocol with finite runtime using four cards with distinguishable symbols and fixed output encoding, and give a four-card protocol with an expected finite runtime using only random cuts. (b) We provide a general translation of proofs for lower bounds to a bounded model checking framework for automatically finding card- and length-minimal protocols and to give additional confidence in lower bounds. We apply this to validate our method and, as an example, confirm our new AND protocol to have a shortest run for protocols using this number of cards.

ISO/IEC standardizes several chosen ciphertext-secure key encapsulation mechanism (KEM) schemes in ISO/IEC 18033-2. However, all ISO/IEC KEM schemes are not quantum resilient. In this paper, we introduce new isogeny-based KEM schemes (i.e., CSIDH-ECIES-KEM and CSIDH-PSEC-KEM) by modifying Diffie-Hellman-based KEM schemes in ISO/IEC standards. The main advantage of our schemes are compactness. The key size and the ciphertext overhead of our schemes are about five times smaller than these of SIKE-KEM which is submitted to NIST's post-quantum cryptosystems standardization.

The LLL algorithm takes as input a basis of a Euclidean lattice, and, within a polynomial number of operations, it outputs another basis of the same lattice but consisting of rather short vectors. We provide a generalization to R-modules contained in K^n for arbitrary number fields K and dimension n, with R denoting the ring of integers of K. Concretely, we introduce an algorithm that efficiently finds short vectors in rank-n modules when given access to an oracle that finds short vectors in rank-2 modules, and an algorithm that efficiently finds short vectors in rank-2 modules given access to a Closest Vector Problem oracle for a lattice that depends only on K. The second algorithm relies on quantum computations and its analysis is heuristic.

In this work we advance the study of leakage-resilient Authenticated Encryption with Associated Data (AEAD) and lay the theoretical groundwork for building such schemes from sponges. Building on the work of Barwell et al. (ASIACRYPT 2017), we reduce the problem of constructing leakage-resilient AEAD schemes to that of building fixed-input-length function families that retain pseudorandomness and unpredictability in the presence of leakage. Notably, neither property is implied by the other in the leakage-resilient setting. We then show that such a function family can be combined with standard primitives, namely a pseudorandom generator and a collision-resistant hash, to yield a nonce-based AEAD scheme. In addition, our construction is quite efficient in that it requires only two calls to this leakage-resilient function per encryption or decryption call. This construction can be instantiated entirely from the T-sponge to yield a concrete AEAD scheme which we call SLAE. We prove this sponge-based instantiation secure in the non-adaptive leakage setting. SLAE bears many similarities and is indeed inspired by ISAP, which was proposed by Dobraunig et al. at FSE 2017. However, while retaining most of the practical advantages of ISAP, SLAE additionally benefits from a formal security treatment.

The customary formulation of authenticated encryption (AE) requires the decrypting party to supply the correct nonce with each ciphertext it decrypts. To enable this, the nonce is often sent in the clear alongside the ciphertext. But doing this can forfeit anonymity and degrade usability. Anonymity can also be lost by transmitting associated data (AD) or a session-ID (used to identify the operative key). To address these issues, we introduce anonymous AE, wherein ciphertexts must conceal their origin even when they are understood to encompass everything needed to decrypt (apart from the receiver's secret state). We formalize a type of anonymous AE we call anAE, anonymous nonce-based AE, which generalizes and strengthens conventional nonce-based AE, nAE. We provide an efficient construction for anAE, NonceWrap, from an nAE scheme and a blockcipher. We prove NonceWrap secure. While anAE does not address privacy loss through traffic-flow analysis, it does ensure that ciphertexts, now more expansively construed, do not by themselves compromise privacy.

We study the possibility of achieving full security, with guaranteed output delivery, for secure multiparty computation of functionalities where only one party receives output, to which we refer as solitary functionalities. In the standard setting where all parties receive an output, full security typically requires an honest majority; otherwise even just achieving fairness is impossible. However, for solitary functionalities, fairness is clearly not an issue. This raises the following question: Is full security with no honest majority possible for all solitary functionalities? We give a negative answer to this question, by showing the existence of solitary functionalities that cannot be computed with full security. While such a result cannot be proved using fairness based arguments, our proof builds on the classical proof technique of Cleve (STOC 1986) for ruling out fair coin-tossing and extends it in a nontrivial way. On the positive side, we show that full security against any number of malicious parties is achievable for many natural and useful solitary functionalities, including ones for which the multi-output version cannot be realized with full security.

Event date: 17 June to 19 June 2020
Submission deadline: 16 December 2019
Notification: 5 March 2020

Multi-proxy multi-signature schemes are useful in distributed networks, where a group of users cooperatively could delegate their administrative rights to the users of another group, who are authorized to generate the proxy signatures cooperatively on behalf of the original signers. In this paper, we aim to propose an ID-based lattice-based multi-proxy multi-signature (ILMPMS) scheme, which enjoys security against quantum computers and efficiency due to ID-based framework, linear operations and possibility of parallel computations based on lattices. For this purpose, we first propose an ID-based lattice-based multi-signature scheme, used as the underlying signature in our ILMPMS scheme. We prove existential unforgeability of both schemes against adaptive chosen-message attack in the random oracle model based on the hardness of the learning with errors problem over standard lattices.

In this work, we introduce and construct $D$-restricted Functional Encryption (FE) for any constant $D \ge 3$, based only on the SXDH assumption over bilinear groups. This generalizes the notion of $3$-restricted FE recently introduced and constructed by Ananth et al. (ePrint 2018) in the generic bilinear group model.

A $D=(d+2)$-restricted FE scheme is a secret key FE scheme that allows an encryptor to efficiently encrypt a message of the form $M=(\vec{x},\vec{y},\vec{z})$. Here, $\vec{x}\in F_{p}^{d\times n}$ and $\vec{y},\vec{z}\in F_{p}^n$. Function keys can be issued for a function $f=\Sigma_{\vec{I}=(i_1,..,i_d,j,k)}\ c_{\vec{I}}\cdot \vec{x}[1,i_1] \cdots \vec{x}[d,i_d] \cdot \vec{y}[j]\cdot \vec{z}[k]$ where the coefficients $c_{\vec{I}}\in F_{p}$. Knowing the function key and the ciphertext, one can learn $f(\vec{x},\vec{y},\vec{z})$, if this value is bounded in absolute value by some polynomial in the security parameter and $n$. The security requirement is that the ciphertext hides $\vec{y}$ and $\vec{z}$, although it is not required to hide $\vec{x}$. Thus $\vec{x}$ can be seen as a public attribute.

$D$-restricted FE allows for useful evaluation of constant-degree polynomials, while only requiring the SXDH assumption over bilinear groups. As such, it is a powerful tool for leveraging hardness that exists in constant-degree expanding families of polynomials over $\mathbb{R}$. In particular, we build upon the work of Ananth et al. to show how to build indistinguishability obfuscation (iO) assuming only SXDH over bilinear groups, LWE, and assumptions relating to weak pseudorandom properties of constant-degree expanding polynomials over $\mathbb{R}$.

We study a relaxed notion of lattice trapdoor called approximate trapdoor, which is defined to be able to invert Ajtai's one-way function approximately instead of exactly. The primary motivation of our study is to improve the efficiency of the cryptosystems built from lattice trapdoors, including the hash-and-sign signatures.

Our main contribution is to construct an approximate trapdoor by modifying the gadget trapdoor proposed by Micciancio and Peikert. In particular, we show how to use the approximate gadget trapdoor to sample short preimages from a distribution that is simulatable without knowing the trapdoor. The analysis of the distribution uses a theorem (implicitly used in past works) regarding linear transformations of discrete Gaussians on lattices.

Our approximate gadget trapdoor can be used together with the existing optimization techniques to improve the concrete performance of the hash-and-sign signature in the random oracle model under (Ring-)LWE and (Ring-)SIS assumptions. Our implementation shows that the sizes of the public-key and signature can be reduced by half from those in schemes built from exact trapdoors.

Abstract. There is a large gap between theory and practice in the complexities of sieving algorithms for solving the shortest vector problem in an arbitrary Euclidean lattice. In this paper, we work towards reducing this gap, providing theoretical refinements of the time and space complexity bounds in the context of the approximate shortest vector problem. This is achieved by relaxing the requirements on the AKS algorithm, rather than on the ListSieve, resulting in exponentially smaller bounds starting from $\mu\approx 2$, for constant values of $\mu$. We also explain why these improvements carry over to also give the fastest quantum algorithms for the approximate shortest vector problem.

In this work we analyze the impact of translating the well-known LLL algorithm for lattice reduction into the quantum setting. We present the first (to the best of our knowledge) quantum circuit representation of a lattice reduction algorithm in the form of explicit quantum circuits implementing the textbook LLL algorithm. Our analysis identifies a set of challenges arising from constructing reversible lattice reduction as well as solutions to these challenges. We give a detailed resource estimate with the Toffoli gate count and the number of logical qubits as complexity metrics.

As an application of the previous, we attack Mersenne number cryptosystems by Groverizing an attack due to Beunardeau et. al that uses LLL as a subprocedure. While Grover's quantum algorithm promises a quadratic speedup over exhaustive search given access to a oracle that distinguishes solutions from non-solutions, we show that in our case, realizing the oracle comes at the cost of a large number of qubits. When an adversary translates the attack by Beunardeau et al. into the quantum setting, the overhead of the quantum LLL circuit may be as large as $2^52$ qubits for the text-book implementation and $2^33$ for a floating-point variant.

We show how to construct structure-preserving signatures (SPS) and unbounded quasi-adaptive non-interactive zero-knowledge (USS QA-NIZK) proofs with a tight security reduction to simple assumptions, being the first with a security loss of $\mathcal{O}(1)$. Specifically, we present a SPS scheme which is more efficient than existing tightly secure SPS schemes and from an efficiency point of view is even comparable with other non-tight SPS schemes. In contrast to existing work, however, we only have a lower security loss of $\mathcal{O}(1)$, resolving an open problem posed by Abe et al. (CRYPTO 2017). In particular, our tightly secure SPS scheme under the SXDH assumption requires 11 group elements. Moreover, we present the first tightly secure USS QA-NIZK proofs with a security loss of $\mathcal{O}(1)$ which also simultaneously have a compact common reference string and constant size proofs (5 elements under the SXDH assumption, which is only one element more than the best non-tight USS QA-NIZK).

From a technical perspective, we present a novel randomization technique, inspired by Naor-Yung paradigm and adaptive partitioning, to obtain a randomized pseudorandom function (PRF). In particular, our PRF uses two copies under different keys but with shared randomness. Then we adopt ideas of Kiltz, Pan and Wee (CRYPTO 2015), who base their SPS on a randomized PRF, but in contrast to their non-tight reduction our approach allows us to achieve tight security. Similarly, we construct the first compact USS QA-NIZK proofs adopting techniques from Kiltz and Wee (EUROCRYPT 2015). We believe that the techniques introduced in this paper to obtain tight security with a loss of $\mathcal{O}(1)$ will have value beyond our proposed constructions.

We give a method to transform any indistinguishability obfuscator that suffers from correctness errors into an indistinguishability obfuscator that is $\textit{perfectly}$ correct, assuming hardness of Learning With Errors (LWE). The transformation requires sub-exponential hardness of the obfuscator and of LWE. Our technique also applies to eliminating correctness errors in general-purpose functional encryption schemes, but here it is sufficient to rely on the polynomial hardness of the given scheme and of LWE. Both of our results can be based $\textit{generically}$ on any perfectly correct, single-key, succinct functional encryption scheme (that is, a scheme supporting Boolean circuits where encryption time is a fixed polynomial in the security parameter and the message size), in place of LWE.

Previously, Bitansky and Vaikuntanathan (EUROCRYPT ’17) showed how to achieve the same task using a derandomization-type assumption (concretely, the existence of a function with deterministic time complexity $2^{O(n)}$ and non-deterministic circuit complexity $2^{\Omega(n)}$) which is non-game-based and non-falsifiable.

We present preprocessing-MPC schemes of arithmetic functions with optimal round complexity, function-independent correlated randomness, and communication and space complexities that grow linearly with the size of the function. We extend our results to the client-server model and present a scheme which enables a user to outsource the storage of confidential data to $N$ distrusted servers and have the servers perform computations over the encrypted data in a single round of communication. We further extend our results to handle Boolean circuits. All our schemes have perfect passive security against coalitions of up to $N-1$ parties. Our schemes are based on a novel secret sharing scheme, Distributed Random Matrix (DRM), which we present here. The DRM secret sharing scheme supports homomorphic multiplications, and, after a single round of communication, supports homomorphic additions.

Our approach deviates from standard conventions of MPC. First, we consider a representation of the function f as a multivariate polynomial (rather than an arithmetic circuit). Second, we divide the problem into two cases. We begin with solving the Non-Vanishing case, in which the inputs are non-zero elements of $F_p$. In this case, our schemes have space complexity $O(nkN)$ and communication complexity $O(nk(N^2))$, where $n$ is the size of the input, and $k$ is the number of monomials of the function. Then, we present several solutions for the general case, in which some of the secrets can be zero. In these solutions, the space and communication complexities are either $O(nk(N^2)(2^n))$ and $O(nk(N^3)(2^n))$, or $O(nkN)$ and $O(nk(N^2))$, respectively, where $K$ is the size of a modified version of $f$. $K$ is bounded by the square of the maximal possible size of $k$.

Homomorphic encryption (HE) schemes enable processing of encrypted data and may be used by a user to outsource storage and computations to an untrusted server. A plethora of HE schemes has been suggested in the past four decades, based on various assumptions, and which achieve different attributes. In this work, we assume that the user and server are quantum computers, and look for HE schemes of classical data. We set a high bar of requirements and ask what can be achieved under these requirements. Namely, we look for HE schemes which are efficient, information-theoretically (IT) secure, perfectly correct, and which support homomorphic operations in a fully-compact and non-interactive way. Fully-compact means that decryption costs O(1) time and space. To the best of our knowledge, there is no known scheme which fulfills all the above requirements. We suggest an encryption scheme based on random bases and discuss the homomorphic properties of that scheme. We demonstrate the usefulness of random bases in an efficient and secure QKD protocol and other applications. In particular, our QKD scheme has safer security in the face of weak measurements.

In 1998, Jerey Hostein, Jill Pipher, and Joseph H. Silverman introduced the famous Ntru cryptosystem, and called it "A ring-based public key cryptosystem". Actually it turns out to be a lattice based cryptosystem that is resistant to Shor's algorithm. There are several modifications to the original Ntru and two of them are selected as round 2 candidates of NIST post quantum public key scheme standardization.

In this paper, we present a simple attack on the original Ntru scheme. The idea comes from Ding et al.'s key mismatch attack. Essentially, an adversary can find information on the private key of a KEM by not encrypting a message as intended but in a manner which will cause a failure in decryption if the private key is in a certain form. In the present, Ntru has the encrypter generating a random polynomial with "small" coefficients, but we will have the coefficients be "large". After this, some further work will create an equivalent key.

Non-interactive proofs of knowledge allow us to publicly demonstrate the faithful execution of arbitrary computations. SNARKs have the additional property of succinctness, meaning that the proofs are short and fast to verify even when the computations involved are large. This property raises the prospect of recursive proof composition: proofs that verify other proofs. All previously known realizations of recursive proof composition have required a trusted setup and cycles of expensive pairing-friendly elliptic curves.

We obtain the first practical example of recursive proof composition without a trusted setup, using only ordinary cycles of elliptic curves. Our primary contribution is a novel technique for amortizing away expensive verification procedures from within the proof verification cycle so that we could obtain recursion using a composition of existing protocols and techniques. We devise a technique for amortizing the cost of verifying multiple inner product arguments which may be of independent interest.

We introduce novel efficient and transparent construction of the polynomial commitment scheme. A polynomial commitment scheme allows one side (the prover) to commit to a polynomial of predefined degree $d$ with a string that can be later used by another side (the verifier) to confirm claimed evaluations of the committed polynomial at specific points. Efficiency means that communication costs of interaction between prover and verifier during the protocol are very small compared to sending the whole committed polynomial itself, and is polylogarithmic in our case. Transparency means that our scheme doesn't require any preliminary trusted setup ceremony. We explicitly state that our polynomial commitment scheme is not hiding, although zero knowledge can be achieved at the application level in most of the cases.