Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2014 | Book

Virtual Black-Box Obfuscation for All Circuits via Generic Graded Encoding Read chapter Read first chapter

Theory of Cryptography

11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings

Editor: Yehuda Lindell

Publisher: Springer Berlin Heidelberg

Book Series : Lecture Notes in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This book constitutes the refereed proceedings of the 11th Theory of Cryptography Conference, TCC 2014, held in San Diego, CA, USA, in February 2014. The 30 revised full papers presented were carefully reviewed and selected from 90 submissions. The papers are organized in topical sections on obfuscation, applications of obfuscation, zero knowledge, black-box separations, secure computation, coding and cryptographic applications, leakage, encryption, hardware-aided secure protocols, and encryption and signatures.

Table of Contents

Frontmatter

Obfuscation

Virtual Black-Box Obfuscation for All Circuits via Generic Graded Encoding
Abstract
We present a new general-purpose obfuscator for all polynomial size circuits. The obfuscator uses graded encoding schemes, a generalization of multilinear maps. We prove that the obfuscator exposes no more information than the program’s black-box functionality, and achieves virtual black-box security, in the generic graded encoded scheme model. This proof is under the Bounded Speedup Hypothesis (BSH, a plausible worst-case complexity-theoretic assumption related to the Exponential Time Hypothesis), in addition to standard cryptographic assumptions. We also prove that it satisfies the notion of indistinguishability obfuscation without without relying on BSH (in the same generic model and under standard cryptographic assumptions).
Very recently, Garg et al. (FOCS 2013) used graded encoding schemes to present a candidate obfuscator for indistinguishability obfuscation. They posed the problem of constructing a provably secure indistinguishability obfuscator in the generic graded encoding scheme model. Our obfuscator resolves this problem (indeed, under BSH it achieves the stronger notion of virtual black box security, which is our focus in this work).
Our construction is different from that of Garg et al., but is inspired by it, in particular by their use of permutation branching programs. We obtain our obfuscator by developing techniques used to obfuscate d-CNF formulas (ITCS 2014), and applying them to permutation branching programs. This yields an obfuscator for the complexity class \(\mathcal{NC}^1\). We then use homomorphic encryption to obtain an obfuscator for any polynomialsize circuit.
Zvika Brakerski, Guy N. Rothblum
Obfuscation for Evasive Functions
Abstract
An evasive circuit family is a collection of circuits \(\mathcal{C}\) such that for every input x, a random circuit from \(\mathcal{C}\) outputs 0 on x with overwhelming probability. We provide a combination of definitional, constructive, and impossibility results regarding obfuscation for evasive functions:
1
The (average case variants of the) notions of virtual black box obfuscation (Barak et al, CRYPTO ’01) and virtual gray box obfuscation (Bitansky and Canetti, CRYPTO ’10) coincide for evasive function families. We also define the notion of input-hiding obfuscation for evasive function families, stipulating that for a random \(C \in{\mathcal{C}}\) it is hard to find, given \(\mathcal{O}(C)\), a value outside the preimage of 0. Interestingly, this natural definition, also motivated by applications, is likely not implied by the seemingly stronger notion of average-case virtual black-box obfuscation.
 
2
If there exist average-case virtual gray box obfuscators for all evasive function families, then there exist (quantitatively weaker) average-case virtual gray obfuscators for all function families.
 
3
There does not exist a worst-case virtual black box obfuscator even for evasive circuits, nor is there an average-case virtual gray box obfuscator for evasive Turing machine families.
 
4
Let \(\mathcal{C}\) be an evasive circuit family consisting of functions that test if a low-degree polynomial (represented by an efficient arithmetic circuit) evaluates to zero modulo some large prime p. Then under a natural analog of the discrete logarithm assumption in a group supporting multilinear maps, there exists an input-hiding obfuscator for \(\mathcal{C}\). Under a new perfectly-hiding multilinear encoding assumption, there is an average-case virtual black box obfuscator for the family \(\mathcal{C}\).
 
Boaz Barak, Nir Bitansky, Ran Canetti, Yael Tauman Kalai, Omer Paneth, Amit Sahai
On Extractability Obfuscation
Abstract
We initiate the study of extractability obfuscation, a notion first suggested by Barak et al. (JACM 2012): An extractability obfuscator \(e{\mathcal{O}}\) for a class of algorithms \(\mathcal{M}\) guarantees that if an efficient attacker \(\mathcal{A}\) can distinguish between obfuscations \(e{\mathcal O}(M_1), e{\mathcal O}(M_2)\) of two algorithms \(M_1,M_2 \in{\mathcal{M}}\), then \(\mathcal{A}\) can efficiently recover (given M 1 and M 2) an input on which M 1 and M 2 provide different outputs.
  • We rely on the recent candidate virtual black-box obfuscation constructions to provide candidate constructions of extractability obfuscators for NC 1; next, following the blueprint of Garg et al. (FOCS 2013), we show how to bootstrap the obfuscator for NC 1 to an obfuscator for all non-uniform polynomial-time Turing machines. In contrast to the construction of Garg et al., which relies on indistinguishability obfuscation for NC 1, our construction enables succinctly obfuscating non-uniform Turing machines (as opposed to circuits), without turning running-time into description size.
  • We introduce a new notion of functional witness encryption, which enables encrypting a message m with respect to an instance x, language L, and function f, such that anyone (and only those) who holds a witness w for x ∈ L can compute f(m,w) on the message and particular known witness. We show that functional witness encryption is, in fact, equivalent to extractability obfuscation.
  • We demonstrate other applications of extractability extraction, including the first construction of fully (adaptive-message) indistinguishability-secure functional encryption for an unbounded number of key queries and unbounded message spaces.
  • We finally relate indistinguishability obfuscation and extractability obfuscation and show special cases when indistinguishability obfuscation can be turned into extractability obfuscation.
Elette Boyle, Kai-Min Chung, Rafael Pass

Applications of Obfuscation

Two-Round Secure MPC from Indistinguishability Obfuscation
Abstract
One fundamental complexity measure of an MPC protocol is its round complexity. Asharov et al. recently constructed the first three round protocol for general MPC in the CRS model. Here, we show how to achieve this result with only two rounds. We obtain UC security with abort against static malicious adversaries, and fairness if there is an honest majority. Additionally the communication in our protocol is only proportional to the input and output size of the function being evaluated and independent of its circuit size. Our main tool is indistinguishability obfuscation, for which a candidate construction was recently proposed by Garg et al.
The technical tools that we develop in this work also imply virtual black box obfuscation of a new primitive that we call a dynamic point function. This primitive may be of independent interest.
Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova
Chosen Ciphertext Security via Point Obfuscation
Abstract
In this paper, we show two new constructions of chosen ciphertext secure (CCA secure) public key encryption (PKE) from general assumptions. The key ingredient in our constructions is an obfuscator for point functions with multi-bit output (MBPF obfuscators, for short), that satisfies some (average-case) indistinguishability-based security, which we call AIND security, in the presence of hard-to-invert auxiliary input. Specifically, our first construction is based on a chosen plaintext secure PKE scheme and an MBPF obfuscator satisfying the AIND security in the presence of computationally hard-to-invert auxiliary input. Our second construction is based on a lossy encryption scheme and an MBPF obfuscator satisfying the AIND security in the presence of statistically hard-to-invert auxiliary input. To clarify the relative strength of AIND security, we show the relations among security notions for MBPF obfuscators, and show that AIND security with computationally (resp. statistically) hard-to-invert auxiliary input is implied by the average-case virtual black-box (resp. virtual grey-box) property with the same type of auxiliary input. Finally, we show that a lossy encryption scheme can be constructed from an obfuscator for point functions (point obfuscator) that satisfies re-randomizability and a weak form of composability in the worst-case virtual grey-box sense. This result, combined with our second generic construction and several previous results on point obfuscators and MBPF obfuscators, yields a CCA secure PKE scheme that is constructed solely from a re-randomizable and composable point obfuscator. We believe that our results make an interesting bridge that connects CCA secure PKE and program obfuscators, two seemingly isolated but important cryptographic primitives in the area of cryptography.
Takahiro Matsuda, Goichiro Hanaoka

Zero Knowledge

Probabilistically Checkable Proofs of Proximity with Zero-Knowledge
Abstract
A probabilistically Checkable Proof (PCP) allows a randomized verifier, with oracle access to a purported proof, to probabilistically verify an input statement of the form “x ∈ L” by querying only few bits of the proof. A PCP of proximity (PCPP) has the additional feature of allowing the verifier to query only few bits of the input x, where if the input is accepted then the verifier is guaranteed that (with high probability) the input is close to some x′ ∈ L.
Motivated by their usefulness for sublinear-communication cryptography, we initiate the study of a natural zero-knowledge variant of PCPP (ZKPCPP), where the view of any verifier making a bounded number of queries can be efficiently simulated by making the same number of queries to the input oracle alone. This new notion provides a useful extension of the standard notion of zero-knowledge PCPs. We obtain two types of results.
  • Constructions. We obtain the first constructions of query-efficient ZKPCPPs via a general transformation which combines standard query-efficient PCPPs with protocols for secure multiparty computation. As a byproduct, our construction provides a conceptually simpler alternative to a previous construction of honest-verifier zero-knowledge PCPs due to Dwork et al. (Crypto ’92).
  • Applications. We motivate the notion of ZKPCPPs by applying it towards sublinear-communication implementations of commit-and-prove functionalities. Concretely, we present the first sublinear-communication commit-and-prove protocols which make a black-box use of a collision-resistant hash function, and the first such multiparty protocols which offer information-theoretic security in the presence of an honest majority.
Yuval Ishai, Mor Weiss
Achieving Constant Round Leakage-Resilient Zero-Knowledge
Abstract
Recently there has been a huge emphasis on constructing cryptographic protocols that maintain their security guarantees even in the presence of side channel attacks. Such attacks exploit the physical characteristics of a cryptographic device to learn useful information about the internal state of the device. Designing protocols that deliver meaningful security even in the presence of such leakage attacks is a challenging task.
The recent work of Garg, Jain, and Sahai formulates a meaningful notion of zero-knowledge in presence of leakage; and provides a construction which satisfies a weaker variant of this notion called (1 + ε)-leakage-resilient-zero-knowledge, for every constant ε > 0. In this weaker variant, roughly speaking, if the verifier learns ℓ bits of leakage during the interaction, then the simulator is allowed to access (1 + ε)·ℓ bits of leakage. The round complexity of their protocol is \(\lceil \frac{n}{\epsilon}\rceil\).
In this work, we present the first construction of leakage-resilient zero-knowledge satisfying the ideal requirement of ε = 0. While our focus is on a feasibility result for ε = 0, our construction also enjoys a constant number of rounds. At the heart of our construction is a new “public-coin preamble” which allows the simulator to recover arbitrary information from a (cheating) verifier in a “straight line.” We use non-black-box simulation techniques to accomplish this goal.
Omkant Pandey
Statistical Concurrent Non-malleable Zero Knowledge
Abstract
The notion of Zero Knowledge introduced by Goldwasser, Micali and Rackoff in STOC 1985 is fundamental in Cryptography. Motivated by conceptual and practical reasons, this notion has been explored under stronger definitions. We will consider the following two main strengthened notions.
Statistical Zero Knowledge: here the zero-knowledge property will last forever, even in case in future the adversary will have unlimited power.
Concurrent Non-Malleable Zero Knowledge: here the zeroknowledge property is combined with non-transferability and the adversary fails in mounting a concurrent man-in-the-middle attack aiming at transferring zero-knowledge proofs/arguments.
Besides the well-known importance of both notions, it is still unknown whether one can design a zero-knowledge protocol that satisfies both notions simultaneously.
In this work we shed light on this question in a very strong sense. We show a statistical concurrent non-malleable zero-knowledge argument system for \(\mathcal{NP}\) with a black-box simulator-extractor.
Claudio Orlandi, Rafail Ostrovsky, Vanishree Rao, Amit Sahai, Ivan Visconti
4-Round Resettably-Sound Zero Knowledge
Abstract
While 4-round constructions of zero-knowledge arguments are known based on the existence of one-way functions, constuctions of resettably-sound zero-knowledge arguments require either stronger assumptions (the existence of a fully-homomorphic encryption scheme), or more communication rounds. We close this gap by demonstrating a 4- round resettably-sound zero-knowledge argument for NP based on the existence of one-way functions.
Kai-Min Chung, Rafail Ostrovsky, Rafael Pass, Muthuramakrishnan Venkitasubramaniam, Ivan Visconti

Black-Box Separations

Can Optimally-Fair Coin Tossing Be Based on One-Way Functions?
Abstract
Coin tossing is a basic cryptographic task that allows two distrustful parties to obtain an unbiased random bit in a way that neither party can bias the output by deviating from the protocol or halting the execution. Cleve [STOC’86] showed that in any r round coin tossing protocol one of the parties can bias the output by Ω(1/r) through a “fail-stop” attack; namely, they simply execute the protocol honestly and halt at some chosen point. In addition, relying on an earlier work of Blum [COMPCON’82], Cleve presented an r-round protocol based on one-way functions that was resilient to bias at most \(O(1/\sqrt r)\). Cleve’s work left open whether ”‘optimally-fair’” coin tossing (i.e. achieving bias O(1/r) in r rounds) is possible. Recently Moran, Naor, and Segev [TCC’09] showed how to construct optimally-fair coin tossing based on oblivious transfer, however, it was left open to find the minimal assumptions necessary for optimally-fair coin tossing. The work of Dachman-Soled et al. [TCC’11] took a step toward answering this question by showing that any black-box construction of optimally-fair coin tossing based on a one-way functions with n-bit input and output needs Ω(n/logn) rounds.
In this work we take another step towards understanding the complexity of optimally-fair coin-tossing by showing that this task (with an arbitrary number of rounds) cannot be based on one-way functions in a black-box way, as long as the protocol is ”‘oblivious’” to the implementation of the one-way function. Namely, we consider a natural class of black-box constructions based on one-way functions, called function oblivious, in which the output of the protocol does not depend on the specific implementation of the one-way function and only depends on the randomness of the parties. Other than being a natural notion on its own, the known coin tossing protocols of Blum and Cleve (both based on one-way functions) are indeed function oblivious. Thus, we believe our lower bound for function-oblivious constructions is a meaningful step towards resolving the fundamental open question of the complexity of optimally-fair coin tossing.
Dana Dachman-Soled, Mohammad Mahmoody, Tal Malkin
On the Power of Public-Key Encryption in Secure Computation
Abstract
We qualitatively separate semi-honest secure computation of nontrivial secure-function evaluation (SFE) functionalities from existence of keyagreement protocols. Technically, we show the existence of an oracle (namely, PKE-oracle) relative to which key-agreement protocols exist; but it is useless for semi-honest secure realization of symmetric 2-party (deterministic finite) SFE functionalities, i.e. any SFE which can be securely performed relative to this oracle can also be securely performed in the plain model.
Our main result has following consequences.
  • There exists an oracle which is useful for some 3-party deterministic SFE; but useless for semi-honest secure realization of any general 2-party (deterministic finite) SFE.
  • With respect to semi-honest, standalone or UC security, existence of keyagreement protocols (if used in black-box manner) is only as useful as the commitment-hybrid for general 2-party (deterministic finite) SFE functionalities.
This work advances (and conceptually simplifies) several state-of-the-art techniques in the field of black-box separations:
1
We introduce a general common-information learning algorithm (CIL) which extends the “eavesdropper” in prior work [1,2,3], to protocols whose message can depend on information gathered by the CIL so far.
 
2
With the help of this CIL, we show that in a secure 2-party protocol using an idealized PKE oracle, surprisingly, decryption queries are useless.
 
3
The idealized PKE oracle with its decryption facility removed can be modeled as a collection of image-testable random-oracles. We extend the analysis approaches of prior work on random oracle [1,2,4,5,3] to apply to this class of oracles. This shows that these oracles are useless for semi-honest 2-party SFE (as well as for key-agreement).
 
These information theoretic impossibility results can be naturally extended to yield black-box separation results (cf. [6]).
Mohammad Mahmoody, Hemanta K. Maji, Manoj Prabhakaran
On the Impossibility of Basing Public-Coin One-Way Permutations on Trapdoor Permutations
Abstract
One of the fundamental research themes in cryptography is to clarify what the minimal assumptions to realize various kinds of cryptographic primitives are, and up to now, a number of relationships among primitives have been investigated and established. Among others, it has been suggested (and sometimes explicitly claimed) that a family of one-way trapdoor permutations (TDP) is sufficient for constructing almost all the basic primitives/protocols in both ‘‘public-key” and ‘‘private-key” cryptography. In this paper, however, we show strong evidence that this is not the case for the constructions of a one-way permutation (OWP), one of the most fundamental primitives in private cryptography. Specifically, we show that there is no black-box construction of a OWP from a TDP, even if the TDP is ideally secure, where, roughly speaking, ideal security of a TDP corresponds to security satisfied by random permutations and thus captures major security notions of TDPs such as one-wayness, claw-freeness, security under correlated inputs, etc. Our negative result might at first sound unexpected because both OWP and (ideally secure) TDP are primitives that implement a ‘‘permutation” that is ‘‘one-way”. However, our result exploits the fact that a TDP is a ‘‘secret-coin” family of permutations whose permutations become available only after some sort of key generation is performed, while a OWP is a publicly computable function which does not have such key generation process.
Takahiro Matsuda

Secure Computation

Towards Characterizing Complete Fairness in Secure Two-Party Computation
Abstract
The well known impossibility result of Cleve (STOC 1986) implies that in general it is impossible to securely compute a function with complete fairness without an honest majority. Since then, the accepted belief has been that nothing non-trivial can be computed with complete fairness in the two party setting. The surprising work of Gordon, Hazay, Katz and Lindell (STOC 2008) shows that this belief is false, and that there exist some non-trivial (deterministic, finite-domain) boolean functions that can be computed fairly. This raises the fundamental question of characterizing complete fairness in secure two-party computation.
In this work we show that not only that some or few functions can be computed fairly, but rather an enormous amount of functions can be computed with complete fairness. In fact, almost all boolean functions with distinct domain sizes can be computed with complete fairness (for instance, more than 99.999% of the boolean functions with domain sizes 31 ×30). The class of functions that is shown to be possible includes also rather involved and highly non-trivial tasks, such as set-membership, evaluation of a private (Boolean) function and private matchmaking.
In addition, we demonstrate that fairness is not restricted to the class of symmetric boolean functions where both parties get the same output, which is the only known feasibility result. Specifically, we show that fairness is also possible for asymmetric boolean functions where the output of the parties is not necessarily the same. Moreover, we consider the class of functions with non-binary output, and show that fairness is possible for any finite range.
The constructions are based on the protocol of Gordon et. al, and the analysis uses tools from convex geometry.
Gilad Asharov
On the Cryptographic Complexity of the Worst Functions
Abstract
We study the complexity of realizing the “worst” functions in several standard models of information-theoretic cryptography. In particular, for the case of security against passive adversaries, we obtain the following main results.
  • OT complexity of secure two-party computation. Every function f:[N]×[N] → {0,1} can be securely evaluated using \(\tilde{O}{(N^{2/3})}\) invocations of an oblivious transfer oracle. A similar result holds for securely sampling a uniform pair of outputs from a set S ⊆ [N]×[N].
  • Correlated randomness complexity of secure two-party computation. Every function f:[N]×[N] → {0,1} can be securely evaluated using \(2^{\tilde{O}{\sqrt{\log N}}}\) bits of correlated randomness.
  • Communication complexity of private simultaneous messages. Every function f:[N]×[N] → {0,1} can be securely evaluated in the non-interactive model of Feige, Kilian, and Naor (STOC 1994) with messages of length \(O(\sqrt{N})\).
  • Share complexity of forbidden graph access structures. For every graph G on N nodes, there is a secret-sharing scheme for N parties in which each pair of parties can reconstruct the secret if and only if the corresponding nodes in G are connected, and where each party gets a share of size \(\tilde{O}{\sqrt{N}}\).
The worst-case complexity of the best previous solutions was Ω(N) for the first three problems and Ω(N/logN) for the last one. The above results are obtained by applying general transformations to variants of private information retrieval (PIR) protocols from the literature, where different flavors of PIR are required for different applications.
Amos Beimel, Yuval Ishai, Ranjit Kumaresan, Eyal Kushilevitz
Constant-Round Black-Box Construction of Composable Multi-Party Computation Protocol
Abstract
We present the first general MPC protocol that satisfies the following: (1) the construction is black-box, (2) the protocol is universally composable in the plain model, and (3) the number of rounds is constant. The security of our protocol is proven in angel-based UC security under the assumption of the existence of one-way functions that are secure against sub-exponential-time adversaries and constant-round semi-honest oblivious transfer protocols that are secure against quasi-polynomial-time adversaries. We obtain the MPC protocol by constructing a constant-round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions that are secure against sub-exponential-time adversaries. To justify the use of such a sub-exponential hardness assumption in obtaining our constant-round CCA-secure commitment scheme, we show that if black-box reductions are used, there does not exist any constant-round CCA-secure commitment scheme under any falsifiable polynomial-time hardness assumptions.
Susumu Kiyoshima, Yoshifumi Manabe, Tatsuaki Okamoto
One-Sided Adaptively Secure Two-Party Computation
Abstract
Adaptive security is a strong security notion that captures additional security threats that are not addressed by static corruptions. For instance, it captures real-world scenarios where “hackers” actively break into computers, possibly while they are executing secure protocols. Studying this setting is interesting from both theoretical and practical points of view. A primary building block in designing adaptively secure protocols is a non-committing encryption (NCE) that implements secure communication channels in the presence of adaptive corruptions. Current constructions require a number of public key operations that grows linearly with the length of the message. Furthermore, general two-party protocols require a number of NCE calls that is linear in the circuit size.
In this paper we study the two-party setting in which at most one of the parties is adaptively corrupted, which we believe is the right security notion in the two-party setting. We study the feasibility of (1) NCE with constant number of public key operations for large message spaces (2) Oblivious transfer with constant number of public key operations for large input spaces of the sender, and (3) constant round secure computation protocols with a number of NCE calls, and an overall number of public key operations, that are independent of the circuit size. Our study demonstrates that such primitives indeed exist in the presence of single corruptions, while this is not known for fully adaptive security.
Carmit Hazay, Arpita Patra
Multi-linear Secret-Sharing Schemes
Abstract
Multi-linear secret-sharing schemes are the most common secret-sharing schemes. In these schemes the secret is composed of some field elements and the sharing is done by applying some fixed linear mapping on the field elements of the secret and some randomly chosen field elements. If the secret contains one field element, then the scheme is called linear. The importance of multi-linear schemes is that they provide a simple non-interactive mechanism for computing shares of linear combinations of previously shared secrets. Thus, they can be easily used in cryptographic protocols.
In this work we study the power of multi-linear secret-sharing schemes. On one hand, we prove that ideal multi-linear secret-sharing schemes in which the secret is composed of p field elements are more powerful than schemes in which the secret is composed of less than p field elements (for every prime p). On the other hand, we prove super-polynomial lower bounds on the share size in multi-linear secret-sharing schemes. Previously, such lower bounds were known only for linear schemes.
Amos Beimel, Aner Ben-Efraim, Carles Padró, Ilya Tyomkin
Broadcast Amplification
Abstract
A d-broadcast primitive is a communication primitive that allows a sender to send a value from a domain of size d to a set of parties. A broadcast protocol emulates the d-broadcast primitive using only point-to-point channels, even if some of the parties cheat, in the sense that all correct recipients agree on the same value v (consistency), and if the sender is correct, then v is the value sent by the sender (validity). A celebrated result by Pease, Shostak and Lamport states that such a broadcast protocol exists if and only if t < n/3, where n denotes the total number of parties and t denotes the upper bound on the number of cheaters.
This paper is concerned with broadcast protocols for any number of cheaters (t < n), which can be possible only if, in addition to point-to-point channels, another primitive is available. Broadcast amplification is the problem of achieving d-broadcast when d′-broadcast can be used once, for d′ < d. Let ϕ n (d) denote the minimal such d′ for domain size d.
We show that for n = 3 parties, broadcast for any domain size is possible if only a single 3-broadcast is available, and broadcast of a single bit (d′ = 2) is not sufficient, i.e., ϕ 3(d) = 3 for any d ≥ 3. In contrast, for n > 3 no broadcast amplification is possible, i.e., ϕ n (d) = d for any d.
However, if other parties than the sender can also broadcast some short messages, then broadcast amplification is possible for any n. Let \(\phi^*_n(d)\) denote the minimal d′ such that d-broadcast can be constructed from primitives d′1-broadcast,…, d′ k -broadcast, where d′ = ∏  i d′ i (i.e., logd′ = ∑  i logd′ i ). Note that \(\phi^*_n(d)\leq\phi_n(d)\). We show that broadcasting 8nlogn bits in total suffices, independently of d, and that at least n − 2 parties, including the sender, must broadcast at least one bit. Hence \(\min(\log d,n-2) \leq \log \phi^*_n(d) \leq 8n\log n\).
Martin Hirt, Ueli Maurer, Pavel Raykov

Coding and Cryptographic Applications

Non-malleable Coding against Bit-Wise and Split-State Tampering
Abstract
Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), aims for protecting the integrity of information against tampering attacks in situations where error-detection is impossible. Intuitively, information encoded by a non-malleable code either decodes to the original message or, in presence of any tampering, to an unrelated message. Non-malleable coding is possible against any class of adversaries of bounded size. In particular, Dziembowski et al. show that such codes exist and may achieve positive rates for any class of tampering functions of size at most \(2^{2^{\alpha n}}\), for any constant α ∈ [0, 1). However, this result is existential and has thus attracted a great deal of subsequent research on explicit constructions of non-malleable codes against natural classes of adversaries.
In this work, we consider constructions of coding schemes against two well-studied classes of tampering functions; namely, bit-wise tampering functions (where the adversary tampers each bit of the encoding independently) and the much more general class of split-state adversaries (where two independent adversaries arbitrarily tamper each half of the encoded sequence). We obtain the following results for these models.
1
For bit-tampering adversaries, we obtain explicit and efficiently encodable and decodable non-malleable codes of length n achieving rate 1 − o(1) and error (also known as “exact security”) \(\exp(-\tilde{\Omega}(n^{1/7}))\). Alternatively, it is possible to improve the error to \(\exp(-\tilde{\Omega}(n))\) at the cost of making the construction Monte Carlo with success probability \(1-\exp(-\Omega(n))\) (while still allowing a compact description of the code). Previously, the best known construction of bit-tampering coding schemes was due to Dziembowski et al. (ICS 2010), which is a Monte Carlo construction achieving rate close to .1887.
 
2
We initiate the study of seedless non-malleable extractors as a natural variation of the notion of non-malleable extractors introduced by Dodis and Wichs (STOC 2009). We show that construction of non-malleable codes for the split-state model reduces to construction of non-malleable two-source extractors. We prove a general result on existence of seedless non-malleable extractors, which implies that codes obtained from our reduction can achieve rates arbitrarily close to 1/5 and exponentially small error. In a separate recent work, the authors show that the optimal rate in this model is 1/2. Currently, the best known explicit construction of split-state coding schemes is due to Aggarwal, Dodis and Lovett (ECCC TR13-081) which only achieves vanishing (polynomially small) rate.
 
Mahdi Cheraghchi, Venkatesan Guruswami
Continuous Non-malleable Codes
Abstract
Non-malleable codes are a natural relaxation of error correcting/ detecting codes that have useful applications in the context of tamper resilient cryptography. Informally, a code is non-malleable if an adversary trying to tamper with an encoding of a given message can only leave it unchanged or modify it to the encoding of a completely unrelated value. This paper introduces an extension of the standard non-malleability security notion - so-called continuous non-malleability - where we allow the adversary to tamper continuously with an encoding. This is in contrast to the standard notion of non-malleable codes where the adversary only is allowed to tamper a single time with an encoding. We show how to construct continuous non-malleable codes in the common split-state model where an encoding consist of two parts and the tampering can be arbitrary but has to be independent with both parts. Our main contributions are outlined below:
1
We propose a new uniqueness requirement of split-state codes which states that it is computationally hard to find two codewords X = (X 0,X 1) and X′ = (X 0,X 1′) such that both codewords are valid, but X 0 is the same in both X and X′. A simple attack shows that uniqueness is necessary to achieve continuous non-malleability in the split-state model. Moreover, we illustrate that none of the existing constructions satisfies our uniqueness property and hence is not secure in the continuous setting.
 
2
We construct a split-state code satisfying continuous non-malleability. Our scheme is based on the inner product function, collision-resistant hashing and non-interactive zero-knowledge proofs of knowledge and requires an untamperable common reference string.
 
3
We apply continuous non-malleable codes to protect arbitrary cryptographic primitives against tampering attacks. Previous applications of non-malleable codes in this setting required to perfectly erase the entire memory after each execution and required the adversary to be restricted in memory. We show that continuous non-malleable codes avoid these restrictions.
 
Sebastian Faust, Pratyay Mukherjee, Jesper Buus Nielsen, Daniele Venturi
Locally Updatable and Locally Decodable Codes
Abstract
We introduce the notion of locally updatable and locally decodable codes (LULDCs). In addition to having low decode locality, such codes allow us to update a codeword (of a message) to a codeword of a different message, by rewriting just a few symbols. While, intuitively, updatability and error-correction seem to be contrasting goals, we show that for a suitable, yet meaningful, metric (which we call the Prefix Hamming metric), one can construct such codes. Informally, the Prefix Hamming metric allows the adversary to arbitrarily corrupt bits of the codeword subject to one constraint – he does not corrupt more than a δ fraction (for some constant δ) of the t “most-recently changed” bits of the codeword (for all 1 ≤ t ≤ n, where n is the length of the codeword).
Our results are as follows. First, we construct binary LULDCs for messages in {0, 1} k with constant rate, update locality of \(\mathcal{O}(\log^2 k)\), and read locality of \(\mathcal{O}(k^\epsilon)\) for any constant ε < 1. Next, we consider the case where the encoder and decoder share a secret state and the adversary is computationally bounded. Here too, we obtain local updatability and decodability for the Prefix Hamming metric. Furthermore, we also ensure that the local decoding algorithm never outputs an incorrect message – even when the adversary can corrupt an arbitrary number of bits of the codeword. We call such codes locally updatable locally decodable-detectable codes (LULDDCs) and obtain dramatic improvements in the parameters (over the information-theoretic setting). Our codes have constant rate, an update locality of \(\mathcal{O}(\log^2 k)\) and a read locality of \(\mathcal{O}(\lambda \log ^2k)\), where λ is the security parameter.
Finally, we show how our techniques apply to the setting of dynamic proofs of retrievability (DPoR) and present a construction of this primitive with better parameters than existing constructions. In particular, we construct a DPoR scheme with linear storage, \(\mathcal{O}(\log^2 k)\) write complexity, and \(\mathcal{O}(\lambda \log k)\) read and audit complexity.
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky

Leakage

Leakage Resilient Fully Homomorphic Encryption
Abstract
We construct the first leakage resilient variants of fully homomorphic encryption (FHE) schemes. Our leakage model is bounded adaptive leakage resilience. We first construct a leakage-resilient leveled FHE scheme, meaning the scheme is homomorphic for all circuits of depth less than some pre-established maximum set at key generation. We do so by applying ideas from recent works analyzing the leakage resilience of public key encryption schemes based on the decision learning with errors (DLWE) assumption to the Gentry, Sahai and Waters ([1]) leveled FHE scheme. We then move beyond simply leveled FHE, removing the need for an a priori maximum circuit depth, by presenting a novel way to combine schemes. We show that by combining leakage resilient leveled FHE with multi-key FHE, it is possible to create a leakage resilient scheme capable of homomorphically evaluating circuits of arbitrary depth, with a bounded number of distinct input ciphertexts.
Alexandra Berkoff, Feng-Hao Liu
Securing Circuits and Protocols against 1/poly(k) Tampering Rate
Abstract
In this work we present an efficient compiler that converts any circuit C into one that is resilient to tampering with 1/poly(k) fraction of the wires, where k is a security parameter independent of the size of the original circuit |C|. Our tampering model is similar to the one proposed by Ishai et al. (Eurocrypt, 2006) where a tampering adversary may tamper with any wire in the circuit (as long as the overall number of tampered wires is bounded), by setting it to 0 or 1, or by toggling with it. Our result improves upon that of Ishai et al. which only allowed the adversary to tamper with 1/|C| fraction of the wires.
Our result is built on a recent result of Dachman-Soled and Kalai (Crypto, 2012), who constructed tamper resilient circuits in this model, tolerating a constant tampering rate. However, their tampering adversary may learn logarithmically many bits of sensitive information. In this work, we avoid this leakage of sensitive information, while still allowing leakage rate that is independent of the circuit size. We mention that the result of Dachman-Soled and Kalai (Crypto, 2012) is only for Boolean circuits (that output a single bit), and for circuits that output k bits, their tampering-rate becomes 1/O(k). Thus for cryptographic circuits (that output k bits), our result strictly improves over (Dachman-Soled and Kalai, Crypto, 2012).
In this work, we also show how to generalize this result to the setting of two-party protocols, by constructing a general 2-party computation protocol (for any functionality) that is secure against a tampering adversary, who in addition to corrupting a party may tamper with 1/poly(k)-fraction of the wires of the computation of the honest party and the bits communicated during the protocol.
Dana Dachman-Soled, Yael Tauman Kalai
How to Fake Auxiliary Input
Abstract
Consider a joint distribution (X,A) on a set \({\mathcal X}\times\{0, 1\}^\ell\). We show that for any family \({\mathcal F}\) of distinguishers \(f : {\cal X} \times \{0, 1\}^\ell \rightarrow\{0,1\}\), there exists a simulator \(h : {\mathcal X} \rightarrow \{0,1\}^\ell\) such that
1
no function in \({\mathcal F}\) can distinguish (X,A) from (X,h(X)) with advantage ε,
 
2
h is only O(23ℓ ε − 2) times less efficient than the functions in \({\mathcal F}\).
 
For the most interesting settings of the parameters (in particular, the cryptographic case where X has superlogarithmic min-entropy, ε > 0 is negligible and \({\mathcal F}\) consists of circuits of polynomial size), we can make the simulator h deterministic.
As an illustrative application of our theorem, we give a new security proof for the leakage-resilient stream-cipher from Eurocrypt’09. Our proof is simpler and quantitatively much better than the original proof using the dense model theorem, giving meaningful security guarantees if instantiated with a standard blockcipher like AES.
Subsequent to this work, Chung, Lui and Pass gave an interactive variant of our main theorem, and used it to investigate weak notions of Zero-Knowledge. Vadhan and Zheng give a more constructive version of our theorem using their new uniform min-max theorem.
Dimitar Jetchev, Krzysztof Pietrzak

Encryption

Standard versus Selective Opening Security: Separation and Equivalence Results
Abstract
Suppose many messages are encrypted using a public-key encryption scheme. Imagine an adversary that may adaptively ask for openings of some of the ciphertexts. Selective opening (SO) security requires that the unopened ciphertexts remain secure, in the sense that this adversary cannot derive any nontrivial information about the messages in the unopened ciphertexts.
Surprisingly, the question whether SO security is already implied by standard security notions has proved highly nontrivial. Only recently, Bellare, Dowsley, Waters, and Yilek (Eurocrypt 2012) could show that a strong form of SO security, simulation-based SO security, is not implied by standard security notions. It remains wide open, though, whether the potentially weaker (and in fact comparatively easily achievable) form of indistinguishability-based SO (i.e., IND-SO) security is implied by standard security. Here, we give (full and partial) answers to this question, depending on whether active or passive attacks are considered.
Concretely, we show that:
(a) For active (i.e., chosen-ciphertext) security, standard security does not imply IND-SO security. Concretely, we give a scheme that is IND-CCA, but not IND-SO-CCA secure.
(b) In the case of passive (i.e., chosen-plaintext) security, standard security does imply IND-SO security, at least in a generic model of computation and for a large class of encryption schemes. (Our separating scheme from (a) falls into this class of schemes.)
Our results show that the answer to the question whether standard security implies SO security highly depends on the concrete setting.
Dennis Hofheinz, Andy Rupp
Dual System Encryption via Predicate Encodings
Abstract
We introduce the notion of predicate encodings, an information-theoretic primitive reminiscent of linear secret-sharing that in addition, satisfies a novel notion of reusability. Using this notion, we obtain a unifying framework for adaptively-secure public-index predicate encryption schemes for a large class of predicates. Our framework relies on Waters’ dual system encryption methodology (Crypto ’09), and encompass the identity-based encryption scheme of Lewko and Waters (TCC ’10), and the attribute-based encryption scheme of Lewko et al. (Eurocrypt ’10). In addition, we obtain obtain several concrete improvements over prior works. Our work offers a novel interpretation of dual system encryption as a methodology for amplifying a one-time private-key primitive (i.e. predicate encodings) into a many-time public-key primitive (i.e. predicate encryption).
Hoeteck Wee

Hardware-Aided Secure Protocols

(Efficient) Universally Composable Oblivious Transfer Using a Minimal Number of Stateless Tokens
Abstract
We continue the line of work initiated by Katz (Eurocrypt 2007) on using tamper-proof hardware for universally composable secure computation. As our main result, we show an efficient oblivious-transfer (OT) protocol in which two parties each create and exchange a single, stateless token and can then run an unbounded number of OTs. Our result yields what we believe is the most practical and efficient known approach for oblivious transfer based on tamper-proof tokens, and implies that the parties can perform (repeated) secure computation of arbitrary functions without exchanging additional tokens.
Motivated by this result, we investigate the minimal number of stateless tokens needed for universally composable OT/secure computation. We prove that our protocol is optimal in this regard for constructions making black-box use of the tokens (in a sense we define). We also show that nonblack-box techniques can be used to obtain a construction using only a single stateless token.
Seung Geol Choi, Jonathan Katz, Dominique Schröder, Arkady Yerukhimovich, Hong-Sheng Zhou
Lower Bounds in the Hardware Token Model
Abstract
We study the complexity of secure computation in the tamperproof hardware token model. Our main focus is on non-interactive unconditional two-party computation using bit-OT tokens, but we also study computational security with stateless tokens that have more complex functionality. Our results can be summarized as follows:
  • There exists a class of functions such that the number of bit-OT tokens required to securely implement them is at least the size of the sender’s input. The same applies for receiver’s input size (with a different class of functionalities).
  • Non-adaptive protocols in the hardware token model imply efficient (decomposable) randomized encodings. This can be interpreted as evidence to the impossibility of non-adaptive protocols for a large class of functions.
  • There exists a functionality for which there is no protocol in the stateless hardware token model accessing the tokens at most a constant number of times, even when the adversary is computationally bounded.
En route to proving our results, we make interesting connections between the hardware token model and well studied notions such as OT hybrid model, randomized encodings and obfuscation.
Shashank Agrawal, Prabhanjan Ananth, Vipul Goyal, Manoj Prabhakaran, Alon Rosen

Encryption and Signatures

Unified, Minimal and Selectively Randomizable Structure-Preserving Signatures
Abstract
We construct a structure-preserving signature scheme that is selectively randomizable and works in all types of bilinear groups. We give matching lower bounds showing that our structure-preserving signature scheme is optimal with respect to both signature size and public verification key size.
State of the art structure-preserving signatures in the asymmetric setting consist of 3 group elements, which is known to be optimal. Our construction preserves the signature size of 3 group elements and also at the same time minimizes the verification key size to 1 group element.
Depending on the application, it is sometimes desirable to have strong unforgeability and in other situations desirable to have randomizable signatures. To get the best of both worlds, we introduce the notion of selective randomizability where the signer may for specific signatures provide randomization tokens that enable randomization.
Our structure-preserving signature scheme unifies the different pairing-based settings since it can be instantiated in both symmetric and asymmetric groups. Since previously optimal structure-preserving signatures had only been constructed in asymmetric bilinear groups this closes an important gap in our knowledge. Having a unified signature scheme that works in all types of bilinear groups is not just conceptually nice but also gives a hedge against future cryptanalytic attacks. An instantiation of our signature scheme in an asymmetric bilinear group may remain secure even if cryptanalysts later discover an efficiently computable homomorphism between the source groups.
Masayuki Abe, Jens Groth, Miyako Ohkubo, Mehdi Tibouchi
On the Impossibility of Structure-Preserving Deterministic Primitives
Abstract
Complex cryptographic protocols are often constructed in a modular way from primitives such as signatures, commitments, and encryption schemes, verifiable random functions, etc. together with zero-knowledge proofs ensuring that these primitives are properly orchestrated by the protocol participants. Over the past decades a whole framework of discrete logarithm based primitives has evolved. This framework, together with so-called generalized Schnorr proofs, gave rise to the construction of many efficient cryptographic protocols.
Unfortunately, the non-interactive versions of Schnorr proofs are secure only in the random oracle model, often resulting in protocols with unsatisfactory security guarantees. Groth and Sahai have provided an alternative non-interactive proof system (GS-proofs) that is secure in the standard model and allows for the “straight line” extraction of witnesses. Both these properties are very attractive, in particular if one wants to achieve composable security. However, GS-proofs require bilinear maps and, more severely, they are proofs of knowledge only for witnesses that are group elements. Thus, researchers have set out to construct efficient cryptographic primitives that are compatible with GS-proofs, in particular, primitives that are structure-preserving, meaning that their inputs, outputs, and public keys consist only of source group elements. Indeed, structure-preserving signatures, commitments, and encryption schemes have been proposed. Although deterministic primitives such as (verifiable) pseudo-random functions or verifiable unpredictable functions play an important role in the construction of many cryptographic protocols, no structure-preserving realizations of them are known so far.
As it turns out, this is no coincidence: in this paper we show that it is impossible to construct algebraic structure-preserving deterministic primitives that provide provability, uniqueness, and unpredictability. This includes verifiable random functions, unique signatures, and verifiable unpredictable functions as special cases. The restriction of structure-preserving primitives to be algebraic is natural, in particular as otherwise it is not possible to prove with GS-proofs that an algorithm has been run correctly. We further extend our negative result to pseudorandom functions and deterministic public key encryption as well as non-strictly structure-preserving primitives, where target group elements are also allowed in their ranges and public keys.
Masayuki Abe, Jan Camenisch, Rafael Dowsley, Maria Dubovitskaya
Backmatter
Metadata
Title
Theory of Cryptography
Editor
Yehuda Lindell
Copyright Year
2014
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-54242-8
Print ISBN
978-3-642-54241-1
DOI
https://doi.org/10.1007/978-3-642-54242-8

Premium Partner

    Image Credits