Advances in Cryptology - CRYPTO 2023

Name: Advances in Cryptology - CRYPTO 2023 | 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part II
Brand: Springer
Price: 117.69 EUR
Availability: OnlineOnly

43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part II

Helena Handschuh Anna Lysyanskaya(Herausgeber*in)

Springer (Verlag)

Erschienen am 8. August 2023

XIX, 792 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-031-38545-2 (ISBN)

117,69 €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
Organization
Contents - Part II
Succinctness
Revisiting Cycles of Pairing-Friendly Elliptic Curves
1 Introduction
1.1 Avoiding Non-native Arithmetic with Cycles
1.2 State of the Art
1.3 Contributions and Organization
2 Pairing-Friendly Elliptic Curves
2.1 Elliptic Curves
2.2 Pairing-Friendly Polynomial Families
3 Cycles of Elliptic Curves
3.1 Definition and Known Results
3.2 Some Properties of Cycles
4 Cycles from Known Families
4.1 Cycles from Parametric-Families
4.2 2-cycles from Parametric Families
5 Density of Pairing-Friendly Cycles
6 Conclusions
A Polynomial Division
B Tables
C SageMath Code
References
Non-interactive Zero-Knowledge from Non-interactive Batch Arguments
1 Introduction
1.1 Technical Overview
2 Preliminaries
2.1 Non-Interactive Zero-Knowledge Arguments for NP
2.2 Non-Interactive Batch Arguments for NP
2.3 Hidden-Bits Generator
3 Hidden-Bits Generator from Batch Arguments
References
Lattice-Based Succinct Arguments from Vanishing Polynomials
1 Introduction
1.1 Our Results
1.2 Related Work
1.3 Subsequent Work
2 Technical Overview
2.1 Vanishing-SIS Commitments
2.2 Efficient Proofs for SIS Relations
2.3 Applications
3 Preliminaries
3.1 Cyclotomic Rings
3.2 Lattice Trapdoors
3.3 Presumed Hard Problems
3.4 Argument Systems
4 Vanishing Short Integer Solutions
4.1 Definition
4.2 On Choice of Parameters
4.3 A Family of Hash Functions with Short Keys
5 Foldable Structures
6 Folding Protocols
6.1 Type-0 Linear Relations
6.2 Type-1 Linear Relations
7 Knowledge-Based Protocols
7.1 Linear Relations
7.2 Well-Formedness of vSIS Commitments
8 Applications
8.1 Proving Binary-Satisfiability of (Structured) Linear Equations
8.2 Rank-1 Constraint Systems
References
Orbweaver: Succinct Linear Functional Commitments from Lattices
1 Introduction
1.1 Our Results
1.2 Related Work
1.3 Technical Overview
2 Preliminaries
2.1 Functional Commitments
2.2 Sampling Algorithm
2.3 Cryptographic Assumptions
3 Cryptanalysis of k-P-R-ISIS
4 Orbweaver: Linear Map Commitments for rings
4.1 Extensions
5 Linear Map Commitments for ZM
5.1 Polynomial Commitments for integers mod p
6 Evaluation
6.1 Optimizations
6.2 Proof and CRS Sizes
References
Non-interactive Universal Arguments
1 Introduction
1.1 Results
1.2 Technical Overview
2 Preliminaries
2.1 Homomorphic Encryption
2.2 Non-interactive Arguments for Deterministic Computations
2.3 Incrementally Verifiable Computation
2.4 Average-Case Puzzles
3 Universal Lifting
3.1 Incrementally Verifiable Computation Lifting
4 Constructing Average-Case Puzzles
4.1 Worst-Case Hardness Assumptions
4.2 Average-Case Puzzles from FHE
References
Succinct Arguments for RAM Programs via Projection Codes
1 Introduction
1.1 Black-Box Succincts Argument for RAM Programs
1.2 Projection Codes
1.3 Related Work
2 Overview of Techniques
2.1 Projection Codes
2.2 Holographic PCPs for RAM Programs
2.3 Succinct Arguments for RAM Programs
3 Preliminaries
3.1 Model of Computation
3.2 Encoding Scheme
3.3 Probabilistically Checkable Proofs of Proximity (PCPPs)
4 Projection Codes
4.1 Constructing Projection Codes
4.2 Instantiations
5 Holographic PCPs for RAM Programs
5.1 Holographic PCPs for Subsets
5.2 Holographic PCPs for RAM Programs
6 Succinct Arguments for RAM Programs
References
Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS
1 Introduction
1.1 Results and Contributions
2 Preliminaries
3 Linear-Time Polynomial Commitments
3.1 Polynomial Commitments for t=2
4 Fast Linear Codes with Linear-Time Encoding
5 Linear-Time SNARKs for R1CS
5.1 A Self-contained Description of Brakedown and Shockwave
6 Implementation and Evaluation
6.1 Evaluation of Polynomial Commitment Schemes
6.2 Evaluation of Brakedown and Shockwave SNARKs
References
Lattice-Based Succinct Arguments for NP with Polylogarithmic-Time Verification
1 Introduction
1.1 Our Results
1.2 Related Work
2 Techniques
2.1 Our Approach
2.2 Polynomial Commitments from Sumcheck Arguments
2.3 Warmup: Delegation over Bilinear Groups
2.4 Leveled Bilinear Modules
2.5 Delegation over Leveled Bilinear-Module Systems
2.6 Polynomial IOP for Product Rings
2.7 Final Protocol: Combining Polynomial Commitments and PIOP
References
SNARGs for Monotone Policy Batch NP
1 Introduction
1.1 Our Results
2 Our Techniques
2.1 The Canonical Protocol
2.2 Enforcing Global Properties with Predicate Extractable Hashing
2.3 New SNARG Construction
2.4 Achieving Somewhere Extractability
2.5 Shortening the CRS
3 Preliminaries
3.1 Hash Family with Local Opening
3.2 Fully Homomorphic Encryption
3.3 Somewhere Extractable Batch Arguments (seBARGs)
3.4 RAM SNARGs
4 SNARGs for Monotone Policy BatchNP
4.1 Definition
5 Predicate Extractable Hash Families
5.1 Syntax and Basic Properties
5.2 Extractable Hash for Bit-Fixing Predicates
5.3 Extractable Hash with Tags for Bit-Fixing Predicates
6 Non-Adaptive SNARG Construction
6.1 Analysis
References
TreePIR: Sublinear-Time and Polylog-Bandwidth Private Information Retrieval from DDH
1 Introduction
1.1 Client-Preprocessing PIR
1.2 Our Contribution
1.3 Related Work
1.4 Notation
1.5 Paper Outline
2 Preliminaries
2.1 Security Definitions for PIR
2.2 Pseudorandom Generators (PRGs) and Pseudorandom Functions (PRFs)
2.3 The GGM PRF Construction and Puncturing
3 Weak Privately Puncturable PRFs
3.1 A wpPRF Construction
4 Applying wpPRFs to PIR
4.1 Constructing Pseudorandom Sets from wpPRFs
4.2 Our TreePIR Scheme
4.3 Sublinear Time, Polylog Bandwidth PIR from the DDH Assumption
4.4 Tuning Efficiencies in TreePIR
5 Performance
5.1 TreePIR with No Recursion
5.2 Recursing to Improve Bandwidth
5.3 Supporting Changing Databases
A Further Optimizations
A.1 Deterministic Client Time
A.2 Generalizing TreePIR to More Flexible Database Sizes
References
Multi-party Homomorphic Secret Sharing and Sublinear MPC from Sparse LPN
1 Introduction
1.1 Our Results
1.2 Related Work
2 Technical Overview
2.1 HSS Construction
2.2 Arguing KDM Security
2.3 Sublinear MPC Construction
3 Preliminaries
3.1 Linear Secret Sharing Schemes
3.2 Homomorphic Secret Sharing
4 Sparse LPN
4.1 KDM Security
5 HSS Construction
5.1 Scheme Description
5.2 Security Analysis
6 Sublinear MPC
6.1 Protocol Description
References
Anonymous Credentials
Lattice Signature with Efficient Protocols, Application to Anonymous Credentials
1 Introduction
1.1 Related Works
1.2 Our Contributions
2 Preliminaries
2.1 Lattices
2.2 Probabilities
2.3 Hardness Assumption
2.4 Signature Scheme
3 A Lattice-Based Signature Scheme
3.1 Description of the Signature
3.2 Security of the Signature
3.3 Our Signature on Modules
4 Zero-Knowledge Arguments of Knowledge
4.1 A Framework for Quadratic Relations over Zq
4.2 Zero-Knowledge Fast Mode Revisited
4.3 Zero-Knowledge Arguments and Relations
5 Privacy-Preserving Protocols and Anonymous Credentials
5.1 Oblivious Signing Protocol
5.2 Message-Signature Pair Possession Protocol
5.3 Application to Anonymous Credentials
References
A Framework for Practical Anonymous Credentials from Lattices
1 Introduction
1.1 Blind Signatures and Anonymous Credentials from ISISf
1.2 Related Work
1.3 Concurrent Work
1.4 Discussion and Open Problems
2 Preliminaries
2.1 NTRU Lattices
2.2 Module-SIS and Module-LWE Problems
2.3 Non-interactive Zero-Knowledge Proofs in the ROM
3 The ISISf Assumption
3.1 Concrete Instantiations of f
3.2 Interactive Version
3.3 Applications to Exotic Signatures
References
Anonymous Tokens with Stronger Metadata Bit Hiding from Algebraic MACs
1 Introduction
2 PMBT: A Case Study
2.1 AT Interface and Security
2.2 Potential Attack for PMBT
3 Anonymous Tokens Revisited
3.1 AT Interface
3.2 Unforgeability
3.3 Unlinkability
3.4 Privacy of the Metadata Bit
4 ATHM: Anonymous Tokens with Hidden Metadata
4.1 The ATHM Components
4.2 The MAC Building Block
4.3 The Simulatable Proof Building Block
5 Performance
6 Security Proof for ATHM in the Generic Group Model
6.1 OMUF Security in GGM and ROM
6.2 UNLINK Security in GGM and ROM
6.3 PMB Security in GGM and ROM
7 Conclusion
References
New Paradigms and Foundations
Revisiting Time-Space Tradeoffs for Function Inversion
1 Introduction
1.1 Our Results
1.2 Our Techniques
1.3 Related Work
1.4 A Note on the Many Facets of Function Inversion
2 Preliminaries
2.1 Definitions of Function Inversion Problems
2.2 Some Basic Probability Results
2.3 Binary Linear Codes
3 An Improvement to Fiat and Naor's Algorithm
3.1 The Algorithm
3.2 Analysis
4 A Lower Bound Against Guess-and-check Non-adaptive Algorithms
5 Comparing Variants of Function Inversion
5.1 Search-to-decision Reduction for Arbitrary Functions
5.2 Search-to-decision Reduction for Average-Case Functions
6 Removing Shared Randomness
References
The Query-Complexity of Preprocessing Attacks
1 Introduction
2 Preliminaries
3 Offline-Online Trade-offs and the Role of Salting
3.1 A General Framework for Offline-Online Attacks
3.2 The Power of Salting
4 Offline-Online Security of Salted Random Oracles
4.1 Pre-image-resistance of a Salted Random Oracle
4.2 Collision-Resistance of a Salted Random Oracle
5 Offline-Online Security of Two-Block Merkle-Damgård
5.1 Pre-image-resistance of Two-Block Merkle-Damgård
5.2 Collision-Resistance of Two-Block Merkle-Damgård
5.3 Proof of Lemma 4
5.4 Proof of Lemma 5
5.5 Proof of Lemma 6
References
Random Oracle Combiners: Breaking the Concatenation Barrier for Collision-Resistance
1 Introduction
1.1 Our Results
1.2 Related Work
2 Preliminaries
2.1 Hash Combiners
2.2 Alternative Models
2.3 Notation
3 Indifferentiability and Hash Combiners
3.1 On Composability of Random-Oracle-Security
4 Random-Oracle-Secure Hash Combiner Construction
4.1 Remarks on Parameters
4.2 Our Security Proof is Tight
4.3 Random-Oracle-Secure Combiners Need Randomness
4.4 Proof of Lemma 2
5 Extensions to Arbitrary Length
5.1 The Merkle-Damgård Transformation
5.2 Arbitrary Length Construction
5.3 A Note on Parameters
5.4 A Prefix Attack on Merkle-Damgård Hash Functions
6 A Short Collision Resistant Hash Function Combiner
6.1 Collision Resistance Definitions
6.2 Merkle-Damgård Yields Collision Resistance
6.3 Proof of Theorem 9
6.4 Proof of Lemma 3
7 Conclusion
7.1 Recommendations for Practice
7.2 Alternative One-stage Model
7.3 Open Questions
References
Individual Cryptography
1 Introduction
1.1 Informal Description of Our Model
1.2 Informal Description of PIK
1.3 Informal Description of ISS
1.4 Related Work
2 Preliminaries
3 The Model
4 Proofs of Individual Knowledge
4.1 Definition
4.2 Construction
4.3 Proof of Theorem 1
4.4 Extensions
5 Individual Secret Sharing
5.1 Standard Secret Sharing
5.2 ISS and IRSS Definitions
5.3 IRSS Construction
5.4 ISS Construction
5.5 Concrete Examples
6 Conclusion
References
Extractors: Low Entropy Requirements Colliding with Non-malleability
1 Introduction
2 Technical Overview
2.1 Collision Resistant Extractors
2.2 Our Non-malleable Extractor Compiler
3 Preliminaries
3.1 Random Variables, Statistical Distance and Entropy
3.2 Min-Entropy
3.3 Extractors
4 A Generic Construction of a Two-Source Non-malleable Extractor
5 Collision Resistance of Extractors
5.1 Generic Collision Resistance for Seeded Extractors
5.2 Collision Resistance of the Raz Extractor
6 A Fully Non-malleable Seeded Extractor
7 A Two-Source Non-malleable Extractor
8 A Two-Source Non-malleable Extractor with Rate 12
References
PAC Privacy: Automatic Privacy Measurement and Control of Data Processing
1 Introduction
2 PAC Privacy
3 Foundation of PAC Privacy
4 Automatic Control of Mutual Information
4.1 Deterministic Mechanism
4.2 Randomized Mechanism
4.3 Towards Optimal Perturbation
5 Composition
6 Comparison Between Adversarial and Instance-based Worst Case
7 Related Works
7.1 Differential Privacy
7.2 Other Privacy Metrics and Learning Theory Quantities
8 Conclusions and Prospects
References
One-Way Functions and the Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions
1 Introduction
1.1 Our Results
1.2 Proof Overview
2 Preliminaries
2.1 One-Way Functions
2.2 Time-Bounded Kolmogorov Complexity
2.3 Average-Case Complexity
3 Theorems
4 OWFs from Hardness of MpKpolyP w.r.t. Any Samplable Distribution
4.1 When D Is Polynomially Bounded
4.2 Bounding Any Samplable Distribution
5 Hardness of MpKpolyP w.r.t. Uniform from OWFs
5.1 Some Additional Preliminaries
5.2 Entropy-Preserving PRGs
5.3 Hardness of MpKtP and MKtP from Cond EP-PRG
A An Alternative Proof of Lemma 46 and Lemma 48
References
Universal Amplification of KDM Security: From 1-Key Circular to Multi-Key KDM
1 Introduction
1.1 Overview
1.2 Extensions and Comparisons
2 Preliminaries
2.1 Garbled Circuits
2.2 KDM Security Definitions
3 Amplifying KDM
3.1 Security
3.2 Symmetric-Key Setting
References
Improved Multi-user Security Using the Squared-Ratio Method
1 Introduction
2 Preliminaries
2.1 Security Notions
2.2 Total Variation Distance, KL Divergence and Chi-Squared Divergence in a Subspace
2.3 Useful Lemma
3 The Squared-Ratio Method
4 Upper Bounds from Mirror Theory
5 Multi-user Security of XoP
6 Multi-user Security of EDM
7 Multi-user Security of a Variant of nEHtM in the Nonce-Respecting Setting
References
The Power of Undirected Rewindings for Adaptive Security
1 Introduction
1.1 Technical Overview
1.2 Roadmap
2 Preliminaries
2.1 Notation
2.2 Probability Theory
2.3 Cryptographic Primitives
3 Analysis of a Repeated Resampling Algorithm
4 Adaptive Security for the GGM PC-PRF
4.1 Proving Security from PR
5 Adaptive Security for LKH
5.1 Pebbling for LKH
5.2 Proving Security from IND-CPA
References
Anamorphic Signatures: Secrecy from a Dictator Who Only Permits Authentication!
1 Introduction
1.1 Our Contribution
2 Definitions and Models
2.1 Security of the Associated Schemes
2.2 Symmetric Anamorphism
3 A First Example
4 Three-Message Public-Coin Protocols
4.1 Anamorphic Three-Message Public-Coin Protocols
4.2 Fiat-Shamir Gives Symmetric Anamorphic Signatures
4.3 A Sufficient Condition for Anamorphism
4.4 Examples of Three-Message Protocols with Randomness Recovering
5 Private Anamorphic Signatures
5.1 Formal Definition of Private Anamorphism
5.2 A Sufficient Condition for Private Anamorphism
6 One-Time Signature Schemes
6.1 Lamport's Tagging Systems
7 The Naor-Yung Paradigm for Signatures
8 Conclusions
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken