Theory of Cryptography

Name: Theory of Cryptography | 13th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10-13, 2016, Proceedings, Part I
Brand: Springer
Price: 96.29 EUR
Availability: OnlineOnly

13th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10-13, 2016, Proceedings, Part I

Eyal Kushilevitz Tal Malkin(Editor)

Springer (Publisher)

Published on 21. December 2015

XIV, 618 pages

E-Book

PDF with digital watermarking

System requirements

978-3-662-49096-9 (ISBN)

€96.29incl. 7% vat

System requirements

for PDF with digital watermarking

E-Book Single Licence

Available for download

Description

More details

Other editions

Content

Intro
Preface
TCC 2016-A
Contents - Part I
Contents - Part II
Obfuscation: Impossibility Results and Constructions
Impossibility of VBB Obfuscation with Ideal Constant-Degree Graded Encodings
1 Introduction
2 Definitions and Preliminaries
2.1 Virtual Black-Box Obfuscation
2.2 Idealized Graded Encodings
3 Impossibility of VBB Obfuscation
4 Impossibility of Subexponential VBB Security
References
On the Impossibility of Virtual Black-Box Obfuscation in Idealized Models
1 Introduction
1.1 Our Results
1.2 Technical Overview
2 Virtual Black-Box Obfuscation
3 Impossibility of VBB in Generic Algebraic Models
3.1 Preliminaries
3.2 Generic Group Model
3.3 Degree-O(1) Graded Encoding Model
4 Impossibility of VBB in the Random TDP Model
4.1 The Construction
4.2 Completeness and Soundness
4.3 Extension to Hierarchical Random TDP
References
Lower Bounds on Assumptions Behind Indistinguishability Obfuscation
1 Introduction
1.1 Our Results
2 Preliminaries
2.1 Black-Box Constructions
2.2 Indistinguishability Obfuscation
2.3 Generic/Idealized Models
3 Separating iO from Random Oracle Based Primitives
4 Hardness of Semi-Black-Box Constructions of iO
4.1 Proving Theorem ??
A Omitted Proofs
References
Indistinguishability Obfuscation: From Approximate to Exact
1 Introduction
1.1 Our Results
1.2 Overview of Our Techniques
2 Preliminaries
2.1 Non-interactive Secure Function Evaluation
2.2 Symmetric Encryption
2.3 Puncturable Pseudorandom Functions
3 Correcting Errors in Indistinguishability Obfuscation
3.1 Approximate and Exact IO
3.2 The Transformation
3.3 Instantiating the Scheme
4 Correcting Errors in Functional Encryption
4.1 Approximate and Exact FE
4.2 The Transformation
4.3 Instantiating the Scheme
5 An Alternative Transformation for IO Based on FE
5.1 Approximate FE from Approximate IO
5.2 FE to IO
References
Output-Compressing Randomized Encodings and Applications
1 Introduction
1.1 Our Results
2 Preliminaries
2.1 Concrete Security
2.2 Standard Cryptographic Primitives
2.3 Indistinguishability Obfuscation
2.4 Functional Encryption
3 Randomized Encoding Schemes
3.1 Distributional Indistinguishability Security
3.2 Compactness and Sublinear Compactness
4 Unbounded-Input IO from Compact RE
4.1 Security Proof
4.2 Nice Distributions
5 Bounded-Input IO from Compact RE in the CRS Model
5.1 Randomized Encoding Schemes in the CRS Model
5.2 Succinctness and Weak-Compactness
5.3 Randomized Encodings with CRS from Compact Functional Encryption
5.4 IO for Circuits from RE in the CRS Model
5.5 Summary of Results Using RE in the CRS Model
6 Impossibility of Compact RE
References
Functional Encryption for Turing Machines
1 Introduction
2 Preliminaries
2.1 Functional Encryption for Turing Machines
2.2 (Compact) FE for Circuits
3 Adaptive 1-Key 1-Ciphertext FE for TMs
3.1 Semi-Adaptive 2-Ary FE for TMs: 1-Key 1-Ciphertext Setting
3.2 Adaptive FE from Semi-adaptive 2-Ary FE for TMs
3.3 Constructing Semi-adaptive 2-Ary FE for TMs: Overview
4 Adaptive FE for TMs
5 Proof of Theorem : Overview
6 Future Directions
A Tools Used in
A.1 Positional Accumulators
A.2 Iterators
A.3 Splittable Signatures
References
Differential Privacy
The Complexity of Computing the Optimal Composition of Differential Privacy
1 Introduction
1.1 Our Results
2 Technical Preliminaries
3 Characterization of OptComp
4 Hardness of OptComp
5 Approximation of OptComp
References
Order-Revealing Encryption and the Hardness of Private Learning
1 Introduction
1.1 Differential Privacy and Private Learning
1.2 Our Techniques
1.3 Order-Revealing Encryption
1.4 Related Work
2 Preliminaries and Definitions
2.1 PAC Learning and Private PAC Learning
2.2 Order-Revealing Encryption
3 The Concept Class EncThresh and Its Learnability
3.1 An Efficient PAC Learner for EncThresh
3.2 Hardness of Privately Learning EncThresh
3.3 The SQ Learnability of EncThresh
4 ORE with Strong Correctness
4.1 Conversion from Weakly Correct ORE
5 A Separation for Representation Learning
References
LWR and LPN
On the Hardness of Learning with Rounding over Small Modulus
1 Introduction
1.1 Learning with Rounding
1.2 Our Results
2 One-Wayness of LWR
2.1 Proof of Theorem 1
2.2 Hardness over Rings
3 Pseudorandomness of LWR
3.1 Predicting the Inner Product
3.2 Learning the Secret
3.3 Proof of Theorem 3
3.4 Rerandomizing the Secret
4 Equivalence of LWR and LWE with Uniform Errors
5 Noise Flooding
A Proof of Lemma 2
References
Two-Round Man-in-the-Middle Security from LPN
1 Introduction
2 Preliminaries
3 Generic Construction
3.1 Tools
3.2 The Generic Construction
3.3 Security
4 Instantiations
4.1 Instantiations from LPN
4.2 Instantiations from Field-LPN
4.3 Instantiations from Weak PRFs
4.4 Instantiation from DDH
A Omitted Proofs
A.1 Proof of Theorem 7
A.2 Proof of Theorem 9
References
Public Key Encryption, Signatures, and VRF
Algebraic Partitioning: Fully Compact and (almost) Tightly Secure Cryptography
1 Introduction
2 Preliminaries
3 The Signature Scheme
3.1 Scheme Description
3.2 Security Analysis
4 Compact and (almost) Tightly Secure Public-Key Encryption
5 Details on the Exact Groth-Sahai Equations in Our Schemes
5.1 The Exact Groth-Sahai Equations for the Proofs in Signatures
5.2 The Exact Groth-Sahai Equations for the Proofs in Ciphertexts
A Illustration of proof strategy for Theorem ??
References
Standard Security Does Imply Security Against Selective Opening for Markov Distributions
1 Introduction
1.1 Our Contributions
1.2 Previous Work
2 Preliminaries
2.1 Games
2.2 Public-Key Encryption Schemes
2.3 IND-CPA and Mult-IND-CPA Security
2.4 IND-SO-CPA Security
3 Selective Opening for Graph-Induced Distributions
3.1 Graphs
3.2 A Bound Using Connected Subgraphs
3.3 A Bound Using the Maximum Border
3.4 A Tighter Reduction for Acyclic Graphs
3.5 A Hybrid Argument for Disconnected Graphs
References
Non-Malleable Encryption: Simpler, Shorter, Stronger
1 Introduction
2 Preliminaries
3 Non-Malleability Under Self-Destruct Attacks
4 Domain Extension
4.1 A New Flavor of Non-Malleable Codes
4.2 Combining Single-Bit PKE and Non-Malleable Codes
4.3 Non-Malleable Code Construction
4.4 Proof of the Non-Malleable Code Construction
4.5 LECSS for the Non-Malleable Code
4.6 Impossibility for Codes Without State
5 Construction from CPA Security
5.1 The CDMW Construction
5.2 Security Proof of the CDMW Construction
5.3 LECSS for the CDMW Construction
6 A General Indistinguishability Paradigm
References
Verifiable Random Functions from Standard Assumptions
1 Introduction
2 Certified Bilinear Group Generators
3 Programmable Vector Hash Functions
3.1 Vector Hash Functions
3.2 Selective Programmability
3.3 Adaptive Programmability
4 A PVHF Based on the Matrix-DDH Assumption
4.1 The Construction
4.2 Selective Security
4.3 Adaptive Security
5 VRFs from Verifiable PVHFs
5.1 A Generic Construction from Verifiable PVHFs
5.2 Correctness, Unique Provability, and Pseudorandomness
A The Need for an Artificial Abort
References
Complexity of Cryptographic Primitives
Homomorphic Evaluation Requires Depth
1 Introduction
2 Definitions
3 Homomorphic Evaluation Requires Depth
4 On CPA-Secure Encryption Schemes in AC0
References
On Basing Private Information Retrieval on NP-Hardness
1 Introduction
1.1 Our Techniques
1.2 Related Work
2 Definitions
2.1 Information Theory Background
2.2 Single-Server One-Round Private Information Retrieval
2.3 Entropy Difference
3 PIR and NP-Hardness
3.1 Proof of the Main Theorem
3.2 Proof of Lemma??
4 Discussion and Open Questions
References
Obfuscation-Based Cryptographic Constructions
On the Correlation Intractability of Obfuscated Pseudorandom Functions
1 Introduction
1.1 Our Results
1.2 Our Techniques
1.3 More on Input-Hiding Obfuscation for Evasive Functions
1.4 More on Related Work
2 Preliminaries
2.1 Obfuscation
2.2 Puncturable Pseudorandom Functions
3 Correlation Intractability
4 Bounded Correlation Intractability from Obfuscating Puncturable PRF
A Correlation Intractability Versus Other Notions
A.1 Relations with Entropy-Preserving Hashing
A.2 Separations Between Correlation Intractability and Other Notions
References
Reconfigurable Cryptography: A Flexible Approach to Long-Term Security
1 Introduction
2 Preliminaries
3 Definitions
4 Constructions
4.1 Reconfigurable Encryption from Indistinguishability Obfuscation
4.2 Reconfigurable Encryption from SCasc
5 Reconfigurable Signatures
5.1 Preliminaries
5.2 Definitions
5.3 Reconfigurable Signatures from Groth-Sahai Proofs
References
Multilinear Maps from Obfuscation
1 Introduction
1.1 Main Contribution
1.2 General Approach
1.3 Attacks on Multilinear Maps
1.4 Related Work
2 Background
2.1 Homomorphic Public-Key Encryption
2.2 Obfuscators
2.3 Dual-Mode NIZK Proof Systems
2.4 Hard Membership Problems
3 Multilinear Groups with Non-unique Encodings
4 The Construction
4.1 Setup
4.2 Validity and Equality
4.3 Group Operations
4.4 The Multilinear Map
4.5 Sampling and Extraction
5 Indistinguishability of Encodings
5.1 Using Probabilistic Indistinguishability Obfuscation
5.2 Doing Without Probabilistic Obfuscation
6 The Multilinear DDH Problem
6.1 Intractable Problems
6.2 The Symmetric Setting
6.3 The Asymmetric Setting
7 The Rank Problem
7.1 Formalization of the Problem
7.2 The RANK Problem with Our MLG Scheme
7.3 Proof Intuition
References
Perfect Structure on the Edge of Chaos
1 Introduction
1.1 This Work
1.2 Technical Overview
2 Preliminaries
2.1 Indistinguishability Obfuscation
2.2 Puncturable Pseudorandom Functions
2.3 Injective One-Way Functions
3 Injective One-Way Functions from iO
3.1 Sometimes Injective One-Way Functions
3.2 Injective OWFs from iO and SIOWFs
4 Trapdoor Permutations from iO
4.1 Standard TDPs
4.2 Enhanced TDPs
4.3 Doubly Enhanced TDPs
4.4 Relaxing Subexponential Security
A On Non-interactive Commitments from iO
References
Cryptographic Assumptions (Invited Talk followed by Panel)
Cryptographic Assumptions: A Position Paper
1 Introduction
2 Our Classification
2.1 Search Complexity Assumptions
2.2 Decisional Complexity Assumptions
2.3 Worst-Case vs. Average-Case Hardness
2.4 Search versus Decision Complexity Assumptions
2.5 Concrete versus Generic Assumptions
2.6 Falsifiability of Complexity Assumptions
2.7 Desirable Properties of Complexity Assumptions
3 Recently Proposed Cryptographic Assumptions
4 Summary
A Falsifiable Assumptions
References
Multiparty Computation
Adaptive Security with Quasi-Optimal Rate
1 Introduction
1.1 Our Contribution
1.2 Our Construction
2 Preliminaries
2.1 Notation
2.2 Non-Committing Encryption
2.3 Learning with Errors
2.4 Error Correcting Codes
2.5 The Binomial and Hypergeometric Distributions
3 Non-Committing Encryption from LWE
3.1 The Basic Scheme
3.2 Correctness and Real World Subsets
3.3 The Simulator
3.4 Proof of Security
References
On the Complexity of Additively Homomorphic UC Commitments
1 Introduction
2 The Protocol
2.1 Protocol HCOM
2.2 Optimizations over [CDD15]
2.3 Protocol Extension
3 Security
4 Comparison with Recent Schemes
A Protocol Extension
References
Simplified Universal Composability Framework
1 Introduction
1.1 Contribution
1.2 Related Work
2 Interactive Turing Machines
3 Graph of Interactive Turing Machines
4 Entities of Models
5 Real Free Models
6 Ideal Free Models
7 Hybrid Free Models
8 Environments and Models
9 Classes of Adversaries
10 Simplified Notation
11 Definition of Security
12 Universal Composition Theorem
13 Transforms of Models
14 Relation to Other Security Frameworks
A Transforms of Models
A.1 Faithful Transforms of ITM Graphs
A.2 Simulating Multiple Interactive Turing Machines
A.3 Simulate Multiple Links
A.4 Redundant Communication Models
A.5 Transforms of Models
A.6 Adversary Converter
References
Characterization of Secure Multiparty Computation Without Broadcast
1 Introduction
1.1 Our Result
1.2 Our Technique
1.3 Additional Related Work
1.4 Open Questions
2 Preliminaries
2.1 Notations
2.2 Protocols
3 Attacking Consistent Protocols
4 Impossibility Results for Secure Computation
4.1 Symmetric Functionalities Secure According to the Real/Ideal Paradigm
4.2 Coin-Flipping Protocols
5 Characterizing Secure Computation Without Broadcast
5.1 No Honest Majority
5.2 Honest Majority
References
Author Index

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Theory of Cryptography

Description

More details

Other editions

Additional editions

Content

System requirements