CryptoDay at CUNY

June 27, 2014 (Friday) at City College (CUNY) on 138th Street and Convent Avenue. Shepard Hall, Room 107.

Program

10:00 – 10:30.	Introduction/Coffee
10:30 – 11:20.	David Cash, Rutgers The Locality of Searchable Encryption.
11:30 – 12:20.	Allison Lewko, Columbia Witness encryption and indistinguishability obfuscation from the multilinear subgroup elimination assumption.
12:30 – 2:30.	Lunch (not provided)
2:30 – 3:20.	Mark Zhandry, Stanford How to Avoid Obfuscation Using Witness PRFs.
3:30 – 4:20.	Pratyay Mukherjee, Aarhus University Efficient Non-Malleable Codes and Key-Derivation for Poly-Size Tampering Circuits.

Getting Here

Address: City College (CUNY) on 138th Street and Convent Avenue. Shepard Hall, Room 107.
[Directions]  [Google map] [Campus map]

Organizers

Tal Rabin (IBM) and Sanjam Garg (IBM)
with the help and support of Rosario Gennaro.

Abstracts

•  The Locality of Searchable Encryption
  David Cash (Rutgers)
  Searchable encryption allows a data owner to encrypt an index in a way that allows for searching on her behalf by an untrusted server that cannot decrypt the data. The author’s recent work (joint with a team at IBM Research) on constructing searchable encryption revealed that, in contrast to most cryptographic computation, the primary performance bottleneck of encrypted search came from poor external memory (disk) utilization and not in, say, number-theoretic processing. This was due to a lack of “spatiallocality” in all known constructions: While performing an encrypted search, the server must read a random-looking sequence of positions on the disk. This non-locality dramatically reduced throughput compared to a plaintext search, which can arrange to read only a few blocks from the disk.Motivated by our difficulties, this work initiates the study of the relationship between external memory utilization and security. While the area of external memory algorithms is well-developed and widely used for deployed systems, we are unaware of any prior connection between the area and security.Our results are primarily negative: We will show that, in an asymptotic sense, the poor external memory utilization of our system is an unavoidable property of any searchable encryption construction. In more detail, we show that any secure searchable encryption must read memory in a non-local way or suffer some other impractical drawback such as hugely enlarging the index during encryption. On the positive side we give a theoretical construction that provides a trade-off between locality and index size not previously achieved.Joint work with Stefano Tessaro.

• Witness encryption and indistinguishability obfuscation from the multilinear subgroup elimination assumption
  Allison Lewko (Columbia)
  We present constructions of witness encryption and indistinguishability obfuscation along with security reductions to the multilinear subgroup elimination assumption. This assumption is a natural multilinear extension of the subgroup decision assumptions used in bilinear groups.Based on joint works with Gentry and Waters and with Gentry, Sahai and Waters.

• How to Avoid Obfuscation Using Witness PRFs
  Mark Zhandry (Stanford)
  Recently, program obfuscation has proven to be an extremely powerful tool and has been used to construct a variety of cryptographic primitives with amazing properties. However, current candidate obfuscators are far from practical and rely on unnatural hardness assumptions about multilinear maps. In this work, we bring several applications of obfuscation closer to practice by showing that a weaker primitive called witness pseudorandom functions (witness PRFs) suffices. Applications include multiparty key exchange without trusted setup, polynomially-many hardcore bits for any one-way function, and more. We then show how to instantiate witness PRFs from multilinear maps. Our witness PRFs are simpler and more efficient than current obfuscation candidates, and involve very natural hardness assumptions about the underlying maps.

• Efficient Non-Malleable Codes and Key-Derivation for Poly-Size Tampering Circuits.
  Pratyay Mukherjee (Aarhus University)
  Non-malleable codes, defined by Dziembowski, Pietrzak and
  Wichs (ICS ’10), provide roughly the following guarantee: if a
  codeword c encoding some message x is tampered to c’ = f(c) such that
  c’ is different from c, then the tampered message x’ contained in c’
  reveals no information about x. Non-malleable codes have applications
  to immunizing cryptosystems against tampering attacks and related-key
  attacks.One cannot have an efficient non-malleable code that protects against
  all efficient tampering functions f as there exists a function which
  can decode the codeword, maul the message and re-encode. However, in
  this work we show “the next best thing”: for any fixed polynomial
  bound s, there is an efficient non-malleable code that protects
  against all tampering functions f computable by a circuit of size s.
  More generally, for any family of tampering functions F of size |F| <
  2^s, there is an efficient non-malleable code that protects against
  all f belonging to F. The rate of our codes, defined as the ratio of
  message to codeword size, approaches 1. Our results are
  information-theoretic and our main proof technique relies on a careful
  probabilistic method argument using limited independence. As a result,
  we get an efficiently samplable family of efficient codes, such that a
  random member of the family is non-malleable with overwhelming
  probability. Alternatively, we can view the result as providing an
  efficient non-malleable code in the “common reference string” (CRS)
  model.Moreover, we also introduce a new notion of non-malleable key
  derivation, which uses randomness x to derive a secret key y = h(x) in
  such a way that, even if x is tampered to a different value x’ = f(x),
  the derived key y’ = h(x’) does not reveal any information about y.
  Our results for non-malleable key derivation are analogous to those
  for non-malleable codes.As a useful tool in our analysis, we rely on the notion of
  “leakage-resilient storage” of Davi, Dziembowski and Venturi (SCN
  ’10) and, as a result of independent interest, we also significantly
  improve on the parameters of such schemes.This is a joint work with Sebastian Faust, Daniele Venturi and Daniel Wichs

Advertisement