Cryptology and Network Security: 22nd International Conference, CANS 2023, Augusta, GA, USA, October 31 – November 2, 2023, Proceedings (Lecture Notes in Computer Science)

This book constitutes the refereed proceedings of the 22 nd International Conference on Cryptology and Network Security, CANS 2023, which was held in October/November 2023 in Augusta, GA, USA. The 25 papers presented were thoroughly revised and selected from the 54 submissions. They are organized in the following topical sections: Schemes I; Basic Primitives; Security; MPC with Cards; Blockchain; MPC and Secret Sharing; Schemes II. Preface Organization Keynote Abstracts Building Covert Communication Systems That Resist Traffic Analysis Cultivating a National Culture of Cybersecurity Contents Schemes I Forward Security Under Leakage Resilience, Revisited 1 Introduction 1.1 Background and Motivation 1.2 Our Contributions in Brief 2 Technical Overview 3 Preliminaries 3.1 Notations 3.2 Different Notions of Entropy 3.3 Primitives Required for Our Constructions. 4 Our Results in the FS+CL Model 4.1 Encryption in the FS+CL Model 4.2 Our Construction 5 Our Results in the FS+(C)EBL Model 5.1 The FS+EBL Model 5.2 NIKE in FS+EBL Model 5.3 Syntax of FS-EBLR NIKE 5.4 Security Model for FS-EBLR NIKE 5.5 Construction of NIKE Scheme in the FS+EBL Model 5.6 Security Proof References Anonymous Broadcast Authentication with Logarithmic-Order Ciphertexts from LWE 1 Introduction 1.1 Related Work 1.2 Our Contributions and Paper Organization 2 Preliminaries 2.1 Anonymous Broadcast Authentication (ABA) 3 Vernam-Styled Multirecipient Encryption with Information-Theoretic Security 4 Template Construction of Base ABA 4.1 A Template 4.2 Anonymity 4.3 Unforgeability 5 Concatenation of ABAs 5.1 Anonymity in the Restricted Device Selection 5.2 Modification Against Recombination Attack 5.3 Anonymity from the Dependency of Algebraic Systems 6 Concrete Scheme and Security Parameters 7 Concluding Remarks References Traceable Policy-Based Signatures with Delegation 1 Introduction 2 Preliminaries and Building Blocks 2.1 Rerandomizable Digital Signature Scheme (RDS) 2.2 Simulation-Sound Extractable NIZK (SE-NIZK) 2.3 Digital Signature Schemes 3 Traceable Policy-Based Signatures (TPBS) 3.1 TPBS Security Definitions 3.2 Privacy 3.3 Unforgeability 3.4 Non-frameability 3.5 Traceability 4 TPBS Generic Construction 5 TPBS Security 6 TPBS Instantiation and Performance 7 Comparisson with PBS and Xu et al.'s Schemes 8 Conclusion References Basic Primitives How to Enumerate LWE Keys as Narrow as in Kyber/Dilithium 1 Introduction 2 Preliminaries 3 How to Enumerate LWE Keys with May's Algorithm 3.1 Brute-Force and Meet-in-the-Middle LWE Key Enumeration 3.2 High-Level Idea of the Algorithm 4 Enumerating Keys from a Probabilistic Distribution 4.1 A Polynomial Fraction of All Keys Achieves Expectations 4.2 Attacking Almost All Keys via Permutations 5 Instantiating LWE-Search with Simple (Rep-0) Representations 5.1 Rep-0 Instantiation of LWE-Search 6 More Representations 6.1 Rep-1 Representations 6.2 Rep-2, Rep-3 Representations 7 Other Distributions – Ternary, B(2), and Uniform 7.1 Ternary Keys—Featuring NTRU, BLISS and GLP 7.2 B(2) and B(3)—Featuring Kyber-512 and Kyber-768,1024 7.3 Uniform Distribution—Featuring Dilithium-1024,2048 8 Parameter Optimization and Implementation 8.1 Parameter Search 8.2 Implementation A Full Parameter Sets: Ternary, Binomial, and Uniform References Towards Minimizing Non-linearity in Type-II Generalized Feistel Networks 1 Introduction 2 Preliminaries 3 A Chosen-Plaintext Attack on 3 Rounds 4 SPRP Security at 5 Rounds with Public Permutations 4.1 Proof Setup 4.2 Bad Transcripts 4.3 Bounding the Ratio ()/() 5 SPRP Security at 5 Rounds with Public Functions 6 Conclusion A The H-Coefficient Technique B Deferred Proofs B.1 Proof of Lemma 2 B.2 Proof of Lemma 3 C MDS Candidates in F N C.1 MDS in Binary Field C.2 MDS in Prime Field References Hardness of Learning AES with Gradient-Based Methods 1 Introduction 2 Preliminaries 2.1 Advanced Encryption Standard 2.2 Statistical Properties of AES 3 Main Result 4 Experiments 5 Conclusion References Security Privacy-Preserving Digital Vaccine Passport 1 Introduction 1.1 Our Contribution 2 Problem Statement and Desirable Properties 2.1 Security Definition 2.2 Desirable Security 2.3 Desirable Performance 3 Cryptographic Preliminaries 3.1 Randomizable Signature Scheme 3.2 Private Information Retrieval 3.3 Private Matching 4 Digital Vaccine Passport Constructions 4.1 System Overview 4.2 PIR-Based Construction (Online Verification) 4.3 Digital Signature-Based Construction (Offline Verification) 5 Performance A Performance B Related Work C Security of Our Digital Signature-Based Construction D Formal Security Definition E Diffie–Hellman-Based Private Matching References Exploiting Android Browser 1 Introduction 2 Background 3 The Proxy Attack 3.1 Threat Model Overview 3.2 Attack Overview 3.3 Attack Heuristics 3.4 Collection of Information 3.5 Launch 3.6 Retrieving Data 4 Evaluation Study 4.1 Settings 4.2 Accessible Information 4.3 Evaluation Results 5 Discussion and Lessons 6 Related Work 7 Conclusion References Are Current CCPA Compliant Banners Conveying User's Desired Opt-Out Decisions? An Empirical Study of Cookie Consent Banners 1 Introduction 2 Related Works 3 Methodology 3.1 Participant Recruitment 3.2 Presurvey Questionnaire 3.3 Online Experiment 3.4 Exit Survey 4 Data Analysis and Results 4.1 Participant Demographics 4.2 Experiment Results 4.3 Exit Survey Result 5 Discussion 5.1 Understanding User Consent Choices and Privacy Actions 5.2 Exploring User Interaction with Consent Banners 5.3 Limitations and Future Work 5.4 Recommendations to Policy Makers 6 Conclusion References MPC with Cards Upper Bounds on the Number of Shuffles for Two-Helping-Card Multi-Input AND Protocols 1 Introduction 1.1 The Mizuki–Sone and Protocol 1.2 Committed-Format Multi-input and Protocol 1.3 Contribution of This Paper 1.4 Related Works 1.5 Organization of This Paper 2 Preliminaries 2.1 Pile-Scramble Shuffle 2.2 Batching Technique 3 Application of Batching to MS-AND Protocol 3.1 Idea 3.2 MSbatching: How to Batch MS-AND Protocols 3.3 Example of Two-Helping-Card and Protocol by MSbatching 4 Class of MSbatching Protocols and Corresponding Problem 4.1 MSbatching Protocols 4.2 MSbatching Move-Sequence Problem 5 Proposed Protocol 5.1 Description of Proposed Protocol 5.2 Proposed Protocol for n=48 6 Search for Optimal Protocols 6.1 Lemmas to Narrow Search Space 6.2 Shortest Move-Sequence Search 6.3 Comparison 7 Conclusion References Free-XOR in Card-Based Garbled Circuits 1 Introduction 2 Preliminaries 3 Card-Based Garbled Circuits 4 Free-XOR in Card-Based Garbled Circuits 5 Eliminating Restriction for Outputs 6 Conclusion References Cryptanalysis Hidden Stream Ciphers and TMTO Attacks on TLS 1.3, DTLS 1.3, QUIC, and Signal 1 Introduction 2 Preliminaries 2.1 Signal Protocol and the Symmetric-Key Ratchet 2.2 TLS 1.3 and the Key Update Mechanism 3 Hidden Stream Ciphers and TMTO Attacks 3.1 Synchronous Stream Ciphers 3.2 Time Memory Trade-Off Attacks 3.3 TMTO Attacks on Signal and TLS 1.3 3.4 Equal Plaintext Prefix 4 Signal Protocol - Analysis and Recommendations 5 TLS 1.3 Family - Analysis and Recommendations 5.1 Time Memory Trade-Off Attacks 5.2 Key Exfiltration Attacks and Frequent Ephemeral Diffie-Hellman 5.3 Analysis of the Procedure Used to Calculate AEAD Limits 6 Conclusions, Recommendations, and Future Work References Differential Cryptanalysis with SAT, SMT, MILP, and CP: A Detailed Comparison for Bit-Oriented Primitives 1 Introduction 2 Preliminaries 3 Cipher Components Models 3.1 XOR Component 3.2 Rotation and Shift Components 3.3 Linear Layer Component 3.4 S-Box Component 3.5 AND/OR Component 3.6 Modular Addition Component 4 Experimental Results 4.1 Choice of Solvers 4.2 Comparison for Task 1 4.3 Comparison for Task 2 4.4 Comparison for Task 3 4.5 Speeding up CryptoMiniSat 5 Conclusion A Differential Cryptanalysis B Formalisms B.1 Satisfiability (SAT) B.2 Satisfiability Modulo Theories (SMT) B.3 Mixed-Integer Linear Programming (MILP) B.4 Constraint Programming (CP) C Experimental Results Tables References Key Filtering in Cube Attacks from the Implementation Aspect 1 Introduction 2 Preliminary 2.1 The Main Procedures of Cube Attacks 2.2 Division Property Based Superpoly Recoveries 2.3 Table Lookup Based Key Filtering Techniques 3 New Attacks on Kreyvium 3.1 New Results for 898-Round Kreyvium 3.2 New Results for 899-Round Kreyvium 3.3 New Results for 900-Round Kreyvium 4 Implementation Dependency 4.1 An Implementation Dependency Analysis Example 5 Further Analysis for Cube Attacks 5.1 Analysis for More Cases of Cube Attacks 5.2 Multiple Cubes Vs Single Cube 6 Conclusions A Details of Our Attacks on Kreyvium A.1 Degree Evaluations of 899-Round Kreyvium A.2 The ANFs of Superpolies Corresponding to Attacks on 898- And 900-Round Kreyvium References New Techniques for Modeling SBoxes: An MILP Approach 1 Introduction 1.1 Related Work 1.2 Our Contribution 1.3 Organization of the Paper 2 Background 2.1 Representation of SBoxes Using Inequalities 3 Filtering Inequalities by Greedy Random-Tiebreaker 3.1 Why Random Tiebreaking Improves the Performance of the Greedy Algorithm? 3.2 Implementations and Results 4 Filtering Inequalities by Subset Addition 4.1 Comparison with Boura and Coggia's ch15BouraC Approach 4.2 Multithreading and Filtration 4.3 Implementation and Results 5 Conclusion A Existing Algorithm for Choosing Best Inequalities B Sample Reduced Inequalities References Blockchain LucidiTEE: Scalable Policy-Based Multiparty Computation with Fairness 1 Introduction 2 Overview of LucidiTEE 2.1 Running Example: Personal Finance App 2.2 Requirements of Acme 2.3 Acme on LucidiTEE 3 Building Blocks 3.1 Trusted Execution Environment (TEE) 3.2 Shared, Append-Only Ledger 3.3 Cryptographic Primitives and Assumptions 4 Adversary Model 5 Policy-Compliant Computation 5.1 Specifying and Creating a Computation 5.2 Binding Inputs to Computations 5.3 Enforcing Policy-Compliance 5.4 Producing Encrypted Output 5.5 Recording Computation on Ledger 5.6 Fair Output Delivery 6 Implementation 7 Evaluation 7.1 Case Studies 7.2 Performance Measurement 8 Related Work 9 Conclusion References Improving Privacy of Anonymous Proof-of-Stake Protocols 1 Introduction 2 Preliminaries 3 Attack on Anonymous PoS and Its Limitations 3.1 Frequency Attacks Against Stake Privacy 3.2 Interval Estimation for Stakes in Practice 4 Privacy of PoS Against Frequency Attack 4.1 (T,,)-Privacy 4.2 (T,,)-Privacy in Practice 5 Anonymous Proof-of-Stake with Noise 5.1 Adding Noise to Anonymous PoS 5.2 (T,,)-Privacy of APoS-N 5.3 Security Properties of Underlying PoS A Hoeffding Bound B AVRF C Frequency Attack over 12 Epochs D Functionalities References Compact Stateful Deterministic Wallet from Isogeny-Based Signature Featuring Uniquely Rerandomizable Public Keys 1 Introduction 2 Preliminaries 2.1 Isogeny-Based Cryptography 2.2 Class Group Action 3 Signature Schemes 3.1 CSI-FiSh 3.2 CSI-SharK 4 Signature Scheme with Perfectly Rerandomizable Keys 4.1 Signature Scheme with Perfectly Rerandomizable Keys from CSI-FiSh 4.2 Signature Scheme with Perfectly Rerandomizable Keys from CSI-SharK 5 Stateful Deterministic Wallet 6 Stateful Deterministic Wallet from Isogenies References CTA: Confidential Transactions Protocol with State Accumulator 1 Introduction 1.1 Our Contributions 1.2 Technique Overview of ZK for Lattice-Based Accumulator 2 Preliminaries 3 Lattice-Based ZK Proofs for Accumulators 3.1 Construction of Lattice-Based Accumulator 3.2 Zero-Knowledge Proofs of Our Accumulator 4 Confidential Transactions with State Accumulator 4.1 Syntax 4.2 Security Model 4.3 Construction of CTA 5 Conclusions A More on Preliminaries A.1 Challenge Space A.2 Rejection Sampling B Proof for Theorem 2 C Proof of Theorem 3 D Proof for Lemma 2 E Proof of Theorem 4 References MPC and Secret Sharing A Plug-n-Play Framework for Scaling Private Set Intersection to Billion-Sized Sets 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Preliminaries 2.1 Private Set Intersection 2.2 Apache Spark 2.3 Threat Model 3 Parallelizing PSI via Binning 3.1 Analysis 3.2 Applying Our Binning Technique 4 Scalable Private Database Joins 4.1 Database Joins Across Data Domains 4.2 System Architecture 4.3 Spark-PSI Implementation 5 Experimental Evaluation 5.1 System Setup 5.2 Microbenchmarking 5.3 End-to-End Performance References Lower Bounds on the Share Size of Leakage Resilient Cheating Detectable Secret Sharing 1 Introduction 1.1 Contributions 1.2 Related Works 2 Model and Definitions 2.1 Secret Sharing 2.2 Cheater Detection 2.3 Leakage Resilient Secret Sharing 2.4 Leakage Resilient Cheating Detectable Secret Sharing 3 Preliminaries 4 A Lower Bound Using Leakage and Tampering of a Single Share 5 A Lower Bound Using Shares of an Unauthorized Set and Leakage of a Single Share 6 Cheater Detectability and Non-Malleability in Secret Sharing 7 Conclusion A Non-malleable Codes B Proofs References Schemes II Lattice-Based Key-Value Commitment Scheme with Key-Binding and Key-Hiding Properties 1 Introduction 1.1 Commitment Scheme and Key-Value Commitment Scheme 1.2 Construction Without a Trusted Setup Based on Lattice Assumption with Key-Binding and Key-Hiding Properties 1.3 Contribution 1.4 Paper Organization 2 Preliminary 3 New Security Assumption and Its Difficulty Proof 3.1 New Definitions as Defined in This Paper 4 Proposed Insert-KVC Based on SIS 4.1 Concrete Explanation of Proposed Insert-KVCm/2,n,q, 4.2 Key-Binding of Proposed Insert-KVCm/2,n,q, 4.3 Key-Hiding of Insert-KVCm/2,n,q, 5 Proposed Key-Value Commitment Based on SIS 5.1 Concrete Explanation of Proposed KVCm,n,q, 5.2 Key-Binding of Proposed KVCm,n,q, 5.3 Key-Hiding of KVCm,n,q, 6 Comparison 7 Conclusion References A Practical Forward-Secure DualRing 1 Introduction 1.1 Motivations 1.2 Overview of Our Construction 1.3 Related Work 2 Preliminaries 2.1 Complexity Assumptions 2.2 DualRing 2.3 Forward Security 3 Definition and Models 3.1 Definition 3.2 Security Models 4 Our Construction 4.1 Security Analysis 5 Extension 6 Implementation and Evaluation 7 Conclusion A Proof of Theorem 1 B Proof of Theorem 2 References Dually Computable Cryptographic Accumulators and Their Application to Attribute Based Encryption 1 Introduction 2 Preliminaries 2.1 Cryptographic Accumulators 2.2 Other Preliminaries 3 A New Accumulator Scheme 4 Dually Computable Cryptographic Accumulators 4.1 Definitions 4.2 Our First Dually Computable Cryptographic Accumulator 5 Application of Dually Computable Accumulator: Attribute Based Encryption 5.1 Security Definitions for ABE 5.2 ABE from Dualy Computable Accumulator: Intuition 5.3 Our CP-ABE Scheme 5.4 Comparison 6 Conclusion References A Minor Note on Obtaining Simpler iO Constructions via Depleted Obfuscators 1 Introduction 1.1 Our Result 1.2 How to Use ADPs to Obfuscate Specific Classes of Circuits 1.3 The Usage of ADPs in Our Scheme 2 Background 2.1 Basic Definitions 2.2 Direct ADPs from Randomized Encodings 3 Our Indistinguishability Obfuscator 4 Security of Our iO Scheme 5 ADPs as Depleted Obfuscators A Puncturable PRFs with Evaluations in NC1 A.1 The Encoding Evaluation Algorithm for the pPRF in ch25TCC:BraVai15 A.2 Punctured Evaluation's Parallel Complexity B GKPVZ13's Encryption Procedure is in NC1 B.1 Attribute-Based Encryption B.2 Fully Homomorphic Encryption B.3 Parallel Complexity of ch25STOC:GKPVZ13's Encryption Procedure when Instantiated with GSW13 and GVW13 References Correction to: Upper Bounds on the Number of Shuffles for Two-Helping-Card Multi-Input AND Protocols Correction to: Chapter 10 in: J. Deng et al. (Eds.): Cryptology and Network Security, LNCS 14342, https://doi.org/10.1007/978-981-99-7563-1_10 Author Index