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 I
Brand: Springer
Price: 117.69 EUR
Availability: OnlineOnly

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

Orr Dunkelman Stefan Dziembowski(Herausgeber*in)

Springer (Verlag)

Erschienen am 27. Mai 2022

XXIX, 823 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-031-06944-4 (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
Abstracts of Invited Talks
Hardware: An Essential Partner to Cryptography
Symmetric Cryptography for Long Term Security
Contents - Part I
Contents - Part II
Contents - Part III
Best Paper Award
EpiGRAM: Practical Garbled RAM
1 Introduction
1.1 Contribution
2 Technical Overview
2.1 The Language Translation Problem
2.2 Lazy Permutations
2.3 Pattern-Leaking (Leaky) Arrays
2.4 Garbled RAM
3 Related Work
4 Preliminaries, Notation, and Assumptions
4.1 Common Notation
4.2 Cryptographic Assumptions
4.3 Garbling Schemes
4.4 Garblings and Sharings
4.5 Oblivious Permutation
5 Approach
5.1 Avoiding Factor Blowup
5.2 Pop-only Oblivious Stacks
5.3 Lazy Permutations
5.4 Our GRAM
6 Evaluation
References
Secure Multiparty Computation
Garbled Circuits with Sublinear Evaluator
1 Introduction
1.1 Our Contribution
1.2 Garbled PIR
1.3 Compact 2PC and Garbled PIR
1.4 High-Level Intuition for Our Approach
2 Related Work
3 Preliminaries
3.1 Reducing GC Communication
3.2 Universal and Set-Universal Circuits
3.3 Garbled Circuit Formalization
3.4 Circuit Syntax
4 Technical Overview
5 Our Construction
5.1 Bucket Table Gadget
5.2 Demultiplexer and Multiplexer
5.3 Our Garbling Scheme
6 Security
6.1 Proofs
References
Round-Optimal and Communication-Efficient Multiparty Computation
1 Introduction
1.1 Related Work
1.2 Overview of Our Results
2 Technical Overview
3 Preliminaries
3.1 Functional Encryption
3.2 Decomposable Functional Encryption Combiner
3.3 Multi Key Fully Homomorphic Encryption
3.4 Secure Multiparty Computation
4 k-Delayed-Input Function MPC
5 Our Compiler: Circuit-Scalable MPC
6 Our Compiler: Circuit-Independent MPC
References
Round-Optimal Byzantine Agreement
1 Introduction
1.1 Technical Overview
1.2 Related Work
2 Model and Definitions
2.1 Communication and Adversary Model
2.2 Cryptographic Primitives
2.3 Agreement Primitives
3 Expand-and-Extract Paradigm
4 Conditional Graded Broadcast
5 Round-Optimal Proxcensus
5.1 Protocol Description
6 Technical Combinatorial Lemma
7 Putting It All Together
7.1 Comparison to Previous Protocols
7.2 Open Problems
References
A Complete Characterization of Game-Theoretically Fair, Multi-Party Coin Toss
1 Introduction
1.1 Our Results and Contributions
1.2 Related Work
2 Technical Overview
2.1 Upper Bound
2.2 Lower Bound
3 Definitions
4 Upper Bound
4.1 Our Final Protocol for Malicious Coalitions
5 Lower Bound
5.1 Parameter Constraints
5.2 Constraint System Implies the Lone-Wolf, Wolf-Minion, and T2-Equality Conditions
5.3 Minimizing t Subject to Constraints
6 Complete Characterization of Maximin Fairness
6.1 Lower Bound
6.2 Upper Bound
A Visualization of the Resilience Parameter
References
Lightweight, Maliciously Secure Verifiable Function Secret Sharing
1 Introduction
1.1 Our Contributions
1.2 Related Work
1.3 Technical Overview
2 Background
2.1 Notation
2.2 Function Secret Sharing
3 Lightweight, Verifiable DPF
3.1 Definitions
3.2 Our Construction
3.3 VDPF Security Proof
4 Verifiable Distributed Multi-Point Function
4.1 Cuckoo-hashing from PRPs
4.2 Verifiable Distributed MPFs via PRP Hashing
5 Implementation & Performance
A Match-Mode VDMPF: Point Matching
References
Highly Efficient OT-Based Multiplication Protocols
1 Introduction
1.1 Background on OT-Based Two-Party Multiplication
1.2 Our Contributions
1.3 Applications
1.4 Related Work
2 Our Techniques
3 Preliminaries
3.1 Notations
3.2 Distributions and Random Variables
3.3 Two-Party Protocols and Functionalities
3.4 Some Inequalities
4 Multiplication with Unpredictable Output Under Attack
4.1 The Ideal Functionality
4.2 The OT-Based Protocol
5 Batching
5.1 The Ideal Functionality
5.2 The OT-Based Protocol
6 Applications
6.1 Realizing Perfect Multiplication
6.2 Generating Correlated Data in the Preprocessing Model
References
Round-Optimal Black-Box Protocol Compilers
1 Introduction
1.1 Our Results
2 Technical Overview
2.1 IPS Compiler
2.2 A New Compiler: Removing Equivocality
2.3 Protocol Compiler in the Random Oracle Model
2.4 Two-Sided NISC
2.5 The Multiparty Setting
3 Preliminaries
3.1 Semi-honest Two-Round Two-Party Computation
3.2 Semi-malicious Two-Round Two-Party Computation
3.3 Extractable Commitments in ROM
3.4 Pairwise Verifiable Secret Sharing
4 Two-Round Client-Server Protocol with Pairwise Verifiability
4.1 Definition
5 Black-Box Protocol Compilers in the Two-Party Setting
5.1 Protocol Compiler in the Random Oracle Model
5.2 Protocol Compiler in the OT Correlations Model
5.3 Extension to the Two-Sided Setting
6 Black-Box Protocol Compilers in the Multiparty Setting
6.1 Protocol Compiler in the Random Oracle Model
6.2 Protocol Compiler in the OT Correlations Model
References
Guaranteed Output in O(n) Rounds for Round-Robin Sampling Protocols
1 Introduction
1.1 Our Contributions
2 Preliminaries
3 A Round-Reducing Compiler
3.1 The Compiler
3.2 Proof of Security
4 A Round-Robin Protocol
4.1 The Protocol
4.2 Proof of Security
4.3 Application: Powers of Tau and Polynomial Commitments
4.4 Application: Sampling Updateable SRSes
4.5 Application: Verifiable Mixnets
5 With Concrete Efficiency
References
Universally Composable Subversion-Resilient Cryptography
1 Introduction
1.1 Subversion-Resilient Cryptography
1.2 Our Contributions
1.3 Technical Overview
2 A UC Model of Reverse Firewalls
2.1 Quick and Dirty Recap of UC
2.2 Modeling Reverse Firewalls
2.3 Specious Corruptions
2.4 Sanitizing Protocols Implementing Regular Ideal Functionalities
2.5 General Case
2.6 Composition
2.7 Computational Transparency
2.8 Strong Sanitation
3 String Commitment
3.1 Sanitizable Commitment Functionality
3.2 Protocol from DDH
4 Coin Tossing
4.1 The Coin Tossing Functionality
4.2 Sanitizing Blum's Protocol
5 Completeness Theorem
5.1 Sanitizable Commit and Prove
5.2 Sanitizing the GMW Compiler
6 Conclusions and Future Work
References
Asymptotically Quasi-Optimal Cryptography
1 Introduction
1.1 Our Results and Techniques
1.2 Perspectives and Open Problems
2 Preliminaries
2.1 Asymptotic Quasi-Optimality
2.2 Ring Learning with Errors
2.3 Ring-LWE Encryption
2.4 Entropy and Extraction
3 AQO Semi-Honest Batch-OLE and Batch-OT
3.1 Gentle Noise-Flooding
3.2 Entropically Secure Batch-OLE Protocol
3.3 Our Batch-OLE and Batch-OT Schemes
4 AQO Batch-OLE: The Malicious Setting
4.1 Entropically Secure OLE Against a Malicious Receiver
5 AQO Zero-Knowledge Arguments
5.1 AQO-Honest Verifier ZK from AQO-Honest Verifier ZKPCP
References
Round-Optimal Multi-party Computation with Identifiable Abort
1 Introduction
1.1 Our Results
1.2 Technical Overview
1.3 Related Work
2 Preliminaries and Standard Definitions
2.1 Non-malleable Commitments Scheme
2.2 Trapdoor Generation Protocol with Bounded Rewind Security
3 Rewind-Secure OT and MPC
4 From MPC with Unanimous Abort to B-rewindable MPC with Unanimous Abort
5 Our Construction: MPC with Identifiable Abort
6 Special BOT-Rewindable Secure Oblivious Transfer
References
On the Security of ECDSA with Additive Key Derivation and Presignatures
1 Introduction
1.1 Our Contributions
2 The EC-GGM
3 Properties of the ECDSA Conversion Function
4 Notions of Security
5 Proof of Security of ECDSA in the EC-GGM
6 ECDSA with Additive Key Derivation
7 ECDSA with Presignatures
7.1 ECDSA with Presignatures and Additive Key Derivation
8 ECDSA with Re-randomized Presignatures
8.1 ECDSA with Re-randomized Presignatures and Additive Key Derivation
9 Homogeneous Key Derivation
9.1 Homogeneous Key Derivation Without Presignatures
9.2 Homogeneous Key Derivation with Presignatures
9.3 Homogeneous Key Derivation with Re-randomized Presignatures
References
Secure Multiparty Computation with Free Branching
1 Introduction
1.1 Our Contributions
2 Technical Overview
2.1 Non-constant Round Branching MPC
2.2 Constant Round (Semi-honest) Protocol
3 Oblivious Inner Product
4 MPC Interface
5 Non-constant Round Semi-honest Branching MPC
6 Constant Round Semi-honest Branching MPC
7 Implementation
7.1 How We Benchmark
7.2 Comparison of Communication Complexity
7.3 Comparison of Running Time
References
Secure Multiparty Computation with Sublinear Preprocessing
1 Introduction
1.1 Our Results
1.2 Technical Overview
2 Preliminaries
2.1 Security Definitions
2.2 Fully Linear Proof Systems
2.3 Additively-Homomorphic Encryption (AHE)
2.4 Ideal Functionalities and Basic Building Blocks
3 The BGIN Compiler ch15BoyleGIN21
4 A New Simplified Verification Protocol
4.1 A Concrete Instantiation for the Zk-FLIOP Protocol
4.2 The Dealer's Ideal Functionality FDealer
5 Online Computation with a Trusted Dealer
6 Distributing the Dealer with Sublinear Communication
References
Practical Non-interactive Publicly Verifiable Secret Sharing with Thousands of Parties
1 Introduction
1.1 The PVSS Problem and Related Work
1.2 An Overview of Our PVSS Construction
1.3 Organization
2 The Underlying Encryption Scheme
2.1 Learning with Errors (LWE)
2.2 Variants of Regev Encryption
2.3 The Multiparty Setting
2.4 An Optimization: Using Module-LWE over Small Rings
2.5 The Encryption Scheme in Our Protocol
3 Proofs of Smallness
3.1 Underlying Commit-and-Prove Systems
3.2 Tails of Distributions and the Johnson-Lindenstrauss Lemma
3.3 A Modular Johnson-Lindenstrauss Variant
3.4 Approximate Proofs of Smallness
3.5 Exact Proofs of Smallness
3.6 Proofs of Smallness for LWE
4 Implementation and Performance
References
Homomorphic Encryption
Sine Series Approximation of the Mod Function for Bootstrapping of Approximate HE
1 Introduction
1.1 This Work
1.2 Problem Overview
1.3 Sine Series
1.4 On Approximating Arcsine
1.5 Organization
2 Sine Series Approximation
2.1 Alternating Series Test (Proof of Main Lemma)
3 Application to Bootstrapping for Approximate HE
4 Evaluating the Sine Series Approximation of the Mod Function
5 Implementation
5.1 Time and Error Dependence on the Number of Slots
5.2 Comparison with Basic Sine and Other Variants
5.3 Comparison with Other Prior Works
A Proof of Lemma 5
References
Limits of Polynomial Packings for Zpk and Fpk
1 Introduction
1.1 Our Contribution
2 Preliminaries
2.1 Notations and Terminologies
2.2 Polynomial Factorizations
2.3 RMFE
3 Packing: Definitions and Basic Facts
3.1 Definitions and Basic Examples
3.2 Decomposition Lemmas
4 More Examples
4.1 HELib Packing
4.2 Overdrive2k Packing
4.3 MHz2k Packing
4.4 Comparison
5 Bounds on Packing Density
5.1 Algebraic Background
5.2 Packing Density of Zpk-Message Packings
5.3 Packing Density of Fpk-Message Packings
6 Level-Consistency
6.1 Definition and Basic Facts
6.2 Level-Consistency in Zpk-Message Packings
6.3 Level-Consistency in Fpk-Message Packings
7 Surjectivity
7.1 Definition and Basic Facts
7.2 Surjectivity in Zpk-Message Packings
7.3 Surjectivity in Fpk-Message Packings
References
High-Precision Bootstrapping for Approximate Homomorphic Encryption by Error Variance Minimization
1 Introduction
1.1 Our Contributions
1.2 Related Works
1.3 Organization of This Paper
2 Preliminaries
2.1 Basic Notation
2.2 The CKKS Scheme
2.3 Signal-to-Noise Ratio Perspective of the CKKS Scheme
3 Bootstrapping of the CKKS Scheme
3.1 Outline of the CKKS Bootstrapping
3.2 Polynomial Approximation of Modular Reduction
3.3 Baby-Step Giant-Step Algorithms
4 Optimal Approximate Polynomial of Modular Reduction for Bootstrapping of the CKKS Scheme
4.1 Error Variance-Minimizing Polynomial Approximation
4.2 Optimality of the Proposed Direct Approximate Polynomial
4.3 Noisy Polynomial Basis and Polynomial Evaluation in the CKKS Scheme
4.4 Optimal Approximate Polynomial for Bootstrapping and the Magnitude of Its Coefficients
4.5 Statistical Characteristics of Modular Reduction
5 Lazy Baby-Step Giant-Step Algorithm
5.1 Reducing Error and Complexity Using Odd Function Property
5.2 Lazy Baby-Step Giant-Step Algorithm
5.3 Error Variance-Minimizing Approximate Polynomial for BSGS Algorithm
5.4 Basis Error Variance Minimization for Even-Degree Terms
6 Performance Analysis and Comparison
6.1 Error Analysis
6.2 Comparison of Bootstrapping and High-Precision Bootstrapping
7 Conclusion
References
Rubato: Noisy Ciphers for Approximate Homomorphic Encryption*-6pt
1 Introduction
1.1 Transciphering and HE-friendly Ciphers
1.2 Our Contribution
1.3 Related Work
2 Preliminaries
2.1 Notations
2.2 Lattice Background
2.3 Learning with Errors
2.4 RtF Transciphering Framework
3 Rubato: A Family of Noisy Ciphers
3.1 Specification
3.2 Parameter Selection
3.3 Design Rationale
4 Security Analysis
4.1 Cryptanalysis Based on Symmetric Primitive Analysis
4.2 Cryptanalysis Based on LWE Analysis
5 Performance Evaluation
5.1 Benchmark and Comparison
References
Field Instruction Multiple Data
1 Introduction
2 Preliminaries
2.1 Fully Homomorphic Encryption
2.2 Finite Extension Fields
2.3 Reverse Multiplication Friendly Embeddings
3 Field Instruction Multiple Data (FIMD)
3.1 RMFE with FHE
3.2 r-fold RMFE
3.3 Composite RMFE with FHE
4 RMFE Parameter Selection with FHE
5 Experiment Results
5.1 Experimental Results for Basic (r)FIMD
5.2 Experimental Results for Composite RMFE
6 Conclusion and Future Work
A Complete Experiment Results
A.1 Basic RMFE
A.2 Composite RMFE
References
Obfuscation
Cryptanalysis of Candidate Obfuscators for Affine Determinant Programs
1 Introduction
1.1 Main Result
1.2 Our Ideas in a Nutshell
2 Preliminaries
2.1 Indistinguishability Obfuscation
3 Affine Determinant Programs
4 The BIJMSZ iO Scheme
4.1 Transformation 1: Random Local Substitutions
4.2 Transformation 2: Small Even-Valued Noise
4.3 Transformation 3: Block-Diagonal Matrices
4.4 Transformation 4: AIK Re-randomization
5 Our Attack
5.1 Base Case
5.2 Advanced Case
5.3 The Scope of the Attack
6 A Plausible Fix and Further Discussions
References
Indistinguishability Obfuscation from LPN over Fp, DLIN, and PRGs in NC0
1 Introduction
2 Technical Overview
2.1 Challenges to Constructing Preprocessed Randomized Encoding
2.2 Constructing Proprocessed Polynomial Encoding
3 Preliminaries
4 Preprocessed Polynomial Encoding
4.1 PPE Construction Details
5 Amortized Randomized Encoding
5.1 Construction Details
6 Preprocessed Randomized Encoding
6.1 Construction of Preprocessed Randomized Encoding
7 Summing Up
References
Incompressible Cryptography
1 Introduction
1.1 Prior Work
1.2 Our Results
1.3 Other Related Work
1.4 Technical Overview
2 Preliminaries
3 Incompressible Encryption: Our Basic Construction
3.1 Definition
3.2 Construction
3.3 Proof of Security
3.4 Instantiating Our FE
4 Rate-1 Incompressible Encryption
4.1 Construction
4.2 Proof of Security
5 Incompressible Signatures: Our Basic Construction
5.1 Definition
5.2 Construction
5.3 Proof of Security
6 Rate-1 Incompressible Signatures
6.1 Incompressible Encoding
6.2 Construction
6.3 Equivalence to Incompressible Encoding
7 Constructing Rate-1 Functional Encryption
7.1 Building Blocks
7.2 Proof of Security
References
COA-Secure Obfuscation and Applications
1 Introduction
1.1 Our Contributions
1.2 Defining COA Obfuscation
1.3 Applications of COA Obfuscation
1.4 Constructing COA Obfuscation
2 Preliminaries
2.1 Non-Interactive Distributionally Indistinguishable (NIDI) Arguments
2.2 CCA Commitments
2.3 Obfuscation
3 New Definitions
3.1 COA-Secure Obfuscation
3.2 Verifiability Fortification for Obfuscation
3.3 COA Fortification for Obfuscation
4 Robust NIDI
5 Constructing COA Secure Obfuscation
6 Keyless Verifiable Watermarking
7 Completely CCA-secure Encryption
7.1 C-CCASecure PKE Scheme in the Plain Model
References
Unclonable Polymers and Their Cryptographic Applications
1 Introduction
1.1 Contributions
1.2 Related Work
2 Unclonable Polymer-Based Data Storage
3 The Consumable Token Functionality
3.1 Ideal Functionality Definition
3.2 A Construction for Consumable Tokens
4 Bounded-query Point Function Obfuscation
4.1 Definition
4.2 Construction
4.3 Security
5 (1,n)-time Programs
5.1 Definition
5.2 Construction and Security
References
Distributed (Correlation) Samplers: How to Remove a Trusted Dealer in One Round
1 Introduction
1.1 Related Work
1.2 Our Contributions
1.3 Technical Overview
2 Preliminaries
3 Defining Distributed Samplers
3.1 Security
4 A Construction with Semi-malicious Security
5 Upgrading to Active Security
5.1 Defeating Rushing
6 Public-Key PCFs for Reverse-Samplable Correlations
6.1 Correlation Functions and Their Properties
6.2 Defining Public Key PCFs
6.3 Public-Key PCF with Trusted Setup
6.4 Our Public-Key PCFs
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken