Advances in Cryptology - EUROCRYPT 2022

Name: Advances in Cryptology - EUROCRYPT 2022 | 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part II
Brand: Springer
Price: 160.49 EUR
Availability: OnlineOnly

41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part II

Orr Dunkelman Stefan Dziembowski(Herausgeber*in)

Springer (Verlag)

Erschienen am 28. Mai 2022

XVII, 909 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-031-07085-3 (ISBN)

160,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
Organization
Contents - Part II
Cryptographic Protocols
Single-Server Private Information Retrieval with Sublinear Amortized Time
1 Introduction
1.1 Our Results
1.2 Overview of Techniques
1.3 Related Work
2 Background
2.1 Standard Definitions
2.2 Definition of Offline/Online PIR
3 Two-Server PIR with a Single-Server Online Phase and Sublinear Amortized Time
Construction 3
4 Single-Server PIR with Sublinear Amortized Time from DCR, QR, DDH, or LWE
5 Single-Server PIR with Optimal Amortized Time and Storage from Fully Homomorphic Encryption
6 Lower Bounds
6.1 Lower Bound for Adaptive Schemes
6.2 Lower Bound for Batch PIR with Advice
7 Conclusion
References
Anamorphic Encryption: Private Communication Against a Dictator
1 Introduction
2 Related Works
3 Our Approach
4 Receiver-Anamorphic Encryption
4.1 Syntax
4.2 Modes of Operation
4.3 Security Notion
4.4 Properties of the Anamorphic Mode with Normal Encryption
4.5 Security of the Fully Anamorphic Mode
5 Constructions
5.1 Rejection Sampling
5.2 The Naor-Yung Transform
5.3 The NY Transform Gives Receive-AM Encryption
6 Sender-Anamorphic Encryption
6.1 Sufficient Conditions for Sender-AM with No Shared Key
6.2 Constructions Based on LWE Encryption Schemes
7 Conclusion
References
A PCP Theorem for Interactive Proofs and Applications
1 Introduction
1.1 Main Results
1.2 A Cryptographic Application to SNARKs
2 Techniques
2.1 Towards Transforming IPs to IOPs
2.2 Local Access to Randomness
2.3 Index-Decodable PCPs
2.4 Local Access to Prover Messages
2.5 Constructing Index-Decodable PCPs
2.6 Commit-and Prove SNARKs from Index-Decodable PCPs
2.7 Hardness of Approximation
References
Group Signatures and More from Isogenies and Lattices: Generic, Simple, and Efficient
1 Introduction
1.1 Our Contribution
1.2 Technical Overview
2 Preliminaries
2.1 Non-interactive Zero-Knowledge Proofs of Knowledge in the ROM
2.2 Accountable Ring Signatures
3 Generic Construction of Accountable Ring Signature and Dynamic Group Signature
3.1 Generic Construction of Accountable Ring Signature
3.2 Accountable Ring Signature to Dynamic Group Signature
3.3 Tightly Secure Variant
4 Group-Action-Based Hard Instance Generators and PKEs
4.1 Group-Action-Based Hard Instance Generator
4.2 Group-Action-Based PKE
5 Sigma Protocol for a ``Traceable'' OR Relation
5.1 From a Group-Action-Based HIG and PKE to Base Traceable or Sigma Protocol
5.2 From Base to Main Traceable or Sigma Protocol
5.3 Base Sigma Protocol for the ``Tight'' Relation R-tight
6 Multi-proof Online Extractable NIZK from Sigma Protocol main traceable OR sigma protocol
7 Instantiations
References
Asymmetric PAKE with Low Computation and communication
1 Introduction
2 Key-Hiding One-Time-Key AKE
2.1 2DH as Key-Hiding One-Time-Key AKE
2.2 One-Pass HMQV as Key-Hiding One-Time-Key AKE
3 Protocol OKAPE: Asymmetric PAKE Construction #1
4 Protocol aEKE: Asymmetric PAKE Construction #2
5 Concrete aPAKE Protocol Instantiations
6 Curve Encodings and Ideal Cipher
A Universally Composable Asymmetric PAKE Model
B Simulator for Proof of Theorem 3
References
Batch-OT with Optimal Rate
1 Introduction
1.1 Our Contribution
1.2 Related Work
2 Technical Overview
2.1 Oblivious Transfer from Homomorphic Encryption
2.2 Download-Rate Optimal String OT
2.3 Our Approach: Recrypting the Receiver's Message
2.4 Dealing with LPN Errors
2.5 Emulating Small Subgroups
3 Preliminaries
3.1 Lattices and Gaussians
3.2 Distributed GGM-PPRF Correlation
4 Compression-Friendly Subgroup Emulation via Gaussian Rounding
5 Rate-1 Circuit-Private Linearly Homomorphic Encryption
5.1 Construction from DDH
6 Co-private Information Retrieval
6.1 Definition
7 Oblivious Transfer with Overall Rate 1
7.1 The Protocol
7.2 Security
8 Oblivious Matrix-Vector Product and Oblivious Linear Evaluation with Overall Rate 1
8.1 OLE Protocol
A Additional Preliminaries
A.1 UC Security
A.2 Learning Parity with Noise
References
Adaptively Secure Computation for RAM Programs
1 Introduction
1.1 Our Results
1.2 Our Techniques
2 Equivocal ORAM
3 RAM-Efficient Equivocal Encryption
3.1 Our Construction
4 Equivocal Garbled RAM
4.1 Our Construction
4.2 Putting It Together
5 Adaptive Zero-Knowledge for RAM
5.1 Splitable Garbling
5.2 Our Adaptive UC ZK Protocol
References
Optimal Broadcast Encryption and CP-ABE from Evasive Lattice Assumptions
1 Introduction
2 Technical Overview
2.1 Our CP-ABE Schemes
2.2 On Evasive Lattice Assumptions
2.3 Additional Related Work
3 Preliminaries
3.1 Lattices Background
3.2 Attribute-Based Encryption
4 Evasive LWE
5 Main Constructions
5.1 Homomorphic Computation on Matrices
5.2 CP-ABE for NC1 Circuits
5.3 Optimal Broadcast Encryption
5.4 CP-ABE for Polynomial-Depth Circuits
6 Discussion on Evasive LWE
References
Embedding the UC Model into the IITM Model
1 Introduction
2 A Brief Overview of the UC and IITM Models
2.1 The UC Model
2.2 The IITM Model
3 Embedding the UC Model in the IITM Model
3.1 Main Conceptual Differences
3.2 Mapping Protocols
3.3 UC Security Implies IITM Security
3.4 UC Composition Implies IITM Composition
3.5 Capturing Dynamically Generated Machine Code
3.6 Discussion: Beyond UC Protocols
4 Impossibility of Embedding the IITM Model into the UC Model
References
Zero-Knowledge Proofs
Zero-Knowledge IOPs with Linear-Time Prover and Polylogarithmic-Time Verifier
1 Introduction
1.1 Our Results
1.2 Related Work on Probabilistic Proofs
1.3 Related Work on Succinct Arguments
2 Techniques
2.1 Approach Overview
2.2 Construction Overview
2.3 From Tensor-Queries to Point-Queries in Zero-Knowledge
2.4 Tensor IOP for R1CS with Semi-honest Verifier Zero Knowledge
2.5 Hiding Properties of Linear Codes
2.6 On Bounded-Query Zero Knowledge
2.7 Linear-Time Succinct Arguments from Linear-Time IOPs
References
Non-Interactive Zero-Knowledge Proofs with Fine-Grained Security
1 Introduction
1.1 Our Contributions
1.2 Technical Details
2 Preliminaries
2.1 Function Families
2.2 Sampling Procedure
2.3 Proof Systems
3 AC0[2]-Protocol for Linear Languages
4 Fine-Grained NIZK for Linear Languages
5 Fine-Grained OR-Proof
6 Fine-Grained NIZK Proof for Circuit SAT
7 Fine-Grained NIZK for AC0CM[2] with Short Proofs
7.1 Definition of Fine-Grained sFHE
7.2 Construction of Fine-Grained sFHE
7.3 Generic Construction of NIZK
8 Fine-Grained Non-Interactive Zap
8.1 Verifiable Correlated Key Generation
8.2 Construction of Fine-Grained Non-Interactive Zap
9 Fine-Grained NIZK in the URS Model
References
On Succinct Non-interactive Arguments in Relativized Worlds
1 Introduction
1.1 Our Results
1.2 Related Work
2 Techniques
2.1 Linear Code Random Oracles
2.2 Accumulation Scheme for Low-Degree Random Oracles
2.3 A Forking Lemma for Linear Code Random Oracles
2.4 A Zero-Finding Game for Low-Degree Random Oracles
2.5 SNARKs for Oracle Computations
3 Preliminaries
3.1 Notations
3.2 Non-interactive Arguments in Oracle Models
3.3 Accumulation Schemes
3.4 Commitment Schemes
4 Linear Code Random Oracles
4.1 Query Transcripts and Partial Oracles
4.2 Constraints
4.3 Query Complexity
4.4 Low-Degree Random Oracles
5 A Forking Lemma for Linear Code Random Oracles
6 Oracle Zero-Finding Games
7 Accumulation Scheme for Low-Degree Random Oracles
References
Families of SNARK-Friendly 2-Chains of Elliptic Curves
1 Introduction
2 Preliminaries
2.1 Background on Bilinear Pairings
2.2 zk-SNARKs
2.3 SNARK-Friendly Chains
3 Inner Curves: Barreto-Lynn-Scott (BLS) Curves
3.1 Parameters with a Polynomial Form
3.2 Faster Co-factor Multiplication
3.3 Subgroup Membership Testing: GT
3.4 Choosing a Curve Coefficient b=1
3.5 SNARK-Friendly Inner BLS Curves
4 Outer Curves: Brezing-Weng, Cocks-Pinch
4.1 Generic BW6 Curve Parameters
4.2 BW6 with BLS-12
4.3 BW6 with BLS-24
4.4 Two-Chains with Inner BLS and Outer Cocks-Pinch
4.5 Comparison of BW6, CP8 and CP12 Outer Curve Performances
5 Implementation and Benchmarking
5.1 SageMath Library: Derive the Curves
5.2 Our Short-List of Curves
5.3 Estimated Complexity of a DL Computation in GF(qk)
5.4 Golang Library: Implement the Short-List Curves
5.5 Benchmarking
6 Conclusion
References
Fiat-Shamir Bulletproofs are Non-Malleable (in the Algebraic Group Model)
1 Introduction
1.1 Technical Overview
1.2 Related Work
2 Preliminaries
3 Simulation-Extractability from State-Restoration Unique Response
3.1 Simulation-Extractability in the AGM
3.2 From Weak Unique Response to Simulation-extractability
3.3 Generic Result on Simulation-Extractability
4 Non-Malleability of Bulletproofs - Arithmetic Circuits
4.1 Algebraic Simulation
4.2 State-Restoration Unique Responses
References
Gemini: Elastic SNARKs for Diverse Environments
1 Introduction
1.1 Our Results
1.2 Related Work
2 Techniques
2.1 Elasticity and a Streaming Model
2.2 A Modular Construction of Elastic SNARKs
2.3 An Elastic Realization of the KZG Polynomial Commitment Scheme
2.4 An Elastic Scalar-Product Protocol
2.5 Warm-up: An Elastic Non-holographic PIOP for R1CS
2.6 Elastic Holographic PIOP for R1CS
2.7 Implementation and Optimizations
2.8 Evaluation
References
Stacking Sigmas: A Framework to Compose -Protocols for Disjunctions
1 Introduction
1.1 Our Contributions
1.2 Related Work
2 Technical Overview
3 Preliminaries
3.1 Notation
3.2 -Protocols
4 Partially-Binding Vector Commitments
4.1 Partially-Binding Vector Commitments from Discrete Log
5 Stackable -Protocols
5.1 Well-Behaved Simulators
5.2 Properties of Stackable -Protocols
5.3 Classical Examples of Stackable -Protocols
5.4 Examples of Stackable ``MPC-in-the-Head'' -Protocols
6 Self-stacking: Disjunctions with the Same Protocol
6.1 Extending to Multiple Languages
References
One-Shot Fiat-Shamir-Based NIZK Arguments of Composite Residuosity and Logarithmic-Size Ring Signatures in the Standard Model
1 Introduction
2 Background and Definitions
2.1 Hardness Assumptions
2.2 Correlation Intractable Hash Functions
2.3 Admissible Hash Functions
2.4 Trapdoor -protocols
2.5 R-Lossy Public-Key Encryption with Equivocation
2.6 Ring Signatures
3 R-Lossy Encryption Schemes from DCR
3.1 An Equivocable RBM-Lossy PKE Scheme from DCR
3.2 A Dense RBM-Lossy PKE Scheme from DCR
4 Trapdoor -Protocols for DCR-Related Languages
4.1 Trapdoor -Protocol Showing that a Paillier Ciphertext/Commitment Contains 0 or 1
4.2 Trapdoor -Protocol Showing that One Out of Many Ciphertexts/Commitments Contains 0
5 Logarithmic-Size Ring Signatures in the Standard Model from DCR and LWE
References
SNARGs for P from Sub-exponential DDH and QR
1 Introduction
1.1 Our Results
1.2 Other Prior Work
2 Technical Overview
2.1 Succinct Interactive Arguments for Bounded Space from Succinct Arguments for Batch NP
2.2 Obtaining a SNARG
2.3 SNARGs for Bounded Space Non-deterministic Computation
3 Preliminaries
3.1 Correlation Intractable Hash Functions
3.2 Somewhere Extractable (SE) Commitments
4 Fiat-Shamir for Arguments
4.1 Round-by-Round Soundness
4.2 FS-Compatible Arguments
4.3 From FS-Compatible Arguments to SNARGs
5 FS-Compatible Arguments for Bounded Space Computations
5.1 FS-Compatible Batch NP Arguments
5.2 Bounded-Space Protocol Construction
5.3 Non-trivial Predicate for Bounded-Space Protocol
5.4 FS-Compatibility for Bounded-Space Protocol
6 FS-Compatible Arguments for Non-deterministic Bounded Space
6.1 Background
6.2 Interactive Arguments for Bounded Space Non-deterministic Computation
6.3 Non-trivial Predicate
6.4 FS-Compatibility W.r.t. Predicate
6.5 SNARGs for P and Beyond
References
Cryptographic Primitives
Optimal Tightness for Chain-Based Unique Signatures
1 Introduction
1.1 Our Contributions
1.2 Technical Idea
1.3 Impossibility of Reductions
2 Definitions
3 Optimal Analysis for the Chain-Based BLS Scheme
4 Optimal Tightness for the Chain-Based BLS Scheme
4.1 Framework of Security Reduction
4.2 Probability Analysis
References
On Building Fine-Grained One-Way Functions from Strong Average-Case Hardness
1 Introduction
1.1 Our Contribution: Inbetween Heuristica and Pessiland
1.2 A Core Abstract Lemma: The Hitting Lemma
1.3 On the Significance of Our Results
1.4 Related Work
2 Preliminaries
2.1 Notation, Computational Models and Oracles
2.2 Fine-Grained One-Way Functions
2.3 Languages
2.4 Pairwise Independent Hash-Functions
3 Technical Overview: FGOWFs from Block-Finding Hardness
3.1 Block-Finding Hardness of L
4 Overview: No FGOWFs from Average-Case Hardness
5 Overview: No FG-OWF from Non-Amortizable Hardness
5.1 Defining the Oracle Distribution T
5.2 Proving Theorem 16
5.3 Proving Theorem 17
6 The Hitting Lemma
6.1 Proof of the Hitting Lemma - Proof Structure
References
On the Multi-user Security of Short Schnorr Signatures with Preprocessing
1 Introduction
1.1 Our Contributions
1.2 Our Techniques
1.3 Related Work
2 Preliminaries
2.1 The Generic Group Model
2.2 The Schnorr Signature Scheme
3 Single-User Security of Short Schnorr Signatures
3.1 Discrete Log Problem with Restricted Discrete Log Oracle
3.2 Security Reduction
4 Multi-user Security of Short Schnorr Signatures
4.1 The Multi-user Bridge-Finding Game
4.2 Security Reduction
5 Multi-user Security of Short Schnorr Signatures with Key-Prefixing Against Preprocessing Attacks
5.1 Security of BRIDGE N-Finding Game with Preprocessing
5.2 Multi-user Security of Key-Prefixed Short Schnorr Signatures with Preprocessing
6 Multi-user Security of Other Fiat-Shamir Signatures
References
Multi-Designated Receiver Signed Public Key Encryption
1 Introduction
1.1 Public Key Encryption Security Properties
1.2 Public Key Encryption for Broadcast
1.3 Multi-Designated Receiver Signed Public Key Encryption
1.4 Applications to Secure (Group) Messaging
1.5 Related Work
2 Preliminaries
3 Public Key Encryption for Broadcast Schemes
3.1 The Security of PKEBC Schemes
4 A PKEBC Scheme from Standard Assumptions
4.1 Security Analysis of PKEBC Construction
5 Multi-Designated Receiver Signed Public Key Encryption Schemes
5.1 The Security of MDRS-PKE Schemes
6 A Multi-Designated Receiver Signed Public Key Encryption Scheme from Standard Assumptions
6.1 Security Analysis of the MDRS-PKE Construction
References
A Fast and Simple Partially Oblivious PRF, with Applications
1 Introduction
2 Preliminaries
2.1 Algebraic Group Model
2.2 Random Oracle Model
2.3 Non-interactive Zero Knowledge Proofs
3 Partially Oblivious Pseudorandom Functions
4 The 3HashSDHI POPRF
5 Security Analysis
5.1 Pseudorandomness
5.2 Request Privacy
6 Performance Evaluation
7 Applications
References
Hiding in Plain Sight: Memory-Tight Proofs via Randomness Programming
1 Introduction
1.1 Our Techniques - An Overview
1.2 Our Results
1.3 Paper Outline
2 Preliminaries
2.1 Computational Model
2.2 Cryptographic Background
3 Adversaries with Access to Random Functions
4 Multi-challenge Security of Digital Signature Schemes
4.1 Syntax and Security
4.2 Multi-challenge Security for Extractable Message Distributions
4.3 Proof of Theorem 1 (1UFCMAmUFRMA)
4.4 Applications and Weakly Extractable Variant
4.5 mSUFCMA Security of RSA-PFDH
5 AE Security of Encrypt-then-PRF
5.1 Syntax and Security Definitions
5.2 Security Result
6 Chosen Ciphertext Security of Public Key Encryption
6.1 Left-or-Right CCA Security of PKE
6.2 Indistinguishable from Random CCA Security of PKE
References
Dynamic Collusion Bounded Functional Encryption from Identity-Based Encryption
1 Introduction
1.1 Technical Overview
1.2 Related Work and Future Directions
1.3 Concurrent Work
2 Preliminaries
2.1 Garbled Circuits
2.2 Identity-Based Encryption
3 Functional Encryption: Dynamic Bounded Collusion
3.1 Bounded Collusion FE: Static and Dynamic
3.2 Upgrading Static to Dynamic Bounded Collusion FE via Weak Optimal Efficiency
4 Tagged Functional Encryption
5 Tagged to Weakly Optimal Static Collusion FE
5.1 Construction
5.2 Correctness, Efficiency, and Security
6 Upgrading Collusion Bound for Tagged FE
7 Building 1-Bounded Collusion Tagged FE from IBE
7.1 Non-Adaptive 1-Bounded Tagged FE from Garbled Circuits and IBE
7.2 Upgrading to Adaptive Security
References
Property-Preserving Hash Functions for Hamming Distance from Standard Assumptions
1 Introduction
1.1 Our Contribution
1.2 Technical Overview
2 Preliminaries
2.1 Property-Preserving Hash Functions
2.2 Lattices
3 Robust Set Encodings
3.1 Instantiation
4 Construction
4.1 PPH for the Hamming Distance Predicate
5 Lower Bound
References
Short Pairing-Free Blind Signatures with Exponential Security
1 Introduction
1.1 A Scheme in the GGM
1.2 AGM Security and Partial Blindness
2 Preliminaries
3 The Weighted Fractional ROS Problem
3.1 Proof of Theorem 1
3.2 Proof of Lemma 1
3.3 Proof of Lemma 2
3.4 Proof of Lemma 3
4 Efficient Blind Signatures in the GGM
4.1 Proof of Theorem 3
4.2 Proof of Lemma 7
5 Efficient Blind Signatures in the AGM
5.1 A Protocol Secure Under the DL Assumption
5.2 Proof of Lemma 9
6 Partially Blind Signatures
References
Real-World Systems
CoCoA: Concurrent Continuous Group Key Agreement
1 Introduction
1.1 Our Contributions
1.2 Related Work
2 Preliminaries
2.1 Continuous Group-key Agreement
2.2 Ratchet Trees
3 The CoCoA Protocol
3.1 Overview
3.2 Users' States and the Key Schedule
3.3 Robustness, Round Hash, and Transcript Hash
3.4 Parent Hash
3.5 The Protocol: CoCoA and Partial Updates
4 Efficiency
5 Security
5.1 Security Model and Safe Predicate
5.2 Security of CoCoA
References
Efficient Schemes for Committing Authenticated Encryption
1 Introduction
2 Preliminaries
3 Committing AE Framework
4 Some Building Blocks
5 A Committing Variant of GCM
6 A Committing Variant of AES-GCM-SIV
7 Adding Key-Committing Security to Legacy AE
References
On the Concrete Security of TLS 1.3 PSK Mode
1 Introduction
2 The TLS 1.3 Pre-shared Key Handshake Protocol
3 Code-based MSKE Model for PSK Modes
3.1 Key Exchange Syntax
3.2 Key Exchange Security
4 Key-Schedule Indifferentiability
4.1 Indifferentiability for the TLS 1.3 Key Schedule in Three Steps
5 Modularizing Handshake Encryption
6 Tight Security of the TLS 1.3 PSK Modes
6.1 TLS 1.3 PSK-only/PSK-(EC)DHE as a MSKE Protocol
6.2 Tight Security Analysis of TLS 1.3 PSK-(EC)DHE
6.3 Proof overview
6.4 Full Security Bound for TLS 1.3 PSK-(EC)DHE and PSK-only
7 Evaluation
References
Correction to: Non-Interactive Zero-Knowledge Proofs with Fine-Grained Security
Correction to: Chapter "Non-Interactive Zero-Knowledge Proofs with Fine-Grained Security" in: O. Dunkelman and S. Dziembowski (Eds.): Advances in Cryptology - EUROCRYPT 2022, LNCS 13276, https://doi.org/10.1007/978-3-031-07085-3_11
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken