Theory of Cryptography

Name: Theory of Cryptography | 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings

Ronald Cramer(Herausgeber*in)

Springer (Verlag)

1. Auflage

Erschienen am 5. März 2012

672 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-28914-9 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken