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(Editor)

Springer (Publisher)

Published on 24. December 2015

XIII, 596 pages

E-Book

PDF with digital watermarking

System requirements

978-3-662-49099-0 (ISBN)

€53.49incl. 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 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

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Theory of Cryptography

Description

More details

Other editions

Additional editions

Content

System requirements