Theory of Cryptography: 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, February 9-11, 2010, Proceedings (Lecture Notes in Computer Science, 5978)

This book constitutes the refereed proceedings of the Seventh Theory of Cryptography Conference, TCC 2010, held in Zurich, Switzerland, February 9-11, 2010. The 33 revised full papers presented together with two invited talks were carefully reviewed and selected from 100 submissions.The papers are organized in topical sections on parallel repetition, obfuscation, multiparty computation, CCA security, threshold cryptography and secret sharing, symmetric cryptography, key-leakage and tamper-resistance, rationality and privacy, public-key encryption, and zero-knowledge. Title Page Preface Organization Table of Contents Parallel Repetition An Efficient Parallel Repetition Theorem Introduction Our Results Some History and Related Papers Our Techniques Outline of Paper Notation and Basic Definitions Simulatable Verifiers The Parallel Repetition Theorem Proof of Theorem 1 Proof of Theorem 1 in the Public-Coin Case Proof of Theorem 1 for $\delta$-Simulatable Verifiers with Verdict Proof of Theorem 1 for $\delta$-Simulatable Verifiers without Verdict Concurrent Repetition References Parallel Repetition Theorems for Interactive Arguments Introduction Parallel Repetition for Public-Coin Arguments Extension to Arguments with Simulatable Verifiers without Verdict Reducing Soundness Error for $Any$ Interactive Arguments Extension to Chernoff-Type Theorems Preliminary and Notation Tight Direct Product Theorem for Public-Coin Arguments Analysis of P$^*_{ideal}$ Arguments with Simulatable Verifier without Verdict Reducing Soundness Error for Any Arguments Extension to Chernoff-Type Theorems Constant-Round AM Arguments Systems References Almost Optimal Bounds for Direct Product Threshold Theorem Introduction Preliminaries Basics Samplers Weakly-Verifiable Puzzles Uniformized Parallel Solvers The Main Theorem Pre-processing and Hypothesis Testing References Appendix Obfuscation On Symmetric Encryption and Point Obfuscation Introduction Our Results Implications Definitions Obfuscation of Point Functions with Multi-bit Output Definitions for Encryption with Weak Keys Encryption with Weak Keys and MBPF Obfuscation Sem. Sec. Encryption and Obfuscation with Independent Messages CPA Encryption and Composable Obfuscation for Indep. Messages KDM Encryption and MBPF Obfuscation Encryption/Obfuscation with Auxiliary Input Implications Encryption with Fully Weak Keys Obfuscation References Obfuscation of Hyperplane Membership Introduction Definitions Virtual Black-Box Obfuscation Vector Spaces Our Assumption Discussion On the Assumption's Hardness Construction Obfuscation of Hyperplanes with Multi-bit Output One-Time Signature Schemes References Invited Talk Secure Computation and Its Diverse Applications Multiparty Computation On Complete Primitives for Fairness Introduction Our Results Related Work Definitions Fairness-Complete Primitives Fairness-Complete Primitives for Two-Party Computation Fairness-Complete Primitives for Multi-party Computation Limits on Fairness-Completeness A Fairness Hierarchy Fairness Combiners Combining with an Honest Majority References On the Necessary and Sufficient Assumptions for UC Computation Introduction The KRA Model Authentication in the A-KRA Model given OWF -Protocols Authentication Multiparty Authentication UC-OT in the A-KRA Model given SA-OT UC Commitment in the C-KRA Model given OWFs UC OT in the A-CRS Model given SA-OT UC-Com in the A-KRA Model Implies SA-OT Conclusions The C-CRS Setup Assumption References From Passive to Covert Security at Low Cost Introduction Our Contribution Related Work and Discussion Preliminaries Auxiliary Functionalities Protocol Implementation of Sub-protocols References CCA Security A Twist on the Naor-Yung Paradigm and Its Application to Efficient CCA-Secure Encryption from Hard Search Problems Introduction Technical Details Preliminaries Notation Key Encapsulation Mechanisms Set Systems Basic Definition Hard Set Systems Algebraic Set Systems Examples IND-CPA Secure KEMs from Commutative Set Systems Hash Proof Systems Definitions Our Trapdoor Language IND-CCA Secure KEMs from Algebraic Set Systems Discussion and Variants References Two Is a Crowd? A Black-Box Separation of One-Wayness and Security under Correlated Inputs Introduction Preliminaries Notation Probabilistic Lemmas Non-uniform Trapdoor Permutations in the Presence of Oracles Our Oracles Oracle Notation The Oracle Break Breaking Security under Correlated Inputs Overview The Adversary Analysis One-Way Trapdoor Permutations Exist Relative to Our Oracle Simulating Break' Equivalence of Break and Break' Main Theorem Extensions References Threshold Cryptography and Secret Sharing Efficient, Robust and Constant-Round Distributed RSA Key Generation Introduction Security Model Probabilistic Primality Test Replicated Integer Secret Sharing Passive Secure Protocol Realizing FRISS Verifiable Replicated Integer Secret Sharing Distributed Primality Testing Active Security Distributed Primality Testing Distributed RSA Moduli Generation Optimizations Conclusion and Acknowledgment References Threshold Decryption and Zero-Knowledge Proofs for Lattice-Based Cryptosystems Introduction Preliminaries Cryptosystem Distributed Decryption (Passive Adversaries) Key Generation and Distribution Decryption Protocol Security Distributed Decryption for Stronger Adversaries Distributed Key Generation Security Zero-Knowledge Proof of Plaintext Knowledge Packed Secret Sharing Hyper-invertible Matrices The Multiparty Protocol References Zero-Knowledge Proof When $q$ Is Not Prime Ideal Hierarchical Secret Sharing Schemes Introduction Ideal Secret Sharing Schemes and Matroids Hierarchical Access Structures Multipartite Matroid Ports and Integer Polymatroids Hierarchical Matroid Ports A Family of Ideal Hierarchical Access Structures A Characterization of Ideal Hierarchical Access Structures Ideal Weighted Threshold Access Structures References Symmetric Cryptography A Hardcore Lemma for Computational Indistinguishability: Security Amplification for Arbitrarily Weak PRGs with Optimal Stretch Introduction (Weak) Pseudorandomness Security Amplification of PRGs A Tight Characterization of Computational Indistinguishability Outline of This Paper Preliminaries Notational Preliminaries and Computational Model Pseudorandom Generators and Randomness Extractors Measures and the Hardcore Lemma Characterizing Computational Indistinguishability Via Hardcore Theorems Non-uniform Case Proof of Theorem 4 The Uniform Case Security Amplification of PRGs The Concatenate-and-Extract Construction Proof of Theorem 6 Optimality of the Output Length References Tail Estimates On Related-Secret Pseudorandomness Introduction Definitions Related-Secret Security Hard-Core Bits Black Token Algorithms The Importance of RS-PRBs Difficulties in Constructing an RS-PRB Discussion References Black Token Reductions for Known Hardcore Bits Other Hardcore Bits Black Token RS-SHCB's to Codes A Domain Extender for the Ideal Cipher Introduction Related Work Definitions An Attack against 2 Rounds Indifferentiability of 3-Round Feistel Construction Practical Considerations Indifferentiability for 2 Rounds in the Honest-But-Curious Model Domain Extension of Tweakable Block Cipher Conclusion References Delayed-Key Message Authentication for Streams Introduction Preliminaries Defining Delayed-Key MACs for Streams Security of Delayed-Key MACs One-Sided Delayed-Key MACs: The Unbounded Case Pseudorandom Permutation One-Sided Delayed-Key MACs: The Bounded Case XOR-Construction Two-Sided Delayed-Key MACs: A Feasibility Result References Key-Leakage and Tamper-Resistance Founding Cryptography on Tamper-Proof Hardware Tokens Introduction Our Results Related Work Preliminaries Unconditional Non-interactive Secure Computation Using Stateful Tokens The Interactive Setting The Non-interactive Setting Two-Party Computation with Stateless Tokens Protocol Intuition References Truly Efficient String Oblivious Transfer Using Resettable Tamper-Proof Tokens Introduction Our Contributions and Outline of the Work Main Idea of Our Approach Related Work Preliminaries Notation and Security Model Strong Pseudorandom Permutation Generators (SPRPG) Oblivious Transfer OT with Resettable Tamper-Proof Cards Protocols for Malicious (Covert) Setting Discussion: Protocol Composition and Practical Considerations Concurrent Composition with the Semi-honest Token References Leakage-Resilient Signatures Introduction Leakage-Resilient Cryptography Leakage-Resilient Signatures Replacing Randomness in Leakage-Resilient Primitives Related Work Preliminaries Leakage Resilient Signatures Standard Signatures Leakage Resilient Signatures Signatures with Bounded Total Leakage Construction of Leakage Resilient Signature Schemes Signatures with Bounded Leakage Resilience Construction of Leakage Resilient Signature Schemes Efficiency and Trade-offs References Public-Key Encryption Schemes with Auxiliary Inputs Introduction The Auxiliary Input Model Our Results Overview of Techniques Preliminaries Security against Auxiliary Inputs Classes of Auxiliary Input Functions Goldreich-Levin Theorem for Large Fields Auxiliary Input Secure Encryption Schemes Construction Based on the DDH Assumption Constructions Based on LWE References Public-Key Cryptographic Primitives Provably as Secure as Subset Sum Introduction Our Contributions and Techniques Comparisons with Lattice-Based Schemes Open Problems Preliminaries The Subset Sum Problem Notation The Encryption Scheme Proof of Security Proof of Correctness Security against Key-Leakage Attacks Oblivious Transfer Protocol OT Based on Subset Sum Proofs of Correctness and Security References Cryptographic Definitions Randomness Extraction Key-Leakage Attacks Oblivious Transfer Rationality and Privacy Rationality in the Full-Information Model Introduction Our Results and Organization Related Work Protocols and Games Resilient Protocols Extensive-Form Games and Protocols Rationality in Selection Protocols – Definitions Rationality in the Face of an Adversary – Definitions Resilience to Rational Coalitions – Definitions Impossibility with Complex Preferences Rational Leader Election Protocols Basic Faithful Leader Election Protocols Combining Rationality and Resilience in Leader Election Rationality in the Face of an Adversary Resilience to Rational Coalitions Rational Random Sampling Protocols Conclusion and Open Problems References Efficient Rational Secret Sharing in Standard Communication Networks Introduction Our Results Overview of Our Approach Comparison to the Kol-Naor Scheme Model and Definitions Secret Sharing and Players' Utilities Notions of Game-Theoretic Equilibria: A Discussion Definitions of Game-Theoretic Equilibria Rational Secret Sharing: The 2-Out-of-2 Case Using Trapdoor Permutations Instead of VRFs Rational Secret Sharing: The $t$-Out-of-$n$ Case References Verifiable Random Functions (VRFs) Bounds on the Sample Complexity for Private Learning and Private Data Release Introduction Our Contributions Related Work Preliminaries Preliminaries from Privacy Preliminaries from Learning Theory Private Learning Learning vs. Private Learning Separation between Private and Non-private PAC Learning Separation between Proper and Improper Private PAC Learning Separation between Efficient and Inefficient Proper Private PAC Learning Lower Bounds for Non-interactive Sanitization References Public-Key Encryption New Techniques for Dual System Encryption and Fully Secure HIBE with Short Ciphertexts Introduction Our Approach Related Work Organization Background Hierarchical Identity Based Encryption Composite Order Bilinear Groups Our IBE System Construction Security Our HIBE System Construction Security Moving to Prime Order Groups Conclusions and Open Directions References Generic Security of Our Complexity Assumptions HIBE Security Proof IBE in Prime Order Groups Construction Complexity Assumptions Security Robust Encryption Introduction Definitions Robustness Failures of Encryption with Redundancy Transforms That Work A SROB-CCA Version of Cramer-Shoup References Invited Talk Privacy-Enhancing Cryptography: From Theoryin to Practice Zero-Knowledge Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs Introduction Background Complexity Assumptions Trapdoor q-Mercurial Commitments Zero-Knowledge Sets and Databases A Construction of Concise qTMC Scheme Implications on the Efficiency of ZK-EDBs Achieving Strong Independence References Security Properties of Zero-Knowledge Databases Eye for an Eye: Efficient Concurrent Zero-Knowledge in the Timing Model Introduction Organization Preliminaries Timing Model Black-Box Concurrent Zero-Knowledge in the Timing Model Other Primitives Our Protocol and Simulator Protocol Overview Description of the Protocol Simulator Overview Description of the Simulator Analysis of the Simulator References Efficiency Preserving Transformations for Concurrent Non-malleable Zero Knowledge Introduction Definitions Building Blocks: Efficient Instantiations Simulatable Commitments The DDN Commitment An Efficiency Preserving Transformation The Extraction Preamble The Transformation Proving Concurrent Non-malleability Efficiency References Efficiency Limitations for Σ-Protocols for Group Homomorphisms Introduction Preliminaries Zero-Knowledge Proofs of Knowledge The -Protocol in Hidden-Order Groups Lower Bounds of the Knowledge Error The Generic Group Model and Groups of Hidden Order Generic -Protocols Efficiency Limitations in the Generic Group Model Generalization to Other Classes of Homomorphisms Proof of Theorem 6 Lower Bounds for the -Protocol in the Plain Model Lower Bounds for Power Homomorphisms Lower Bounds for Exponentiation Homomorphisms Conclusion References Composition of Zero-Knowledge Proofs with Efficient Provers Introduction Definitions and Preliminaries Interactive Proofs Zero Knowledge Composition Sequential Zero Knowledge Previous Results New Results Parallel Zero Knowledge Previous Results New Results Conclusions and Open Problems References Private Coins versus Public Coins in Zero-Knowledge Proof Systems Introduction Preliminaries and Definitions Fully Black-Box Constructions The Collision Finding Class The Oracle Sam$^{\pi}_d$ The Complexity Class CF$_d$ From Private Coins to Public Coins Weak Duality Lemma Strong Duality Lemma Black-Box Lower Bounds for Zero Knowledge Lower Bounds Zero-Knowledge Proofs and Arguments Lower Bounds for Concurrent Zero Knowledge References Erratum to: Theory of Cryptography Author Index