Zero-Knowledge

Frontmatter

On the Existence of Three Round Zero-Knowledge Proofs

Abstract

We study the round complexity of zero-knowledge (ZK) proof systems. While five round ZK proofs for \({\mathsf {NP}}\) are known from standard assumptions [Goldreich-Kahan, J. Cryptology’96], Katz [TCC’08] proved that four rounds are insufficient for this task w.r.t. black-box simulation. In this work, we study the feasibility of ZK proofs using non-black-box simulation. Our main result is that three round private-coin ZK proofs for \({\mathsf {NP}}\) do not exist (even w.r.t. non-black-box simulation), under certain assumptions on program obfuscation. Our approach builds upon the recent work of Kalai et al. [Crypto’17] who ruled out constant round public-coin ZK proofs under the same assumptions as ours.

Nils Fleischhacker, Vipul Goyal, Abhishek Jain

Statistical Witness Indistinguishability (and more) in Two Messages

Abstract

Two-message witness indistinguishable protocols were first constructed by Dwork and Naor (FOCS 2000). They have since proven extremely useful in the design of several cryptographic primitives. However, so far no two-message arguments for NP provided statistical privacy against malicious verifiers. In this paper, we construct the first:

\(\circ \) Two-message statistical witness indistinguishable (SWI) arguments for NP.
\(\circ \) Two-message statistical zero-knowledge arguments for NP with super-polynomial simulation (Statistical SPS-ZK).
\(\circ \) Two-message statistical distributional weak zero-knowledge (SwZK) arguments for NP, where the simulator is a probabilistic polynomial time machine with oracle access to the distinguisher, and the instance is sampled by the prover in the second round.

These protocols are based on quasi-polynomial hardness of two-message oblivious transfer (OT), which in turn can be based on quasi-polynomial hardness of DDH or QR or \(N^{th}\) residuosity. We also show how such protocols can be used to build more secure forms of oblivious transfer.

Along the way, we show that the Kalai and Raz (Crypto 09) transform compressing interactive proofs to two-message arguments can be generalized to compress certain types of interactive arguments. We introduce and construct a new technical tool, which is a variant of extractable two-message statistically hiding commitments, building on the recent work of Khurana and Sahai (FOCS 17). These techniques may be of independent interest.

Yael Tauman Kalai, Dakshita Khurana, Amit Sahai

An Efficiency-Preserving Transformation from Honest-Verifier Statistical Zero-Knowledge to Statistical Zero-Knowledge

Abstract

We present an unconditional transformation from any honest-verifier statistical zero-knowledge (HVSZK) protocol to standard SZK that preserves round complexity and efficiency of both the verifier and the prover. This improves over currently known transformations, which either rely on some computational assumptions or introduce significant computational overhead. Our main conceptual contribution is the introduction of instance-dependent SZK proofs for NP, which serve as a building block in our transformation. Instance-dependent SZK for NP can be constructed unconditionally based on instance-dependent commitment schemes of Ong and Vadhan (TCC’08).

As an additional contribution, we give a simple constant-round SZK protocol for Statistical-Difference resembling the textbook HVSZK proof of Sahai and Vadhan (J.ACM’03). This yields a conceptually simple constant-round protocol for all of SZK.

Pavel Hubáček, Alon Rosen, Margarita Vald

Implementing Multiparty Computation

Frontmatter

Efficient Maliciously Secure Multiparty Computation for RAM

Abstract

A crucial issue, that mostly affects the performance of actively secure computation of RAM programs, is the task of reading/writing from/to memory in a private and authenticated manner. Previous works in the active security and multiparty settings are based purely on the SPDZ (reactive) protocol, hence, memory accesses are treated just like any input to the computation. However, a garbled-circuit-based construction (such as BMR), which benefits from a lower round complexity, must resolve the issue of converting memory data bits to their corresponding wire keys and vice versa.

In this work we propose three techniques to construct a secure memory access, each appropriates to a different level of abstraction of the underlying garbling functionality. We provide a comparison between the techniques by several metrics. To the best of our knowledge, we are the first to construct, prove and implement a concretely efficient garbled-circuit-based actively secure RAM computation with dishonest majority.

Our construction is based on our third (most efficient) technique, cleverly utilizing the underlying SPDZ authenticated shares (Damgård et al., Crypto 2012), yields lean circuits and a constant number of communication rounds per physical memory access. Specifically, it requires no additional circuitry on top of the ORAM’s, incurs only two rounds of broadcasts between every two memory accesses and has a multiplicative overhead of 2 on top of the ORAM’s storage size.

Our protocol outperforms the state of the art in this settings when deployed over WAN. Even when simulating a very conservative RTT of 100 ms our protocol is at least one order of magnitude faster than the current state of the art protocol of Keller and Scholl (Asiacrypt 2015).

Marcel Keller, Avishay Yanai

Efficient Circuit-Based PSI via Cuckoo Hashing

Abstract

While there has been a lot of progress in designing efficient custom protocols for computing Private Set Intersection (PSI), there has been less research on using generic Multi-Party Computation (MPC) protocols for this task. However, there are many variants of the set intersection functionality that are not addressed by the existing custom PSI solutions and are easy to compute with generic MPC protocols (e.g., comparing the cardinality of the intersection with a threshold or measuring ad conversion rates).

Generic PSI protocols work over circuits that compute the intersection. For sets of size n, the best known circuit constructions conduct \(O(n \log n)\) or \(O(n \log n / \log \log n)\) comparisons (Huang et al., NDSS’12 and Pinkas et al., USENIX Security’15). In this work, we propose new circuit-based protocols for computing variants of the intersection with an almost linear number of comparisons. Our constructions are based on new variants of Cuckoo hashing in two dimensions.

We present an asymptotically efficient protocol as well as a protocol with better concrete efficiency. For the latter protocol, we determine the required sizes of tables and circuits experimentally, and show that the run-time is concretely better than that of existing constructions.

The protocol can be extended to a larger number of parties. The proof technique presented in the full version for analyzing Cuckoo hashing in two dimensions is new and can be generalized to analyzing standard Cuckoo hashing as well as other new variants of it.

Benny Pinkas, Thomas Schneider, Christian Weinert, Udi Wieder

Overdrive: Making SPDZ Great Again

Abstract

SPDZ denotes a multiparty computation scheme in the preprocessing model based on somewhat homomorphic encryption (SHE) in the form of BGV. At CCS ’16, Keller et al. presented MASCOT, a replacement of the preprocessing phase using oblivious transfer instead of SHE, improving by two orders of magnitude on the SPDZ implementation by Damgård et al. (ESORICS ’13). In this work, we show that using SHE is faster than MASCOT in many aspects:

1.

We present a protocol that uses semi-homomorphic (addition-only) encryption. For two parties, our BGV-based implementation is six times faster than MASCOT on a LAN and 20 times faster in a WAN setting. The latter is roughly the reduction in communication.

2.

We show that using the proof of knowledge in the original work by Damgård et al. (Crypto ’12) is more efficient in practice than the one used in the implementation mentioned above by about one order of magnitude.

3.

We present an improvement to the verification of the aforementioned proof of knowledge that increases the performance with a growing number of parties, doubling it for 16 parties.

Marcel Keller, Valerio Pastro, Dragos Rotaru

Non-interactive Zero-Knowledge

Frontmatter

Efficient Designated-Verifier Non-interactive Zero-Knowledge Proofs of Knowledge

Abstract

We propose a framework for constructing efficient designated-verifier non-interactive zero-knowledge proofs (\(\mathsf {DVNIZK}\)) for a wide class of algebraic languages over abelian groups, under standard assumptions. The proofs obtained via our framework are proofs of knowledge, enjoy statistical, and unbounded soundness (the soundness holds even when the prover receives arbitrary feedbacks on previous proofs). Previously, no efficient \(\mathsf {DVNIZK}\) system satisfying any of those three properties was known. Our framework allows proving arbitrary relations between cryptographic primitives such as Pedersen commitments, ElGamal encryptions, or Paillier encryptions, in an efficient way. For the latter, we further exhibit the first non-interactive zero-knowledge proof system in the standard model that is more efficient than proofs obtained via the Fiat-Shamir transform, with still-meaningful security guarantees and under standard assumptions. Our framework has numerous applications, in particular for the design of efficient privacy-preserving non-interactive authentication.

Pyrros Chaidos, Geoffroy Couteau

Quasi-Optimal SNARGs via Linear Multi-Prover Interactive Proofs

Abstract

Succinct non-interactive arguments (SNARGs) enable verifying \(\mathsf {NP} \) computations with significantly less complexity than that required for classical \(\mathsf {NP} \) verification. In this work, we focus on simultaneously minimizing the proof size and the prover complexity of SNARGs. Concretely, for a security parameter \(\lambda \), we measure the asymptotic cost of achieving soundness error \(2^{-\lambda }\) against provers of size \(2^\lambda \). We say a SNARG is quasi-optimally succinct if its proof length is \(\widetilde{O}(\lambda )\), and that it is quasi-optimal, if moreover, its prover complexity is only polylogarithmically greater than the running time of the classical \(\mathsf {NP} \) prover. We show that this definition is the best we could hope for assuming that \(\mathsf {NP} \) does not have succinct proofs. Our definition strictly strengthens the previous notion of quasi-optimality introduced in the work of Boneh et al. (Eurocrypt 2017).

This work gives the first quasi-optimal SNARG for Boolean circuit satisfiability from a concrete cryptographic assumption. Our construction takes a two-step approach. The first is an information-theoretic construction of a quasi-optimal linear multi-prover interactive proof (linear MIP) for circuit satisfiability. Then, we describe a generic cryptographic compiler that transforms our quasi-optimal linear MIP into a quasi-optimal SNARG by relying on the notion of linear-only vector encryption over rings introduced by Boneh et al. Combining these two primitives yields the first quasi-optimal SNARG based on linear-only vector encryption. Moreover, our linear MIP construction leverages a new robust circuit decomposition primitive that allows us to decompose a circuit satisfiability instance into several smaller circuit satisfiability instances. This primitive may be of independent interest.

Finally, we consider (designated-verifier) SNARGs that provide optimal succinctness for a non-negligible soundness error. Concretely, we put forward the notion of “1-bit SNARGs” that achieve soundness error \(1\text {/}2\) with only one bit of proof. We first show how to build 1-bit SNARGs from indistinguishability obfuscation, and then show that 1-bit SNARGs also suffice for realizing a form of witness encryption. The latter result highlights a two-way connection between the soundness of very succinct argument systems and powerful forms of encryption.

Dan Boneh, Yuval Ishai, Amit Sahai, David J. Wu

Anonymous Communication

Frontmatter

Untagging Tor: A Formal Treatment of Onion Encryption

Abstract

Tor is a primary tool for maintaining anonymity online. It provides a low-latency, circuit-based, bidirectional secure channel between two parties through a network of onion routers, with the aim of obscuring exactly who is talking to whom, even to adversaries controlling part of the network. Tor relies heavily on cryptographic techniques, yet its onion encryption scheme is susceptible to tagging attacks (Fu and Ling 2009), which allow an active adversary controlling the first and last node of a circuit to deanonymize with near-certainty. This contrasts with less active traffic correlation attacks, where the same adversary can at best deanonymize with high probability. The Tor project has been actively looking to defend against tagging attacks and its most concrete alternative is proposal 261, which specifies a new onion encryption scheme based on a variable-input-length tweakable cipher.

We provide a formal treatment of low-latency, circuit-based onion encryption, relaxed to the unidirectional setting, by expanding existing secure channel notions to the new setting and introducing circuit hiding to capture the anonymity aspect of Tor. We demonstrate that circuit hiding prevents tagging attacks and show proposal 261’s relay protocol is circuit hiding and thus resistant against tagging attacks.

Jean Paul Degabriele, Martijn Stam

Exploring the Boundaries of Topology-Hiding Computation

Abstract

Topology-hiding computation (THC) is a form of multi-party computation over an incomplete communication graph that maintains the privacy of the underlying graph topology. In a line of recent works [Moran, Orlov & Richelson TCC’15, Hirt et al. CRYPTO’16, Akavia & Moran EUROCRYPT’17, Akavia et al. CRYPTO’17], THC protocols for securely computing any function in the semi-honest setting have been constructed. In addition, it was shown by Moran et al. that in the fail-stop setting THC with negligible leakage on the topology is impossible.

In this paper, we further explore the feasibility boundaries of THC.

We show that even against semi-honest adversaries, topology-hiding broadcast on a small (4-node) graph implies oblivious transfer; in contrast, trivial broadcast protocols exist unconditionally if topology can be revealed.
We strengthen the lower bound of Moran et al. identifying and extending a relation between the amount of leakage on the underlying graph topology that must be revealed in the fail-stop setting, as a function of the number of parties and communication round complexity: Any n-party protocol leaking \(\delta \) bits for \(\delta \in (0,1]\) must have \(\varOmega (n/\delta )\) rounds.

We then present THC protocols providing close-to-optimal leakage rates, for unrestricted graphs on n nodes against a fail-stop adversary controlling a dishonest majority of the n players. These constitute the first general fail-stop THC protocols. Specifically, for this setting we show:

A THC protocol that leaks at most one bit and requires \(O(n^2)\) rounds.
A THC protocol that leaks at most \(\delta \) bits for arbitrarily small non-negligible \(\delta \), and requires \(O(n^3/\delta )\) rounds.

These protocols also achieve full security (with no leakage) for the semi-honest setting. Our protocols are based on one-way functions and a (stateless) secure hardware box primitive. This provides a theoretical feasibility result, a heuristic solution in the plain model using general-purpose obfuscation candidates, and a potentially practical approach to THC via commodity hardware such as Intel SGX. Interestingly, even with such hardware, proving security requires sophisticated simulation techniques.

Marshall Ball, Elette Boyle, Tal Malkin, Tal Moran

Isogeny

Frontmatter

Supersingular Isogeny Graphs and Endomorphism Rings: Reductions and Solutions

Abstract

In this paper, we study several related computational problems for supersingular elliptic curves, their isogeny graphs, and their endomorphism rings. We prove reductions between the problem of path finding in the \(\ell \)-isogeny graph, computing maximal orders isomorphic to the endomorphism ring of a supersingular elliptic curve, and computing the endomorphism ring itself. We also give constructive versions of Deuring’s correspondence, which associates to a maximal order in a certain quaternion algebra an isomorphism class of supersingular elliptic curves. The reductions are based on heuristics regarding the distribution of norms of elements in quaternion algebras.

We show that conjugacy classes of maximal orders have a representative of polynomial size, and we define a way to represent endomorphism ring generators in a way that allows for efficient evaluation at points on the curve. We relate these problems to the security of the Charles-Goren-Lauter hash function. We provide a collision attack for special but natural parameters of the hash function and prove that for general parameters its preimage and collision resistance are also equivalent to the endomorphism ring computation problem.

Kirsten Eisenträger, Sean Hallgren, Kristin Lauter, Travis Morrison, Christophe Petit

Leakage

Frontmatter

On the Complexity of Simulating Auxiliary Input

Abstract

We construct a simulator for the simulating auxiliary input problem with complexity better than all previous results and prove the optimality up to logarithmic factors by establishing a black-box lower bound. Specifically, let \(\ell \) be the length of the auxiliary input and \(\epsilon \) be the indistinguishability parameter. Our simulator is \(\tilde{O}(2^{\ell }\epsilon ^{-2})\) more complicated than the distinguisher family. For the lower bound, we show the relative complexity to the distinguisher of a simulator is at least \(\varOmega (2^{\ell }\epsilon ^{-2})\) assuming the simulator is restricted to use the distinguishers in a black-box way and satisfy a mild restriction.

Yi-Hsiu Chen, Kai-Min Chung, Jyun-Jie Liao

Key Exchange

Frontmatter

Fuzzy Password-Authenticated Key Exchange

Abstract

Consider key agreement by two parties who start out knowing a common secret (which we refer to as “pass-string”, a generalization of “password”), but face two complications: (1) the pass-string may come from a low-entropy distribution, and (2) the two parties’ copies of the pass-string may have some noise, and thus not match exactly. We provide the first efficient and general solutions to this problem that enable, for example, key agreement based on commonly used biometrics such as iris scans.

The problem of key agreement with each of these complications individually has been well studied in literature. Key agreement from low-entropy shared pass-strings is achieved by password-authenticated key exchange (PAKE), and key agreement from noisy but high-entropy shared pass-strings is achieved by information-reconciliation protocols as long as the two secrets are “close enough.” However, the problem of key agreement from noisy low-entropy pass-strings has never been studied.

We introduce (universally composable) fuzzy password-authenticated key exchange (fPAKE), which solves exactly this problem. fPAKE does not have any entropy requirements for the pass-strings, and enables secure key agreement as long as the two pass-strings are “close” for some notion of closeness. We also give two constructions. The first construction achieves our fPAKE definition for any (efficiently computable) notion of closeness, including those that could not be handled before even in the high-entropy setting. It uses Yao’s garbled circuits in a way that is only two times more costly than their use against semi-honest adversaries, but that guarantees security against malicious adversaries. The second construction is more efficient, but achieves our fPAKE definition only for pass-strings with low Hamming distance. It builds on very simple primitives: robust secret sharing and PAKE.

Pierre-Alain Dupont, Julia Hesse, David Pointcheval, Leonid Reyzin, Sophia Yakoubov

Bloom Filter Encryption and Applications to Efficient Forward-Secret 0-RTT Key Exchange

Abstract

Forward secrecy is considered an essential design goal of modern key establishment (KE) protocols, such as TLS 1.3, for example. Furthermore, efficiency considerations such as zero round-trip time (0-RTT), where a client is able to send cryptographically protected payload data along with the very first KE message, are motivated by the practical demand for secure low-latency communication.

For a long time, it was unclear whether protocols that simultaneously achieve 0-RTT and full forward secrecy exist. Only recently, the first forward-secret 0-RTT protocol was described by Günther et al. (Eurocrypt 2017). It is based on Puncturable Encryption. Forward secrecy is achieved by “puncturing” the secret key after each decryption operation, such that a given ciphertext can only be decrypted once (cf. also Green and Miers, S&P 2015). Unfortunately, their scheme is completely impractical, since one puncturing operation takes between 30 s and several minutes for reasonable security and deployment parameters, such that this solution is only a first feasibility result, but not efficient enough to be deployed in practice.

In this paper, we introduce a new primitive that we term Bloom Filter Encryption (BFE), which is derived from the probabilistic Bloom filter data structure. We describe different constructions of BFE schemes, and show how these yield new puncturable encryption mechanisms with extremely efficient puncturing. Most importantly, a puncturing operation only involves a small number of very efficient computations, plus the deletion of certain parts of the secret key, which outperforms previous constructions by orders of magnitude. This gives rise to the first forward-secret 0-RTT protocols that are efficient enough to be deployed in practice. We believe that BFE will find applications beyond forward-secret 0-RTT protocols.

David Derler, Tibor Jager, Daniel Slamanig, Christoph Striecks

OPAQUE: An Asymmetric PAKE Protocol Secure Against Pre-computation Attacks

Abstract

Password-Authenticated Key Exchange (PAKE) protocols allow two parties that only share a password to establish a shared key in a way that is immune to offline attacks. Asymmetric PAKE (aPAKE) strengthens this notion for the more common client-server setting where the server stores a mapping of the password and security is required even upon server compromise, that is, the only allowed attack in this case is an (inevitable) offline exhaustive dictionary attack against individual user passwords. Unfortunately, most suggested aPAKE protocols (that dispense with the use of servers’ public keys) allow for pre-computation attacks that lead to the instantaneous compromise of user passwords upon server compromise, thus forgoing much of the intended aPAKE security. Indeed, these protocols use – in essential ways – deterministic password mappings or use random “salt” transmitted in the clear from servers to users, and thus are vulnerable to pre-computation attacks.

We initiate the study of Strong aPAKE protocols that are secure as aPAKE’s but are also secure against pre-computation attacks. We formalize this notion in the Universally Composable (UC) settings and present two modular constructions using an Oblivious PRF as a main tool. The first builds a Strong aPAKE from any aPAKE (which in turn can be constructed from any PAKE [18]) while the second builds a Strong aPAKE from any authenticated key-exchange protocol secure against reverse impersonation (a.k.a. KCI). Using the latter transformation, we show a practical instantiation of a UC-secure Strong aPAKE in the Random Oracle model. The protocol (“OPAQUE”) consists of 2 messages (3 with mutual authentication), requires 3 and 4 exponentiations for server and client, respectively (2 to 4 of which can be fixed-base depending on optimizations), provides forward secrecy, is PKI-free, supports user-side hash iterations, and allows a user-transparent server-side threshold implementation.

Stanislaw Jarecki, Hugo Krawczyk, Jiayu Xu

Quantum

Frontmatter

Unforgeable Quantum Encryption

Abstract

We study the problem of encrypting and authenticating quantum data in the presence of adversaries making adaptive chosen plaintext and chosen ciphertext queries. Classically, security games use string copying and comparison to detect adversarial cheating in such scenarios. Quantumly, this approach would violate no-cloning. We develop new techniques to overcome this problem: we use entanglement to detect cheating, and rely on recent results for characterizing quantum encryption schemes. We give definitions for (i) ciphertext unforgeability, (ii) indistinguishability under adaptive chosen-ciphertext attack, and (iii) authenticated encryption. The restriction of each definition to the classical setting is at least as strong as the corresponding classical notion: (i) implies \(\mathsf {INT\text {-}CTXT}\), (ii) implies \(\mathsf {IND\text {-}CCA2}\), and (iii) implies \(\mathsf {AE}\). All of our new notions also imply \(\mathsf {QIND\text {-}CPA}\) privacy. Combining one-time authentication and classical pseudorandomness, we construct symmetric-key quantum encryption schemes for each of these new security notions, and provide several separation examples. Along the way, we also give a new definition of one-time quantum authentication which, unlike all previous approaches, authenticates ciphertexts rather than plaintexts.

Gorjan Alagic, Tommaso Gagliardoni, Christian Majenz

Tightly-Secure Key-Encapsulation Mechanism in the Quantum Random Oracle Model

Abstract

Key-encapsulation mechanisms secure against chosen ciphertext attacks (IND-CCA-secure KEMs) in the quantum random oracle model have been proposed by Boneh, Dagdelen, Fischlin, Lehmann, Schafner, and Zhandry (CRYPTO 2012), Targhi and Unruh (TCC 2016-B), and Hofheinz, Hövelmanns, and Kiltz (TCC 2017). However, all are non-tight and, in particular, security levels of the schemes obtained by these constructions are less than half of original security levels of their building blocks.

In this paper, we give a conversion that tightly converts a weakly secure public-key encryption scheme into an IND-CCA-secure KEM in the quantum random oracle model. More precisely, we define a new security notion for deterministic public key encryption (DPKE) called the disjoint simulatability, and we propose a way to convert a disjoint simulatable DPKE scheme into an IND-CCA-secure key-encapsulation mechanism scheme without incurring a significant security degradation. In addition, we give DPKE schemes whose disjoint simulatability is tightly reduced to post-quantum assumptions. As a result, we obtain IND-CCA-secure KEMs tightly reduced to various post-quantum assumptions in the quantum random oracle model.

Tsunekazu Saito, Keita Xagawa, Takashi Yamakawa

A Concrete Treatment of Fiat-Shamir Signatures in the Quantum Random-Oracle Model

Abstract

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. 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., TCHES 2018) 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.5 KB public keys and 2.7 KB 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.7 KB public keys and 5.7 KB 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.

Eike Kiltz, Vadim Lyubashevsky, Christian Schaffner

Non-maleable Codes

Frontmatter

Non-malleable Randomness Encoders and Their Applications

Abstract

Non-malleable Codes (NMCs), introduced by Dziembowski, Peitrzak and Wichs (ITCS 2010), serve the purpose of preventing “related tampering” of encoded messages. The most popular tampering model considered is the 2-split-state model where a codeword consists of 2 states, each of which can be tampered independently. While NMCs in the 2-split state model provide the strongest security guarantee, despite much research in the area we only know how to build them with poor rate (\(\varOmega (\frac{1}{logn})\), where n is the codeword length). However, in many applications of NMCs one only needs to be able to encode randomness i.e., security is not required to hold for arbitrary, adversarially chosen messages. For example, in applications of NMCs to tamper-resilient security, the messages that are encoded are typically randomly generated secret keys. To exploit this, in this work, we introduce the notion of “Non-malleable Randomness Encoders” (NMREs) as a relaxation of NMCs in the following sense: NMREs output a random message along with its corresponding non-malleable encoding.

Our main result is the construction of a 2-split state, rate-\(\frac{1}{2}\) NMRE. While NMREs are interesting in their own right and can be directly used in applications such as in the construction of tamper-resilient cryptographic primitives, we also show how to use them, in a black-box manner, to build a 3-split-state (standard) NMCs with rate \(\frac{1}{3}\). This improves both the number of states, as well as the rate, of existing constant-rate NMCs.

Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Sruthi Sekar

Non-malleable Codes from Average-Case Hardness: , Decision Trees, and Streaming Space-Bounded Tampering

Abstract

We show a general framework for constructing non-malleable codes against tampering families with average-case hardness bounds. Our framework adapts ideas from the Naor-Yung double encryption paradigm such that to protect against tampering in a class \({\mathcal {F}}\), it suffices to have average-case hard distributions for the class, and underlying primitives (encryption and non-interactive, simulatable proof systems) satisfying certain properties with respect to the class.

We instantiate our scheme in a variety of contexts, yielding efficient, non-malleable codes (NMC) against the following tampering classes:

Computational NMC against \({\mathsf {A}}{\mathsf {C}}^0\) tampering, in the CRS model, assuming a PKE scheme with decryption in \({\mathsf {A}}{\mathsf {C}}^0\) and NIZK.
Computational NMC against bounded-depth decision trees (of depth \(n^\epsilon \), where n is the number of input variables and constant \(0<\epsilon <1\)), in the CRS model and under the same computational assumptions as above.
Information theoretic NMC (with no CRS) against a streaming, space-bounded adversary, namely an adversary modeled as a read-once branching program with bounded width.

Ours are the first constructions that achieve each of the above in an efficient way, under the standard notion of non-malleability.

Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Tal Malkin

Provable Symmetric Cryptography

Frontmatter

Naor-Reingold Goes Public: The Complexity of Known-Key Security

Abstract

We study the complexity of building secure block ciphers in the setting where the key is known to the attacker. In particular, we consider two security notions with useful implications, namely public-seed pseudorandom permutations (or psPRPs, for short) (Soni and Tessaro, EUROCRYPT ’17) and correlation-intractable ciphers (Knudsen and Rijmen, ASIACRYPT ’07; Mandal, Seurin, and Patarin, TCC ’12).

For both these notions, we exhibit constructions which make only two calls to an underlying non-invertible primitive, matching the complexity of building a pseudorandom permutation in the secret-key setting. Our psPRP result instantiates the round functions in the Naor-Reingold (NR) construction with a secure UCE hash function. For correlation intractability, we instead instantiate them from a (public) random function, and replace the pairwise-independent permutations in the NR construction with (almost) \(O(k^2)\)-wise independent permutations, where k is the arity of the relations for which we want correlation intractability.

Our constructions improve upon the current state of the art, requiring five- and six-round Feistel networks, respectively, to achieve psPRP security and correlation intractability. To do so, we rely on techniques borrowed from Impagliazzo-Rudich-style black-box impossibility proofs for our psPRP result, for which we give what we believe to be the first constructive application, and on techniques for studying randomness with limited independence for correlation intractability.

Pratik Soni, Stefano Tessaro

Updatable Encryption with Post-Compromise Security

Abstract

An updatable encryption scheme allows to periodically rotate the encryption key and move already existing ciphertexts from the old to the new key. These ciphertext updates are done with the help of a so-called update token and can be performed by an untrusted party, as the update never decrypts the data. Updatable encryption is particularly useful in settings where encrypted data is outsourced, e.g., stored on a cloud server. The data owner can produce an update token, and the cloud server can update the ciphertexts.

We provide a comprehensive treatment of ciphertext-independent schemes, where a single token is used to update all ciphertexts. We show that the existing ciphertext-independent schemes and models by Boneh et al. (CRYPTO’13) and Everspaugh et al. (CRYPTO’17) do not guarantee the post-compromise security one would intuitively expect from key rotation. In fact, the simple scheme recently proposed by Everspaugh et al. allows to recover the current key upon corruption of a single old key. Surprisingly, none of the models so far reflects the timely aspect of key rotation which makes it hard to grasp when an adversary is allowed to corrupt keys. We propose strong security models that clearly capture post-compromise and forward security under adaptive attacks. We then analyze various existing schemes and show that none of them is secure in this strong model, but we formulate the additional constraints that suffice to prove their security in a relaxed version of our model. Finally, we propose a new updatable encryption scheme that achieves our strong notions while being (at least) as efficient as the existing solutions.

Anja Lehmann, Björn Tackmann

Springer Professional

About this book

Table of Contents

Frontmatter

Zero-Knowledge

Frontmatter

On the Existence of Three Round Zero-Knowledge Proofs

Statistical Witness Indistinguishability (and more) in Two Messages

An Efficiency-Preserving Transformation from Honest-Verifier Statistical Zero-Knowledge to Statistical Zero-Knowledge

Implementing Multiparty Computation

Frontmatter

Efficient Maliciously Secure Multiparty Computation for RAM

Efficient Circuit-Based PSI via Cuckoo Hashing

Overdrive: Making SPDZ Great Again

Non-interactive Zero-Knowledge

Frontmatter

Efficient Designated-Verifier Non-interactive Zero-Knowledge Proofs of Knowledge

Quasi-Optimal SNARGs via Linear Multi-Prover Interactive Proofs

Anonymous Communication

Frontmatter

Untagging Tor: A Formal Treatment of Onion Encryption

Exploring the Boundaries of Topology-Hiding Computation

Isogeny

Frontmatter

Supersingular Isogeny Graphs and Endomorphism Rings: Reductions and Solutions

Leakage

Frontmatter

On the Complexity of Simulating Auxiliary Input

Key Exchange

Frontmatter

Fuzzy Password-Authenticated Key Exchange

Bloom Filter Encryption and Applications to Efficient Forward-Secret 0-RTT Key Exchange

OPAQUE: An Asymmetric PAKE Protocol Secure Against Pre-computation Attacks

Quantum

Frontmatter

Unforgeable Quantum Encryption

Tightly-Secure Key-Encapsulation Mechanism in the Quantum Random Oracle Model

A Concrete Treatment of Fiat-Shamir Signatures in the Quantum Random-Oracle Model

Non-maleable Codes

Frontmatter

Non-malleable Randomness Encoders and Their Applications

Non-malleable Codes from Average-Case Hardness: , Decision Trees, and Streaming Space-Bounded Tampering

Provable Symmetric Cryptography

Frontmatter

Naor-Reingold Goes Public: The Complexity of Known-Key Security

Updatable Encryption with Post-Compromise Security

Backmatter

Premium Partner