Public-Key Cryptography – PKC 2023 : 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Atlanta, GA, USA, May 7–10, 2023, Proceedings, Part I

The two-volume proceedings set LNCS 13940 and 13941 constitutes the refereed proceedings of the 26th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2023, which took place in March 2023 in Atlanta, GA, USA. The 49 papers included in these proceedings were carefully reviewed and selected from 183 submissions. They focus on all aspects of public-key cryptography, covering Post-Quantum Cryptography, Key Exchange and Messaging, Encryption, Homomorphic Cryptography and other topics. Preface Organization Contents – Part I Contents – Part II Post-quantum Cryptography Post-quantum Anonymity of Kyber 1 Introduction 1.1 Our Contributions 1.2 Technical Overview 1.3 Related Work 2 Preliminaries 2.1 Quantum Random Oracle Model 2.2 Cryptographic Primitives 3 Specification of Kyber 3.1 Security Properties of Kyber.PKE 4 IND-CCA Security of Kyber in the QROM 5 ANO-CCA Security of Kyber in the QROM 5.1 SPR-CCA Security of Kyber.KEM 5.2 SPR-CCA Security of Hybrid PKE Derived from Kyber.KEM References QCCA-Secure Generic Transformations in the Quantum Random Oracle Model 1 Introduction 1.1 Our Results 1.2 Related Work 2 Preliminaries 2.1 Notation 2.2 Quantum Random Oracle Model 3 Plaintext Extraction of the Oracle-Masked Scheme 4 Application in the Quantum Security Proof 4.1 FO: From OW-CPA to IND-qCCA in the QROM 4.2 REACT: From OW-qPCA to IND-qCCA in the QROM 4.3 TCH: From OW-qPCA to IND-qCCA in the QROM A The Construction of UExt A.1 The Construction of UExt for FO A.2 The Construction of UExt for REACT A.3 The Construction of UExt for T"0365T B Cryptographic Primitives B.1 Secret-Key Encryption B.2 Public-Key Encryption B.3 Key Encapsulation References A Thorough Treatment of Highly-Efficient NTRU Instantiations 1 Introduction 1.1 Speed 1.2 Decryption Error and Compactness 1.3 Proofs in the (Q)ROM 1.4 Concrete Results and Comparison to the State of the Art 2 Preliminaries 2.1 Notation 2.2 Cryptographic Definitions 3 Worst-Case to Average-Case Decryption Error 3.1 Simple Transformation ACWC0 with Redundancy 3.2 Transformation ACWC Without Redundancy 4 NTRU Encryption over NTT Friendly Rings 4.1 Notation 4.2 The Binomial Distribution 4.3 The NTRU Problem and Variants 4.4 NTRU-A: Encryption Based on R-NTRU + R-LWE2 for =2d 4.5 Generic NTRU Encryption and Error-Reducing Transformations References A Lightweight Identification Protocol Based on Lattices 1 Introduction 1.1 Contribution 1.2 Related Work 1.3 Outline 2 Background 2.1 Cyptographic Primitives 2.2 Protocol Security 3 The Identification Protocol 3.1 Description of the Identification Protocol 3.2 Security Analysis of the Identification Protocol 3.3 Extension to the Quantum Random Oracle Model 4 An Identification Protocol Based on Kyber 4.1 Security and Design Rationales 4.2 Parameter Sets 4.3 Implementation 4.4 Side-Channel Protection 5 Conclusion References POLKA: Towards Leakage-Resistant Post-quantum CCA-Secure Public Key Encryption 1 Introduction 2 Technical Overview and Cautionary Note 3 Background 3.1 Lattices and Discrete Gaussian Distributions 3.2 Rings and Ideal Lattices 4 POLKA: Rationale and Specifications 4.1 The Scheme with an Additive Mask 4.2 Black-Box Security Analysis 4.3 Parameters and Instantiations 5 Side-Channel Security Analysis 5.1 Leveled Implementation and Design Goals 5.2 Learning with Physical Rounding Assumption 5.3 Hardware Performance Evaluation 6 Conclusions References Attacks The Hidden Number Problem with Small Unknown Multipliers: Cryptanalyzing MEGA in Six Queries and Other Applications 1 Introduction 1.1 Technical Overview 1.2 Applying HNP-SUM to MEGA Cryptanalysis 1.3 Applying HNP-SUM to Implicit Factoring 2 Background 2.1 Lattices 2.2 The Hidden Number Problem 3 Solving HNP-SUM 3.1 Solving HNP-SUM with n = 2 3.2 Construction for n > 2 3.3 Alternative Basis for the Sublattice 3.4 Recovering Unknown Multipliers 3.5 Sublattice Determinant 3.6 Sublattice Recovery via Lattice Reduction 3.7 Experimental Evaluation 4 Application: Cryptanalyzing MEGA 4.1 Attack Context for MEGA 4.2 Original MEGA Attack of Backendal, Haller, and Paterson 4.3 Expressing Leakage Algebraically 4.4 Obtaining Most Significant Bytes 4.5 Refining Approximations 4.6 Recovering Unknown Multipliers 4.7 Recovering Plaintexts 4.8 Recovering the Factorization 4.9 Complexity 4.10 Experimental Evaluation 5 Application: Implicit Factoring 5.1 LSBs or MSBs Shared 5.2 Middle Bits Shared 5.3 Experimental Evaluation References Hull Attacks on the Lattice Isomorphism Problem 1 Introduction 1.1 Contributions 1.2 Technical Overview 2 Preliminaries 2.1 Lattices and Codes 2.2 Quadratic Forms 2.3 The p-adic Numbers 2.4 Genus Symbol 2.5 Relevant Values of s for the s-Hull 3 Extensions of the Definition of the Genus 4 The Genus of the Hull 5 A Lattice with a Better Attack via the Hull 5.1 When the Hull Is Trivial 5.2 Signed Permutation Equivalence and Graph Isomorphism 6 Conclusion 6.1 Revising LIP Hardness Conjecture 6.2 Unimodular Lattices 6.3 Open Question References A Key-Recovery Attack Against Mitaka in the t-Probing Model 1 Introduction 1.1 Our Contribution 2 Preliminaries 2.1 Operators and Relations 2.2 Cyclotomic Fields 2.3 Vectors and Matrices 2.4 Lattices and Gaussians 2.5 Masking 3 Description of Mitaka 3.1 Private and Public Keys 3.2 Signing Procedure 3.3 The Proof Outline of Mitaka and Its Flaw 4 Our Attack 4.1 Placing the Probes 4.2 Recovering the Signing Key 5 Concrete Results 5.1 Simulating the Leakage 5.2 Low-noise Regime: "026B30D b0"0362b0 - b0 "026B30D < 1/2 5.3 High-noise Regime: "026B30D b0"0362b0 - b0 "026B30D < q 5.4 Moderate-noise Regime: "026B30D b0"0362b0 - b0 "026B30D < 1 6 Conclusion References Signatures Hardening Signature Schemes via Derive-then-Derandomize: Stronger Security Proofs for EdDSA 1 Introduction 2 Preliminaries 3 Functor Framework 4 The Soundness of Derive-then-Derandomize 5 Security of EdDSA 6 Indifferentiability of Shrink-MD Class of Functors References Security Analysis of RSA-BSSA 1 Introduction 2 Definition of a Two-Move Blind Signature Scheme 2.1 Strong One-More Unforgeability 2.2 Blindness 2.3 A New Definition: Blind Tokens 3 The RSA-BSSA Scheme 3.1 The Basic Scheme 3.2 RSA-BSSA, Version A 3.3 RSA-BSSA, Version B 4 Blindness of RSA-BSSA 4.1 Blindness of the Signing Protocol 4.2 Blindness of Variants a and B 4.3 The Basic Version Is a Blind Token Scheme 4.4 Blindness of Chaum-RSA-FDH 5 Unforgeability of RSA-BSSA A Statement of Computational Hardness Assumptions B The Verification Algorithm, Step by Step References Extendable Threshold Ring Signatures with Enhanced Anonymity 1 Introduction 1.1 Our Contributions 2 Related Work 3 Preliminaries 3.1 Groth-Sahai Proofs 4 Extendable Threshold Ring Signature 5 Extendable Non-interactive Witness Indistinguishable Proof of Knowledge 6 Our Extendable Threshold Ring Signature 6.1 Security of Our Extendable Threshold Ring Signature 7 Our Extendable Non-Interactive Witness Indistinguishable Proof of Knowledge 7.1 GS Proofs of Partial Satisfiability 7.2 High-level Overview of Our ENIWI 7.3 Our ENIWI References Tracing a Linear Subspace: Application to Linearly-Homomorphic Group Signatures 1 Introduction 1.1 Contributions 1.2 Technical Overview 1.3 Organization 2 Preliminaries 2.1 Hardness Assumptions 2.2 Linearly-Homomorphic Signatures 3 Codes with the Fully Identifiable Parent Property 4 An Efficient Tracing Algorithm for Linear Subspaces 5 Linear-Subspace Tracing and Anonymity 6 A Model for Linearly-Homomorphic Group Signatures 7 Generic Construction of a LH-GSig Scheme 7.1 Properties of LH-Sig Schemes 7.2 High-level Description 7.3 Our Scheme 7.4 Efficiency References Isogenies SCALLOP: Scaling the CSI-FiSh 1 Introduction 1.1 Contribution 1.2 Technical Overview 2 Preliminaries 2.1 Elliptic Curves and Isogenies 2.2 Representing and Evaluating Isogenies 2.3 Orientation of Supersingular Curves and Ideal Group Action 3 The Generic Group Action 3.1 Factorization of Ideals and Decomposition of Isogenies 3.2 Effective Orientation 3.3 The Group Action Computation from the Effective Orientation 4 Security of a Group Action 5 SCALLOP: a Secure and Efficient Group Action 5.1 Parameter Choice and Precomputation 5.2 The Group Action Computation 6 Concrete Instantiation 6.1 Parameter Selection 6.2 Performance 7 Security Discussion: Evaluating the Descending Isogeny References Round-Optimal Oblivious Transfer and MPC from Computational CSIDH 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Preliminaries 2.1 Basic Cryptographic Primitives 2.2 Cryptographic Group Actions 2.3 Oblivious Transfer (OT) 3 Round-Optimal UC-Secure OT from wU-EGA 3.1 Warm-Up: 2-Round UC-OT Against Semi-honest Receiver 3.2 2-Round Maliciously Secure UC-OT 4 Round-Optimal OT in Plain Model from wU-EGA 4.1 Overview 4.2 Our Protocol-2 5 OT Extension from Reciprocal EGA 5.1 Reciprocal EGA and Reciprocal CSIDH 5.2 OT Construction of ch14LaiGG21 5.3 Constructing OT Extension Protocols from Reciprocal (R)EGA References Generic Models for Group Actions 1 Introduction 1.1 Contributions 2 Preliminaries 2.1 Notation 2.2 Security Games 2.3 Quantum Notation 3 Group Actions 3.1 Definitions 3.2 The CSIDH Group Action 3.3 Group Action Assumptions 4 Generic Group Action Model 4.1 Definitions and Relations 4.2 Generic Group Action Model with Twists 4.3 Quantum Generic Group Action Model 4.4 Comparison with the Generic Model by Montgomery and Zhandry 5 Algebraic Group Action Model 5.1 Definition and Relations 5.2 Results in the Quantum Algebraic Group Action Model with Twists 5.3 Security Analysis of ElGamal in the Quantum Algebraic Group Action Model with Twists References Crypto for Crypto CRAFT: Composable Randomness Beacons and Output-Independent Abort MPC From Time 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Preliminaries 2.1 The TARDIS ch16EC:BDDNO21 Composable Time Model 2.2 Trapdoor Verifiable Sequential Computation 2.3 Multi-party Message Delivery 3 Publicly Verifiable Time-Lock Puzzles 4 Universally Composable Verifiable Delay Functions 5 UC-Secure Semi-synchronous Randomness Beacons 5.1 Randomness Beacons from TLPs 5.2 Using a Public Ledger FLedger with TLP-RB 5.3 Randomness Beacons from VDFs 6 MPC with (Punishable) Output-Independent Abort 6.1 Functionalities for Output-Independent Abort 6.2 Building MPC with Output-Independent Abort References Efficient and Universally Composable Single Secret Leader Election from Pairings 1 Introduction 1.1 Our Contribution 1.2 Other Related Work 1.3 Organization 2 Preliminaries 2.1 Notation 2.2 SXDH Assumption 2.3 Functional Encryption 2.4 Functional Encryption for Modular Keyword Search 2.5 Our Realization of FE for Modular Keyword Search 2.6 Non Interactive Zero-Knowledge 2.7 UC Model and Ideal Functionalities 3 Universally Composable SSLE 3.1 A Parametrised Definition 4 UC-secure SSLE from FE for Modular Keyword Search 5 An Efficient UC-secure SSLE from SXDH 5.1 Intuition 5.2 SSLE Protocol with Ideal Setup Functionality 5.3 Realising the Setup 6 Efficiency Considerations References Simple, Fast, Efficient, and Tightly-Secure Non-malleable Non-interactive Timed Commitments 1 Introduction 2 Preliminaries 3 Standard Model Constructions 3.1 Non-interactive Zero-Knowledge Proofs 3.2 Standard-Model Instantiation of SS-NIZKs 3.3 Construction of Linearly Homomorphic Non-malleable NITC 3.4 Construction of Multiplicatively Homomorphic Non-malleable NITC References Certifying Giant Nonprimes 1 Introduction 1.1 Our Contribution 1.2 Technical Overview 1.3 Related Work 2 Preliminaries 3 Pietrzak's PoE in Groups of Known Order 3.1 (Non-)Soundness 4 Certifying Non-Primality of Proth Primes 4.1 Completeness 4.2 Soundness 4.3 Efficiency 4.4 Comparison with Pietrzak's PoE 5 Open Problems A Attacking Pietrzak's Protocol in Proth Number Groups References Transparent Batchable Time-lock Puzzles and Applications to Byzantine Consensus 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Technical Overview 2.1 Time-Lock Puzzles with Batch Solving 2.2 Application 1: Efficient Byzantine Broadcast 2.3 Application 2: Permissionless Consensus in the Mobile Sluggish Model 3 Cryptographic Background 3.1 Time-Lock Puzzles 3.2 Puncturable Pseudorandom Functions 3.3 Indistinguishability Obfuscation 4 Time-Lock Puzzles with Batch Solving 4.1 Definition 4.2 Bounded Batching of TLPs 4.3 Unbounded Batching of TLPs 5 Application 1: Byzantine Broadcast 5.1 Model and Definitions 5.2 Protocol 6 Application 2: Nakamoto Consensus Secure Against a Mobile Sluggish Adversary 6.1 Attack on Nakamoto Consensus in the Mobile Sluggish Model 6.2 Model 6.3 Protocol References Pairings Decentralized Multi-Authority Attribute-Based Inner-Product FE: Large Universe and Unbounded 1 Introduction 2 Technical Overview 2.1 Constructing the Small Universe MA-ABUIPFE 2.2 Constructing the Large Universe MA-ABUIPFE 3 Preliminaries 3.1 Notations 3.2 Complexity Assumptions 4 Decentralized (Large Universe) MA-ABUIPFE for LSSS 5 The Proposed Small Universe MA-ABUIPFE from DBDH 5.1 The Construction 5.2 Correctness 5.3 Security Analysis 6 The Proposed Large Universe MA-ABUIPFE from L-DBDH References Multi-Client Inner Product Encryption: Function-Hiding Instantiations Without Random Oracles 1 Introduction 1.1 Our Results and Contributions 1.2 Additional Related Work 2 Overview of Our Constructions and Techniques 2.1 Why Prior Work Needed a Random Oracle 2.2 Removing the RO: A Strawman Idea 2.3 Our Selectively Secure Construction 2.4 Proving Selective Function-Hiding Security 2.5 Achieving Adaptive Function-Hiding Security 2.6 Removing the ``All-or-Nothing'' Admissibility Rule 3 Definitions: Multi-Client Inner Product Encryption 4 Preliminaries 4.1 Function-Hiding (Single-Input) Inner Product Encryption 4.2 Correlated Pseudorandom Function 5 Function-Hiding MCIPE 5.1 Selective Function-Hiding MCIPE References GLUE: Generalizing Unbounded Attribute-Based Encryption for Flexible Efficiency Trade-Offs 1 Introduction 1.1 Our Contributions 1.2 New Construction: GLUE 1.3 Generalizing RW13 by Generalizing the Hash 1.4 Security Proof 1.5 Practical Extensions 1.6 Efficiency Comparison with Existing Schemes Supporting (1)-(5) 2 Preliminaries 2.1 Access Structures 2.2 Attribute-based Encryption 2.3 Full Security Against Chosen-Plaintext Attacks 2.4 Pairings (or Bilinear Maps) 2.5 Pair Encoding Schemes 3 Generalizing Rouselakis-Waters 3.1 The Rouselakis-Waters Scheme 3.2 First Attempt: A Naive Approach 3.3 Second (Successful) Attempt 3.4 More Efficient Decryption 4 Our Construction 4.1 The Associated Pair Encoding Scheme 5 The Security Proof 5.1 The Rouselakis-Waters Proof 5.2 Generalizing the Rouselakis-Waters Proof 5.3 The Selective Symbolic Property 5.4 Co-selective Symbolic Property 6 Performance Analysis 7 Applying Multiple Instantiations of GLUE in Practice 8 Future Work 9 Conclusion References Key Exchange and Messaging EKE Meets Tight Security in the Universally Composable Framework 1 Introduction 1.1 Technical Overview 1.2 Roadmap 2 Preliminaries 2.1 Hardness Assumptions 3 PAKE with Tight Security in the UC Framework 3.1 UC Framework for PAKE 3.2 The 2DH-EKE Protocol 3.3 Security Analysis 4 Asymmetric PAKE with Optimal Tightness in the UC Framework 4.1 UC Framework for aPAKE 4.2 The 2DH-aEKE Protocol 4.3 Security Analysis 5 Optimal Reduction Loss in aPAKE 6 Tight Security for 2DH-SPAKE2 in the Relaxed UC Framework References A Universally Composable PAKE with Zero Communication Cost 1 Introduction 2 Preliminaries 2.1 Overview of the UC Framework 2.2 Overview of PAKE 3 A No-Message UC PAKE 4 Seven Equivalent Ways to Guarantee Correctness 4.1 Three Equivalent Ways to Guarantee Correctness 4.2 Three Sets of Variants 4.3 Putting It Together 5 Impossibility of a Direct Solution 6 PAKE as a Three-Party Protocol 6.1 Correctness 6.2 PAKE Guaranteeing Output 7 Conclusion References Sender-binding Key Encapsulation 1 Introduction 2 Preliminaries 2.1 The KEM-DEM Framework 2.2 Game-based Security Notions 2.3 Simulation-based Security and UC 2.4 Ideal Functionalities 3 Related Work 4 Sender-binding Key Encapsulation 5 Realizing Secure Message Transfer 6 Realizing Secure Channels 7 Efficient LWE-based Construction 8 Conclusion References Pattern Matching in Encrypted Stream from Inner Product Encryption 1 Introduction 1.1 Related Works 1.2 Our Contributions 2 Definitions 2.1 Functional Encryption 2.2 Some Classes of Functional Encryption 3 From HVE to SEPM Through Fragmentation 3.1 Fragmentation 3.2 Conversion 3.3 Security 4 Hidden Vector Encryption from Inner Product Encryption 4.1 KSW Conversion 4.2 Security Analysis of KSW Conversion 4.3 Our Conversion 4.4 Selective Security 5 Adaptive Security 5.1 Key Privacy 5.2 Examples of Key Private IPE Schemes 5.3 Examples of Non Key Private IPE Schemes 5.4 Security Result 6 Consequences References Author Index