Public-Key Cryptography – PKC 2020: 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Edinburgh, UK, May 4–7, 2020, Proceedings, Part II (Security and Cryptology)

The two-volume set LNCS 12110 and 12111 constitutes the refereed proceedings of the 23 rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, PKC 2020, held in Edinburgh, UK, in May 2020. The 44 full papers presented were carefully reviewed and selected from 180 submissions. They are organized in topical sections such as: functional encryption; identity-based encryption; obfuscation and applications; encryption schemes; secure channels; basic primitives with special properties; proofs and arguments; lattice-based cryptography; isogeny-based cryptography; multiparty protocols; secure computation and related primitives; post-quantum primitives; and privacy-preserving schemes. Preface Organization Contents – Part II Contents – Part I Lattice-Based Cryptography The Randomized Slicer for CVPP: Sharper, Faster, Smaller, Batchier 1 Introduction 1.1 Contributions 1.2 Working Heuristics 2 Preliminaries 2.1 Notation 2.2 Spherical Geometry 2.3 Lattices 2.4 Solving CVPP with the Randomized Slicer 3 The Random Walk Model 4 Numerical Approximations 4.1 Discretization 4.2 Convex Optimization 4.3 Numerical Results 5 An Exact Solution for the Randomized Slicer 6 Memoryless Nearest Neighbour Searching 7 Bounded Distance Decoding with Preprocessing 8 Application to Graph-Based NNS References Tweaking the Asymmetry of Asymmetric-Key Cryptography on Lattices: KEMs and Signatures of Smaller Sizes 1 Introduction 1.1 Comparison with NIST Round2 Lattice-Based PKEs/KEMs 1.2 Comparison with NIST Round2 Lattice-Based Signatures 1.3 Organizations 2 Preliminaries 2.1 Notation 2.2 Definitions 2.3 High/Low Order Bits and Hints 3 An Improved KEM from AMLWE 3.1 Design Rationale 3.2 The Construction 3.3 Provable Security 3.4 Choices of Parameters 4 An Improved Signature from AMLWE and AMSIS 4.1 Design Rationale 4.2 The Construction 4.3 Provable Security 4.4 Choices of Parameters 5 Known Attacks Against AMLWE and AMSIS 5.1 Concrete Security of KEM 5.2 Concrete Security of SIG A Definitions of Hard Problems References MPSign: A Signature from Small-Secret Middle-Product Learning with Errors 1 Introduction 1.1 Contributions 1.2 Comparison with Prior Works 2 Preliminaries 2.1 Polynomials and Matrices 2.2 Gaussian Distributions 2.3 Polynomial and Middle-Product Learning with Errors 2.4 Cryptographic Definitions 3 Hardness of Middle-Product LWE with Small Secrets 4 An Attack on Inhomogeneous PSIS with Small Secrets 5 A Signature Scheme Based on Small Secrets MPLWE 5.1 The Identification Scheme 5.2 The Signature Scheme 6 Concrete Parameters 7 Implementation References Proofs and Arguments II Witness Indistinguishability for Any Single-Round Argument with Applications to Access Control 1 Introduction 1.1 Our Witness Indistinguishability Transformation 1.2 Application: Succinct Single-Round Access Control 1.3 Technical Overview of Our WI Transformation 2 Witness Indistinguishability for Any Argument System 2.1 Preliminaries 2.2 Private Remote Evaluation 2.3 Making Single-Round Protocols Witness Indistinguishable 3 Succinct Single-Round Access Control Scheme 3.1 Delegation for Batch-NP Families 3.2 Known Batch Delegation Schemes 3.3 Our Scheme 3.4 Proof of Theorem 3.7 for Our Construction References Boosting Verifiable Computation on Encrypted Data 1 Introduction 1.1 Ensuring Correctness of Privacy-Preserving Computation 1.2 Our Contributions 1.3 Organization 2 Notation and Definitions 2.1 Commitment Schemes 2.2 SNARKs – Succinct Non-Interactive Arguments of Knowledge 3 Proof Systems for Arithmetic Function Evaluation over Quotient Polynomial Rings 3.1 Formal Description of Our Rq- Scheme 3.2 Security Analysis 4 Applications to Computing on Encrypted Data 4.1 Verifiable Computation 4.2 Our VC Scheme 4.3 Preserving Privacy of the Inputs Against the Verifier 5 Bivariate Polynomial Commitment 5.1 Computational Assumptions 5.2 Knowledge Commitment for Bivariate Polynomials 6 CaP-SNARK for Bivariate Polynomial Evaluation 6.1 Relations for Bivariate Polynomial Partial Evaluation 6.2 Our BivPE- Scheme for Bivariate Polynomial Evaluation 7 CaP-SNARK for Simultaneous Evaluations 7.1 Commitment for Multiple Univariate Polynomials 7.2 Succinct Proof of Multiple Evaluations in a Point k 7.3 Efficiency and Comparison 8 Security Analysis of Our CaP BivPE- References Isogeny-Based Cryptography Lossy CSI-FiSh: Efficient Signature Scheme with Tight Reduction to Decisional CSIDH-512 1 Introduction 1.1 Background 1.2 Our Contribution 2 Preliminaries 2.1 Identification Protocols 2.2 Digital Signature Schemes 2.3 Pseudorandom Functions 2.4 Fiat-Shamir Transformation 2.5 Class Group Actions and Hardness Assumption 3 Base Lossy Identification Protocol from CSIDH-512 3.1 Hardness Assumption: Decisional CSIDH 3.2 Construction of Base Lossy Identification Protocol 3.3 Security of Base Lossy Identification Protocol IDBasels 3.4 Lossy Soundness Amplification of IDBasels 4 Optimized Lossy Identification Protocol from CSIDH-512 4.1 Hardness Assumption: Fixed-Curve Multi-decisional CSIDH 4.2 Enlarging Challenge Space of Base Lossy Identification Protocol 4.3 (Almost) Doubling Challenge Space of Lossy Identification Scheme IDEnChls 4.4 Lossy Soundness Amplification of IDDenChls 5 Lossy CSI-FiSh: Tightly Secure Signature from CSIDH-512 5.1 Construction of Lossy CSI-FiSh 5.2 Instantiations and Comparison to CSI-FiSh 6 Conclusions and Open Problems References Threshold Schemes from Isogeny Assumptions 1 Introduction 2 Preliminaries 2.1 Shamir's Secret Sharing and Threshold Cryptosystems 2.2 Hard Homogeneous Spaces 3 Threshold Schemes from HHS 3.1 Threshold Group Action 3.2 Threshold HHS ElGamal Decryption 3.3 Threshold Signatures 4 Instantiations Based on Isogeny Graphs 4.1 Supersingular Complex Multiplication 4.2 CSIDH and CSI-FiSh 4.3 Instantiation of the Threshold Schemes 5 Conclusion References Multiparty Protocols Topology-Hiding Computation for Networks with Unknown Delays 1 Introduction 1.1 Contributions 1.2 Related Work 2 The Probabilistic Unknown Delay Model 2.1 Impossibility of Stronger Models 2.2 Adversary 2.3 Communication Network and Clocks 2.4 Additional Related Work 3 Protocols for Restricted Classes of Graphs 3.1 Synchronous THC from Random Walks 3.2 Protocol for Cycles 3.3 Protocol for Trees 4 Protocol for General Graphs 4.1 Preprocessing 4.2 Computation 4.3 Computing the Eulerian Cycle A Adversarially-Controlled Delays Leak Topology A.1 Adversarially-Controlled Delay Indistinguishability-based Security Definition A.2 Proof that Adversarially-Controlled Delays Leak Topology B PKCR* Encryption B.1 Construction of PKCR* Based on DDH C The Function Executed by the Hardware Boxes References Sublinear-Round Byzantine Agreement Under Corrupt Majority 1 Introduction 1.1 Our Results and Contributions 2 Preliminaries 2.1 Protocol Execution Model 2.2 Byzantine Agreement 3 Technical Roadmap: Nearly Round-Optimal BA for Corrupt Majority 3.1 Warmup: Any Constant Fraction of Static Corruption 3.2 Achieving Adaptive Security and Removing the Leader Election Oracle 3.3 Organization of the Subsequent Formal Sections 4 Formal Description of Fmine-Hybrid Protocol 4.1 Ideal Functionality Fmine for Random Eligibility Determination 4.2 Formal Protocol in the Fmine-Hybrid World 4.3 Analysis in the Fmine-Hybrid World 5 Removing the Idealized Functionality Fmine 5.1 Preliminary: Adaptively Secure Non-interactive Zero-Knowledge Proofs 5.2 Adaptively Secure Non-interactive Commitment Scheme 5.3 Removing Fmine with Cryptography References Bandwidth-Efficient Threshold EC-DSA 1 Introduction 2 Preliminaries 2.1 The Elliptic Curve Digital Signature Algorithm 2.2 Building Blocks from Class Groups 2.3 Algorithmic Assumptions 3 Threshold EC-DSA Protocol 3.1 ZKAoK Ensuring a CL Ciphertext Is Well Formed 3.2 Interactive Set Up for the CL Encryption Scheme 3.3 Resulting Threshold EC-DSA Protocol 4 Security 4.1 Simulating the Key Generation Protocol 4.2 Simulating the Signature Generation 4.3 The Simulation of a Semi-correct Execution 4.4 Non Semi-correct Executions 4.5 Concluding the Proof 5 Further Improvements 5.1 An Improved ZKPoK Which Kills Low Order Elements 5.2 Assuming a Standardised Group 6 Efficiency Comparisons References Secure Computation and Related Primitives Blazing Fast OT for Three-Round UC OT Extension 1 Introduction 1.1 Our Contributions 1.2 More Discussion on Related Works 2 Preliminaries 3 Technical Overview 3.1 Overview of KOS 3.2 Relaxation in the OT Functionality 3.3 Usage in KOS OT Extension 3.4 Optimized OT Protocol in the Observable RO Model 3.5 Circumventing the Impossibility Result of ch11C:GMMM18 4 Weakening the Oblivious Transfer Functionality 5 Oblivious Transfer Extension Using OT 5.1 Security Proof 5.2 Efficiency 6 Implementing Instances of FSF-rOT 6.1 Security Proof 6.2 Efficiency 7 Implementation and Evaluation References Going Beyond Dual Execution: MPC for Functions with Efficient Verification 1 Introduction 1.1 Results in the 1-bit Leakage Model 1.2 Extending Dual Execution to Other Protocols 2 Preliminaries 2.1 Verifiable Secret Sharing (VSS) 2.2 Secure Computation with 1-bit Leakage 2.3 Garbled Circuits 2.4 The ch12BeaverMR90 Garbling 3 Dual Execution with Efficient Verification 4 Additively Secure Protocols with Program Checkers 4.1 Additive Attacks and AMD Circuits 4.2 Additive Security of BMR Distributed Garbling 4.3 Compiling Additively Secure Protocols 5 Perfect Matching Protocol Secure up to Additive Attacks References MonZ2ka: Fast Maliciously Secure Two Party Computation on Z2k 1 Introduction 2 Preliminaries 2.1 Notation 2.2 Linearly-Homomorphic Encryption for Messages in Z2n 2.3 Commitments 2.4 Security Model 2.5 Value-Representation in SPDZ2k 3 Offline Phase 3.1 On the Impossibility of Enhanced-CPA Security in Z2n: Comparing with Overdrive Offline Phase 4 Joye-Libert Cryptosystem and Companion Protocols 4.1 Zero-Knowledge Proof of Correct Multiplication 4.2 Zero-Knowledge Proof of Correct Multiplication of Two Committed (or Encrypted) Values 5 Efficiency Analysis References Post-Quantum Primitives Generic Authenticated Key Exchange in the Quantum Random Oracle Model 1 Introduction 1.1 Our Contributions 2 Preliminaries 2.1 Public-Key Encryption 2.2 Key Encapsulation 2.3 Quantum Computation 3 The FO Transformation: QROM Security with Correctness Errors 3.1 Modularisation of TPunc 3.2 Transformation FOm and Correctness Errors 3.3 CCA Security Without Disjoint Simulatability 4 Two-Message Authenticated Key Exchange 5 Transformation from PKE to AKE 5.1 IND-StAA Security Without Disjoint Simulatability References Threshold Ring Signatures: New Definitions and Post-quantum Security 1 Introduction 1.1 Limitations of Previous Work 1.2 Our Contribution 2 Related Work 3 Preliminaries 3.1 Threshold Ring Signatures in Presence of Active Adversaries 4 Post-quantum Secure Threshold Ring Signatures 5 Post-quantum Security of TRS 5.1 Proofs 6 Trapdoor Commitments from OWFs 6.1 On the Notion of Binding in Presence of Quantum Adversaries References Tight and Optimal Reductions for Signatures Based on Average Trapdoor Preimage Sampleable Functions and Applications to Code-Based Signatures 1 Introduction 2 Preliminaries 3 Digital Signatures and EUF-CMA Security Model in a Classical/Quantum Setting 4 Family of ATPSF 4.1 Constructing a Signature Scheme from ATPSF 5 One-Wayness, Collision Resistance and the Claw with Random Function Problem 5.1 Definitions 5.2 Relating These Different Advantages 6 Tight Reduction to the Claw Problem, with ATPSF 6.1 Proof of Our Main Theorem 7 Quantum Security Proof in the QROM 7.1 The Quantum Random Oracle Model 7.2 Tight Quantum Security of SF 8 Applying the Result to Code-Based Signatures Based on ATPSF 8.1 Canonical Construction of Code-Based ATPSF 8.2 Relating Hardness of Breaking the CBATPSF with the Hardness of Breaking Standard Code-Based Problems 8.3 Wave Instantiation 9 Conclusion References Cryptanalysis and Concrete Security Faster Cofactorization with ECM Using Mixed Representations 1 Introduction 2 Preliminaries 2.1 The Elliptic Curve Method 2.2 Montgomery Curves 2.3 Twisted Edwards Curves 2.4 The Best of Both Worlds 2.5 Parameterization 3 Scalar Multiplication 3.1 Generation of Double-Base Expansions 3.2 Generation of Double-Base Chains 3.3 Generation of Lucas Chains 4 Combination of Blocks for ECM Stage 1 4.1 Bos–Kleinjung Algorithm 4.2 Our Algorithm 5 Results and Comparison 6 Conclusion A Counting Double-Base Expansions References Improved Classical Cryptanalysis of SIKE in Practice 1 Introduction 2 Preliminaries: van Oorschot-Wiener's Collision Search 2.1 The CSSI Problem 2.2 The Meet-in-the-middle Claw Finding Algorithm 2.3 Solving CSSI with van Oorschot-Wiener 2.4 Complexity Analysis of van Oorschot-Wiener 3 Parallel Collision Search for Supersingular Isogenies 3.1 Solving SIKE Instances 3.2 Applying van Oorschot-Wiener to SIKE 3.3 Partial Isogeny Precomputation 3.4 Fast Collision Checking 4 Implementation 5 Analysis of SIKE Round-2 Parameters 5.1 Concrete Security of SIKE Round-2 Parameters 5.2 Concrete Security of SIKEp434 References A Short-List of Pairing-Friendly Curves Resistant to Special TNFS at the 128-Bit Security Level 1 Introduction 2 The Special Tower Number Field Sieve 2.1 Estimation of TNFS Cost 2.2 Special Polynomial Selection 3 Complete Families of Pairing-Friendly Curves 3.1 Brezing–Weng Constructions of Pairing-Friendly Curves 3.2 Reducing the Possibilities 3.3 Security Estimate for the Finite Field 4 Optimal Ate Pairing Computation: Miller Loop 4.1 Prime Embedding Degrees 11 and 13 4.2 Even Embedding Degrees 10 and 14 4.3 Comparison 5 Overview of the 192-Bit Security Level 6 Conclusion References Privacy-Preserving Schemes Privacy-Preserving Authenticated Key Exchange and the Case of IKEv2 1 Introduction 1.1 Privacy in AKE Protocols 1.2 A New Security Model 1.3 Comparison with TOR and Practical Motivation 1.4 IPsec IKEv2 Is PPAKE 1.5 On the Challenge of Constructing PPAKE 1.6 Contributions 1.7 Related Works 1.8 Building Blocks 2 PPAKE in Practice: Generic Construction, Comparison and Limitations 3 Security Model for PPAKE 3.1 Computational Model for Key Exchange 3.2 Adversarial Model for Key Exchange 3.3 Original Key Partnering 3.4 Security and Privacy Model 3.5 Additional Considerations 4 Internet Protocol Security (IPsec) 5 IKEv2 Is a Secure PPAKE Protocol 5.1 Proof for Initiator-Adversaries 5.2 Additional Considerations 6 Summary and Future Work References Linearly-Homomorphic Signatures and Scalable Mix-Nets 1 Introduction 1.1 State of the Art 1.2 Our Approach 1.3 Organization 2 Computational Assumptions 2.1 Classical Assumptions 2.2 Unlinkability Assumption 3 Linearly-Homomorphic Signatures 3.1 Definition and Security 3.2 Our One-Time Linearly-Homomorphic Signature 3.3 Notations and Constraints 3.4 FSH Linearly-Homomorphic Signature Scheme 4 Mix-Networks 4.1 General Description 4.2 Difficulties 4.3 Our Scheme 4.4 Constant-Size Proof 4.5 Efficiency 5 Security Analysis 5.1 Proof of Soundness 5.2 Proof of Privacy: Unlinkability 6 Applications 6.1 Electronic Voting 6.2 Message Routing References Efficient Redactable Signature and Application to Anonymous Credentials 1 Introduction 1.1 Our Contribution 1.2 Organisation 2 Preliminaries 3 Redactable Signatures 3.1 Syntax 3.2 Security Model 4 Short Redactable Signatures 4.1 Our Construction 4.2 Achieving Unlinkability 4.3 Security Analysis 5 Anonymous Credentials 5.1 Syntax 5.2 Security Model 6 Our Anonymous Credentials System 6.1 Our Construction 6.2 Security Analysis 7 Efficiency 8 Conclusion References Author Index The two-volume set LNCS 12110 and 12111 constitutes the refereed proceedings of the 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, PKC 2020, held in Edinburgh, UK, in May 2020. The 44 full papers presented were carefully reviewed and selected from 180 submissions. They are organized in topical sections such as: functional encryption; identity-based encryption; obfuscation and applications; encryption schemes; secure channels; basic primitives with special properties; proofs and arguments; lattice-based cryptography; isogeny-based cryptography; multiparty protocols; secure computation and related primitives; post-quantum primitives; and privacy-preserving schemes. -- Provided by publisher