Oct 16, 2015 (Friday) at Columbia
Costas Engineering Commons, in the CEPSR Building Room 750
Located at 530 West 120th Street, New York, NY
Program
9:30 – 10:00.  Introduction/Coffee 
10:00 – 10:50. 
Alessandra Scafuro, Boston University
New Realizations of Adaptively Secure Gabled Circuits

11:00 – 11:50. 
Fabrice Ben Hamouda, ENS
Implicit ZeroKnowledge Arguments and Applications to the Malicious Setting

12:00 – 2:00.  Lunch (not provided) 
2:00 – 2:50. 
Mor Weiss, Technion
Practical Solutions for Format Preserving Encryption

3:00 – 3:50. 
Ron Rothblum, MIT
Proofs and Arguments of Proximity: Verifying Computations in SubLinear Time

Venue
Columbia University, CEPSR building Room 750
There is also an entrance to the building from 120th street between Broadway and Amsterdam but it’s more complicated (e.g., it may require an ID to get in; there you go first in one elevator to 4th floor and then switch to the other elevator to 7th).
Organizers
Tal Rabin (IBM)
with the help and support of Tal Malkin.
Abstracts
 New Realizations of Adaptively Secure Gabled Circuits/ Alessandra Scafuro (Boston University) A garbled circuit can be evaluated on a single garbled input without revealing any information beyond the output. The size of the garbled input and the time that it takes to create it should be much smaller than the size of the circuit, and ideally only proportional to the input size. Yao’s garbled circuit construction achieves this with static security when the input is chosen by the adversary prior to the seeing the garbled circuit. It had remained a longstanding open problem to achieve adaptive security where the adversary can choose the input adaptively after seeing the garbled circuit.
In this work we provide a framework that allows us to lightly modify Yao’s garbling scheme and prove adaptive security under various parameter regimes. In particular, we can get a scheme based on oneway functions where the size of the garbled input is only proportional to the width of the circuit (which corresponds to the space complexity of the computation) rather that the entire size of the circuit. More broadly, we develop a connection between constructing adaptively secure schemes in our framework and a certain type of pebble complexity.Joint work with Brett Hemenway, Zahra Jafargholi, Rafail Ostrovsky, Daniel Wichs.
 Implicit ZeroKnowledge Arguments and Applications to the Malicious Setting/ Fabrice Ben Hamouda (ENS) We introduce implicit zeroknowledge arguments (iZK) and simulationsound variants thereof (SSiZK); these are lightweight alternatives to zeroknowledge arguments for enforcing semihonest behavior. Our main technical contribution is a construction of efficient twoflow iZK and SSiZK protocols for a large class of languages under the (plain) DDH assumption in cyclic groups in the common reference string model. As an application of iZK, we improve upon the roundefficiency of existing protocols for securely computing inner product under the DDH assumption. This new protocol in turn provides privacypreserving biometric authentication with lower latency.Joint work with Geoffroy Couteau, David Pointcheval, and Hoeteck Wee.
Published at Crypto 2015. Eprint 2015/246.
 Practical Solutions for FormatPreserving Encryption/Mor Weiss (Technion) Format Preserving Encryption (FPE) schemes encrypt a plaintext into a ciphertext while preserving its format (e.g., a valid socialsecurity number is encrypted into a valid socialsecurity number), thus allowing encrypted data to be stored and used in the same manner as unencrypted data. Motivated by the ever increasing use of cloud computing and memory delegation, which require preserving both the privacy and the format of the plaintext, several FPE schemes for general formats have been previously suggested. However, previous solutions were both insecure and inefficient in practice.In this talk I will present an efficient FPE scheme with optimal security which includes, in addition to encryption and decryption algorithms, also a method of representing general (complex) formats. All our algorithms are efficient, and do not require an expensive setup. Security is guaranteed by preserving only formatspecific properties during encryption, while hiding all messagespecific properties.Motivated by experimental results which show that in many cases large formats domains cannot be encrypted efficiently, we extend our scheme to support large formats. The extended scheme employs a userdefined bound on the maximal format size, thus obtaining a flexible securityefficiency tradeoff and guaranteeing the “best possible” security (under the size limitation).
Joint work with: Boris Rosenberg and Mohammad Barham

Proofs and Arguments of Proximity: Verifying Computations in SubLinear Time / Ron Rothblum (MIT) An interactive proof of proximity (IPP) is an interactive protocol in which a prover tries to convince a sublineartime verifier that x \in L. Since the verifier runs in sublineartime, following the property testing literature, the verifier is only required to reject inputs that are far from L. In a recent work, (Guy) Rothblum, Vadhan and Wigderson (STOC, 2013) constructed an IPP for every language computable by a low depth circuit.
In this work we consider the computational analogue, where soundness is required to hold only against a computationally bounded cheating prover. We call such protocols interactive arguments of proximity.Assuming the existence of a subexponentially secure FHE scheme, we construct a oneround argument of proximity for every language computable in time t, where the running time of the verifier is o(n) + polylog(t) and the running time of the prover is poly(t).As our second result, assuming sufficiently hard cryptographic PRGs, we give a lower bound, showing that the parameters obtained both in the IPPs of Rothblum etal, and in our arguments of proximity, are close to optimal.Based on joint work with Yael Kalai.