Theory of Cryptography

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

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

Eyal Kushilevitz Tal Malkin(Herausgeber*in)

Springer (Verlag)

Erschienen am 24. Dezember 2015

XIII, 596 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-662-49099-0 (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

Intro
Preface
TCC 2016-A
Contents - Part II
Contents - Part I
Zero Knowledge and PCP
Making the Best of a Leaky Situation: Zero-Knowledge PCPs from Leakage-Resilient Circuits
1 Introduction
1.1 Our Results and Techniques
2 Preliminaries
2.1 Circuit Compilers
2.2 Leakage-Resilient Circuit Compilers (LRCCs)
3 SAT-Respecting Relaxed LRCC
3.1 The Construction
3.2 A SAT-Respecting Relaxed LRCC over F2
3.3 Withstanding Leakage from AC 0 Circuits with Gates
4 WIPCPs and CZKPCPs
4.1 Distributed ZK and WI Proofs
A A Leakage-Indistinguishable Encoding Scheme
References
Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs
1 Introduction
1.1 Our Contributions
2 Preliminaries
2.1 Probabilistically Checkable Proofs
2.2 Probabilistically Checkable Proofs of Proximity
2.3 Zero Knowledge PCPs
2.4 Reed--Muller and Reed--Solomon Codes
3 Duplex PCPs
4 Main Theorem
4.1 Proof Sketch
4.2 Roadmap of the Rest of the Paper
5 Linear Algebraic CSPs and Their Canonical PCPs
5.1 Linear Algebraic Constraint Satisfaction Problems
5.2 A Canonical PCP for Linear Algebraic CSPs
6 Zero-Knowledge Duplex PCPs from Randomizable Linear Algebraic CSPs
6.1 Randomizable Linear Algebraic CSPs
6.2 Construction of Zero-Knowledge Duplex PCPs
7 From NTIME to Randomizable Linear Algebraic CSPs
7.1 Algebraic Problems and Group Preservation
7.2 Algebraic Problems Naturally Reduce to Linear Algebraic CSPs
7.3 From Group-Preserving Algebraic Problems to Randomizable Linear Algebraic CSPs
7.4 An Efficient Reduction from NTIME to Group-Preserving Algebraic Problems
7.5 Combining the Two Reductions
8 Proof of Theorem4
References
From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back
1 Introduction
1.1 Zero-Information Unambiguous Arthur-Merlin Communication Protocols
1.2 Private Simultaneous Message Protocols
1.3 ZAM vs. PSM
2 Our Results
2.1 From Perfect PSM to ZAM
2.2 From ZAM to One-Sided PSM
2.3 From 1PSM to PSM and CDS
3 Preliminaries
4 Definitions
4.1 PSM-Based Models
4.2 ZAM
5 From pPSM to ZAM
6 From ZAM to 1PSM
7 From 1PSM to PSM
References
A Transform for NIZK Almost as Efficient and General as the Fiat-Shamir Transform Without Programmable Random Oracles
1 Introduction
1.1 Our Results
1.2 Comparison
2 HVZK Proof Systems and -Protocols
2.1 3-Round Public-Coin HVZK Proofs and WI
2.2 Challenge Lengths of 3-Round HVZK Proofs
2.3 3-Round Public-Coin HVZK Proofs for or Composition of Statements
3 Non-Interactive Argument Systems
4 NIWI Argument Systems from 3-Round HVZK Proofs
5 Our Transform: NIZK from HVZK
6 Details on Some -Protocols
A Dual Mode Commitments and the Need for Strong -protocols
A.1 A Subtlety in Lindell's Construction: The Need of Strong -protocols
B An Optimal-Sound (and Not Special Sound) 3-Round Perfect Special HVZK Proof
References
Improved OR-Composition of Sigma-Protocols
1 Introduction
1.1 Our Contribution
1.2 Our Techniques
1.3 Discussion
1.4 Applications
1.5 Open Problems
2 Definitions
3 -Protocols
3.1 -protocols and Witness Indistinguishability
3.2 Or Composition of -protocols: the CDS-OR Transform
4 t-Instance-Dependent Trapdoor Commitment Schemes
5 Our New OR-Composition Technique
5.1 Witness Indistinguishability of Our Transform
6 Applications
References
Oblivious RAM
Onion ORAM: A Constant Bandwidth Blowup Oblivious RAM
1 Introduction
1.1 Server Computation in ORAM
1.2 Attempts to ``Break'' the Goldreich-Ostrovsky Lower Bound
1.3 Our Contributions
1.4 Related Work
2 Overview of Techniques
3 Bounded Feedback ORAM
3.1 Bounded Feedback ORAM Basics
3.2 New Triplet Eviction Procedure
4 Semi-honest Onion ORAM with an Additively Homomorphic Encryption
4.1 Additively Homomorphic Select Sub-protocol
4.2 Detailed Protocol
4.3 Bounding Layers
4.4 Remarks on Cryptosystem Requirements
5 Security Against Fully Malicious Server
5.1 Abstract Server-Computation ORAM
5.2 Semi-honest to Malicious Compiler
6 Optimizations and Analysis
6.1 Optimizations
6.2 Damgård-Jurik Cryptosystem
6.3 Asymptotic Analysis
6.4 Concrete Analysis (Semi-honest Case Only)
6.5 Other Optimizations and Remarks
7 Conclusion and Open Problems
A Definitions of Server-Computation ORAM
A.1 Security Definition
B Proofs
B.1 Bounded Feedback ORAM: Bounding Overflows
B.2 Onion ORAM: Bounding Layers of Encryption
B.3 Malicious Security Proof
References
Oblivious Parallel RAM and Applications
1 Introduction
1.1 Applications of OPRAM
1.2 Technical Overview
1.3 Related Work
2 Preliminaries
2.1 Parallel RAM (PRAM) Programs
2.2 Tree-Based ORAM
2.3 Sorting Networks
3 Oblivious PRAM
3.1 Rudimentary Solution: Requiring Large Bandwidth
3.2 Oblivious Routing, Aggregation, and Multi-cast
3.3 Putting Things Together
References
Oblivious Parallel RAM: Improved Efficiency and Generic Constructions
1 Introduction
1.1 Subtree-OPRAM
1.2 The Generic Transformation
2 Oblivious (Parallel) RAM
3 OPRAM with O(log2 N) Server Communication Overhead
3.1 Subtree-ORAM
3.2 Oblivious Inter-client Communication Protocols
3.3 Subtree-OPRAM
4 Generic OPRAM Scheme
4.1 Oblivious Dictionaries
4.2 The Generic OPRAM Protocol
A Correctness and Obliviousness of ORAM
B Review of Path-ORAM
C Analysis of Subtree-ORAM
D Analysis of Subtree-OPRAM
E Analysis of Generic-OPRAM
References
ABE and IBE
Déjà Q: Encore! Un Petit IBE
1 Introduction
1.1 Our Contributions
1.2 Our Techniques
1.3 Discussion
2 Preliminaries
2.1 Composite-Order Bilinear Groups and Cryptographic Assumptions
2.2 Anonymous Identity-Based Encryption
2.3 Broadcast Encryption
3 Identity-Based Encryption
3.1 Core Lemma
3.2 Our IBE Scheme
3.3 A Candidate Prime-Order Scheme
4 Broadcast Encryption
4.1 Overview
4.2 Our Broadcast Encryption Scheme
A Asymmetric Composite-Order Bilinear Groups
References
A Study of Pair Encodings: Predicate Encryption in Prime Order Groups
1 Introduction
2 Preliminaries
2.1 Predicate Encryption (PE)
3 Pair Encoding Schemes
3.1 Security
4 Dual System Groups
4.1 Syntax
4.2 Properties
5 Predicate Encryption from Pair Encodings
6 Proof of Security
7 Ciphertext-Policy ABE
7.1 Pair Encoding Scheme
7.2 Relaxed Perfect Security
7.3 Instantiation: Constant-Size Ciphertext
References
Codes and Interactive Proofs
Optimal Amplification of Noisy Leakages
1 Introduction
1.1 Our Contributions
1.2 A High-Level Proof Outline
1.3 Our Techniques
2 Preliminaries
3 Our Main Result
3.1 Proof of Theorem 1
4 Lower Bounds
A Proofs
A.1 Proof of Proposition 1
A.2 Proof of Proposition 2
A.3 Proof of Lemma 2
A.4 Proof of Lemma 3
A.5 Proof of Lemma 4
A.6 Proof of Theorem 2
A.7 Proof of Lemma 6
A.8 Harmonic Analysis
References
Rational Sumchecks
1 Introduction
1.1 Our Results
1.2 Comparison to Alternative Delegation Schemes
1.3 Other Related Work
2 Preliminaries
3 Rational Sumcheck Protocols
4 Composition of Classical and Rational Interactive Proofs
4.1 Substituting Oracle by Rational Proof in Interactive Proof
4.2 Substituting Oracle by Rational Multi-prover Proof in Multi-prover Proof
5 Rational Delegation for NC
5.1 The Protocol of Goldwasser, Kalai and Rothblum [15]
5.2 Single-Round Rational Arguments for NC
6 Rational Delegation for P
6.1 The Protocol of Kalai, Raz and Rothblum [19]
6.2 No-Signaling Rational Multi-prover Proofs for Deterministic Computations
6.3 Single-Round Rational Arguments for P
A Building Blocks
References
Interactive Coding for Interactive Proofs
1 Introduction
2 Resilient Interactive Protocols
3 Backtracking-Resilient Protocols
4 Compiling Backtracking-Resilient Protocols Against Adversarial Channel Errors
5 Analysis of the Compiled Algorithms
5.1 Completeness
5.2 Soundness
6 Conclusions and Open Problems
References
Information-Theoretic Local Non-malleable Codes and Their Applications
1 Introduction
1.1 Results
1.2 Techniques
1.3 Organization of the Paper
2 Preliminaries
2.1 Notation
2.2 Definitions
3 Non-malleable Codes with O"0365O(k) Locality Against Fsplit4
4 Non-malleable Codes with O() Locality Against Fhalf
4.1 Quoted Non-malleability
4.2 Achieving Full Non-malleability
5 Updatability and Security Against Continual Attacks
6 Applications of Local Non-malleable Codes
References
Optimal Computational Split-state Non-malleable Codes
1 Introduction
1.1 Technical Overview
1.2 Prior Work
2 Preliminaries
2.1 Non-malleable Codes in the Split-State Model
2.2 Building Blocks
3 Our Construction
3.1 Proof of Non-malleability
4 Proof of Theorem 1
5 Necessity of One-Way Functions
References
Limitations of Obfuscation and Obfuscation-Avoiding Constructions
How to Avoid Obfuscation Using Witness PRFs
1 Introduction
1.1 Motivating Example: Non-interactive Key Exchange Without Setup
1.2 Our Contributions: Witness PRFs
1.3 Techniques
1.4 Directions for Future Work
1.5 Other Related Work
2 Preliminaries
2.1 Subset-Sum
2.2 Multilinear Maps
3 Witness PRFs
3.1 Security
4 An Abstraction: Subset-Sum Encoding
4.1 A Simple Instantiation from Multilinear Maps
4.2 Witness PRFs from Subset-Sum Encodings
5 Applications
5.1 CCA-secure Public Key Encryption
5.2 Non-interactive Multiparty Key Exchange
References
Cutting-Edge Cryptography Through the Lens of Secret Sharing
1 Introduction
1.1 Overview of Our Techniques
2 Preliminaries
2.1 Monotone-NP and Access Structures
2.2 Commitment Schemes
2.3 Multilinear Maps
2.4 Witness Pseudorandom Functions
2.5 Indistinguishability Obfuscation
3 Distributed Secret Sharing
3.1 Alternative Definitions
3.2 Distributed Secret Sharing Implies One-Way Functions
3.3 Distributed Secret Sharing for Threshold
3.4 Distributed Secret Sharing Is Equivalent to Witness PRFs
4 Functional Secret Sharing
4.1 Functional Secret Sharing Is Equivalent to iO
References
Functional Encryption Without Obfuscation
1 Introduction
1.1 Our Results
1.2 Overview of Our Techniques
1.3 Instantiating Our Assumptions
1.4 Independent Work
1.5 Subsequent Work
2 Preliminaries: Graded Encoding Schemes
3 Additional Background
3.1 Adaptively Secure FE
3.2 Branching Programs
4 Slotted Functional Encryption
4.1 Core Predicates
4.2 Additional Derivable Predicates
4.3 Reductions
5 Slotted Functional Encryption for NC1
5.1 Security Proof
5.2 Adaptively Secure FE for NC1
References
On Constructing One-Way Permutations from Indistinguishability Obfuscation
1 Introduction
1.1 Our Contributions
1.2 Related Work
1.3 Overview of Our Results
1.4 Paper Organization
2 Preliminaries
2.1 Oracle-Aided One-Way Permutation Families
2.2 Indistinguishability Obfuscation for Oracle-Aided Circuits
3 Impossibility for Constructions Based on iO and One-Way Functions
3.1 The Class of Constructions
3.2 Proof Overview and the Oracle
3.3 Attacking Domain-Invariant Permutation Families Relative to
3.4 Proof of Theorem 3.3
4 Impossibility for Constructions Based on One-Way Functions
References
Contention in Cryptoland: Obfuscation, Leakage and UCE
1 Introduction
1.1 VGBO and AI-DHI
1.2 Key-Message Leakage Resilience
1.3 UCE for Split Sources
1.4 Discussion and Related Work
2 Preliminaries
3 VGBO and the AI-DHI Assumption
4 KM-Leakage Resilient Encryption
5 UCE for Split Sources
References
Point-Function Obfuscation: A Framework and Generic Constructions
1 Introduction
1.1 The State of Point-Function Obfuscation
1.2 Contributions in Brief
1.3 Definitional Framework
1.4 Generic Constructions
1.5 Alternative Notions and Relations Between Notions
1.6 Discussion and Further Related Work
2 Notation and Standard Definitions
3 Point-Function Obfuscation Framework
4 (d)iO for Multi-circuit Samplers
5 Generic Constructions of PO
5.1 PO from iO
5.2 PO from DPKE
5.3 PO from UCE
6 Alternative Security Notions for PO
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken