[Zha16] 
How to Avoid Obfuscation Using Witness PRFs
TCC 2016
[PDF]
[ePrint]
We propose a new cryptographic primitive called witness pseudorandom functions (witness PRFs). Witness PRFs are related to
witness encryption, but appear strictly stronger: we show that witness PRFs can be used for applications such as multiparty key
exchange without trsuted setup, polynomiallymany hardcore bits for any oneway function, and several others that were previously
only possible using obfuscation. Current candidate obfuscators are far from practical and typically rely on unnatural hardness
assumptions about multilinear maps. We give a construction of witness PRFs from multilinear maps that is simpler and much more
efficient than current obfuscation candidates, thus bringing several applications of obfuscation closer to practice. Our construction
relies on new but very natural hardness assumptions about the underlying maps that appear to be resistant to a recent line of attacks.
@inproceedings{Zha16, author = {Mark Zhandry}, title = {How to Avoid Obfuscation Using Witness PRFs}, booktitle = {Proceedings of TCC 2016}, misc = {Full version available at \url{http://eprint.iacr.org/2014/301}}, year = {2016} }

[KZ16] 
CuttingEdge Cryptography Through the Lens of Secret Sharing
TCC 2016
[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.
In this work, we consider two very natural extensions of secret sharing. In the first, which we
call distributed secret sharing, there is no trusted dealer at all, and instead the role of the dealer is distributed amongst the parties themselves. Distributed
secret sharing can be thought of as combining the features of multiparty noninteractive key exchange and standard secret sharing, and may be useful in settings
where the secret is so sensitive that no one individual dealer can be trusted with the secret. Our second notion is called functional secret sharing, which incorporates
some of the features of functional encryption into secret sharing by providing more finegrained access to the secret. Qualified subsets of parties do not learn the
secret, but instead learn some function applied to the secret, with each set of parties potentially learning a different function.
Our main result is that both
of the extensions above are equivalent to several recent cuttingedge primitives. In particular, generalpurpose distributed secret sharing is equivalent to witness
PRFs, and generalpurpose functional secret sharing is equivalent to indistinguishability obfuscation. Thus, our work shows that it is possible to view some of the
recent developments in cryptography through a secret sharing lens, yielding new insights about both these cuttingedge primitives and secret sharing.
@inproceedings{KZ16, author = {Ilan Komargodski and Mark Zhandry}, title = {CuttingEdge Cryptography Through the Lens of Secret Sharing}, booktitle = {Proceedings of TCC 2016}, misc = {Full version available at \url{http://eprint.iacr.org/2015/735}}, year = {2016} }

[NWZ15] 
Anonymous Traitor Tracing: How to Embed Arbitrary Information in a Key
[PDF]
[ePrint]

[BLR^{+}15] 
Semantically Secure OrderRevealing Encryption: MultiInput Functional Encryption Without Obfuscation
EuroCrypt 2015
[PDF]
[ePrint]

[BMSZ15] 
PostZeroizing Obfuscation: The case of Evasive Circuits
[PDF]
[ePrint]
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.
In this work, we initiate the study of postzeroizing obfuscation, and we present a construction for the special case of evasive functions. We
show that our obfuscator survives all known attacks on the underlying multilinear maps, by proving that no encodings of 0 can be created by
a genericmodel adversary. Previous obfuscators (for both evasive and general functions) were either analyzed in a lessconservative "prezeroizing"
model that does not capture recent attacks, or were proved secure relative to assumptions that are now known to be false.
To prove security, we introduce a new technique for analyzing polynomials over multilinear map encodings. This technique shows that the types of
encodings an adversary can create are much more restricted than was previously known, and is a crucial step toward achieving postzeroizing security.
We also believe the technique is of independent interest, as it yields efficiency improvements for existing schemes.
@misc{BMSZ15, author = {Saikrishna Badrinarayanan and Eric Miles and Amit Sahai and Mark Zhandry}, title = {PostZeroizing Obfuscation: The case of Evasive Circuits}, misc = {Full version available at \url{http://eprint.iacr.org/2015/167}}, year = {2015} }

[SZ14] 
Obfuscating LowRank Matrix Branching Programs
[PDF]
[ePrint]
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 generalpurpose 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.
In our work, we build the first core
obfuscator that can apply to matrix branching programs where matrices can be of arbitrary rank. We prove security of our
obfuscator in the generic multilinear model, demonstrating a new proof technique that bypasses Kilian`s statistical simulation
theorem. Furthermore, our obfuscator achieves two other notable advances over previous work:
• Our construction allows for nonsquare matrices of arbitrary dimensions. We also show that this flexibility yields
concrete efficiency gains.
• Our construction allows for a single obfuscation to yield multiple bits of output. All previous work yielded only one bit
of output.
Our work leads to significant efficiency gains for obfuscation. Furthermore, our work can be applied to achieve efficiency gains
even in applications not directly using obfuscation.
@misc{SZ14, author = {Amit Sahai and Mark Zhandry}, title = {Obfuscating LowRank Matrix Branching Programs}, misc = {Full version available at \url{http://eprint.iacr.org/2014/773}}, year = {2014} }
Subsumed by [BMSZ15]

[Zha14] 
Adaptively Secure Broadcast Encryption with Small System Parameters
[PDF]
[ePrint]
We build the first publickey 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 polylogarithmic in the total number of users. Previous broadcast schemes with
similar parameters are either proven secure in a weaker static model, or rely on nonfalsifiable knowledge assumptions.
@misc{Zha14, author = {Mark Zhandry}, title = {Adaptively Secure Broadcast Encryption with Small System Parameters}, misc = {Full version available at \url{http://eprint.iacr.org/2014/757}}, year = {2014} }

[BZ14] 
Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation
CRYPTO 2014
[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:
• Our multiparty noninteractive key exchange protocol does not require a trusted setup. Moreover,
the size of the published value from each user is independent of the total number of users.
• Our broadcast encryption schemes support distributed setup, where users choose their own
secret keys rather than be given secret keys by a trusted entity. The broadcast ciphertext size is
independent of the number of users.
• Our traitor tracing system is fully collusion resistant with short ciphertexts, secret keys,
and public key. Ciphertext size is logarithmic in the number of users and secret key size is independent
of the number of users. Our public key size is polylogarithmic in the number of users. The recent
functional encryption system of Garg, Gentry, Halevi, Raykova, Sahai, and Waters also leads to a traitor
tracing scheme with similar ciphertext and secret key size, but the construction in this paper is simpler
and more direct. These constructions resolve an open problem relating to differential privacy.
• Generalizing our traitor tracing system gives a private broadcast encryption scheme (where broadcast
ciphertexts reveal minimal information about the recipient set) with optimal size ciphertext.
Several of our proofs of security introduce new tools for proving security using indistinguishability obfuscation.
@inproceedings{BZ14, author = {Dan Boneh and Mark Zhandry}, title = {Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation}, booktitle = {Proceedings of CRYPTO 2014}, misc = {Full version available at \url{http://eprint.iacr.org/2013/642}}, year = {2014} }

[HJK^{+}14] 
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 universal sampler scheme as a method sampling securely from
arbitrary distributions.
We first motivate such a notion by describing several applications including generating
the trusted parameters for many schemes from just a single trusted setup. We further demonstrate the versatility of universal
sampler by showing how they give rise to applications such as identitybased encryption and multiparty key exchange.
We give a solution in the random oracle model based on indistinguishability obfuscation. At the heart of our construction and
proof is a new technique we call "delayed backdoor programming".
@misc{HJKSWZ14, author = {Dennis Hofheinz and Tibor Jager and Dakshita Khurana and Amit Sahai and Brent Waters and Mark Zhandry}, title = {How to Generate and use Universal Samplers}, misc = {Full version available at \url{http://eprint.iacr.org/2014/507}}, year = {2014} }

[ABG^{+}13] 
DifferingInputs Obfuscation and Applications
[PDF]
[ePrint]
