# Publications

__Obfuscation__Order-Revealing Encryption Quantum Traitor Tracing

[MZ18] |
New Multilinear Maps from CLT13 with Provable Security Against Zeroizing Attacks
[PDF] [ePrint] We devise the first weak multilinear map model for CLT13 multilinear maps (Coron et al., CRYPTO 2013) that captures all known classical polynomial-time attacks on the maps.
We then show important applications of our model. First, we show that in our model, several existing obfuscation and order-revealing encryption schemes, when instantiated with
CLT13 maps, are secure against known attacks under a mild algebraic complexity assumption used in prior work. These are schemes that are actually being implemented for
experimentation. However, until our work, they had no rigorous justification for security. @inproceedings{MZ18, |
||

[BGMZ18] |
Preventing Zeroizing Attacks on GGH15
[PDF] [ePrint] The GGH15 multilinear maps have served as the foundation for a number of cutting-edge cryptographic proposals. Unfortunately, many schemes built on GGH15 have been explicitly
broken by so-called "zeroizing attacks," which exploit leakage from honest zero-test queries. The precise settings in which zeroizing attacks are possible have remained unclear.
Most notably, none of the current indistinguishability obfuscation (iO) candidates from GGH15 have any formal security guarantees against zeroizing attacks. @inproceedings{BGMZ18, |
||

[BLMZ18] |
New Techniques for Obfuscating Conjunctions
A conjunction is a function $f(x_1,\dots,x_n) = \bigwedge_{i \in S} l_i$ where $S \subseteq [n]$ and each $l_i$ is $x_i$ or $\neg x_i$.
Bishop et al. (CRYPTO 2018) recently proposed obfuscating conjunctions by embedding them in the error positions of a noisy Reed-Solomon
codeword and placing the codeword in a group exponent. They prove distributional virtual black box (VBB) security in the generic group
model for random conjunctions where $|S| \geq 0.226n$. While conjunction obfuscation is known from LWE, these constructions rely on
substantial technical machinery. @misc{BLMZ18, |
||

[LZ17] |
Decomposable Obfuscation: A Framework for Building Applications of Obfuscation From Polynomial Hardness
[PDF] [ePrint] There is some evidence that indistinguishability obfuscation (iO) requires either exponentially many assumptions or (sub)exponentially hard assumptions, and indeed, all
known ways of building obfuscation suffer one of these two limitations. As such, any application built from iO suffers from these limitations as well. However, for most
applications, such limitations do not appear to be inherent to the application, just the approach using iO. Indeed, several recent works have shown how to base applications
of iO instead on functional encryption (FE), which can in turn be based on the polynomial hardness of just a few assumptions. However, these constructions are quite
complicated and recycle a lot of similar techniques. @inproceedings{LZ17, |
||

[Zha17] |
Quantum Lightning Never Strikes the Same State Twice
Public key quantum money can be seen as a version of the quantum no-cloning theorem that holds even when the quantum states can be verified by the adversary. In this work,
investigate @misc{Zha17, |
||

[GPSZ17] |
Breaking the Sub-Exponential Barrier in Obfustopia
[PDF] [ePrint] Indistinguishability obfuscation (iO) has emerged as a surprisingly powerful notion. Almost all known cryptographic primitives can be constructed from general purpose iO and
other minimalistic assumptions such as one-way functions. The primary challenge in this direction of research is to develop novel techniques for using iO since iO by itself
offers virtually no protection to secret information in the underlying programs. When dealing with complex situations, often these techniques have to consider an exponential
number of hybrids (usually one per input) in the security proof. This results in a sub-exponential loss in the security reduction. Unfortunately, this scenario is becoming more
and more common and appears to be a fundamental barrier to current techniques. @inproceedings{GPSZ17, |
||

[MZ17] |
Encryptor Combiners: A Unified Approach to Multiparty NIKE, (H)IBE, and Broadcast Encryption
We define the concept of an encryptor combiner. Roughly, such a combiner takes as input n public keys for a public key encryption scheme, and produces a new combined
public key. Anyone knowing a secret key for one of the input public keys can learn the secret key for the combined public key, but an outsider who just knows the input
public keys (who can therefore compute the combined public key for himself) cannot decrypt ciphertexts from the combined public key. We actually think of public keys
more generally as encryption procedures, which can correspond to, say, encrypting to a particular identity under an IBE scheme or encrypting to a set of attributes
under an ABE scheme. @misc{MZ17, |
||

[HJK^{+}16] |
How to Generate and use Universal Samplers
[PDF] [ePrint] The random oracle is an idealization that allows to model a hash function as an oracle that will output a uniformly random
string given an input. We introduce the notion of @inproceedings{HJKSWZ16, |
||

[GMM^{+}16] |
Secure Obfuscation in a Weak Multilinear Map Model
[PDF] [ePrint] All known candidate indistinguishibility obfuscation (iO) schemes rely on candidate multilinear maps. Until recently, the strongest proofs of security
available for iO candidates were in a generic model that only allows "honest" use of the multilinear map. Most notably, in this model the zero-test procedure
only reveals whether an encoded element is 0, and nothing more. @inproceedings{GMMSSZ16, Merged version of [BMS16] and [MSZ16] |
||

[KMUZ16] |
Strong Hardness of Privacy from Weak Traitor Tracing
[PDF] [ePrint] Despite much study, the computational complexity of differential privacy remains poorly understood. In this paper we consider the computational complexity of
accurately answering a family Q of @inproceedings{KMUZ16, |
||

[Zha16b] |
The Magic of ELFs
(Best Young Researcher Award)[PDF] [ePrint] [slides] We introduce the notion of an @inproceedings{Zha16b, |
||

[MSZ16b] |
Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13
[PDF] [ePrint] In this work, we put forward a new class of polynomial-time attacks on the original multilinear maps of Garg, Gentry, and Halevi (2013). Previous polynomial-time attacks
on GGH13 were "zeroizing" attacks that generally required the availability of low-level encodings of zero. Most significantly, such zeroizing attacks were not applicable
to candidate indistinguishability obfuscation (iO) schemes. iO has been the subject of intense study. @inproceedings{MSZ16b, |
||

[MSZ16a] |
Secure Obfuscation in a Weak Multilinear Map Model: A Simple Construction Secure Against All Known Attacks
All known candidate indistinguishibility obfuscation (iO) schemes rely on candidate multilinear maps. Until recently, the strongest proofs of security available
for iO candidates were in a generic model that only allows "honest" use of the multilinear map. Most notably, in this model the zero-test procedure only reveals
whether an encoded element is 0, and nothing more. @misc{MSZ16a, |
||

[BMSZ16] |
Post-Zeroizing Obfuscation: New Mathematical Tools, and the Case of Evasive Circuits
[PDF] [ePrint] [slides] Recent devastating attacks by Cheon et al.~[Eurocrypt`15] and others have highlighted significant gaps in our intuition about security in candidate
multilinear map schemes, and in candidate obfuscators that use them. The new attacks, and some that were previously known, are typically called
"zeroizing" attacks because they all crucially rely on the ability of the adversary to create encodings of 0. @inproceedings{BMSZ16, |
||

[NWZ16] |
Anonymous Traitor Tracing: How to Embed Arbitrary Information in a Key
[PDF] [ePrint] In a traitor tracing scheme, each user is given a different decryption key. A content distributor can encrypt digital content using a public encryption key
and each user in the system can decrypt it using her decryption key. Even if a coalition of users combines their decryption keys and constructs some "pirate decoder"
that is capable of decrypting the content, there is a public tracing algorithm that is guaranteed to recover the identity of at least one of the users in the coalition
given black-box access to such decoder. @inproceedings{NWZ16, |
||

[KZ16] |
Cutting-Edge Cryptography Through the Lens of Secret Sharing
[PDF] [ePrint] Secret sharing is a mechanism by which a trusted dealer holding a secret "splits" a secret into many "shares" and distributes the shares to a collection
of parties. Associated with the sharing is a monotone access structure, that specifies which parties are "qualified" and which are not: any qualified subset
of parties can (efficiently) reconstruct the secret, but no unqualified subset can learn anything about the secret. In the most general form of secret sharing,
the access structure can be any monotone NP language. @inproceedings{KZ16, |
||

[Zha16a] |
How to Avoid Obfuscation Using Witness PRFs
[PDF] [ePrint] We propose a new cryptographic primitive called @inproceedings{Zha16a, |
||

[BLR^{+}15] |
Semantically Secure Order-Revealing Encryption: Multi-Input Functional Encryption Without Obfuscation
[PDF] [ePrint] Deciding "greater-than" relations among data items just given their encryptions is at the heart of search algorithms on encrypted
data, most notably, non-interactive binary search on encrypted data. Order-preserving encryption provides one solution, but provably
provides only limited security guarantees. Two-input functional encryption is another approach, but requires the full power of
obfuscation machinery and is currently not implementable. @inproceedings{BLRSZZ15, |
||

[SZ14] |
Obfuscating Low-Rank Matrix Branching Programs
In this work, we seek to extend the capabilities of the "core obfuscator" from the work of Garg, Gentry, Halevi, Raykova, Sahai,
and Waters (FOCS 2013), and all subsequent works constructing general-purpose obfuscators. This core obfuscator builds upon
approximate multilinear maps, and applies to matrix branching programs. All previous works, however, limited the applicability of
such core obfuscators to matrix branching programs where each matrix was of full rank. As we illustrate by example, this
limitation is quite problematic, and intuitively limits the core obfuscator to obfuscating matrix branching programs that cannot
"forget." At a technical level, this limitation arises in previous work because all previous work relies on Kilian`s statistical
simulation theorem, which is false when applied to matrices not of full rank. @misc{SZ14, Subsumed by [BMSZ16] |
||

[Zha14] |
Adaptively Secure Broadcast Encryption with Small System Parameters
We build the first public-key broadcast encryption systems that simultaneously achieve adaptive security against arbitrary number of colluders, have small system parameters, and have security proofs that do not rely on knowledge assumptions or complexity leveraging. Our schemes are built from either composite order multilinear maps or obfuscation and enjoy a ciphertext overhead, private key size, and public key size that are all poly-logarithmic in the total number of users. Previous broadcast schemes with similar parameters are either proven secure in a weaker static model, or rely on non-falsifiable knowledge assumptions. @misc{Zha14, |
||

[BZ14] |
Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation
[PDF] [ePrint] [slides] In this work, we show how to use indistinguishability obfuscation (iO) to build multiparty key exchange,
efficient broadcast encryption, and efficient traitor tracing. Our schemes enjoy several interesting
properties that have not been achievable before: @inproceedings{BZ14, |
||

[ABG^{+}13] |
Differing-Inputs Obfuscation and Applications
In this paper, we study of the notion of differing-input obfuscation, introduced by Barak et al. (CRYPTO 2001,
JACM 2012). For any two circuits @misc{ABGSZ13, |