Monthly Archives: September 2015

Oct 16, 2015  (Friday) at Columbia

Costas Engineering Commons, in the CEPSR Building Room 750

Located at 530 West 120th Street, New York, NY


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 Zero-Knowledge 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 Sub-Linear Time


Columbia University, CEPSR building Room 750

Directions to CEPSR (Shapiro) building are available here (on the bottom):
Here are two options to enter the building:
You enter from campus (that’s 4th floor) and go up to 7th floor and then look for the appropriate room.

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).

Tal Rabin (IBM)
with the help and support of Tal Malkin.


  • 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 long-standing 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 one-way 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 Zero-Knowledge Arguments and Applications to the Malicious Setting/ Fabrice Ben Hamouda (ENS) We introduce implicit zero-knowledge arguments (iZK) and simulation-sound variants thereof (SSiZK); these are lightweight alternatives to zero-knowledge arguments for enforcing semi-honest behavior. Our main technical contribution is a construction of efficient two-flow 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 round-efficiency of existing protocols for securely computing inner product under the DDH assumption. This new protocol in turn provides privacy-preserving 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 Format-Preserving Encryption/Mor Weiss (Technion) Format Preserving Encryption (FPE) schemes encrypt a plaintext into a ciphertext while preserving its format (e.g., a valid social-security number is encrypted into a valid social-security 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 set-up. Security is guaranteed by preserving only format-specific properties during encryption, while hiding all message-specific 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 user-defined bound on the maximal format size, thus obtaining a flexible security-efficiency 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 Sub-Linear Time / Ron Rothblum (MIT) An interactive  proof of proximity (IPP) is an interactive protocol in which a prover tries to convince a sublinear-time verifier that x \in L. Since the verifier runs in sublinear-time, 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 sub-exponentially secure FHE scheme, we construct a one-round 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 et-al, and in our arguments of proximity, are close to optimal.
    Based on joint work with Yael Kalai.