Applied Cryptography and Network Security : 21st International Conference, ACNS 2023, Kyoto, Japan, June 19–22, 2023, Proceedings, Part II

The LNCS two-volume set 13905 and LNCS 13906 constitutes the refereed proceedings of the 21st International Conference on Applied Cryptography and Network Security, ACNS 2023, held in Tokyo, Japan, during June 19-22, 2023. The 53 full papers included in these proceedings were carefully reviewed and selected from a total of 263 submissions. They are organized in topical sections as follows: Part I: side-channel and fault attacks; symmetric cryptanalysis; web security; elliptic curves and pairings; homomorphic cryptography; machine learning; and lattices and codes. Part II: embedded security; privacy-preserving protocols; isogeny-based cryptography; encryption; advanced primitives; multiparty computation; and Blockchain. Preface Organization Contents – Part II Contents – Part I Embedded Security A Forkcipher-Based Pseudo-Random Number Generator 1 Introduction 2 Preliminaries 2.1 Notation 2.2 Systems, Transcripts and the H-coefficient Proof Technique 3 Security Model 4 Our Constructions 4.1 A Forkcipher-Based Condenser 4.2 Our FCRNG PRNG Construction 5 Security Proofs 5.1 Security of FCTRCond 5.2 Security of FCRNG 5.3 Security of FCRNG-T 6 Discussion 7 Efficiency Estimations 8 Conclusion and Open Problems A Security of FCTRCond References DMA'n'Play: Practical Remote Attestation Based on Direct Memory Access 1 Introduction 2 Background 2.1 U(S)ART and SPI 2.2 Direct-Memory-Access (DMA) 3 Assumptions and Attacker Model 4 Challenges 5 Concept 5.1 Using DMA for Attestation 5.2 DMA'n'Play Attestation 5.3 Verifier 5.4 Locking of DMA-Controllers 5.5 Hardware Requirements and Target Platforms 5.6 Devices Without Source Code 6 Implementation 6.1 Attested Device 6.2 Verifier 6.3 DMA'n'Play To-Go 6.4 Integration Guidelines 7 Evaluation 7.1 Case Study 7.2 Real-Time Capabilities 7.3 System Performance View 7.4 Feasibility of Full Memory Attestation 7.5 Power Consumption 7.6 Summary 8 Security Discussion 9 Related Work 9.1 Remote Attestation 9.2 DMA Security 10 Conclusion References Recommendation for a Holistic Secure Embedded ISA Extension 1 Introduction 2 Technical Background 2.1 Code Injection & Reuse Attacks 2.2 Glitching Attacks 3 Preliminaries 3.1 System Model 3.2 Adversary Model 3.3 Security Goals 4 Literature Study 4.1 Glitching Defenses 4.2 CFI 4.3 Memory Integrity 5 Our Recommendation 5.1 Basic Block Level 5.2 Function Level 5.3 Global Level 6 Proof-of-concept 6.1 ISA Implementation and Simulation 6.2 Code Transformation 6.3 Software and Hardware Considerations 6.4 Security Evaluation 6.5 Evaluation 7 Future Work 8 Conclusion References QuantumCharge: Post-Quantum Cryptography for Electric Vehicle Charging 1 Introduction 2 Background 2.1 E-Mobility Architecture 2.2 Post-Quantum Cryptography on Embedded Systems 3 System and Attacker Model 4 Requirements 5 Security Concept 5.1 Analysis of PnC Cryptographic Algorithms 5.2 General Approach 5.3 Extending ISO 15118 with QuantumCharge 6 Formal Security Verification 7 Implementation and Practical Feasibility Evaluation 8 Conclusion A Appendix A.1 Tamarin Lemma for [sr7]RS7 References Privacy-Preserving Protocols Constant-Round Multiparty Private Function Evaluation with (Quasi-)Linear Complexities 1 Introduction 2 Notations and Preliminaries 2.1 Outgoing Wires and Ingoing Wires 2.2 Public Info 2.3 EP and OEP 2.4 OSN 3 Overview 4 Main Protocol 4.1 Multiparty Constant-Round PFE 4.2 Optimize 4.3 HE-OEP 5 Efficiency Analysis 5.1 Communication Complexity 5.2 Computation Complexity 5.3 Round Complexity A OSN Protocol A.1 Switching Network and Permutation Network A.2 OSN B Security Proof References Predicate Private Set Intersection with Linear Complexity 1 Introduction 2 Related Works 3 Problem Formulation 3.1 Defining PPSI 3.2 Design Goal 4 Preliminaries 4.1 Secret Sharing 4.2 Hashing Techniques 4.3 Oblivious Transfer 4.4 Secure Comparison 4.5 Technique Overview of Circuit-PSI 5 The Construction of PPSI 5.1 High-Level Overview 5.2 Technical Description 5.3 The Predicate Masking Protocol 5.4 The Batched Secure Comparison Protocol 5.5 Applications of PPSI 6 Security Analysis 7 Performance Evaluation 7.1 Implementation Details 7.2 Experimental Environment 7.3 Evaluation for the Applications of PPSI 7.4 Theoretical Analyses 7.5 Performance Comparison with CGS 8 Conclusion References A Framework for UC Secure Privacy Preserving Biometric Authentication Using Efficient Functional Encryption 1 Introduction 1.1 Related Work 2 Preliminaries 2.1 (Secret Key) Function Hiding Functional Encryption 3 Modeling Biometric Authentication in the UC Framework 3.1 Threat Model 3.2 The Ideal Functionality 4 The Framework 4.1 Use Case 4.2 Requirements 4.3 The Protocol 4.4 Security Proof 5 Instantiation 6 Implementation 7 Conclusion and Future Work A Security Proof References Private Information Retrieval with Result Verification for More Servers 1 Introduction 1.1 Our Contribution 1.2 Paper Organization 2 Preliminaries 2.1 Notation 2.2 Constant Weight Code 2.3 Cramer's Rule 2.4 Woodruff-Yekhanin PIR 3 The PIR-RV Model 4 k-Server PIR-RV Protocol 4.1 Overview 4.2 Our Construction 5 Conclusion References Isogeny-Based Cryptography Practical Robust DKG Protocols for CSIDH 1 Introduction 2 Preliminaries 2.1 Isogeny-Based Cryptography 2.2 DKG Protocols and Piecewise Verifiable Proofs 3 Robust DKG for CSIDH Using Bivariate Polynomials 3.1 A VSS Based on Bivariate Polynomials 3.2 Robust Distributed Generation of [x]E0 4 Robust DKG for Structured Public Keys 5 Efficiency of the DKG Protocols and Optimizations 6 Conclusion A Security Proofs A.1 Proof of Theorem 4.1 B Computational and Communication Costs of Our Protocols References Efficient Isogeny Proofs Using Generic Techniques 1 Introduction 1.1 Contribution 1.2 Related Work 2 Preliminaries 2.1 Notations 2.2 Isogeny Graphs 2.3 Proof Systems 2.4 Rank-1 Constraint Systems 2.5 MPC-in-the-Head 2.6 Reed-Solomon IOPs 3 Construction 3.1 Hardness Assumptions and Relations 3.2 High-Level Overview 3.3 From Isogeny Relation to R1CS Instance 3.4 Optimization for R1CS over Fp2 3.5 Optimization for Lifting to Fp Fp 3.6 Parameter Choice 4 Implementation and Evaluation 4.1 Comparison to Secuer PoK 4.2 Identification Scheme for Moderate Length Walks 5 Conclusion A Preventing Backtracking References Low Memory Attacks on Small Key CSIDH 1 Introduction 2 Preliminaries 2.1 Restricted Effective Group Actions 2.2 Cryptographic Group Actions and Computational Assumptions 2.3 Isogeny-Based REGAs 3 Adapting Techniques to the REGA-DLOGm Setting 3.1 Pollard-Style Random Walks: A Galbraith-Hess-Smart Adaptation 3.2 Meet-in-the-Middle (MitM) 3.3 Parallel Collision Search (PCS) 4 A New Time-Memory Trade-Off Using Representations 4.1 A First Representation-Based Approach 4.2 Interpolation Using Partial Representations 4.3 Increasing the Amount of Representations 4.4 Enforcing an Equal Weight Distribution 4.5 The Case of Arbitrary m 4.6 Potential Impact on Bit Security Level A The Case of Larger m References Encryption On the Complete Non-malleability of the Fujisaki-Okamoto Transform 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Preliminaries 2.1 Notation 2.2 Public-Key Encryption 2.3 Secret-Key Encryption 3 Completely Non-malleable KEMs 4 Analysis of Fujisaki-Okamoto Transforms 4.1 Analysis of the U/m Transformations 4.2 Analysis of the U/ Transformations 4.3 Modified Transformation 5 Relation with Completely Non-malleable PKE 5.1 NM-ATK* PKE -3mu NM-ATK* KEM 5.2 NM-ATK* KEM + NM-ATK SKE-3mu NM-ATK* PKE A Supporting Proofs A.1 Proof of Theorem 1 A.2 Proof of Theorem 3 A.3 Proof of Theorem 4 A.4 Proof of Theorem 5 References Optimal Security Notion for Decentralized Multi-Client Functional Encryption 1 Introduction 2 Preliminaries 2.1 Hardness Assumptions 2.2 Dual Pairing Vector Spaces 3 Technical Overview 3.1 Motivations for a Refinement on Admissibility 3.2 Towards a New Admissibility Condition Under Separated Corruption of Keys 3.3 Optimality of the New Admissibility: A Conceptual Challenge 3.4 DMCFE for Inner Products with Refined Security Model 4 A Stronger Security Model for Decentralized Multi-Client Functional Encryption 4.1 Optimality of Admissibility as per Definition 6 5 DMCFE for Inner Products with Stronger Security Against Complete Queries 5.1 Construction 5.2 Adaptive Security Against Static Corruptions of Secret Keys 6 DMCFE for Inner-Products with Stronger Security Against Incomplete Queries 6.1 Constructions References Anonymous (Hierarchical) Identity-Based Encryption from Broader Assumptions 1 Introduction 1.1 Our Results 1.2 Technical Overview 2 Background 2.1 Hard Problems and Hardcore Predicates 2.2 Anonymous (Hierarchical) Identity-Based Encryption 2.3 Chameleon Encryption (CE) 2.4 Blind Public Key Encryption 2.5 Blind Garbled Circuits 2.6 Delegatable Pseudorandom Functions 3 Blind Chameleon Encryption 3.1 Definition 3.2 Our Construction 4 Anonymous Identity-Based Encryption 4.1 Blind Identity-Based Encryption 4.2 Our Construction 5 Anonymous Hierarchical Identity-Based Encryption 5.1 Blind OTSE from Blind CE 5.2 Blind HIBE from Blind OTSE 6 A(H)IBE from -Hiding Assumption 7 Discussions 8 Concluding Remarks A Proof of Security A.1 Proof of Theorem 3 A.2 Proof of Theorem 5 A.3 Proof of Theorem 6 A.4 Proof of Theorem 9 A.5 Proof of Theorem 10 A.6 Proof of Theorem 12 References Publicly Auditable Functional Encryption 1 Introduction 1.1 Our Results 1.2 Overview of Techniques 2 Related Work 3 Preliminaries 3.1 Functional Encryption 3.2 Multi Input Functional Encryption 4 Publicly Auditable Functional Encryption 4.1 Public Auditability Definitions 5 PAFE Constructions from FE 5.1 Auditability with Trusted Authority 5.2 Auditability with Untrusted Authority 6 Relations Among PA Definitions 7 Publicly Auditable Inner-Product MIFE 8 Conclusion and Discussion A Proof of Theorem 1 References Advanced Primitives Robustly Reusable Fuzzy Extractors in a Post-quantum World 1 Introduction 2 Preliminaries 2.1 Quantum Random Oracle Model (QROM) 2.2 Fuzzy Extractor Definitions 3 Simple Hash Construction and Results 4 Simple Robustly Reusable Fuzzy Extractors 4.1 Reusability in the QROM 4.2 Reusable Robustness in the QROM 4.3 Parameters and Efficiency 5 Post-Quantum Standard Model Construction 6 Conclusion A Quantum Computation Preliminaries B Preliminaries for Standard Model Construction C (Ring-)LPN Preliminaries D Deferring Measurements for Recorded Classical Oracle Queries E Separate Robustness and Reusability Proofs E.1 Robustness in the Classical ROM F Security Proof for Ring-LPN SKEM References Subversion-Resilient Authenticated Encryption Without Random Oracles 1 Introduction 1.1 Subversion-Resilience Models 1.2 Towards Subversion-Resilient Authenticated Encryption 1.3 Our Contribution 1.4 Discussion 2 Subversion-Resilience 2.1 Notation and Model 2.2 Subversion-Resilience 2.3 Achieving Subversion-Resilience 3 Pseudorandom Functions 3.1 Constructing Subversion-Resilient PRFs 4 MAC 4.1 MAC from PRFs 5 Symmetric Encryption 6 Authenticated Encryption 6.1 Achieving Subversion-Resilience via Encrypt-then-MAC References Scored Anonymous Credentials 1 Introduction 1.1 A Critical Review of Existing Systems 1.2 Our Contribution 2 Definitions 2.1 Syntax of Scored (or Blocklistable) Anonymous Credentials 2.2 Security Requirements 3 Proposed System 3.1 Building Blocks 3.2 Key Ideas 3.3 Instantiation 3.4 Efficiency and Flexibility Highlights 3.5 Discussion on Privacy and Security Issues 3.6 Integration with Other System Components 4 Performance 4.1 Computation and Communication Complexities 4.2 Empirical Results 5 Conclusion A Batch BBS+ Signature B Alternative for Zero-Knowledge Argument of a Shuffle C Authentication using Batch-BBS+ and Range Proof D Security D.1 Simulation-Based Model D.2 Proof References GeT a CAKE: Generic Transformations from Key Encaspulation Mechanisms to Password Authenticated Key Exchanges 1 Introduction 1.1 Our Contributions 1.2 Outline of the Paper 2 Preliminaries 2.1 Notations 2.2 Key Encapsulation Mechanism 2.3 Learning with Errors 2.4 CRYSTALS-Kyber 3 Password Authenticated Key Exchange 3.1 Introduction to PAKE 3.2 The Universal Composability (UC) Model 4 Two Pieces of One Cake: Study of EKE and OEKE 4.1 CAKE 4.2 OCAKE 5 Crystal-Kyber 5.1 Security Properties 5.2 Instantiation of the Block Cipher 5.3 Parameters 6 Conclusion and Perspectives References Multiparty Computation Explicit and Nearly Tight Lower Bound for 2-Party Perfectly Secure FSS 1 Introduction 1.1 Our Contributions 1.2 Technical Overview 1.3 Organization 2 Preliminaries 2.1 Notation 2.2 Function Secret Sharing 3 Known Negative Results 3.1 Lower Bound for Information-Theoretic DPF 3.2 Connection to One-Way Function 4 Our Explicit Lower Bound 4.1 Conversion from IT-FSS to Simplified IT-FSS 4.2 Lower Bound for Simplified IT-FSS 4.3 Examples for Specific Function Classes 5 Nearly Optimal Construction References Multi-Theorem Fiat-Shamir Transform from Correlation-Intractable Hash Functions 1 Introduction 1.1 Our Results 1.2 Technical Overview 1.3 Related Work 2 Preliminaries 2.1 Diffie-Hellman Related Definitions 2.2 Non-Interactive Argument Systems Related Definitions 2.3 Sigma-protocol Related Definitions 2.4 Multi-theorem, Adaptive Non-interactive Proofs 2.5 Semi-adaptive Soundness 2.6 Semi-instance-dependant (SID) Trapdoor Sigma-Protocol 2.7 Correlation-intractable Hash Functions and FS Transform 3 NIZK with Adaptive Multi-theorem ZK A SID Trapdoor Sigma-Protocols for Non-DH Tuples and Proofs A.1 Efficiency analysis References Game-Theoretically Secure Protocols for the Ordinal Random Assignment Problem 1 Introduction 1.1 Technical Challenges 1.2 Our Contributions 1.3 Other Related Work 2 Preliminaries 2.1 Some Well-Known Properties of Mechanisms 2.2 Security Notions of Protocols 3 Standard Building Blocks 3.1 Augmented Protocols for the Lottery Problem 4 Impossibility Result to Achieve Maximin Security 4.1 Reduction from Coin-Flipping Problem 5 Achieving Perfect Maximin Security 5.1 Preference Priority (PP) Protocol 5.2 Maximin Security Analysis 6 Achieving Uniform Dominance 6.1 OnlinePSVar Protocol 6.2 OnlinePSVar Achieves Uniform Dominance 6.3 OnlinePSVar Is Not Maximin Secure nor Strongly Truthful 7 Conclusion References A New Approach to Garbled Circuits 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Technical Overview 3 Preliminaries 4 The Scheme 4.1 Garbling Algorithm 4.2 Motivating Our Scheme 4.3 Security 5 Supporting Free-XOR A Additional Details of the Scheme A.1 Setting the Length of RO Output B Proof of Theorem 1 B.1 Proof Setup B.2 The Complete Proof References Blockchain Mt. Random: Multi-tiered Randomness Beacons 1 Introduction 1.1 Our Contributions 1.2 Technical Overview 1.3 Related Works 2 Preliminaries 2.1 Adversarial and Communication Models 2.2 Packed Shamir Secret Sharing 2.3 Non-interactive Zero Knowledge Proofs 2.4 Publicly Verifiable Secret Sharing (PVSS) 2.5 Verifiable Random Functions (VRFs) 2.6 Threshold Verifiable Random Functions (TVRFs) 2.7 Threshold Encryption 3 Distributed Key Generation via PVSS 4 GULL: Gradual Release of PVSS Outputs via Threshold Encryption 5 Constructing Mt. Random 5.1 Security Analysis 6 Efficiency Analysis References Revisiting Transaction Ledger Robustness in the Miner Extractable Value Era 1 Introduction 1.1 Contributions 2 Transaction Ledger Model 2.1 Ledger Backbone Model 2.2 Dictatorial Miners 3 Content Preference Robustness 3.1 Rational Liveness 3.2 Rational Transaction Ordering 3.3 Restrictions on the Environment 4 Compiling a Robust Ledger into a CPR Ledger 4.1 CPR Compiler 4.2 Compiler Overview 4.3 Time-Lock Transaction Generation Oracle 4.4 Chain Validity Function 4.5 Input Contribution Function 4.6 Chain Reading Function 4.7 Security Analysis 5 Discussions 6 Conclusion A Related Work B Transaction Ledger Protocol C Analysis of Theorem 1 References An Empirical Analysis of Security and Privacy Risks in Android Cryptocurrency Wallet Apps 1 Introduction 2 Background and Data Collection Methodology 2.1 Background 2.2 Cryptocurrency Wallet Apps Collection on Google Play 3 Assessment Methodology 3.1 Static Analysis 3.2 Network Measurements 3.3 Compliance and User Comments Analysis 4 Static Analysis Result 4.1 Permission Analysis 4.2 Third-party Libraries Penetration 4.3 Malware Presences 4.4 Anti-analysis detection 5 Dynamic Analysis Result 5.1 Securing Network Requests 5.2 Sensitive Data Aggregation and Sharing 5.3 Third-party Domain Request 6 Privacy Policy Compliance and User Review Results 6.1 Privacy Policy Analysis 6.2 User Reviews Analysis 7 Related Work 8 Conclusion A List of Anti-analysis Methods in Wallet Apps B Keywords for Personal Data Transmission Analysis References Author Index