
List of accepted papers
(In order of appearance)
Track C: Security and Foundations of Cryptography
 Private Multiparty Sampling and Approximation of Vector Combinations
 Yuval Ishai, Tal Malkin, Martin J. Strauss and Rebecca N. Wright

We consider the problem of private efficient data mining of
verticallypartitioned databases. Each of several parties holds a
column of a data matrix (a vector) and the parties want to investigate
the componentwise combination of their vectors. The parties want to
minimize communication and local computation while guaranteeing
privacy in the sense that no party learns more than necessary.
Sublinearcommunication private protocols have been primarily been
studied only in the twoparty case. We give efficient multiparty
protocols for sampling a row of the data matrix and for computing
arbitrary functions of a row, where the row index is additively shared
among two or more parties. We also give protocols for approximating
the componentwise sum, minimum, or maximum of the columns in which the
communication and the number of publickey operations are at most
polynomial in the size of the small approximation and polylogarithmic
in the number of rows.
 ConstantRound Private Database Queries
 Nenad Dedic and Payman Mohassel

We consider several private database query problems. The starting
point of this work is the element rank problem: the server holds a
database of n integers, and the user an integer q; the
user wishes to find out how many database records are smaller than
q, without revealing q; nothing else about the database
should be disclosed. We show a noninteractive communicationefficient
solution to this problem. We then use it to solve more complex private
database queries: range queries, range queries in plane and
higherdimensional generalizations of element rank. We also show an
improved solution to the kth ranked element problem,
and a solution to private keyword search using weaker assumptions
than in previous results. All our solutions assume semihonest adversarial behaviour.
 Deterministic HistoryIndependent Strategies for Storing Information on WriteOnce Memories
 Tal Moran, Moni Naor and Gil Segev

Motivated by the challenging task of designing "secure" vote
storage mechanisms, we deal with information storage mechanisms that
operate in extremely hostile environments. In such environments, the
majority of existing techniques for information storage and for security
are susceptible to powerful adversarial attacks. In this setting, we
propose a mechanism for storing a set of at most K elements from
a large universe of size N on writeonce memories in a manner
that does not reveal the insertion order of the elements. Whereas
previously known constructions were either inefficient (required
Θ(K^{2}) memory), randomized, or employed cryptographic
techniques which are unlikely to be available in hostile environments,
we eliminate each of these undesirable properties. The total amount of
memory used by the mechanism is linear in the number of stored elements
and polylogarithmic in the size of the universe of elements.
In addition, we consider one of the classical distributed computing
problems: Conflict resolution in multipleaccess channels. By
establishing a tight connection with the basic building block of our
mechanism, we construct the first deterministic and nonadaptive
conflict resolution algorithm whose running time is optimal up to
polylogarithmic factors.
 Trading Static for Adaptive Security in Universally Composable ZeroKnowledge
 Aggelos Kiayias and HongSheng Zhou

Adaptive security, while more realistic as an adversarial model,
is typically much harder to achieve compared to static security in
cryptographic protocol design. Universal composition (UC)
provides a very attractive framework for the modular design of
cryptographic protocols that captures both static and adaptive
security formulations. In the UC framework, one can design
protocols in hybrid worlds that allow access to idealized
functionalities and then apply the universal composition theorem
to obtain more concrete protocol instances. The zeroknowledge
(ZK) ideal functionality is one of the most useful
subprotocols in modular cryptographic design. Given an adaptively
secure protocol in the ideal ZKhybridworld do we always need an
adaptively secure realization of the ZK functionality in order to
preserve adaptive security under composition? In this work,
perhaps surprisingly, we find that this is not so and in fact
there are useful protocol instances that we can "trade static
security for adaptive security."
We investigate the above setting, by introducing a weakened ZK
ideal functionality, called the ideal leakingzeroknowledge
functionality (LZK) that leaks some information about the witness
to the adversary in a certain prescribed way. We show that while
LZK is interchangeable to ZK against static adversaries, ZK is
more stringent when adaptive adversaries are considered. We then
proceed to characterize a class of protocols in the
hybridZKworld that can be "transported" to the
LZKhybridworld without forfeiting their security against
adaptive adversaries. Our results demonstrate that in such
settings a static protocol realization of ZK is sufficient for
ensuring adaptive security for the parent hybrid protocol
something that enables simplified and substantially more
efficient UC realizations of such protocols.
 A Characterization of NonInteractive InstanceDependent CommitmentSchemes (NIC)
 Bruce Kapron, Lior Malka and Venkatesh Srinivasan

We provide a new characterization of certain
zeroknowledge protocols as noninteractive instancedependent
commitmentschemes (NIC). To obtain this result we consider the
notion of Vbit protocols, which are very common, and found
many applications in zeroknowledge. Our characterization result
states that a protocol has a Vbit zeroknowledge protocol if
and only if it has a NIC. The NIC inherits its hiding property
from the zeroknowledge property of the protocol, and vice versa.
Our characterization result yields a framework that strengthens and
simplifies many zeroknowledge protocols in various settings. For
example, applying this framework to the result of Micciancio et
al. (who showed that some problems, including
GRAPHNONISOMORPHISM
and QUADRATICRESIDUOUSITY,
unconditionally have a concurrent zeroknowledge
proof) we easily get that arbitrary, monotone boolean formulae over
a large class of problems (which contains, e.g., the complement of
any random selfreducible problem) unconditionally have a
concurrent zeroknowledge proof.
 Private Locally Decodable Codes
 Rafail Ostrovsky, Omkant Pandey and Amit Sahai

We consider the problem of constructing efficient locally decodable
codes in the presence of a computationally bounded adversary.
Assuming the existence of oneway functions, we construct
efficient locally decodable codes with positive information rate
and low (almost optimal) query complexity which can correctly
decode any given bit of the message from constant channel error rate
ρ. This compares favorably to our state of knowledge
locallydecodable codes without cryptographic assumptions. For all
our constructions, the probability for any polynomialtime
adversary, that the decoding algorithm incorrectly decodes any bit
of the message is negligible in the security parameter.
 Hash Functions in the DedicatedKey Setting: Design Choices and MPP Transforms
 Mihir Bellare and Thomas Ristenpart

In the dedicatedkey setting, one uses a compression function
f:{0,1}^{k}×{0,1}^{n+d}→{0,1}^{n}
to build a family of hash functions
H^{f}:K×M→{0,1}^{n} indexed
by a key space K. This is different from the more traditional design
approach used to build hash functions such as MD5 or SHA1, in which
compression functions and hash functions do not have dedicated key
inputs. We explore the benefits and drawbacks of building hash
functions in the dedicatedkey setting (as compared to the more
traditional approach), highlighting several unique features of the
former. Should one choose to build hash functions in the dedicatedkey
setting, we suggest utilizing multipropertypreserving (MPP) domain
extension transforms. We analyze seven existing dedicatedkey
transforms with regard to the MPP goal and propose two simple new MPP
transforms.
 Unrestricted Aggregate Signatures
 Mihir Bellare, Chanathip Namprempre and Gregory Neven

Secure use of the BGLS aggregate signature
schemes is restricted to the aggregation of distinct messages (for
the basic scheme) or persigner distinct messages (for the
enhanced, prependpublickey version of the scheme). We argue that
these restrictions preclude interesting applications, make usage
of the schemes errorprone and are generally undesirable in
practice. Via a new analysis and proof, we show how the
restrictions can be lifted, yielding the first truly unrestricted
aggregate signature scheme. Via another new analysis and proof, we show
that the distinct signer restriction on the
sequential aggregate signature schemes can also
be dropped, yielding an unrestricted sequential aggregate
signature scheme.
 Ring Signatures of SubLinear Size without Random Oracles
 Nishanth Chandran, Jens Groth and Amit Sahai

Ring signatures, introduced by Rivest, Shamir and Tauman, enable a
user to sign a message anonymously on behalf of a "ring". A ring is a
group of users, which includes the signer. We propose a ring signature
scheme that has size O(√N) where N is the number of
users in the ring. An additional feature of our scheme is that it has
perfect anonymity.
Our ring signature like most other schemes uses the common reference
string model. We offer a variation of our scheme, where the signer is
guaranteed anonymity even if the common reference string is maliciously
generated.
 Offline/OnlineMixing
 Ben Adida and Douglas Wikström

We introduce an offline precomputation technique for mixnets that
drastically reduces the amount of online computation needed. Our
method can be based on any additively homomorphic cryptosystem and is
applicable when the number of senders and the maximal bitsize of
messages are relatively small.
 Fully Collusion Resistant BlackBox Traitor Revocable Broadcast Encryption with Short Private Keys
 Jun Furukawa and Nuttapong Attrapadung

Broadcast encryption schemes enable senders to efficiently broadcast
ciphertexts to a large set of receivers in a way that only nonrevoked
receivers can decrypt them.
Blackbox traitor revocable broadcast encryption schemes are broadcast
encryption schemes that enable a tracer, who is given a pirate
decoder, to identify traitors by blackbox accessing the given pirated
decoder and to revoke traitors so identified.
In this paper, we propose a fully collusion resistant blackbox traitor
revocable broadcast encryption scheme in which the size of each
private key is constant, the size of the public key is proportional to
the number of receivers, and the sizes of ciphertexts are sublinear
with respect to the number of receivers.
The encryption procedure in our scheme requires only a public key. The
tracing procedure in it requires only a public key and blackbox access
to a resettable pirate decoder.
The security of our scheme is proved in the generic bilinear group
model if the subgroup decision assumption holds.

