CRYPTO 2012

An Enciphering Scheme Based on a Card Shuffle

Viet Tung Hoang (University of California, Davis)

Ben Morris (University of California, Davis)

Phillip Rogaway (University of California, Davis)

Tweakable Blockciphers with Beyond Birthday-Bound Security

Will Landecker (Portland State University)

Thomas Shrimpton (Portland State University)

Seth Terashima (Portland State University)

Breaking and Repairing GCM Security Proofs
Tetsu Iwata (Nagoya University, Japan)

Keisuke Ohashi (Nagoya University, Japan)

Kazuhiko Minematsu (NEC Corporation, Japan)

On The Distribution of Linear Biases: Three Instructive Examples
Mohamed Ahmed Abdelraheem (Technical University, Denmark)

Martin Ågren (Lund University, Sweden)

Peter Beelen (Technical University, Denmark)

Gregor Leander (Technical University, Denmark)

Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs

Eric Miles (Northeastern University)

Emanuele Viola (Northeastern University)

Must you know the code of f to securely compute f?

Mike Rosulek (University of Montana)

Adaptively Secure Multi-Party Computation with Dishonest Majority

Sanjam Garg (UCLA)

Amit Sahai (UCLA)

Collusion-Preserving Computation

Joel Alwen (ETH Zurich, Switzerland)

Jonathan Katz (University of Maryland)

Ueli Maurer (ETH Zurich, Switzerland)

Vassilis Zikas (University of Maryland)

Secret Sharing Schemes for Very Dense Graphs

Amos Beimel (Ben Gurion University, Israel)

Yuval Mintz (Ben Gurion University, Israel)

Oriol Farras (Universitat Rovira i Virgili, Spain)

Functional Encryption with Bounded Collusions via Multi-Party Computation

Sergey Gorbunov (University of Toronto, Canada)

Vinod Vaikuntanathan (University of Toronto, Canada)

Hoeteck Wee (George Washington University)

New Proof Methods for Attribute-Based Encryption: Achieving Full Security through Selective Techniques

Allison Lewko (University of Texas, Austin)

Brent Waters (University of Texas, Austin)

Dynamic Credentials and Ciphertext Delegation for Attribute-Based Encryption

Amit Sahai (UCLA)

Hakan Seyalioglu (UCLA)

Brent Waters (University of Texas, Austin)

Functional Encryption for Regular Languages

Brent Waters (University of Texas, Austin)

Secure Database Commitments and Universal Arguments of Quasi Knowledge
Melissa Chase (Microsoft Research Redmond)

Ivan Visconti (University of Salerno, Italy)

Succinct Arguments from Multi-Prover Interactive Proofs and their Efficiency Benefits
Nir Bitansky (Tel Aviv University, Israel)

Alessandro Chiesa (MIT)

On the Security of TLS-DHE in the Standard Model

Tibor Jager (Ruhr-University, Germany)

Florian Kohlar (Ruhr-University, Germany)

Sven Schäge (University College London, UK)

Jörg Schwenk (Ruhr-University, Germany)

Semantic Security for the Wiretap Channel

Mihir Bellare (UCSD)

Stefano Tessaro (MIT)

Alexander Vardy (UCSD)

Multi-Instance Security and its Application to Password-Based Cryptography

Mihir Bellare (UCSD)

Thomas Ristenpart (University of Wisconsin-Madison)

Stefano Tessaro (MIT)

Hash Functions Based on Three Permutations: A Generic Security Analysis

Bart Mennink (KU Leuven, Belgium)

Bart Preneel (KU Leuven, Belgium)

To Hash or Not to Hash Again? (In)differentiability Results for H^2 and HMAC

Yevgeniy Dodis (NYU)

Thomas Ristenpart (University of Wisconsin-Madison)

John Steinberger (Tsinghua University, China)

Stefano Tessaro (MIT)

New Preimage Attacks Against Reduced SHA-1

Simon Knellwolf (ETH Zurich and FHNW, Switzerland)

Dmitry Khovratovich (Microsoft Research Redmond)

Stam's Conjecture and Threshold Phenomena in Collision Resistance

John Steinberger (Tsinghua University, Beijing, China)

Xiaoming Sun (Chinese Academy of Sciences, China)

Zhe Yang (Hulu, Beijing, China)

Universal Composability From Essentially Any Trusted Setup

Mike Rosulek (University of Montana)

Impossibility Results for Static Input Secure Computation

Sanjam Garg (UCLA)

Abishek Kumarasubramanian (UCLA)

Rafail Ostrovsky (UCLA)

Ivan Visconti (University of Salerno, Italy)

New Impossibility Results for Concurrent Composition and a Non-Interactive Completeness Theorem for Secure Computation

Shweta Agrawal (UCLA)

Vipul Goyal (MSR, India)

Abhishek Jain (UCLA)
Manoj Prabhakaran (UIUC)

Amit Sahai (UCLA)

Abstract:
We consider the client-server setting for the concurrent composition of secure protocols: in this setting, a single server interacts with multiple clients concurrently, executing with each client a specified protocol where only the client should receive any nontrivial output. Such a setting is easily motivated from an application standpoint. There are important special cases for which positive results are known such as concurrent zero knowledge protocols and it has been an open question whether other natural functionalities such as Oblivious Transfer (OT) are possible in this setting.

In this work:

- We resolve this open question by showing that unfortunately, even in this very limited concurrency setting, broad new impossibility results hold, ruling out not only OT, but in fact all nontrivial finite asymmetric functionalities. Our new negative results hold even if the inputs of all honest parties are fixed in advance, and the adversary receives no auxiliary information.

- Along the way, we establish a new unconditional completeness result for asymmetric functionalities, where we characterize functionalities that are non-interactively complete secure against active adversaries. When we say that a functionality F is non-interactively complete, we mean that every other asymmetric functionality can be realized by parallel invocations of several copies of F, with no other communication in any direction. Our result subsumes a completeness result of Kilian [STOC'00] that uses protocols which require additional interaction in both directions.

Black-Box Constructions of Composable Protocols without Set-Up

Huijia Rachel Lin (MIT and Boston University)

Rafael Pass (Cornell University)

Crowd-Blending Privacy

Johannes Gehrke (Cornell University)

Michael Hay (Cornell University)

Edward Lui (Cornell University)

Rafael Pass (Cornell University)

Differential Privacy with Imperfect Randomness

Yevgeniy Dodis (NYU)

Adriana Lopez-Alt (NYU)

Ilya Mironov (Microsoft Research)

Salil Vadhan (Harvard University)

Tamper and Leakage Resilience in the Split-State Model

Feng-Hao Liu (Brown University)

Anna Lysyanskaya (Brown University)

Securing Circuits Against Constant-Rate Tampering

Dana Dachman-Soled (Microsoft Research New England)

Yael Tauman Kalai (Microsoft Research New England)

How to Compute under AC^0 Leakage without Secure Hardware

Guy Rothblum (Microsoft Research Silicon Valley)

Group Signatures with Almost-for-free Revocation

Benoit Libert (UCL, Belgium)

Thomas Peters (UCL, Belgium)

Moti Yung (Google Inc. and Columbia University)

Tightly Secure Signatures and Public-Key Encryption

Dennis Hofheinz (Karlsruhe Institute of Technology, Germany)

Tibor Jager (Karlsruhe Institute of Technology, Germany)

Efficient Padding Oracle Attacks on Cryptographic Hardware

Romain Bardou (INRIA, France)

Riccardo Focardi (Università Ca' Foscari, Italy)

Yusuke Kawamoto (University of Birmingham, United Kingdom)

Lorenzo Simionato (Università Ca' Foscari, Venezia, Italy)

Graham Steel (INRIA, France)

Joe-Kai Tsay (NTNU, Norway)

Public Keys

Arjen K. Lenstra (EPFL, Switzerland)

James P. Hughes (Self, Palo Alto)

Maxime Augier (EPFL, Switzerland)

Joppe W. Bos (EPFL, Switzerland)

Thorsten Kleinjung (EPFL, Switzerland)

Christophe Wachter (EPFL, Switzerland)

Multiparty Computation from Somewhat Homomorphic Encryption

Ivan Damgard (Aarhus University, Denmark)

Valerio Pastro (Aarhus University, Denmark)

Nigel Smart (University of Bristol, United Kingdom)

Sarah Zakarias (Aarhus University, Denmark)

Near-Linear Unconditionally-Secure Multiparty Computation with a Dishonest Minority

Eli Ben-Sasson (Technion , Israel)

Serge Fehr (CWI, The Netherlands)

Rafail Ostrovsky (UCLA)

A New Approach to Practical Active-Secure Two-Party Computation

Jesper Buus Nielsen (Aarhus University, Denmark)

Peter Sebastian Nordholt (Aarhus University, Denmark)

Claudio Orlandi (Bar-Ilan University, Israel)

Sai Sheshank Burra (Indian Institute of Technology, Guwahati, India)

The Curious Case of Non-Interactive Commitments

Mohammad Mahmoody (Cornell University)

Rafael Pass (Cornell University)

Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems

Itai Dinur (Weizmann Institute, Israel)

Orr Dunkelman (Weizmann Institute and University of Haifa, Israel)

Nathan Keller (Weizmann Institute and Bar-Ilan University, Israel)

Adi Shamir (Weizmann Institute, Israel)

Resistance Against Iterated Attacks Revisited

Asli Bay (EPFL, Switzerland)

Atefeh Mashatan (EPFL, Switzerland)

Serge Vaudenay (EPFL, Switzerland)

Secure Identity-based Encryption in the Quantum Random Oracle Model

Mark Zhandry (Stanford University)

Quantum to Classical Randomness Extractors

Mario Berta (ETH Zurich, Switzerland)

Omar Fawzi (McGill University, Canada)

Stephanie Wehner (National University of Singapore, Singapore)

Actively Secure Two-Party Evaluation of any Quantum Operation

Frédéric Dupuis (ETH Zürich)

Louis Salvail (Université de Montréal, Canada)

Jesper Buus Nielsen (Aarhus University)

On the Impossibility of Constructing Efficient Key Encapsulation and Programmable Hash Functions in Prime Order Groups

Goichiro Hanaoka (RISEC, AIST, Japan)

Takahiro Matsuda (RISEC, AIST, Japan)

Jacob C.N. Schuldt (RISEC, AIST, Japan)

Hardness of Computing Individual Bits for One-way Functions on Elliptic Curves

Alexandre Duc (EPFL, Switzerland)

Dimitar Jetchev (EPFL, Switzerland)

Homomorphic Evaluation of the AES Circuit

Craig Gentry (IBM Research)

Shai Halevi (IBM Research)

Nigel P. Smart (University of Bristol, United Kingdom)

Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP

Zvika Brakerski (Stanford University)