Applied Cryptography and Network Security: 22nd International Conference, ACNS 2024, Abu Dhabi, United Arab Emirates, March 5–8, 2024, Proceedings, Part I

Preface
Organization
Abstracts of Keynote Talks
Applying Machine Learning to Securing Cellular Networks
Real-World Cryptanalysis
CAPTCHAs: What Are They Good For?
Contents – Part I
Contents – Part II
Contents – Part III
Cryptographic Protocols
CryptoZoo: A Viewer for Reduction Proofs
1 Introduction
2 Related Work
3 State-Separating Proofs
4 A Proof Viewer for SSPs
4.1 Proof Viewing Concepts
4.2 Implementation Considerations
5 Case Study: IND-CPA Vs. Simulation-Based Security
6 Case Study: Constant-Depth GGM Tree
7 Case Study: Yao's Garbling Scheme
8 Comparison
8.1 Yao's Garbling Scheme
8.2 SSP Proofs of TLS 1.3
8.3 SSP Proofs of the MLS Key Schedule
8.4 Formal Verification Tools for SSPs
9 Conclusion and Future Work
References
Element Distinctness and Bounded Input Size in Private Set Intersection and Related Protocols
1 Introduction
2 Related Work and Background
2.1 Private Set Intersection (PSI)
2.2 PSI Variants
2.3 PSI with Restrictions
2.4 PSI with Multiset Input
2.5 Zero-Knowledge Proofs
2.6 Homomorphic Encryption
3 Proving Element Distinctness
3.1 Puzzle-Based PoED Construction
3.2 Analysis of PoED-Puzzle Protocol
4 PSI with Element Distinctness Check
4.1 Adversary Model
4.2 Definition of AD-PSI
4.3 A Construction for AD-PSI Based on PoED-puzzle
4.4 Alternative AD-PSI and Modified Construction
5 AD-PSI Variants
5.1 PSI-CA with Element Distinctness (AD-PSI-CA)
5.2 PSI-X with Element Distinctness (AD-PSI-X)
5.3 PSI-DT with Element Distinctness (AD-PSI-DT)
6 Completing Bounded-Size-Hiding-PSI
7 Authorized PSI with Element Distinctness
7.1 AD-APSI Definition
7.2 AD-APSI Construction
7.3 Security Analysis
8 Conclusion
A Security Proof for AD-PSI-puzzle
B AD-PSI Variants
C Security Proof for AD-APSI
References
A New Approach to Efficient and Secure Fixed-Point Computation
1 Introduction
1.1 Related Work
1.2 Construction Blueprint
2 Preliminaries
2.1 UC Functionalities
3 Truncation
3.1 RNS in MPC
3.2 Fixed-Point Arithmetic
4 The Construction
4.1 Preprocessing
4.2 Lifting
4.3 Probabilistic Truncation
4.4 Error Reduction
5 Efficiency
5.1 Implementation
5.2 Comparison with Related Techniques
References
Auditable Attribute-Based Credentials Scheme and Its Application in Contact Tracing
1 Introduction
2 Preliminaries
3 Auditable Attribute-Based Credentials Scheme
3.1 Auditable Public Keys
3.2 Formal Definitions of Auditable ABC
3.3 Our Constructions and Analysis
4 Application: Contact Tracing
4.1 An Auditable ABC-Based Construction
4.2 Security and Analysis
4.3 Implementation
5 Conclusion
A The Necessity of Enhancing Contact Tracing Systems
B The SPS-EQ Scheme from ch4spseqspspkc2022
C Extending the BLS Signature ch4bls01 with APK
References
Verification Protocol for Stable Matching from Conditional Disclosure of Secrets
1 Introduction
1.1 Our Contribution
1.2 Applications
1.3 Organization
2 Related Works
2.1 Stable Matching
2.2 Conditional Disclosure of Secrets
2.3 Multi-client Verifiable Computation
3 Preliminaries
3.1 Stable Matching
3.2 Conditional Disclosure of Secrets
3.3 Multi-client Verifiable Computation
3.4 Secret Sharing
4 Proposed CDS Schemes
4.1 CDS Scheme for Unstable Matching
4.2 CDS Scheme for Stable Matching
4.3 Possible Improvements
5 Verification Protocol for Stable Matching
6 Implementation
7 Concluding Remarks
References
Non-malleable Fuzzy Extractors
1 Introduction
1.1 Our Results
1.2 Related Work
2 Preliminaries
2.1 (Keyless) Fuzzy Extractors
2.2 Non-malleable Codes
3 Non-malleable Fuzzy Extractors
4 Construction
5 Fuzzy Tamper-Resilient Security
6 Conclusions
References
Upgrading Fuzzy Extractors
1 Introduction
1.1 Our Contribution
1.2 Related Work
1.3 Discussion and Future Work
2 Preliminaries
2.1 Entropy Definitions
2.2 Obfuscation Definitions
2.3 Fuzzy Extractors
3 Weakly-Private Fuzzy Extractors
3.1 Weakly Private FE from FE and MBCC Obfuscation
3.2 Weakly Private FE from Secure Sketch and MBCC Obfuscation
4 Robustness
5 Reuse
A Privacy vs FE Security
B Reusability from Composable MBCC Obfuscation
References
X-Lock: A Secure XOR-Based Fuzzy Extractor for Resource Constrained Devices
1 Introduction
2 Related Works
3 Background
4 X-Lock: Construction Details
5 X-Lock: Algorithm Analysis
5.1 Security Analysis
5.2 Bias and Correlation Analysis
5.3 Costs Analysis
6 Implementation and Comparison
7 Conclusion
References
Encrypted Data
Efficient Clustering on Encrypted Data
1 Introduction
2 Related Works
3 Background
3.1 Approximate Homomorphic Encryption CKKS
3.2 Newton's Method
4 System Architecture and Threat Model
4.1 System Architecture
4.2 Threat Model
4.3 Security
5 Fully Privacy-Preserving Clustering Scheme Based on FHE
5.1 Preliminaries
5.2 Ciphertext Comparison
5.3 Ciphertext Division
5.4 Converting the One-Hot Vectors to Label in Plaintexts
5.5 The Complete Algorithm for Privacy-Preserving Clustering
5.6 Security Proof
6 An Optimized Algorithm
6.1 Block Clustering Scheme
6.2 Block Clustering Scheme with Cluster Selection
7 Experiment Results
7.1 Experiment Setup
7.2 Clustering Accuracy
7.3 Run Time
7.4 Performance of Block Clustering Scheme with Cluster Selection
8 Conclusions
References
Generic Construction of Forward Secure Public Key Authenticated Encryption with Keyword Search
1 Introduction
2 Preliminaries
2.1 PAEKS
2.2 0/1 Encodings
3 Definition of FS-PAEKS
4 Our Generic Construction of FS-PAEKS
5 Security Analysis
6 Vulnerability of the Jiang Et Al. FS-PAEKS Scheme
7 Conclusion
References
Encryption Mechanisms for Receipt-Free and Perfectly Private Verifiable Elections
1 Introduction
1.1 Our Contributions
1.2 Our Techniques
1.3 Related Work
1.4 Overview of Paper
2 Background
2.1 Assumptions and Primitives
2.2 Traceable Receipt-Free Encryption (TREnc)
2.3 Commitment Consistent Encryption (CCE)
3 The Construction of Our Scheme
3.1 Description
3.2 Verification Equations
3.3 Security Analysis
3.4 Efficiency
4 Application to E-Voting
4.1 Voting Scheme with a Homomorphic Tally
4.2 Voting Scheme with a Mixnet Tally
5 Conclusion
A Scheme Description for Complex Ballots
B Deferred Proofs
B.1 Correctness
B.2 Strong Randomizability
B.3 TCCA Security
B.4 Traceability
B.5 Verifiability
References
Two-Party Decision Tree Training from Updatable Order-Revealing Encryption
1 Introduction
1.1 Related Work
1.2 Our Contribution
1.3 Outline
2 Preliminaries
2.1 The Universal Composability Model
2.2 Order-Revealing Encryption
2.3 Decision Tree Training
3 Updatable Order-Revealing Encryption
4 Secure Decision Tree Training
4.1 Variations of the Training Process
4.2 Graceful Degradation Using Enclaves
5 Analysis of the Leakage
5.1 Leakage for Random Message Selection
5.2 Additional Leakage for Malicious Message Selection
5.3 Transformation for Non-uniform Distributions
6 Implementation and Evaluation
6.1 Evaluation of the Updatable ORE Scheme
6.2 Evaluation of the Protocol
7 Conclusion
A A Brief Introduction to the UC Framework
References
KIVR: Committing Authenticated Encryption Using Redundancy and Application to GCM, CCM, and More
1 Introduction
1.1 Research Challenges
1.2 Contributions
1.3 Organization
2 Preliminaries
3 Committing Security with Plaintext Redundancy
3.1 Plaintext with Redundancy
3.2 Definitions for Committing Security with Redundancy
4 KIVR Transform
4.1 Specification of KIVR
4.2 Security of KIVR
5 Committing Security of KIVR with CTR-Based AE
5.1 Specification of CTR-Based AE
5.2 CMT-4-Security of KIVR[CTRAE]
6 Proof of Theorem 1
6.1 Tools
6.2 Symbol Definitions
6.3 Deriving the CMT-4-Security Bound
6.4 Bounding Pr[(C,T)=(C,T) coll]
7 Committing Security of KIVR with GCM, GCM-SIV, and CCM
7.1 Specifications of GCM, GCM-SIV, and CCM
7.2 CMT-4-Security of KIVR[GCM], KIVR[GCM-SIV], and KIVR[CCM]
7.3 Tightness of the CMT-4-Security of KIVR[GCM] and KIVR[GCM-SIV]
7.4 On the Tightness of CMT-4-Security of KIVR[CCM]
8 Committing Security of KIVR with CTR-HMAC
8.1 Specification of CTR-HMAC
8.2 CMT-4-Security Bound of KIVR[CTR-HMAC]
8.3 Tightness of the CMT-4-Security of KIVR[CTR-HMAC]
9 Conclusion
A Multi-user Security for AE
B Multi-user PRF Security
C mu-AE Security of AE Schemes with KIVR
D Proof of Theorem 2 for KIVR[GCM-SIV]
E Proof of Theorem 3
References
Signatures
Subversion-Resilient Signatures Without Random Oracles
1 Introduction
1.1 Subversion-Resilient Signatures with Watchdogs
1.2 Technical Challenges
1.3 Our Contributions
1.4 Alternative Models
2 Model and Preliminaries
2.1 Notation and Model
2.2 Subversion-Resilience
2.3 Achieving Subversion-Resilience
2.4 Assumptions
2.5 Pseudorandom Functions
3 Subversion-Resilient One-Way Functions
3.1 One-Way Permutations
3.2 Subversion-Resilient One-Way Functions
4 Subversion-Resilient Hash Functions
5 Subversion-Resilient Signatures
5.1 Digital Signatures
5.2 Lamport Signatures
5.3 The Naor-Yung Construction
6 Discussion
References
Practical Lattice-Based Distributed Signatures for a Small Number of Signers
1 Introduction
1.1 Contribution
1.2 Technical Overview
1.3 Related Work
2 Background
3 Distributed Signature Protocol
3.1 Protocol Description
3.2 Security Analysis
3.3 Concrete Parameters
A More Related Work
B Additional Background
B.1 Forking Lemma
C Hardness Estimation of MLWE and MSIS
D Indistinguishability of Hybrids H2 and H1
References
Building MPCitH-Based Signatures from MQ, MinRank, and Rank SD
1 Introduction
2 Preliminaries
2.1 The MPC-in-the-Head Paradigm
2.2 Methodology
2.3 Matrix Multiplication Checking Protocol
3 Proof of Knowledge for MQ
4 Proofs of Knowledge for MinRank and Rank SD
4.1 Matrix Rank Checking Protocols
4.2 Proof of Knowledge for MinRank
4.3 Proof of Knowledge for Rank SD
5 Running Times
A Methodology
A.1 MPCitH Optimizations
B State of the Art – Performances
B.1 Multivariate Quadratic Problem
B.2 MinRank Problem
B.3 Rank Syndrome Decoding Problem
C Benchmark Analysis
References
Exploring SIDH-Based Signature Parameters
1 Introduction
2 Preliminaries
2.1 Protocols and Digital Signatures
2.2 Supersingular Isogenies
2.3 Quaternion Algebra
2.4 SIDH
2.5 Algorithms for Computing Isogenies
3 Signatures Based on SIDH Squares
3.1 Proposed Constructions
4 Analysis of KLPT-Based Attacks
4.1 The KLPT Algorithm for Extremal Order
4.2 KLPT Algorithm for Non-extremal Order
4.3 Parameters Secure Against KLPT-Based Attacks
5 Analysis of Other Attacks
5.1 Attacks Based on the SIDH Attacks
5.2 Attacks on the Zero-Knowledge Property
6 Concrete Instantiations and Parameters Size
7 Conclusion
References
Biscuit: New MPCitH Signature Scheme from Structured Multivariate Polynomials
1 Introduction
1.1 Overview of MPCitH-Based Signature Schemes
1.2 Organization of the Paper and Main Results
2 Preliminaries
2.1 Notations
2.2 The PowAff2u Problem
2.3 Digital Signature Scheme
2.4 5-Pass Identification Schemes
2.5 MPC-in-the-Head: From MPC to Zero-Knowledge
2.6 Proof Systems for Arbitrary Circuits
3 Interactive Protocols for PowAff2
3.1 Multi-Party Computation Protocol for PowAff2
3.2 Zero-Knowledge Proof of Knowledge for PowAff2
4 Biscuit Signature Scheme
4.1 Parameters
5 Security Analysis
5.1 About the Hardness of PowAff2
5.2 Key Recovery Attacks
5.3 Forgery Attacks
5.4 Existential Unforgeability
6 Implementation
6.1 Canonical Representation Optimization
6.2 Hypercube Optimization
6.3 Vectorization
6.4 Performances and Memory Consumption
References
Author Index