Cryptography Research       


 Shai Halevi photo Heqing Huang photoTal  Rabin photo

Cryptography Research - Seminars

We are very interested in interacting with the research and academic community. In fact, we run the Cryptography Research Seminar where you can tell us about your interesting new results. Here is list of upcoming and recent past seminars.

Friday October 19, 2012 11am

TITLE: Practical Yet Universally Composable Two-Server Password-Authenticated Secret Sharing
SPEAKER: Gregory Neven, IBM Zurich

ABSTRACT: Password-authenticated secret sharing (PASS) schemes, first introduced by Bagherzandi et al. at CCS 2011, allow users to distribute data among several servers so that the data can be recovered using a single human-memorizable password, but no single server (or even no collusion of servers up to a certain size) can mount an off-line dictionary attack on the password or learn anything about the data. We propose a new, universally composable (UC) security definition for the two-server case (2PASS) in the public-key setting that addresses a number of relevant limitations of the previous, non-UC definition. For example, our definition makes no prior assumptions on the distribution of passwords, preserves security when honest users mistype their passwords, and guarantees secure composition with other protocols in spite of the unavoidable non-negligible success rate of online dictionary attacks. We further present a concrete 2PASS protocol and prove that it meets our definition. Given the strong security guarantees, our protocol is surprisingly efficient: in its most efficient instantiation under the DDH assumption in the random-oracle model, it requires fewer than twenty elliptic-curve exponentiations on the user’s device. We achieve our results by careful protocol design and by exclusively focusing on the twoserver public-key setting.

Joint work with Jan Camenisch (IBM Research – Zurich) and Anna Lysyanskaya (Brown University), to appear at CCS 2012.

Thursday October 4, 2012 11am

TITLE: Publicly Verifiable Delegation of Large Polynomials and Matrix Computations
SPEAKER: Dario Fiore, NYU

ABSTRACT: Outsourced computations (where a client requests a server to perform some computation on its behalf) are becoming increasingly important due to the rise of Cloud Computing and the proliferation of mobile devices. Since cloud providers may not be trusted, a crucial problem is the verification of the integrity and correctness of such computation, possibly in a {\em public} way, i.e., the result of a computation can be verified by any third party, and requires no secret key -- akin to a digital signature on a message.

In this talk I will present new protocols for publicly verifiable secure outsourcing of {\em Evaluation of High Degree Polynomials} and {\em Matrix Multiplication}. Compared to previously proposed solutions, ours improve in efficiency and offer security in a stronger model and under standard assumptions. Perhaps more interestingly, our new solutions can handle operations over finite fields of any characteristic (starting from 2), and they can thus support also public verification of boolean formulas.

This talk is based on joint work with Rosario Gennaro that is going to appear at ACM CCS 2012, and follow-up work with Dario Catalano, Rosario Gennaro and Konstantinos Vamvourellis (

Thursday September 27, 2012, 11am

TITLE: New Proof Methods for Attribute-Based Encryption: Achieving Full Security through Selective Techniques
SPEAKER: Allison Lewko, MSR New England

ABSTRACT: We develop a new methodology for utilizing the prior techniques to prove selective security for functional encryption systems as a direct ingredient in devising proofs of full security. This deepens the relationship between the selective and full security models and provides a path for transferring the best qualities of selectively secure systems to fully secure systems. In particular, we present a Ciphertext-Policy Attribute-Based Encryption scheme that is proven fully secure while matching the efficiency of the state of the art selectively secure systems.

(Joint work with Brent Waters)

Monday September 17, 2012, 11am

TITLE: On the (Im)Possibility of Tamper-Resilient Cryptography: Using Fourier Analysis in Computer Viruses
SPEAKER: Kai-Min Chung, Cornell

ABSTRACT: We study the resilience of cryptographic primitives in the presence of efficient tampering of the secret random bits of the parties. We consider, so-called, \emph{$p$-tampering attackers} that may tamper with each bit of the random tape with probability $p$ while they have to decide about the value of tampered bits in an \emph{online} way. We present positive and negative results:

- Any CPA secure encryption scheme, bit commitment scheme, or efficient-prover zero-knowledge protocol can be ``broken'' with advantage $\Omega(p)$ by a $p$-tampering attacker. The core of this result is a new Fourier analytic technique for biasing the output of bounded value functions, which may be of independent interest (and provides an alternative, and in our eyes simpler, proof of the classic Santha-Vazirani theorem).

- Assuming the existence of one-way functions, cryptographic primitives with a ``threshold-0''-falsifiable security game (e.g., signatures, identification protocols, witness hiding protocols, etc) can be made resilient to $p$-tampering attacks for arbitrary large $p = 1/\poly(n)$ where $n$ is the security parameter.

(Joint work with Per Austrin, Mohammad Mahmoody, Rafael Pass, and Karn Seth)

Thursday March 1, 11am -- Hawthorne 3N-F28

TITLE: Vector Commitments and their Applications
SPEAKER: Dario Fiore, NYU

ABSTRACT: We introduce a new primitive that we call {\em Vector Commitment} (VC, for short). Informally, VCs allow to commit to an ordered sequence of $q$ values $(m_1, \ldots, m_q)$ (i.e., a vector) in such a way that one can later open the commitment at specific positions (e.g., prove that $m_i$ is the $i$-th committed message). For security, Vector Commitments are required to satisfy a notion that we call \emph{position binding} which states that an adversary should not be able to open a commitment to two different values at the same position. Moreover, what makes our primitive interesting is that we require VCs to be {\em concise}, i.e. the size of the commitment string and of its openings has to be independent of the vector length.

We show two realizations of VCs based on standard and well established assumptions, such as RSA, and Computational Diffie-Hellman (in bilinear groups).

Next, we turn our attention to applications and we show that Vector Commitments turn out to be useful in a variety of contexts, as they allow for compact and efficient solutions which significantly improve previous works either in terms of efficiency of the resulting solutions, or in terms of "quality" of the underlying assumption, or both. These applications include: Verifiable Databases with Efficient Updates, Updatable Zero-Knowledge Databases, and Universal Dynamic Accumulators.

This is a joint work with Dario Catalano. A version of the manuscript is available here

Thursday February 9

TITLE: More efficient NIZKs for DLIN and similar languages with Applications.
AUTHOR: Charanjit Jutla, IBM Research.

ABSTRACT: The talk will begin with a crash course on Groth-Sahai NIZKs, following which we will show how to build more efficient NIZKs for the DLIN language under its own hardness assumption. This construction is actually inspired by Waters' Dual System IBE, although the proof technique is novel.

As an application we show that this leads to a more efficient UC Commitment scheme (Fischlin, Libert, Manulis 2011).

We also show how this construction is extended to get Waters' Signature Scheme as well as (adaptive) IBEs. The novel interpretation actually gives more efficient dual-system IBE than Waters' dual-system IBE.

Thursday December 8th TITLE: Detecting Dangerous Queries: A New Approach for Chosen Ciphertext Security
SPEAKER: Brent Waters, U. of Texas at Austin.

ABSTRACT: I will present a new approach for creating chosen ciphertext secure encryption. The focal point of our work is a new abstraction that we call Detectable Chosen Ciphertext Security (DCCA). Intuitively, this notion is meant to capture systems that are not necessarily chosen ciphertext attack (CCA) secure, but where we can detect whether a certain query CT can be useful for decrypting (or distinguishing) a challenge ciphertext CT*.

We show how to build chosen ciphertext secure systems from DCCA security. We motivate our techniques by describing multiple examples of DCCA systems including creating them from 1-bit CCA secure encryption --- capturing the recent Myers-shelat result (FOCS 2009). Our work identifies DCCA as a new target for building CCA secure systems.

Joint work with Allison Lewko and Susan Hohenberger.

Thursday December 1, 2011

TITLE: Non-Interactive and Re-Usable UC String Commitments with Adaptive Security
SPEAKER: Mark Manulis, T.U. Darmstadt

ABSTRACT: This year marks the 10th anniversary of UC commitments. Previous schemes succeeded in providing a variety of useful properties, with regard to security, efficiency, and usability. A brief discussion shows that there is still much work to be done. I will present two schemes that are first provably secure constructions of universally composable (UC) commitments (in pairing-friendly groups) that simultaneously combine the key properties of being non-interactive, supporting commitments to strings (instead of bits only), and offering re-usability of the common reference string for multiple commitments. Both schemes are adaptively secure assuming reliable erasures. Security of both schemes relies on the standard Decision Linear assumption. The first scheme is based on the recent interactive and non-adaptive UC commitment scheme of Lindell (Eurocrypt 2010), for which in the pairing-based setting Groth-Sahai proofs are used to simultaneously remove interaction and obtain adaptive security. The second scheme is obtained using pairing-based trapdoor commitments to group elements, in combination with Groth-Sahai proofs and DLIN-based Cramer-Shoup encryption. This scheme can be understood as a non-interactive (pairing-based) version of interactive Camenisch-Shoup UC commitments (Crypto 2003). This talk is based on the joint work with Marc Fischlin and Benoit Libert from Asiacrypt 2011.

Thursday December 8, 2011, 11am -- Hawthorne 3N-J21

TITLE: Detecting Dangerous Queries: A New Approach for Chosen Ciphertext Security
SPEAKER: Brent Waters, University of Texas, Austin

ABSTRACT: I will present a new approach for creating chosen ciphertext secure encryption. The focal point of our work is a new abstraction that we call Detectable Chosen Ciphertext Security (DCCA). Intuitively, this notion is meant to capture systems that are not necessarily chosen ciphertext attack (CCA) secure, but where we can detect whether a certain query CT can be useful for decrypting (or distinguishing) a challenge ciphertext CT*. We show how to build chosen ciphertext secure systems from DCCA security. We motivate our techniques by describing multiple examples of DCCA systems including creating them from 1-bit CCA secure encryption --- capturing the recent Myers-shelat result (FOCS 2009). Our work identifies DCCA as a new target for building CCA secure systems.

Thursday November 17, 2011

TITLE: Tamper and Leakage Resilience in the Split-State Model
SPEAKER: Feng-Hao Liu, Brown University

ABSTRACT: It is notoriously difficult to create hardware that is immune from side channel and tampering attacks. A lot of recent literature, therefore, has instead considered algorithmic defenses from such attacks. In this paper, we show how to algorithmically secure any cryptographic functionality from continual split-state leakage and tampering attacks. A split-state attack on cryptographic hardware is one that targets separate parts of the hardware separately. Our construction does not require the hardware to have access to randomness. On contrast, prior work on protecting from continual combined leakage and tampering [KKS11] required true randomness for each update. Our construction is in the common reference string (CRS) model; the CRS must be hard-wired into the device. We note that prior negative results show that it is impossible to algorithmically secure a cryptographic functionality against a combination of arbitrary continual leakage and tampering attacks without true randomness; therefore restricting our attention to the split-state model is justified. Our construction is simple and modular, and relies on a new construction, in the CRS model, of non-malleable codes with respect to split-state tampering functions, which may be of independent interest. Joint work with Anna Lysyanskaya

Thursday November 10, 2011

TITLE: How to Delegate and Verify in Public: Verifiable Computation from Attribute-based Encryption
SPEAKER: Mariana Raykova, Columbia University

ABSTRACT: The wide variety of small, computationally weak devices, and the growing number of computationally intensive tasks makes the delegation of computation to large data centers a desirable solution. However, computation outsourcing is useful only when the result returned can be trusted, which makes verifiable computation (VC) a must for such scenarios. In this work we extend the definition of verifiable computation in two important directions: public delegation and public verifiability, which have important applications in many practical delegation scenarios. Yet, existing VC constructions based on standard cryptographic assumptions fail to achieve these properties. As the primary contribution of our work, we establish an important (and somewhat surprising) connection between verifiable computation and attribute-based encryption (ABE),a primitive that has been widely studied. Namely, we show how to construct a VC scheme with public delegation and public verifiability from any ABE scheme.
The VC scheme verifies any function in the class of functions covered by the permissible ABE policies. This scheme enjoys a very efficient verification algorithm that depends only on the output size. We show a similar construction from ABE with outsourced decryption~\cite{green2011outsource}, which gives us a multi-function VC scheme that allows the verifiable evaluation of multiple functions on the same preprocessed input. We also explore the opposite direction of the ABE-VC relationship and show an ABE construction from a modified VC scheme.
Joint work with Bryan Parno and Vinod Vaikuntanathan.

Thursday November 3, 2011

TITLE: Leakage-Tolerant Interactive Protocols
SPEAKER: Nir Bitansky, Tel-Aviv University

ABSTRACT: We put forth a framework for expressing security requirements from interactive protocols in the presence of leakage. The framework allows expressing different levels of leakage-tolerance of protocols, namely the preservation (or degradation) of security, under coordinated attacks that include various forms of leakage from the secret states of participating parties. The framework extends the universally composable (UC) security framework. We also prove a variant of the UC theorem, that enables modular design and analysis of protocols even in face of general, non-modular leakage. We then construct leakage-tolerant protocols for basic tasks, such as, secure-communication, message-authentication, commitment, oblivious-transfer and zero-knowledge. A central component in several of our constructions is the observation that resilience to adaptive party corruptions (in some strong sense) implies leakage-tolerance in an essentially optimal way. If time allows, I'll describe how leakage-tolerant secure-communication can be applied to construct obfuscation mechanisms for general programs that rely on minimal use of trusted hardware, and remain secure even if the trusted hardware is leaky.
Based on joint work with Ran Canetti, Shafi Goldwasser, Shai Halevi, Yael Kalai and Guy Rothblum.

Thursday October 27, 2011

TITLE: Security Proofs for RSA-OAEP in the Standard Model
SPEAKER: Adam O'Neill, Boston University.

ABSTRACT: RSA-OAEPis a popular ``provably secure'' way to encrypt with the RSA trapdoor permutation in practice, proposed byBellare and Rogaway (Eurocrypt 1994).Essentially, the scheme first pre-processes an input plaintext -- namely, by applying two hash functions in an invertible way to the plaintext concatenated with some number of random coins -- before applying RSA. An important caveat is that the security analysis of the scheme was done in the "random oracle (RO) model", which, roughly speaking, heuristically models hash functions as truly random functions available via oracles to all parties.
Unfortunately, it is known that, in general, a scheme that is secure in the RO model may necessarily be insecure in the "standard model" where hash functions are required to be efficiently computable (Canetti et al., J. ACM 2004). Here we endeavor to give a supplemental analysis of RSA-OAEPin the standard model.
Our main result (with Eike Kiltz and Adam Smith, at Crypto 2010) is a proof that RSA-OAEPachieves semantic security (i.e., "passive security") in the standard model under reasonable assumptions. We begin by outlining a general approach to proving semantic security of RSA-OAEP in the standard model.We then explain how to implement it based on the recently proposed notion of "lossy" trapdoor functions by Peikert and Waters (STOC 2008) combined with (some novel extensions to) a variant of the Leftover Hash Lemma due to Dodis and Smith (STOC 2005). We deduce that RSA-OAEPis semantically secure if RSA is lossy and the first hash function used in the pre-processing stage is $t$-wise independent for appropriate $t$. (No assumption is made on the second hash function for this result; in particular, neither hash function is modeled as a random oracle.) Finally, we show that RSA is lossy under the "Phi-Hiding Assumption" of Cachin, Micali, and Stadler (Eurocrypt 1999), originally proposed in the context of private information retrieval. I will try to save time towards the end of the talk to discuss on-going efforts to extend this result in various ways, namely to use hash function families with shorter keys and to address the more challenging case of chosen-ciphertext attacks (i.e., "active security").

Thursday October 6, 2011

TITLE: Relatively-Sound NIZKs and PAKE
SPEAKER: Arnab Roy, IBM Research

ABSTRACT: We define a new notion of relatively-sound non-interactive zero-knowledge (NIZK) proofs, where a private verifier with access to a trapdoor continues to be sound even when the Adversary has access to simulated proofs and common reference strings. It is likely that this weaker notion of relative-soundness suffices in most applications which need simulation-soundness. We show that for certain languages which are diverse groups, and hence allow smooth projective hash functions, one can obtain more efficient single-theorem relatively-sound NIZKs as opposed to simulation-sound NIZKs. We also show that such relatively-sound NIZKs can be used to build rather efficient publicly-verifiable CCA2-encryption schemes. By employing this new publicly-verifiable encryption scheme along with an associated smooth projective-hash, we show that a recent PAK-model single-round password-based key exchange protocol of Katz and Vaikuntanathan, (TCC 2011), can be made much more efficient. We also show a new single round UC-secure password-based key exchange protocol with only a constant number of group elements as communication cost, whereas the previous single round UC-protocol required Omega(k) group elements, where k is the security parameter.
Paper available here. Joint work with Charanjit Jutla.

Friday September 16, 2011

TITLE: Concurrent Security and Non Malleability
SPEAKER: Rafael Pass, Cornell University.

ABSTRACT: The Internet enables concurrent executions of cryptographic protocols. This concurrent setting, however, also brings forth new types of coordinated attacks in which an adversary controls many parties, interleaving the executions of the various protocol instances, and attempts to “maul” messages from one execution to use in another. In this talk, I will survey some recent methods for achieving concurrent security without relying on any trusted-setup (such as e.g., Common Reference Strings). Based on joint works with Ran Canetti and Huijia Lin.

Thursday September 8, 2011

TITLE: Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller.
SPEAKER: Chris Peikert, Georgia Tech.

ABSTRACT: I will describe new ways of generating and using ``strong trapdoors'' in cryptographic lattices, which are simultaneously simple, efficient, easy to implement (even in parallel), and asymptotically optimal with very small hidden constants. For example, at strong levels of concrete security we obtain key sizes at least 60 times smaller than with previous techniques. Our methods involve a *new kind of trapdoor* (not a "short basis"), and include specialized efficient algorithms for inverting LWE, randomly sampling SIS preimages, and securely delegating trapdoors.
The simple structure of the new trapdoor and associated algorithms can also be exposed in applications, including all those built using "bonsai tree" techniques, leading to further simplifications and efficiency improvements. For example, we give a new CCA-secure encryption scheme that enjoys the best security and efficiency properties of all prior (incomparable) lattice-based constructions, simultaneously.
This is joint work with Daniele Miccancio.