Theory of Cryptography
9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings
Published on 5. March 2012
672 pages
978-3-642-28914-9 (ISBN)
Description
This book constitutes the thoroughly refereed proceedings of the 9th Theory of Cryptography Conference, TCC 2012, held in Taormina, Sicily, Italy, in March 2012.
The 36 revised full papers presented were carefully reviewed and selected from 131 submissions. The papers are organized in topical sections on secure computation; (blind) signatures and threshold encryption; zero-knowledge and security models; leakage-resilience; hash functions; differential privacy; pseudorandomness; dedicated encryption; security amplification; resettable and parallel zero knowledge.
More details
Other editions
Additional editions
Ronald Cramer
Theory of Cryptography
9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings
Book
03/2012
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title Page
- Preface
- Organization
- Table of Contents
- Secure Computation
- Computing on Authenticated Data
- Introduction
- Overview
- Definitions
- Security: Unforgeability
- Security: Context Hiding (a.k.a., Privacy)
- Related Work
- Preliminaries: Algebraic Settings
- A Powers-of-2 Construction for Quoting Substrings
- Subsets and Weighted Averages
- References
- Identifying Cheaters without an Honest Majority
- Introduction
- Our Results
- Preliminaries
- Secret Sharing
- Locally Identifiable Secret Sharing
- Our Construction
- Relaxing Local Identifiability
- Unanimously Identifiable Commitments
- A Unanimously Identifiable Commitment Scheme
- Unanimously Identifiable Secret Sharing
- Applications
- Model of Computation
- Complete Primitives for MPC
- Partial Fairness with Preprocessing
- References
- On the Security of the "Free-XOR" Technique
- Introduction
- Security of the Free-XOR Technique?
- Related Work
- Organization
- Preliminaries
- Yao's Garbled Circuit Construction
- The Free-XOR Technique
- Correlation-Robust Hash Functions
- Insufficiency of Correlation Robustness
- Where the Reduction Fails
- A Counter-Example
- Proving Security of the Free-XOR Approach
- Conclusion
- References
- Secure Two-Party Computation with Low Communication
- Introduction
- Notations and Definitions
- Public Key Encryption Schemes
- Fully Homomorphic Encryption Schemes
- Efficient Probabilistic Checkable Proofs (PCP)
- Collision Resistant Hashing and Merkle Trees
- Non-interactive Zero-Knowledge Proofs
- Extractable Hash Functions
- The Knowledge of Exponent Assumption
- Secure Two-Party Computation with Low Communication
- Security against Honest-But-Curious Adversaries
- Security against a Malicious P1
- Security against Malicious Adversaries
- References
- (Blind) Signatures and Threshold Encryption
- Non-interactive CCA-Secure Threshold Cryptosystems with Adaptive Security: New Framework and Constructions
- Introduction
- Background and Definitions
- Definitions for Threshold Public Key Encryption
- Hardness Assumptions in Composite Order Groups
- Assumptions in Prime Order Groups
- All-But-One Perfectly Sound Threshold Hash Proof Systems
- Adaptively Secure Robust Non-interactive CCA2-Secure Threshold Cryptosystems from All-But-One Perfectly Sound Threshold Hash Proof Systems
- Instantiations
- Construction in Groups of Composite Order N=p1p2
- Construction in Prime Order Groups
- References
- Round-Optimal Privacy-Preserving Protocols with Smooth Projective Hash Functions
- Introduction
- Definitions
- Notations
- Oblivious Signature-Based Envelope
- An Efficient OSBE Scheme
- High-Level Instantiation
- Security Properties
- Our Efficient OSBE Instantiation
- Security and Efficiency
- An Efficient Blind Signature
- Definitions
- Our Instantiation
- Security
- References
- On the Instantiability of Hash-and-Sign RSA Signatures
- Introduction
- Our Results
- Our Technique
- Other Related Work
- RSA-FDH in the Generic Group Model
- The Generic Group Model
- RSA-FDH Signature Schemes in the Generic Group Model
- Weakly Black-Box Proofs of Security
- There Exists No RSA-FDH with a Weakly Black-Box Proof
- The Forger
- The Breaker F
- The Emulator
- Putting It Together
- References
- Beyond the Limitation of Prime-Order Bilinear Groups, and Round Optimal Blind Signatures
- Introduction
- Notations and Definitions
- Round-Optimal Blind Signature in Prime-Order Group
- Symmetric Bilinear Group with Projecting Pairing
- Construction
- Bilinear Group: Both Cancelling and Projecting
- Interpreting Limitation Result in MSF10
- Our Construction
- Cancelling, Projecting, and Translating
- Conclusions and Further Work
- References
- Zero-Knowledge and Security Models
- On Efficient Zero-Knowledge PCPs
- Introduction
- Our Results
- Efficient Nonadaptive ZK-PCPs
- Simplifying Bounded-Query ZK-PCPs
- Black-Box Sublinear ZK Arguments
- On Nonadaptive Efficient ZK-PCPs
- Main Ideas and Framework
- The Case of Straight-Line Simulation
- References
- Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments
- Introduction
- Preliminaries
- Our Techniques
- Progression-Free Sets
- Cryptographic Tools
- New Hadamard Product Argument
- New Permutation Argument
- New NIZK Argument for Circuit Satisfiability
- References
- Point Obfuscation and 3-Round Zero-Knowledge
- Introduction
- Our Contribution
- Reflections on the Use of Point Obfuscation
- Definitions and Tools
- Weak Zero-Knowledge and Witness Hiding
- 2-Message Delegation
- Point Obfuscation with Auxiliary Input
- Digital Lockers and Circular Digital Lockers
- 3-Round WH
- 3-Round WZK
- Acknowledgements
- References
- Confidentiality and Integrity: A Constructive Perspective
- Introduction
- Game-Based Security Definitions
- Constructive Cryptography
- Secure Communication
- Related Work
- Outline
- Preliminaries
- Notation
- Discrete Systems
- The Simulation-Based Security Definition
- Resources and Protocols as Discrete Systems
- Formalizing Games
- Notions of Confidentiality and Integrity
- Confidentiality
- Integrity
- Relation to Game-Based Security Definitions
- Goals and Attack Models
- Indistinguishability of Ciphertexts
- Specific Variants of Integrity
- Combining Notions of Confidentiality and Integrity
- A Critique of Game-Based Security Notions
- Conclusion
- References
- Leakage-Resilience
- Leakage-Resilient Circuits without Computational Assumptions
- Introduction
- Our Contributions
- Comparison to Related Work
- Preliminaries
- Leakage Model
- Leakage-Resilient Storage
- An Informal Description of the Protocol
- The Ingredients
- Leakage-Resilient Refreshing of LRS
- Leakage-Resilient Computation of Generalized Multiplication
- The Compiler
- Arithmetic Circuits
- Protocols Computing Circuits
- The Security Definition
- The Construction
- Extensions
- References
- A Parallel Repetition Theorem for Leakage Resilience
- Introduction
- Our Results
- Prior Work
- Overview of Our Techniques
- Paper Organization
- Public-Key Primitives, Parallel-Repetition, Leakage Attacks
- A Unified Framework for Public-Key Primitives
- Parallel Repetition
- Leakage Attacks
- Point-Wise Leakage Resilience
- First Relaxation: Almost Leakage Resilience
- Second Relaxation: Leakage Resilience with Advice
- Relation to Bounded Leakage
- Why Known Schemes Are Point-Wise Leakage Resilient
- Direct-Product Theorem for a Constant Number of Repetitions
- Direct-Product Theorem for Polynomially Many Repetitions
- Leakage from Computationally Indistinguishable Schemes
- References
- How to Split Min-Entropy
- Leakage-Tolerant Interactive Protocols
- Introduction
- Our Contribution
- Modeling Leakage in the UC Framework
- Universal Composition of Leaky Protocols
- From Adaptive Security to Leakage-Tolerance
- Realizing Leaky Adaptations of Basic Interactive Tasks
- Zero-Knowledge from Ideal Leaky Commitments
- Authenticated Channels
- On the Difficulty in Achieving General Leakage-Tolerant MPC
- References
- Hash Functions
- On the Publ ic Indifferentiability and Correlation Intractability of the 6-Round Feistel Construction
- Introduction
- Preliminaries
- Notations and Definitions
- Sequential Indifferentiability
- Seq-Indifferentiability of the 6-Round Feistel Construction
- Applications to Correlation Intractability
- References
- Collisions Are Not Incidental: A Compression Function Exploiting Discrete Geometry
- Introduction
- Preliminaries
- Probabilistic Analysis of Adaptive Adversaries
- A More Refined Approach
- Counting Successes
- A New Double-Length Compression Function
- Proof of Collision Resistance (Theorem 3)
- Overall Strategy
- Partitions, Bunches and Some Auxiliary Events
- Bounding Collisions: Focusing on Pr[E1] and Pr[E3]
- Bounding Overall Collinearity: Bounding Pr[E2]
- Blockcipher-Based Instantiation
- References
- Differential Privacy
- Lower Bounds in Differential Privacy
- Introduction
- Lower Bound by Volume Arguments
- Linear Lower Bound for Arbitrary Queries
- Information Loss in Differentially Private Protocols
- Lower Bound on Noise for Counting Queries
- Lower Bounds for Approximate Differential Privacy
- LP Decoding, Euclidean Sections and Hardness of Releasing -way Marginals
- References
- Iterative Constructions and Private Data Release
- Introduction
- Our Results and Techniques
- Related Work
- Preliminaries
- Iterative Database Constructions
- Query Release from Iterative Database Construction
- Privacy Analysis
- Utility Analysis
- An Iterative Database Construction Based on Frieze/Kannan
- Results for Synthetic Data
- Randomized Response and Synthetic Data for Cut Queries
- Towards Improving on Randomized Response for Synthetic Data
- References
- Other Iterative Database Construction Algorithms
- The Median Mechanism
- The Multiplicative Weights Mechanism
- Pseudorandomness I
- From Non-adaptive to Adaptive Pseudorandom Functions
- Introduction
- Our Result
- Proof Idea
- Related Work
- Preliminaries
- Notations
- Ensemble of Function Families
- Our Construction
- FH Is Computationally Indistinguishable From H
- H Is Statistically Indistinguishable From
- Putting It Together
- Handling Polynomial Security
- From Polynomial to Super-Polynomial Security
- Hardness Preserving Constructions of Pseudorandom Functions
- Introduction
- Preliminaries
- Definitions
- The GGM Construction
- Levin's Trick
- Hardness Preserving and Good Constructions
- Our Construction
- References
- Intuition for Conjecture [conjecture][1][1]1
- Computational Extractors and Pseudorandomness
- Introduction
- Proper Computational Extractors
- Preliminaries
- Proper Computational Extractors and Proper Stretch
- The Equivalence of Proper Extractors and One-Way Functions
- The Cost of Black-Box Constructions of Proper Extractors from OWPs
- Unconditional Fully Black-Box Lower Bound
- Unconditional Lower Bound in the Asymptotic, Uniform Setting
- Unconditional Lower Bounds in the Concrete, Non-uniform Setting
- Construction from Exponentially-Hard One-Way Permutations
- Practical Computational Extractors from Weak PRF
- Application to Key Derivation
- References
- Dedicated Encryption I
- Functional Re-encryption and Collusion-Resistant Obfuscation
- Introduction
- Collusion Resistant Obfuscation
- Functional Re-encryption
- Overview of Results and Techniques
- Collusion Resistant Secure Obfuscation
- Average-Case Secure Obfuscation
- Average-Case Secure Obfuscation with Collusion
- Securely Obfuscating Functional Re-encryption
- Preliminaries
- Collusion-Resistant Functional Re-encryption
- Construction of the Encryption Schemes
- Obfuscation for Functional Re-encryption
- Proof of Collusion-Resistant Secure Obfuscation
- References
- How to Delegate and Verify in Public: Verifiable Computation fromAttribute-Based Encryption
- Introduction
- Our Results and Techniques
- Other Results
- Definitions
- Public Verifiable Computation
- Key-Policy Attribute-Based Encryption
- Verifiable Computation from ABE
- Main Construction
- Instantiations
- Conclusions and Future Work
- References
- On Black-Box Reductions between Predicate Encryption Schemes
- Introduction
- Our Results
- Techniques
- Preliminaries
- Sharing-Based Constructions and Impossibility Results
- The Communication Complexity Approach
- Separating TPE from IBE
- References
- Security Amplification
- Lossy Functions Do Not Amplify Well
- Introduction
- Lossy Trapdoor Functions
- Relative Lossiness
- Lossiness Amplification
- Our Results
- Relation to the Collision Problem
- Related Work
- On Black-Box Separations
- Overview of Our Approach
- An Upper Bound on Black-Box Lossiness Amplification
- Proof of Lemma 3.5
- Extension to Collections of Lossy Functions
- The Random bold0mu mumu ={g0,g1,f}={g0,g1,f}Raw={g0,g1,f}={g0,g1,f}={g0,g1,f}={g0,g1,f}
- (Non-)Communicating bold0mu mumu **Raw****
- References
- Counterexamples to Hardness Amplification beyond Negligible
- Introduction
- Hardness Amplification Definitions and Conjectures
- Hard and One-Way Relations
- Counterexample for Signature Schemes
- Overview
- Our Signature Scheme
- Attack on the Direct Product
- Counterexample for One-Way Relations and Functions
- Our Construction
- Justifying the ESPR Assumption
- References
- Resettable and Parallel Zero Knowledge
- Resettable Statistical Zero Knowledge
- Introduction
- Our Contribution
- Technical Difficulties and New Techniques
- Notation and Tools
- Instance-Dependent Commitments and Proofs
- Resettable Partially Honest-Verifier Statistical Zero Knowledge
- Resettable Statistical ZK from Perfect Non-interactive ID Commitments
- Resettable Statistical ZK for All Languages in SZK
- 2-Round Statistical Witness Indistinguishability
- References
- The Knowledge Tightness of Parallel Zero-Knowledge
- Introduction
- Our Results
- Related Works
- Connection to Concurrent Zero-Knowledge
- Preliminaries
- Construction
- The Protocol
- The Simulator
- Lower Bound
- The Random Termination Verifier Vk*
- Soundness of D
- References
- Simultaneously Resettable Arguments of Knowledge
- Introduction
- Resettably Sound rWI Arguments of Knowledge
- Formal Construction of simresWIAoK
- Security Proof
- Application in the BPK Model
- Simultaneously Resettable Identification Schemes
- References
- Dedicated Encryption II
- Subspace LWE
- Introduction
- Hard Learning Problems
- Notation
- The (Subspace) LWE Problem
- The Hardness of SLWE
- Applications
- Security against Related Key Attacks
- Weak Randomness and New Constructions
- References
- Bounded-Collusion IBE from Key Homomorphism
- Introduction
- Overview of the Techniques
- Other Related Work
- Preliminaries
- IND-CPA Security for Bounded-Collusion IBE
- Complexity Assumption
- Mapping Identities to Linearly Independent Vectors
- From PKE to Bounded Collusion IBE: General Conditions and Construction
- Linear Key Homomorphism
- Identity Map Compatibility
- Linear Hash Proof Property
- Construction
- Security
- QR-Based Construction
- Compatible Mapping and Resulting IBE Construction
- Security of the IBE
- Open Problems
- References
- A Unified Approach to Deterministic Encryption: New Constructions and a Connection to Computational Entropy
- Introduction
- Our Results
- Our Tools
- Preliminaries
- Deterministic Encryption
- Our Tools
- A Precise Definitional Equivalence for DE
- Measuring Computational Entropy of Induced Distributions
- A (Crooked) Leftover Hash Lemma for Correlated Distributions
- Encrypt-with-Hardcore Scheme from Robust HCFs
- Single-Message Instantiations of EwHCore
- Getting Robust Hardcore Functions
- Putting It Together
- Bounded Multi-message Security and its Instantiations
- The New Notion and Variations
- Our Basic Scheme
- Our Optimized Scheme
- References
- Pseudorandomness II
- A Dichotomy for Local Small-Bias Generators
- Introduction
- Easy, Sometimes Hard, and Almost Always Hard Predicates
- Our Results
- Why Polynomial Stretch?
- Why Small-Bias?
- Related Work
- Techniques and Ideas
- Fooling Light Tests
- Fooling Heavy Tests
- Proving Theorem 2
- Non-degenerate Predicates Are Hard
- Fooling Light Tests
- Fooling Heavy Tests
- Linear Tests Break Degenerate Predicates
- Small Bias vs. Cryptographic Security for Local Functions
- Robustness and Myopic Backtracking Algorithms
- References
- Randomness Condensers for Efficiently Samplable, Seed-Dependent Sources
- Introduction
- Definitions and Preliminaries
- Seed-Dependent Condensers
- Condensers from Collision Resistance
- Application to Key Derivation
- Simple Bound for Unpredictability Applications
- General Bound through Squared Advantage
- Side-Information and Fiat-Shamir
- References
- Uniqueness Is a Different Story: Impossibility of Verifiable Random Functionsfrom Trapdoor Permutations
- Introduction
- Our Results
- Overview of the Techniques
- Other Related Work
- Preliminaries
- The Black-Box Separation
- Towards the Definition of B
- The Formal Separation Theorem
- Insecurity of VUFs Relative to Our Oracles
- Security of ATDPs Relative to Our Oracles
- Defining the Simulator
- References
- Author Index
