Abstract

We show how to obfuscate a large and expressive class of programs, which we call compute-and-compare programs, under the learning-with-errors (LWE) assumption. Each such program CC[f,y]CC[f,y] is parametrized by an arbitrary polynomial-time computable function ff along with a target value yy and we define CC[f,y](x)CC[f,y](x) to output 11 if f(x)=yf(x)=y and 00 otherwise. In other words, the program performs an arbitrary computation ff and then compares its output against a target yy. Our obfuscator satisfies distributional virtual-black-box security, which guarantees that the obfuscated program does not reveal any partial information about the function ff or the target value yy, as long as they are chosen from some distribution where yy has sufficient pseudo-entropy given ff. We also extend our result to multi-bit compute-and-compare programs MBCC[f,y,z](x)MBCC[f,y,z](x)which output a message zz if f(x)=yf(x)=y.

Compute-and-compare programs are powerful enough to capture many interesting obfuscation tasks as special cases. This includes obfuscating conjunctions, and therefore we improve on the prior work of Brakerski et al. (ITCS ’16) which constructed a conjunction obfuscator under a non-standard “entropic” ring-LWE assumption, while here we obfuscate a significantly broader class of programs under standard LWE. We show that our obfuscator has several interesting applications. For example, we can take any encryption scheme and publish an obfuscated plaintext equality tester that allows users to check whether an arbitrary ciphertext encrypts some target value yy; as long as yy has sufficient pseudo-entropy this will not harm semantic security. We can also use our obfuscator to generically upgrade attribute-based encryption to predicate encryption with one-sided attribute-hiding security, as well as witness encryption to indistinguishability obfuscation which is secure for all null circuits. Furthermore, we show that our obfuscator gives new circular-security counter-examples for public-key bit encryption and for unbounded length key cycles.

Our result uses the graph-induced multi-linear maps of Gentry, Gorbunov and Halevi (TCC ’15), but only in a carefully restricted manner which is provably secure under LWE. Our technique is inspired by ideas introduced in a recent work of Goyal, Koppula and Waters (EUROCRYPT ’17) in a seemingly unrelated context.

Abstract

A garbling scheme is used to garble a circuit C and an input x in a way that reveals the output C(x) but hides everything else. In many settings, the circuit can be garbled off-line without strict efficiency constraints, but the input must be garbled very efficiently on-line, with much lower complexity than evaluating the circuit. Yao’s garbling scheme [31] has essentially optimal on-line complexity, but only achieves selective security, where the adversary must choose the input x prior to seeing the garbled circuit. It has remained an open problem to achieve adaptive security, where the adversary can choose x after seeing the garbled circuit, while preserving on-line efficiency.

In this work, we modify Yao’s scheme in a way that allows us to prove adaptive security under one-way functions. In our main instantiation we achieve on-line complexity only proportional to the width w of the circuit. Alternatively we can also get an instantiation with on-line complexity only proportional to the depth d (and the output size) of the circuit, albeit incurring in a 2O(d)2O(d) security loss in our reduction. More broadly, we relate the on-line complexity of adaptively secure garbling schemes in our framework to a certain type of pebble complexity of the circuit. As our main tool, of independent interest, we develop a new notion of somewhere equivocal encryption, which allows us to efficiently equivocate on a small subset of the message bits.

Abstract

For many cryptographic primitives, it is relatively easy to achieve selective security (where the adversary commits a-priori to some of the choices to be made later in the attack) but appears difficult to achieve the more natural notion of adaptive security (where the adversary can make all choices on the go as the attack progresses). A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption (Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b). Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework that connects all of these works and allows us to present them in a unified and simplified fashion. Moreover, we use the framework to derive a new result for adaptively secure secret sharing over access structures defined via monotone circuits. We envision that further applications will follow in the future. Underlying our framework is the following simple idea. It is well known that selective security, where the adversary commits to nn-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary’s advantage by a factor of up to 2n2n. However, in some cases the proof of selective security proceeds via a sequence of hybrids, where each pair of adjacent hybrids locally only requires some smaller partial information consisting of m≪nm≪n bits. The partial information needed might be completely different between different pairs of hybrids, and if we look across all the hybrids we might rely on the entire nn-bit commitment. Nevertheless, the above is sufficient to prove adaptive security, at the cost of amplifying the adversary’s advantage by a factor of only 2m≪2n2m≪2n. In all of our examples using the above framework, the different hybrids are captured by some sort of a graph pebbling game and the amount of information that the adversary needs to commit to in each pair of hybrids is bounded by the maximum number of pebbles in play at any point in time. Therefore, coming up with better strategies for proving adaptive security translates to various pebbling strategies for different types of graphs.

Abstract:

We introduce two new cryptographic notions in the realm of public and symmetric key encryption.

– Encryption with invisible edits is an encryption scheme with two tiers of users: “privileged” and “unprivileged”. Privileged users know a key pair (pk, sk) and “unprivileged” users know a key pair (pk_e, sk_e) which is associated with an underlying edit e to be applied to messages encrypted. When an unprivileged user attempts to decrypt a ciphertext generated by a privileged user of an underlying plaintext m, it will be decrypted to an edited m’=Edit(m,e). Here, Edit is a supported edit function and e is a description of the particular edit. A user shouldn’t be able to tell whether he’s an unprivileged or a privileged user.

– An encryption with deniable edits is an encryption scheme which allows a user who owns a ciphertext c encrypting a large corpus of data m under a secret key sk, to generate an alternative but legitimate looking secret key sk_{c,e}, that decrypts c to an “edited” version of the data m’=Edit(m,e). This generalizes classical receiver deniable encryption, which is a special case of deniable edits where the edit function completely replaces the original data. The new flexibility allows to design solutions with much smaller key sizes than required in classical receiver deniable encryption allowing the key size to only scale with the description size of the edit e which can be much smaller than the plaintext data m.

We construct encryption schemes with invisible and deniable edits for any polynomial-time computable edit function under minimal assumptions: in the public-key setting we require the existence of standard public-key encryption and in the symmetric-key setting require the existence of one-way functions.

The solutions to both problems use common ideas, however there is a significant conceptual difference between deniable edits and invisible edits. Whereas encryption with deniable edits enables a user to modify the meaning of a single ciphertext in hindsight, the goal of encryption with invisible edits is to enable ongoing modifications of multiple ciphertexts

Abstract

We consider a setting where users store their encrypted documents on a remote server and can selectively share documents with each other. A user should be able to perform keyword searches over all the documents she has access to, including the ones that others shared with her. The contents of the documents, and the search queries, should remain private from the server.

This setting was considered by Popa et al. (NSDI ’14) who developed a new cryptographic primitive called Multi-Key Searchable Encryption (MKSE), together with an instantiation and an implementation within a system called Mylar, to address this goal. Unfortunately, Grubbs et al. (CCS ’16) showed that the proposed MKSE definition fails to provide basic security guarantees, and that the Mylar system is susceptible to simple attacks. Most notably, if a malicious Alice colludes with the server and shares a document with an honest Bob then the privacy of all of Bob’s search queries is lost.

In this work we revisit the notion of MKSE and propose a new strengthened definition that rules out the above attacks. We then construct MKSE schemes meeting our definition. We first give a simple and efficient construction using only pseudorandom functions. This construction achieves our strong security definition at the cost of increasing the server storage overhead relative to Mylar, essentially replicating the document each time it is shared. We also show that high server storage overhead is not inherent, by giving an alternate (albeit impractical) construction that manages to avoid it using obfuscation.

Abstract:

A garbling scheme is used to garble a circuit C and an input x in a way that reveals the output C(x)
but hides everything else. An adaptively secure scheme allows the adversary to specify the input x after
seeing the garbled circuit. Applebaum et al. (CRYPTO ’13) showed that in any garbling scheme with
adaptive simulation-based security, the size of the garbled input must exceed the output size of the circuit.
Here we show how to circumvent this lower bound and achieve significantly better efficiency under the
minimal assumption that one-way functions exist by relaxing the security notion from simulation-based
to indistinguishability-based.
We rely on the recent work of Hemenway et al. (CRYPTO ’16) which constructed an adaptive
simulation-based garbling scheme under one-way functions. The size of the garbled input in their scheme
is as large as the output size of the circuit plus a certain pebble complexity of the circuit, where the latter
is (e.g.,) bounded by the space complexity of the computation. By building on top of their construction
and adapting their proof technique, we show how to remove the output size dependence in their result
when considering indistinguishability-based security.
As an application of the above result, we get a symmetric-key functional encryption based on one-way
functions, with indistinguishability-based security where the adversary can obtain an unbounded number
of function secret keys and then adaptively a single challenge ciphertext. The size of the ciphertext only
depends on the maximal pebble complexity of each of the functions but not on the number of functions
or their circuit size.