Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques Lyon, France, April 23–27, 2023 Proceedings, Part IV

Preface
Organization
Contents – Part IV
Blockcipher and Hash Function Cryptanalysis
Truncated Boomerang Attacks and Application to AES-Based Ciphers
	1 Introduction
	2 Preliminaries
		2.1 The AES Round Function
		2.2 Differentials and Truncated Differentials
		2.3 Boomerang Attacks
		2.4 Improvements of the Boomerang Attack
	3 Truncated Boomerang Attacks
		3.1 Truncated Boomerang Distinguisher
		3.2 Truncated Boomerang Key-Recovery Attack
	4 Optimized Boomerang Attacks on 6-Round AES
		4.1 Optimized Distinguisher
		4.2 Optimized Key-Recovery Attack
		4.3 Key-Recovery with Secret S-Boxes
	5 Application to 8-Round Kiasu-BC
	6 Application to TNT-AES
	7 Modeling the Framework Using MILP
		7.1 Results on AES-128 and Kiasu-BC
	8 Application to Deoxys-BC
	9 Conclusion
	References
Better Steady than Speedy: Full Break of SPEEDY-7-192
	1 Introduction
		1.1 Our Contribution
	2 Differential Cryptanalysis
	3 Finding Good Differentials on SPEEDY
		3.1 Specifications of the SPEEDY Family of Block Ciphers
		3.2 Differential Properties of SPEEDY
		3.3 Searching for Good Differential Trails
		3.4 Multiple Differentials
	4 Attack on SPEEDY-7-192
		4.1 Trade-Off Between Differential Probability and Efficient Sieving
		4.2 Data Generation
		4.3 Sieving of the Pairs
		4.4 Recovering the Key
	5 Discussion and Conclusion
	References
Exploiting Non-full Key Additions: Full-Fledged Automatic Demirci-Selçuk Meet-in-the-Middle Cryptanalysis of SKINNY
	1 Introduction
	2 Primarily
		2.1 Notations
		2.2 Basic DS-MITM Attack
		2.3 Techniques for Enhancing the DS-MITM Attack
		2.4 Brief Description of SKINNY Block Cipher
	3 The Non-full Key-Addition Technique
	4 Full-Fledged Framework with New Improvement Techniques
		4.1 A High Level Overview
		4.2 Modelling the Basic DS-MITM Distinguisher
		4.3 Modelling the Differential Enumeration Technique
		4.4 Modelling Key-Dependent-Sieve Technique
		4.5 Modelling the Non-full Key-Addition Technique
		4.6 Modelling the Tweak-Difference Cancellation Technique
		4.7 Modelling the Key-Recovery Phase
	5 Results of SKINNY Block Cipher
		5.1 Brief Illustration of Figures and Complexity Computation
		5.2 25 Rounds Attack on SKINNY-128-384 (376-Bit Key, 8-Bit Tweak)
	6 Discussions
	References
Efficient Detection of High Probability Statistical Properties of Cryptosystems via Surrogate Differentiation
	1 Introduction
	2 Efficient Algorithms for Detecting High-Probability Differentials
		2.1 Previous Algorithms and a Lower Bound
		2.2 The Fundamental Algorithm
		2.3 A Memoryless Variant of the Algorithm
		2.4 A Fixed Amount of Available Memory Variant of the High-Probability Differentials Detection Algorithm
		2.5 A Worst-Case Variant of the Algorithm
		2.6 Experimental Verification
	3 Efficient Algorithms for Detecting High-Probability Linear Approximations
		3.1 Previous Algorithms and a Lower Bound
		3.2 A New Efficient Algorithm
	4 Detecting Other High-Probability Statistical Properties
	5 Summary and Open Problems
	References
Finding the Impossible: Automated Search for Full Impossible-Differential, Zero-Correlation, and Integral Attacks
	1 Introduction
	2 Background
		2.1 Impossible Differential Attack
		2.2 Multidimensional Zero-Correlation Attack
		2.3 Relation Between the Zero-Correlation and Integral Attacks
		2.4 Constraint Satisfaction and Constraint Optimization Problems
		2.5 Encoding Deterministic Truncated Trails
	3 Modeling the Distinguishers
	4 Modeling the Key Recovery for Impossible Differentials
		4.1 Overview of the COP Model
		4.2 Detailed Model for SKINNY
	5 Modeling the Key Recovery of ZC and Integral Attacks
	6 Conclusion and Future Works
	References
Meet-in-the-Middle Preimage Attacks on Sponge-Based Hashing*-12pt
	1 Introduction
	2 Preliminaries
		2.1 The Meet-in-the-Middle Attack
		2.2 The Sponge-Based Hash Function
		2.3 The Keccak-f Permutations
		2.4 Ascon-Hash and Ascon-XOF
		2.5 Xoodyak and Xoodoo Permutation
	3 Meet-in-the-Middle Attack on Sponge-Based Hashing
		3.1 The Conditions in the MitM Attack
	4 MitM Preimage Attack on Keccak
		4.1 Preliminaries on Keccak
		4.2 MILP Model of the MitM Preimage Attack on Keccak
		4.3 MitM Preimage Attack on 4-Round Keccak-512
	5 MitM Preimage Attack on Xoodyak-XOF
		5.1 MILP Model of the MitM Preimage Attack on Xoodyak-XOF
		5.2 MitM Preimage Attack on 3-Round Xoodyak-XOF
	6 MitM Preimage Attack on Ascon-XOF
		6.1 MILP Model of the MitM Preimage Attack on Ascon-XOF
		6.2 MitM Preimage Attack on 4-Round Ascon-XOF
	7 Conclusion and Discussion
	References
Analysis of RIPEMD-160: New Collision Attacks and Finding Characteristics with MILP*-12pt
	1 Introduction
	2 Preliminaries
		2.1 Notation
		2.2 Description of RIPEMD-160
		2.3 The Differential Conditions for RIPEMD-160
		2.4 Previous Methods to Search for Differential Characteristics
		2.5 On MILP/SAT-Based Automatic Methods
	3 Finding Signed Differential Characteristics with MILP
		3.1 Modelling Signed Difference Transitions
		3.2 Describing Signed Differences
		3.3 Modelling the Modular Addition
		3.4 Modelling the Expansions of the Modular Difference
		3.5 Modelling Boolean Functions
		3.6 Modelling a5 = a1 b3s
		3.7 Detecting More Contradictions
		3.8 The Full Model for RIPEMD-160
	4 Collision Attacks on 36-Round RIPEMD-160
		4.1 Fulfilling Differential Conditions
		4.2 Complexity Evaluations and Simulations
	5 Further Works and Discussions
	References
Collision Attacks on Round-Reduced SHA-3 Using Conditional Internal Differentials
	1 Introduction
	2 Description of SHA-3
	3 Overview of the Attack
		3.1 Notations
		3.2 Overview of the Attack
		3.3 A Variant of Birthday Attack
	4 Description of Internal Difference
		4.1 Internal Difference Sets and Representatives
		4.2 Transition Probability of Internal Difference
	5 The Framework and Basic Techniques
		5.1 The Framework of the Attack
		5.2 Finding Messages Conforming 2-Round Internal Differential Characteristic
		5.3 Collecting Messages Belonging to Different Internal Difference
		5.4 Bounding the Size of Collision Subset
		5.5 The Target Internal Difference Algorithm
	6 Results and Complexity Analysis
		6.1 Collision Attacks on 4-Round SHA3-384 and SHAKE256
		6.2 A Collision Attack on 4-Round SHA3-512
		6.3 A Collision Attack on 5-Round SHAKE256
		6.4 Summary of Collision Attacks
	7 Conclusions
	A  Internal Differential Characteristics for the Attacks
	B  Appendix: Difference Conditions Table of KECCAK Sbox
	C  Appendix: Values of Difference Conditions Table of KECCAK Sbox
	D  Appendix: 2D Affine Subspaces of KECCAK Sbox
	References
Symmetric Designs
From Farfalle to Megafono via Ciminion: The PRF Hydra for MPC Applications
	1 Introduction
		1.1 Related Works: Ciminion and the MPC Protocols
		1.2 The Megafono Design Strategy
		1.3 The PRF Hydra
		1.4 MPC Performance and Comparison
		1.5 Notation
	2 Symmetric Primitives for MPC Applications
		2.1 MPC Use Cases and Key Schedules
		2.2 Cost Metric for MPC Applications
	3 Starting Points of Megafono: Farfalle and Ciminion
	4 The Megafono Strategy for Hydra
		4.1 Rationale of Megafono
		4.2 Modes of Use of Megafono
	5 Specification of Hydra
		5.1 The PRF Hydra
		5.2 The Body of the Hydra: The Permutation B
		5.3 The Rolling Function
		5.4 The Heads of the Hydra: The Permutation HK
		5.5 Number of Rounds
	6 Design Rationale of B, Ri and HK
		6.1 The Body B
		6.2 The Heads HK
		6.3 The Rolling Functions Ri
	7 Security Analysis
		7.1 Overview
		7.2 Security Analysis of B
		7.3 Statistical and Invariant Subspace Attacks on HK
		7.4 Algebraic and Gröbner Basis Attacks on HK
	8 Hydra in MPC Applications
	References
Coefficient Grouping: Breaking Chaghri and More*-12pt
	1 Introduction
	2 Preliminaries
		2.1 Notation
		2.2 On the Finite Field Fpn
		2.3 Description of Chaghri
	3 The Coefficient Grouping Technique
		3.1 Tracing the Form of the Univariate Polynomial
		3.2 A Natural Optimization Problem
	4 Cryptanalysis of Full-Round Chaghri
		4.1 The Key-Recovery Attack on 13.5 Rounds of Chaghri
		4.2 Further Refining the Upper Bounds
		4.3 On the Multivariate Case
	5 Achieving an Almost Exponential Degree Increase
		5.1 Searching for Secure Affine Transforms B(x)
		5.2 Evaluating the Algebraic Degree for the Multivariate Case
		5.3 New Parameters for Chaghri
	6 Conclusion
	References
Pitfalls and Shortcomings for Decompositions and Alignment
	1 Introduction
	2 Main Results on the Uniqueness of Decompositions
		2.1 Preliminaries
		2.2 Defining a (Maximal) Decomposition
		2.3 A Sufficient and Necessary Condition for Unique Decompositions
	3 Re-aligning Alignment
	4 Aligned and Unaligned Versions of PRESENT
		4.1 Digraphs and PRESENT
		4.2 Linear Cryptanalysis
		4.3 Differential Cryptanalysis
	5 An in Depth Analysis of the Uniqueness of Decompositions
		5.1 The Case of Trivial Intersections
		5.2 The Case of Non-trivial Intersections
	6 Conclusion
	References
Generic Attack on Duplex-Based AEAD Modes Using Random Function Statistics
	1 Introduction
	2 Preliminaries
		2.1 Preliminaries on Random Functions
		2.2 Description of a Vanilla Duplex-Based AEAD Mode
		2.3 Security Model
	3 Description of the Attack
		3.1 Observation on Duplex-Based AEAD Modes
		3.2 High Level Description of the Attack
		3.3 Precomputation Phase
		3.4 Analysis of the Offline Algorithm
		3.5 Online Phase
		3.6 Complexity and Success Probability of the Attack
		3.7 Key-Recovery
	4 Small Scale Experiments
	5 Application to Concrete Duplex-Based Modes
		5.1 Highlights
		5.2 Schemes to Which the Attack Can Be Applied
		5.3 Modes that Frustrate Our Attack
	6 Conclusion
	References
Context Discovery and Commitment Attacks
	1 Introduction
	2 Background
	3 Granular Committing Encryption Definitions
	4 Context Discovery Attacks Against AEAD
	5 Restrictive Commitment Attacks via k-Sum Problems
	6 Related Work
	References
.25em plus .1em minus .1emImpossibility of Indifferentiable Iterated Blockciphers from 3 or Less Primitive Calls*-12pt
	1 Introduction
	2 Preliminaries
	3 Technical Overview
		3.1 Fundamental Properties
		3.2 Full Characterization of 1-Call Cipher E1
		3.3 Attack 2-Call Iterated Cipher E2
		3.4 Attack 3-Call Iterated Cipher E3
	4 Fundamental Properties
	5 General 1-Call Blockciphers
		5.1 General Model of 1-Call Blockciphers/Rounds
		5.2 Properties of 1-Call Blockciphers/Rounds
		5.3 Attack 1-Call Blockciphers
	6 Attack 2-Call Iterated Blockciphers
	7 Attack 3-Call Iterated Blockciphers
	References
Optimal Security for Keyed Hash Functions: Avoiding Time-Space Tradeoffs for Finding Collisions
	1 Introduction
		1.1 Our Results
		1.2 Related Work
	2 Technical Overview
		2.1 Keyed Merkle Tree Analysis
	3 Preliminaries
	4 Merkle-Damgård Framework with a Keyed Inner Hash
	5 Instantiating the Inner Hash: Standard MD
	6 Instantiating the Inner Hash: Two-Level Merkle Tree
		6.1 The AGL ch15AkshimaGL22 Framework
		6.2 Two-Level Merkle Tree
		6.3 Variable-Input Length Hash from Two-Level Merkle Trees
	References
Proof of Mirror Theory for a Wide Range of max
	1 Introduction
		1.1 Main Result and Our Contribution
		1.2 Applications of Theorem Pi Pj for Any max
		1.3 Related Work
	2 Probability of Disjointness: An Equivalent Formulation
		2.1 Proof of Equivalence
		2.2 Proof of Theorem [thm:equiv]1\'
	3 Proof of Proposition1
		3.1 Initial Condition
		3.2 Link-Deletion Equation and Proof Overview
		3.3 Size Lemma
		3.4 Recursive Inequality of D-Terms
		3.5 Final Wrap up of Proof
	4 Cryptographic Applications
		4.1 The H Coefficients Technique
		4.2 The XORP Construction
		4.3 Optimally Secure Variable-Input-Length PRFs
		4.4 Feistel Schemes
		4.5 A Comparative Study of the Security Bounds
	5 Conclusion and Future Work
	A  Postponed Proofs
		A.1  Proof of Lemma2
		A.2 Proof of Recursive Inequality Lemma
	References
Non-adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions
	1 Introduction
		1.1 Our Contribution
		1.2 Additional Related Work
		1.3 Paper Organisation
	2 Our Technique
		2.1 Non-adaptive UOWHF
		2.2 Next-Bit Unreachable Entropy
		2.3 Almost-UOWHF
	3 Preliminaries
		3.1 Notations
		3.2 One-Way Functions
		3.3 Universal One Way Hash Functions
		3.4 Hash Families
		3.5 Entropy and Accessible Entropy
		3.6 Useful Facts
	4 Non-adaptive UOWHF from One-Way Functions
		4.1 Proving Claim4.5
	5 Almost-UOWHF from One-Way Functions
		5.1 Almost-UOWHF
		5.2 Next-Bit Unreachable Entropy
		5.3 Next-Bit Unreachable Entropy to Almost-UOWHF
	References
XOCB: Beyond-Birthday-Bound Secure Authenticated Encryption Mode with Rate-One Computation
	1 Introduction
	2 Preliminaries
	3 Description of XOCB
	4 Security of XOCB
		4.1 Proof Setup
		4.2 Simulating  in the Ideal World
		4.3 Proof of Theorem 1
	5 On the Tightness of the Bound of XOCB
	6 Implementations of XOCB
	7 Conclusions
	References
Side-Channels and Masking
Improved Power Analysis Attacks on Falcon
	1 Introduction
	2 Preliminaries
		2.1 Linear Algebra and Lattices
		2.2 Gaussian Distributions
		2.3 NTRU
		2.4 Falcon Signature Scheme
	3 Gaussian Samplers of Falcon
		3.1 FFOSampler
		3.2 SamplerZ
		3.3 BaseSampler
	4 Improved Key Recovery from Half Gaussian Leakage
		4.1 The Attack of ch19Guerreau2022
		4.2 Our Key Recovery
		4.3 Experimental Results of Key Recovery
	5 Power Analysis Using Sign Leakage
		5.1 Side-Channel Analysis
		5.2 Key Recovery Using Sign Leakage
		5.3 Key Recovery Using both Sign and Half Gaussian Leakages
		5.4 A Countermeasure Against the Sign Leakage
	6 Attacks on Mitaka
		6.1 Mitaka Signatures Filtered by Leakages
		6.2 Experimental Results
	7 Conclusion
	A Theoretical Analysis for the LSP Algorithm
	B Attacks on Other Falcon Parameters
	References
.26em plus .1em minus .1emEffective and Efficient Masking with Low Noise Using Small-Mersenne-Prime Ciphers*-12pt
	1 Introduction
	2 From Boolean to Prime Field Arithmetic Masking
		2.1 Methodology
		2.2 Information Theoretic Evaluation Results
		2.3 Theoretical Explanation
		2.4 Intuitive Explanation
		2.5 Impact of the Prime Size
		2.6 Parallel Leakage
		2.7 Final Remark
	3 Performance and Cost
		3.1 Small Mersenne Primes
		3.2 Masked Multiplication in Binary Fields vs. Prime Fields
		3.3 Larger Prime Ciphers
	4 AES-prime for Prime Encodings
		4.1 AES-prime Design for p=27-1
		4.2 Security Analysis
	5 Experimental Validation
		5.1 Target Devices and Experimental Setups
		5.2 Software Case Study
		5.3 Hardware Case Study
	6 Conclusions
	References
One-Hot Conversion: Towards Faster Table-Based A2B Conversion
	1 Introduction
		1.1 Our Contributions
	2 Preliminaries
		2.1 Notation
		2.2 Masking
	3 Intuitive Introduction to One-Hot Conversion
	4 Arithmetic to Boolean Conversion
		4.1 Generalization
	5 Arithmetic to 1-Bit Boolean
		5.1 Method Description
		5.2 Generalization
		5.3 Applications to Lattice-Based Encryption
	6 Implementation Aspects
		6.1 Software Optimizations
		6.2 Parallelization
	7 Validation
		7.1 A2B Conversion
		7.2 Masked Comparison
	8 Conclusions and Future Work
	References
Author Index