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

Preface
Organization
Abstracts of Invited Talks
Challenges and Solutions to Post-Quantum Secure Messaging
Language-enforced Data Confidentiality against Memory Disclosure and Transient Execution Attacks
Contents – Part I
Contents – Part II
Side-Channel and Fault Attacks
Formal Verification of Arithmetic Masking in Hardware and Software
1 Introduction
2 Background
2.1 Masking Schemes and Applications
2.2 Mask Conversion Techniques
2.3 Masking Verification with Rebecca/Coco
2.4 Adversary Model
3 Verification of Arithmetic Masking in the Boolean Domain
3.1 Modeling Arithmetic Expressions Using Boolean Logic
3.2 Tailoring the Verification Approach
3.3 Example
4 Application to Masked Hardware Implementations
4.1 Formal Analysis
4.2 Empirical Analysis
5 Application to Masked Software Implementations
5.1 Software Verification Setup
5.2 Verification of Algebraic Share Conversions
5.3 Verification of Table-Based Share Conversions
5.4 Application to Table-Based Conversion Algorithms
5.5 Application to ARX-Based Constructions
6 Conclusion
A Iterative and Unrolled Circuits
B Fourier Expansion of the Arithmetic Addition
C Coron et al.-A2B
D Sanity Check Measurement Setup (RNG Off)
E Schneider et al.-B2A ch1schneider2019conversion
F Debraize-A2B
G Goubin ch1goubin2001a2b
H Table Lookup on Gate-Level
References
Layered Binary Templating
1 Introduction
2 Background
3 Layered Binary Templating Attack
3.1 Threat Model
3.2 High-Level Overview of the Templating Phase
3.3 Templating with Different Spatial Granularity
3.4 Beyond Huge Pages
3.5 Templating Phase Implementation
4 Compiler- and Linker-Introduced Spatial Distance
4.1 First-Come-First-Serve Data Placement
4.2 Data Deduplication During Compilation
4.3 Deduplication in the Linking Step
5 Evaluation and Exploitation Phase
6 Mitigation and Discussion
7 Conclusion
A Cache-Hit Ratios (Extended)
References
HS-Based Error Correction Algorithm for Noisy Binary GCD Side-Channel Sequences
1 Introduction
1.1 Our Contributions
1.2 Outline
2 Background
2.1 RSA Key Generation in OpenSSL
2.2 Binary GCD Algorithm
2.3 Related Works on SCAs on the Binary GCD
2.4 Related Works on Error Corrections for Noisy RSA Keys
2.5 Side Chabnnel Attacks Proposed by Aldaya et al.
2.6 Coppersmith's Method
2.7 AGTB Error Correction Algorithm
3 Our Error Correction Algorithm
3.1 Overview of Our Error Correction Algorithm
3.2 Expand
3.3 Our Proposed Z-encoding
3.4 Prune
3.5 Our Proposed Loss Function
4 Estimation of Type 1 Error Probability Distribution
4.1 Probability Distribution Derived from SCA
4.2 Deriving an Approximate Probability Distribution
5 Experiments to Evaluate Error Correction Algorithms
5.1 Discrete Probability Functions Used in Likelihood-Based Loss Functions in Our Algorithm
5.2 Evaluation of Error Correction Algorithms Using Artificially Error-Generated Sequences
5.3 Evaluation of Error Correction Algorithms Using Sequences Collected by Actual SCA
5.4 Discussion for Analyses on 4096-bit RSA
6 Conclusion
A Finding Such that PSCA and PAPPROX are Closest
B Details About the AGTB Algorithm
B.1 Prune
B.2 Implementation of the AGTB Algorithm
B.3 Setting Parameters as Input for the AGTB Algorithm
B.4 Experiment to Evaluate the AGTB Algorithm
References
Divide and Rule: DiFA- Division Property Based Fault Attacks on PRESENT and GIFT
1 Introduction
1.1 Related Work
1.2 Our Contribution
2 Preliminaries and Background
2.1 Notations
2.2 Zero-Sum Distinguishers and Division Property
2.3 Fault Attacks
2.4 PRESENT ch4DBLP:confspschesspsBogdanovKLPPRSV07
2.5 GIFT ch4DBLP:confspschesspsBanikPPSST17
3 DiFA: Division Property Based Fault Analysis
4 Mounting DiFA on GIFT64
5 Mounting DiFA on PRESENT-80/128
5.1 Last Round Key Recovery
6 On the Inapplicability of DiFA on GIFT-128
7 Conclusion and Open Problems
A Results on GIFT-128
B Sbox Division Trail Algorithm
C PRESENT Partial Subkeys Recovery of the Last Two Rounds
C.1 Last Round Key Recovery of PRESENT
References
Symmetric Cryptanalysis
A Novel Automatic Technique Based on MILP to Search for Impossible Differentials
1 Introduction
2 Preliminaries
2.1 Notations
2.2 Impossible Differential Cryptanalysis
3 Modeling Difference Propagation of Basic Operations with Linear Inequalities
4 Applications to Midori-64, CRAFT, and SKINNY-64
4.1 Midori-64
4.2 6-Round Impossible Differential of Midori-64
4.3 CRAFT and SKINNY-64
5 Impossible Differential Cryptanalysis of 11-Round Midori-64
5.1 Modeling the Extended Rounds for Midori-64
5.2 Impossible Differential Cryptanalysis of 11-Round Midori-64
6 Conclusion
A The Example IDs of 13-Round CRAFT and 12-Round SKINNY-64
B The Proof of Theorem 1
References
Meet-in-the-Filter and Dynamic Counting with Applications to Speck
1 Introduction
2 Related Work
3 Preliminaries
4 The Meet-in-the-Filter (MiF) Attack
4.1 The MiF Tool
4.2 Key Recovery Using Single-Trail Analysis
4.3 Key Recovery Using Multiple-Trail Analysis (Counting)
4.4 Distributions of Weights in MiF Trails
4.5 Key Recovery Complexity Analysis
5 Efficient Meet-in-the-Filter for the Block Cipher Speck
6 Application of the Meet-in-the-Filter Attack to Speck
6.1 Attacks on 11 Rounds of Speck32/64
6.2 Attacks on 12 to 15 Rounds of Speck32/64
6.3 Attacks on 13 to 20 Rounds of Speck64/128
A Differentials
B Parameters and Complexities of Our Attacks on Speck32 and Speck64
C Key Recovery Complexity Graphs
D Memory Optimizations for the Multi-Trail Key Recovery Procedure
E Computing the Required Multiplier for Counting
References
Near Collision Attack Against Grain V1
1 Introduction
1.1 Contribution and Organization of the Paper
2 Algebraic Description of Grain V1
3 Preliminaries
4 State Recovery Attack
4.1 Online Stage I: Collecting and Storing Keystream Bits
4.2 Online Stage II: Further Filtering
4.3 Online Stage III: 3rd Filtering
4.4 Online Stage IV: Solving Equation System
4.5 Actual Algorithm for Solving
4.6 Formal Algorithm and Time Complexity
4.7 Extending Attacks to Grain-128
5 Conclusion
A Cost of Executing One Round of Grain V1
B Difference Vectors
C Reducing the Memory Footprint
C.1 The Effect of Low Sampling Resistance
C.2 Modified Algorithm and Time Complexity
C.3 Comparison with Generic Attacks on Stream Ciphers
D Extending the Attack to Grain-128
References
TIDAL: Practical Collisions on State-Reduced Keccak Variants
1 Introduction
2 Preliminaries
2.1 Keccak Internal State and the SPONGE Mode of Operation
3 Revisiting the Target Internal Difference Algorithm
4 TIDAL: Extending TIDA Using Linearization
4.1 Degrees of Freedom for TIDAL
4.2 Experimental Verification
5 Finding Collisions Using TIDAL
5.1 Using Null-Space for Generating Conforming Message Subspace
5.2 A Note on Round Constants
5.3 Experimental Verification
5.4 A Note on Inner vs Outer Collisions
6 Comparative Analysis
7 Conclusion
A Collision on 6-Round
B The Observations that Help in S-box Linearization ch8GuoLLLQS20
C Effect on Hamming Weight of Round Constants
References
Web Security
Tiny WFP: Lightweight and Effective Website Fingerprinting via Wavelet Multi-Resolution Analysis
1 Introduction
2 Threat Model
3 Related Work
3.1 WF Based on Feature Engineering and Machine Learning
3.2 WF Based on Deep Learning
3.3 WF Attacks Towards Better Scalability
3.4 WF Defenses
4 Approach
4.1 Traffic Trace Encoding
4.2 Wavelet-Based Dimensionality Reduction
4.3 Workflow of Wavelet Dimensionality Reduction
4.4 Lightweight Neural Network Architecture
5 Evaluation
5.1 Experimental Setup
5.2 Ablation Study of Network Lightweight and Wavelet-Based Dimensionality Reduction
5.3 Closed-World Performance on Non-defended Dataset
5.4 Closed-World Performance on Defended Dataset
5.5 Open-World Evaluation
6 Discussion
7 Conclusion
References
Capturing Antique Browsers in Modern Devices: A Security Analysis of Captive Portal Mini-Browsers
1 Introduction
2 Problem Definition
2.1 Background
2.2 Attacker Model
2.3 Desired Properties
3 Assessment Tool: Wi-Fi Chameleon
4 Security Strength Evaluation
4.1 Tested Devices
4.2 Evaluation Metrics
4.3 Evaluation Results
5 Attack Vulnerability Analysis
6 Discussion
6.1 Case Study: Browser Perspective
6.2 Case Study: Access Point Perspective
7 Defense Scheme
7.1 Approach 1. Secure Captive Portal Browser Extension
7.2 Approach 2. Identity Verification Strategies
8 Related Work
9 Conclusion
A Appendix
A.1 Tested Devices
A.2 Screenshots of Test Devices
References
Those Aren't Your Memories, They're Somebody Else's: Seeding Misinformation in Chat Bot Memories
1 Introduction
2 Background and Target Bot Architecture
2.1 Memory Module
2.2 Internet Search Module
2.3 Conversing with the Chat Bot
2.4 Threat Model and Attack Overview
3 Generating Unintended Memories
3.1 Will the Chat Bot Remember Me?
3.2 Crafting Queries for Chosen Bad Memories
4 Recalling Misinformation
4.1 Method and Experiment Setup
4.2 Results
5 Possible Defenses
5.1 Supervising Responses
5.2 Preventing Poisoned Memories
6 Memory Injection Vulnerability in Other Chat Bots
7 Ethical Considerations
8 Related Work
9 Conclusion
A Results per Retrieval Query
B Example of Parlai Debug Output
References
Social Honeypot for Humans: Luring People Through Self-managed Instagram Pages
1 Introduction
2 Related Works
3 Methodology
3.1 Overview and Motivation
3.2 Topic Selection
3.3 Post Generation Strategies
3.4 Engagement Plans
4 Implementation
4.1 Topic Selection
4.2 Testbed
5 Honeypots Evaluation
5.1 Overall Performance
5.2 Honeypot Trends Analysis
5.3 The Impact of Honeypots Configuration
5.4 Baseline Comparison
6 Social Analyses
6.1 Comments Analysis
6.2 Followers Analysis
6.3 Reached Audience
7 Toward a Real Implementation
7.1 Use Cases
7.2 Challenges and Limitations
8 Conclusions
A Implementation Details
A.1 Models
A.2 Spamming
B Sponsored Content Analyses
References
Elliptic Curves and Pairings
Pairings in Rank-1 Constraint Systems
1 Introduction
2 Pairing-Based SNARKs
2.1 Rank-1 Constraint System
3 Background on Pairings
4 Pairing-friendly 2-Chains
5 Algebraic Tori and Pairings
5.1 Torus-Based Arithmetic
6 Pairings in R1CS
6.1 Miller Loop
6.2 Final Exponentiation
7 Implementation and Benchmark
8 Conclusion
References
Binary Kummer Line
1 Introduction
1.1 Our Contributions
2 Binary Kummer Line
2.1 Scalar Multiplication
2.2 Binary Kummer Line and the Associated Elliptic Curve
2.3 Equivalence Between BKL(1:b) and Eb
2.4 Retrieving y-Coordinate
3 Binary Edwards Curve
4 Right-to-Left Montgomery Ladder
4.1 Differential Addition Formulas in ScalarMultR2LwPrecomp
5 Binary Kummer Line over Field F2251
5.1 Set of Scalars
6 Scalar Multiplication
6.1 Scalar Multiplication of BKL251
6.2 Scalar Multiplication of BEd251
6.3 Operation Count Comparison
7 Batch Binary Kummer Lines
8 Implementations and Timings
9 Conclusion
1 Implemented Field Arithmetic
1.1 Field Element Representation
1.2 Reduction
1.3 Addition and Subtraction
1.4 Multiplication by Small Constant
1.5 Field Multiplication
1.6 Unreduced Field Multiplication (multUnreduced)
1.7 Field Addition of Unreduced Field Elements (addReduce)
1.8 Field Squaring
1.9 Field Inverse
1.10 Conditional Swap
2 Correctness and Efficiency of the Implementation
References
Generalised Asynchronous Remote Key Generation for Pairing-Based Cryptosystems
1 Introduction
2 Asynchronous Remote Key Generation
2.1 The ARKG Model
2.2 Security Definitions
3 Generalised ARKG
3.1 -AKG Schemes
3.2 Our General Transformation from -AKG to ARKG
4 Pairing-Based -AKG and ARKG Schemes from Uber Assumption
4.1 Notations and Building Blocks
4.2 Symmetric Pairings
4.3 Asymmetric Pairings
5 Applications to Pairing-Based Signatures
5.1 ARKG for Selected Signature Schemes over Type-1 Pairings
5.2 ARKG for Selected Signature Schemes over Type-3 Pairings
5.3 Implementation and Performance
6 Conclusion
A More Proofs
A.1 Proof of Theorem 3
A.2 Proof of Lemma 2
A.3 Proof of Lemma 3
A.4 Proof of Corollary 3
A.5 Proof of Corollary 2
A.6 Proof of Corollary 4
A.7 Proof of Corollary 5
A.8 Proof of Corollary 6
A.9 Proof of Corollary 7
B Preliminaries
References
Homomorphic Cryptography
PIE: p-adic Encoding for High-Precision Arithmetic in Homomorphic Encryption
1 Introduction
1.1 Our Results
2 Notations and Foundations
2.1 Notations
2.2 Results and Techniques from p-adic Arithmetic
3 PIE: A Rational Encoder
3.1 Choosing the Message Space GM
4 PIE with a Batch FHE over Integers
4.1 PIE with IDGHV
4.2 IDGHV-Compatible Encoding Parameters and Message Space
5 PIE with Modified Fan-Vercauteren HE
5.1 PIE with ModFV
5.2 PIE vs. CLPX: Input Space Advantage
6 Experimental Results
A Appendix: Encodings with Primes and Prime Powers
A.1 Choosing the Encoding Parameters p and r
B Appendix: Extending Farey Rationals for Larger Input Space
References
Analysis and Prevention of Averaging Attacks Against Obfuscation Protocols
1 Introduction
1.1 Contributions
1.2 Related Work
2 Preliminaries
2.1 Homomorphic Encryption
2.2 Proxy Re-encryption
2.3 Overview of RVP
3 Averaging Attacks Against Obfuscation Protocols
3.1 Adversary Model
3.2 Averaging Attacks Against RVP
3.3 Deterministically Correct
3.4 Random Output
3.5 General Case
4 Data-Dependent Deterministic Obfuscation
4.1 A D³O Instantiation
4.2 mRVP - Modified Ratio Verification Protocol with D³O
5 Evaluation of Performance and Applicability
5.1 mRVP and Baselines
5.2 Experimental Setup
5.3 Runtime Evaluation
5.4 Accuracy Evaluation
5.5 Summary
6 Conclusion and Future Work
A Appendix
A.1 Local Differential Privacy
A.2 Averaging Attacks Against Obfuscation Protocols: Formalization of the Special Case
A.3 Averaging Attacks Against Obfuscation Protocols: Omitted Statement
References
FLSwitch: Towards Secure and Fast Model Aggregation for Federated Deep Learning with a Learning State-Aware Switch
1 Introduction
2 Preliminary
2.1 Federated Learning
2.2 Threat Model
2.3 Homomorphic Encryption
3 Secure and Fast Model Aggregation
3.1 FLSwitch Overview
3.2 Homomorphic Aggregation
3.3 Fast Aggregation
3.4 Learning State-Aware Switch
4 Security Analysis
5 Evaluation
5.1 Experimental Setup
5.2 Experimental Result
6 Related Work
7 Conclusion
References
Machine Learning
Fast and Efficient Malware Detection with Joint Static and Dynamic Features Through Transfer Learning
1 Introduction
2 Related Work
2.1 Static Malware Analysis
2.2 Dynamic Malware Analysis
2.3 AI-based Malware Detection
2.4 Transfer Learning for Malware Detection
3 Malware Analysis and Feature Extraction
3.1 Static Analysis and Feature Extraction
3.2 Dynamic Analysis and Feature Extraction
3.3 Feature Aggregation
4 Deep Learning-Based Malware Detection Models
4.1 Neural Network Architectures for Individual Feature Vectors
4.2 Neural Network Architecture for Aggregated Feature Vectors
5 Transfer Learning with Knowledge Distillation
6 Performance Evaluation
6.1 Dataset
6.2 Hyper-parameters Setting
6.3 Performance Metrics
6.4 Performance of Teacher Model
6.5 Transfer Learning for EMBER Features
6.6 Transfer Learning with OPCODE Features
6.7 End-to-End Detection Delay
7 Conclusion
A Ablation Studies
A.1 Transfer Learning for API-ARG Features
A.2 Experiments with Different Neural Network Architectures
B Implementation of Neural Network Architecture for Individual Feature Vectors
C Neural Network Architecture of Aggregated Original Features
D Speeding up Dynamic Analysis with Distributed Cuckoo Infrastructure
E Discussion on Model Updating
References
Efficient Network Representation for GNN-Based Intrusion Detection
1 Introduction
2 Related Work
3 Preliminaries
3.1 NIDS Problem Statement
3.2 General Graph Definition
3.3 Graph-Line Representation
3.4 Graph Neural Network
4 Proposed Framework
4.1 Data Pre-processing Phase
4.2 Phase 1: Graph Creation
4.3 Phase 2: Feature Extraction Phase
4.4 Phase 3: Flows Classification
5 Evaluation Procedure
6 Results and Discussion
6.1 Experimental Settings
6.2 Evaluation Metrics
6.3 Results
7 Conclusion
References
EVADE: Efficient Moving Target Defense for Autonomous Network Topology Shuffling Using Deep Reinforcement Learning
1 Introduction
2 Related Work
2.1 Secure Network Topology
2.2 Network Resilience in Network Science
3 Problem Statement
4 System Model
4.1 Network Model
4.2 Node Model
4.3 Attack Model
5 Description of EVADE
5.1 Ranking Vulnerabilities Using VREN
5.2 Solution Search with FSS
5.3 DRL-based Optimal Budget Identification
5.4 Greedy MTD Using Density Optimization (DO)
5.5 Hybrid MTD with EVADE and DO
5.6 Practical Applicability of EVADE and DO
6 Experiment Setup
7 Simulation Experimental Results
8 Limitations
9 Conclusions
References
Steal from Collaboration: Spy Attack by a Dishonest Party in Vertical Federated Learning
1 Introduction
2 Preliminaries
2.1 Deep Neural Networks
2.2 Vertical Federated Learning
3 Problem Statement
3.1 Formulation of Spy Attack
3.2 Threat Model
4 Designs of Spy Attack
4.1 Overview
4.2 Dishonest Statement in Entity Alignment
4.3 Spy Attack by the Active Party
4.4 Spy Attack by the Passive Party
4.5 Extending to Multiple Parties VFL Scenario
5 Experimental Evaluation
5.1 Experimental Setup
5.2 Evaluation of Spy Attack
5.3 Effect of Hyper-Parameter
5.4 Effect of the Number of Parties
6 Possible Defense
6.1 Noisy Representations
6.2 Distance Correlation Minimization
6.3 Encrypted Representations
6.4 Detecting the Attack
7 Conclusion
References
Lattices and Codes
Forward Security of Fiat-Shamir Lattice Signatures
1 Introduction
1.1 Our Treatments
2 Preliminary
2.1 Lattices and Gaussian Measures
2.2 Hard Problems
2.3 Forward-Secure Signature
3 A Gentle Primer: Unifying Lattice Signatures in RO
3.1 Global Trapdoor vs. Constrained Trapdoor
3.2 A Signature Framework: Global Trapdoor Sampler
4 Tools: Trapdoor Evolution Algorithm
4.1 Basic Strategies
4.2 Combinatorial Strategies: Trapdoor Evolution Algorithm
5 Forward-Secure Lattice-Based Fiat-Shamir Signature
6 Conclusion
A Proof of Theorem 1
References
Shorter and Faster Identity-Based Signatures with Tight Security in the (Q)ROM from Lattices
1 Introduction
2 Technical Overview
3 Preliminaries
4 Preliminary Results
4.1 Results on Statistical Distance
4.2 Singular Values of Random Matrix
4.3 Lattice Trapdoors
4.4 Hash Reprogramming in the ROM and the QROM
5 Generic Transformation from EUFnaCMA to EUFCMA security in the ROM and the QROM
6 IBS Scheme in the ROM and the QROM, Based on SIS
7 IBS Scheme in the ROM and the QROM, Based on RSIS
8 Conclusion
8.1 Parameters (proof of Concept) and Discussion
8.2 Future Work
References
A Gapless Post-quantum Hash Proof System in the Hamming Metric
1 Introduction
2 Preliminaries
2.1 Coding Theory
2.2 Hash Proof System
3 Hamming Quasi-cyclic Hash Proof System
3.1 Hamming Quasi-cyclic
3.2 Hash Proof System Construction
4 Security
4.1 Hardness Assumptions
4.2 Smoothness
5 Applications
5.1 Witness Encryption
5.2 Password Authenticated Key Exchange
6 Practical Considerations
7 Conclusion
A The FQCDSD Problem
A.1 Formal FQCDSD Oracle
A.2 Hardness of the FQCDSD Problem
B Stern-Like Protocols for HQC
B.1 Proof of HQC Ciphertext Validity
B.2 Proof of Related HQC Ciphertexts
References
Spherical Gaussian Leftover Hash Lemma via the Rényi Divergence
1 Introduction
2 Preliminaries
2.1 Linear Algebra
2.2 Lattices
2.3 Statistics
2.4 Gaussians
3 Approximately Orthogonal Matrices
4 Continuous Weak Spherical Gaussian LHL
4.1 (Plain) Continuous Weak Spherical Gaussian LHL
4.2 Improvement with Noise Flooding
5 Discrete Weak Spherical Gaussian LHL
6 A Sharper LWE Self-reduction
7 Application to the Independence Heuristic
7.1 Brief Overview of the TFHE Construction
7.2 Mitigating the Independence Heuristic for TFHE
8 Conclusion and Open Problems
References
BIKE Key-Recovery: Combining Power Consumption Analysis and Information-Set Decoding
1 Introduction
2 Preliminaries
2.1 Coding Theory
2.2 BIKE Scheme
2.3 Decoding MDPC Codes
2.4 Optimising the Bit-Flipping Algorithm
3 Overview of Our Attack
3.1 Constant-Time Syndrome Rotation for Cortex-M4
3.2 Determine Bit Values
3.3 Information Set Decoder
4 Experimentation on the Cortex-M4
4.1 Measurement Setup
4.2 Attack on the Plain C Implementation
4.3 Attack on an Assembly Instruction
5 Countermeasure
6 Conclusion
A Analysis of the ISD Complexity
References
Author Index