Preface
Organization
Contents
Foundation
CRS-Updatable Asymmetric Quasi-Adaptive NIZK Arguments
1 Introduction
1.1 Motivation
1.2 Our Results
2 Preliminaries
3 Updatable Asymmetric QA-NIZK
3.1 Security Definitions for Updatable QA-NIZK Arguments
3.2 Construction of Updatable Asymmetric QA-NIZKs
3.3 Security Proof for Our Construction
4 Knowledge Soundness of (Updatable) Asymmetric QA-NIZK Arguments
5 Discussion and Future Work
A CRS-update Hiding Proof
References
ParaDiSE: Efficient Threshold Authenticated Encryption in Fully Malicious Model
1 Introduction
1.1 Approaches to Threshold Symmetric Encryption
1.2 Revisiting Threshold Authenticated Encryption
1.3 Contributions
2 Technical Overview
2.1 Security Definitions
2.2 Constructions
2.3 Related Work
3 Preliminaries
4 Threshold Authenticated Encryption
4.1 Syntax
4.2 Decryption Criteria
4.3 Security
5 Construction from Indifferential AE
5.1 Random Injection
5.2 The Construction
5.3 Security
6 Constructions from Threshold PRF and Signature
6.1 IND-RCCA TAE Using DPRF and Threshold Signature
A Performance Experiments
References
Stronger Security and Generic Constructions for Adaptor Signatures
1 Introduction
1.1 Background and Problems
1.2 Our Contributions
2 Preliminary
3 Definitions and Relations
3.1 Relations with Previous Notions
3.2 Modular Proofs from Simple Notions
4 Generic Constructions
A Omitted Proofs
A.1 Proof of Theorem 5
A.2 Proof of Theorem 7
References
Entropic Hardness of Module-LWE from Module-NTRU
1 Introduction
2 Preliminaries
2.1 Algebraic Number Theory
2.2 Lattices
2.3 Probabilities
2.4 Noise Lossiness
2.5 Module Learning with Errors and Module NTRU
3 Structured LWE
3.1 Structured LWE and Structured NTRU
3.2 (Mild) Hardness
4 Entropic Hardness of Structured LWE
4.1 From Sometimes Lossiness to the Entropic Hardness of Structured LWE
4.2 Construction of Sometimes Lossy Pseudorandom Distributions
5 Instantiation for M-LWE
5.1 Invertibility and Singular Values of Discrete Gaussian Matrices
5.2 Instantiation
5.3 On the Statistical Entropic Hardness of M-LWE
6 Related Work
References
Symmetric Key Cryptology
New Algorithm for Exhausting Optimal Permutations for Generalized Feistel Networks-12pt
1 Introduction
2 Preliminaries
2.1 Generalized Feistel Networks
2.2 Diffusion Round
3 Path Building Algorithm
3.1 Graph Representation of a Feistel Permutation
3.2 The MakePath Algorithm
3.3 Skeletons
4 Non-even-odd Case: Search for Optimal Permutations
4.1 Up to 2k=32
4.2 Towards an Impossibility Result
5 Even-odd Case: Search for New Properties
5.1 Number of Paths
5.2 Number of S-Boxes
5.3 TWINE
6 Conclusion
A Proofs of Proposition 3 and 4
References
Minimizing Even-Mansour Ciphers for Sequential Indifferentiability (Without Key Schedules)
1 Introduction
1.1 Our Contributions
1.2 Organization
2 Preliminaries
3 Slide Attack on the Single-Key, Single-Permutation EMSP
4 Seq-Indifferentiability of EM2P4
4.1 Simulator of EM2P4
4.2 The Indistinguishability Proof
4.3 Abort Probability of SE,P
4.4 Indistinguishability of 1 and 3
5 Conclusion
References
INT-RUP Security of SAEB and TinyJAMBU
1 Introduction
1.1 Designing Area-Efficient Authenticated Ciphers
1.2 Authenticated Ciphers Under Release of Unverified Plaintext (RUP) Setting
1.3 Towards RUP-Secure Single-state On-the-Fly Authenticated Encryption
1.4 Our Contribution and Significance of the Result
2 Preliminaries
2.1 Authenticated Encryption
2.2 Integrity Security in RUP Setting
3 SAEB AEAD Mode and Its INT-RUP Security
3.1 INT-RUP Attack on SAEB
4 INT-RUP Security of SAEB
4.1 Definition and Probability of Bad Transcripts
4.2 Analysis of the Good Transcripts
5 TinyJAMBU and Its INT-RUP Security
5.1 Definition and Probability of Bad Transcripts
5.2 Analysis of the Good Transcripts
6 Conclusion and Future Works
References
Offset-Based BBB-Secure Tweakable Block-ciphers with Updatable Caches
1 Introduction
1.1 Our Contributions
2 Preliminaries
2.1 Distinguishing Advantage
2.2 TPRP, TPRP and TSPRP Security Notions
2.3 Authenticated Encryption and Its Security Notion
2.4 Coefficients H Technique
2.5 Mirror Theory
3 Finding a Suitable Tweakable Block-cipher
3.1 Attempt with Same Offset
3.2 Independent Offsets
3.3 Updatable Offsets
3.4 Offsets with Updatable Caches
3.5 TPRP Security Analysis of OTBC-3
4 An Application of OTBC-3
4.1 Nonce Handling
4.2 Handling Incomplete Blocks
4.3 Security Claims
References
ISAP+: ISAP with Fast Authentication
1 Introduction
1.1 ISAP and Its Variants
1.2 Improving the Throughput of ISAP
1.3 Our Contributions
1.4 Relevance of the Work
2 Preliminaries
2.1 Notations
2.2 Distinguishing Advantage
2.3 Authenticated Encryption and Its Security Notion
2.4 The Coefficients H Technique
2.5 Fixed Input - Variable Output PRFs with Prefix Property
2.6 Multi-target 2nd Pre-image with Associated Data
3 An EtHM Paradigm for NAEAD
3.1 Specification
3.2 Security of EtHM
3.3 Proof of Lemma 1
4 Multi-target 2nd Pre-image Security of Sponge Based Hashes
4.1 Sponge Hash and Its 2PI+ Security
4.2 Feed Forward Based Sponge Hash and Its 2PI+ Security
5 ISAP+: A Throughput-Efficient Variant of ISAP
5.1 Specification of ISAP+
5.2 Design Rationale
5.3 Security of ISAP+
6 Conclusion
References
Protocols and Implementation
Revisiting the Efficiency of Perfectly Secure Asynchronous Multi-party Computation Against General Adversaries
1 Introduction
1.1 Technical Overview
2 Preliminaries and Existing Asynchronous Primitives
2.1 The Asynchronous Universal Composability (UC) Framework
2.2 Existing Asynchronous Primitives
3 Perfectly-Secure Pre-processing Phase Protocol
3.1 Optimistic Multiplication Protocol
3.2 Multiplication Protocol with Cheater Identification
3.3 Multiplication Protocol
3.4 The Pre-processing Phase Protocol
4 MPC Protocol in the Pre-processing Model
References
Protego: Efficient, Revocable and Auditable Anonymous Credentials with Applications to Hyperledger Fabric
1 Introduction
2 Cryptographic Background
2.1 Notation
2.2 Set-Commitment Scheme Supporting Disjoint Sets ch11UsPKC2022
2.3 Structure-Preserving Signatures on Equivalence Classes ch11UsPKC2022
3 Our ABC Model
4 Protego
5 Evaluation
6 Conclusions and Future Work
A Our NIZK Argument for Issuer-hiding
References
Hybrid Scalar/Vector Implementations of Keccak and SPHINCS+ on AArch64
1 Introduction
2 Preliminaries
2.1 Keccak
2.2 SPHINCS+
2.3 ArmArchitecture
3 Keccak on AArch64–Architecture
3.1 Scalar Implementation
3.2 Armv8.4-A Neon Implementation
3.3 Armv8-A Neon Implementation
4 Keccak-f1600 on AArch64–Microarchitecture
4.1 Scalar Implementation
4.2 Armv8-A Neon Implementation
4.3 Armv8.4-A Neon Implementation
4.4 Hybrid Implementations
5 Results
5.1 Benchmarking Environments
5.2 Keccak-f1600 Performance
5.3 SPHINCS+ Performance
References
Parallel Isogeny Path Finding with Limited Memory
1 Introduction
2 Preliminaries
2.1 Elliptic Curves and Isogenies
2.2 Meet in the Middle (MitM)
2.3 Parallel Collision Search
3 Accurate Formulas for vOW and MitM
3.1 Meet in the Middle
3.2 Golden Collision Search
3.3 Simplified Cost Models for Montgomery Curves
4 Practical Results on Solving the SIPFD
4.1 Practical Results of Our MitM CPU Implementation
4.2 Practical Considerations for Our vOW GPU Implementation
4.3 Practical Results of Our vOW GPU Implementation
References
Cryptanalysis
Distinguishing Error of Nonlinear Invariant Attacks-12pt
1 Introduction
2 Nonlinear Invariant Attack
2.1 Building Distinguishers
3 Error Probability for Uniform Random Function
4 Error Probability for Uniform Random Permutation
5 Computational Results
6 Conclusion
References
Weak Subtweakeys in SKINNY
1 Introduction
1.1 Outline and Contributions
2 The SKINNY Family of Block Ciphers
3 Linear Cryptanalysis
4 Linear Trails of 3́942"̇613A``4547"603ASm3́942"̇613A45`47`"603ATm, k `3́9`42`"̇613A4547"603ASm
5 Patching the Problem
6 Conclusion
References
Full Round Zero-Sum Distinguishers on TinyJAMBU-128 and TinyJAMBU-192 Keyed-Permutation in the Known-Key Setting
1 Introduction
1.1 Existing Analysis on TinyJAMBU Permutation
1.2 Our Contributions
1.3 Paper Structure
2 Preliminaries
2.1 Notations
2.2 Boolean Functions and Upper Bounds on the Degree
2.3 Monomial Prediction
2.4 Computing the Algebraic Degree Using Monomial Prediction
3 The Specification of TinyJAMBU
4 Zero-Sum Distinguishers on TinyJAMBU
4.1 MILP Modeling
4.2 MILP Model for the Monomial Trails of TinyJAMBU
4.3 Degree Estimation of the TinyJAMBU Permutation
4.4 Basic Zero-Sum Distinguisher
4.5 Extending to Full Rounds Using Inside-Out Approach
5 Improved Zero-Sum Distinguisher
5.1 Extending to Full Rounds Using Inside-Out Approach
5.2 Attack on TinyJAMBU-192 and TinyJAMBU-256
5.3 Experimental Verification
6 Conclusion
A The Algebraic Degree of TinyJAMBU-128 Permutation and Its Inverse
References
Monte Carlo Tree Search for Automatic Differential Characteristics Search: Application to SPECK
1 Introduction
1.1 Related Works
1.2 Structure of This Work
2 Preliminaries
2.1 Notation
2.2 Monte Carlo Tree Search
2.3 Differential Cryptanalysis
2.4 Modular Addition and (Partial) DDTs
2.5 The SPECK Family of Block Ciphers
2.6 Differential Characteristics and Key Recovery in SPECK
3 Lipmaa's Algorithms: Known Facts and New Results
3.1 Overview of Algorithm 2
3.2 High Level Overview of Lipmaa-Moriai Alg. 3
3.3 A Fix for the Original Algorithm
3.4 Finding -Optimal Transitions
4 Differential Characteristic Search with MCTS
4.1 A General Algorithm
4.2 Limitations of This Approach
5 Application to SPECK
5.1 The Start-in-the-Middle Approach
5.2 Branching Number and the Choice of
5.3 Adding Further Heuristics to Improve the Search
5.4 Experimental Results and Discussion
6 Conclusions
A All Optimal Characteristics on SPECK32
B Best Characteristics Found with Our Method
C Pseudocode for the Search Algorithm
References
Finding Three-Subset Division Property for Ciphers with Complex Linear Layers
1 Introduction
1.1 Motivation
1.2 Our Contributions
1.3 Organization of the Paper
2 Preliminaries
2.1 Notation
2.2 Bit-Based Division Property
2.3 The MILP Model for CBDP
3 The MILP Model for BDPT
3.1 Some Observations on BDPT Propagation Rule for S-box
3.2 MILP Model of BDPT for Complex Linear Layer
3.3 MILP Model of BDPT for Key-XOR
3.4 MILP Model Construction of r-Round Function
4 Automatic Search Algorithm for r-Round Integral Distinguisher
4.1 Initial BDPT
4.2 Stopping Rule
4.3 Search Algorithm
4.4 Correctness of Search Algorithm
5 Applications to Block Ciphers
5.1 Applications to PRINCE and MANTIS
5.2 Applications to KLEIN and PRIDE
5.3 Applications to SIMON, SIMON (102)
6 Conclusion and Future Work
References
Improved Truncated Differential Distinguishers of AES with Concrete S-Box
1 Introduction
2 Preliminaries and Backgrounds
2.1 Notations
2.2 Short Description of AES
2.3 4-Round Truncated Differential Distinguisher of AES
3 Divide-and-Combine Technique
3.1 Obstacles of Direct Calculation
3.2 Calculate the Probability of 4-Round Truncated Differential with One Active Cell in Input and One Inactive in Output
3.3 Calculate the Probability of 4-Round Truncated Differential with One Active Cell in Input and Two Inactive in Output
4 New 4-Round Truncated Differential Distinguisher
4.1 Statistical Framework Using Conditional Probability
4.2 4-Round Truncated Differential Distinguisher Using Conditional Probability
5 Extend to 5-Round Truncated Differential
6 6-Round Truncated Differential Distinguisher
6.1 Extended 6-Round Truncated Differential
6.2 Distinguishing Attack on 6-Round AES
7 Conclusion and Future Work
A Brief Description of Small-AES ch1910.1007sps11502760sps10.
B Algorithm 5 and Algorithm 6 in the Calculation of 4-Round Truncated Differential with One Active Cell in Input and Two Inactive in Output
References
Boolean Functions
Modifying Bent Functions to Obtain the Balanced Ones with High Nonlinearity
1 Introduction
1.1 Contribution and Organization
2 Preliminaries
3 Nonlinearity of Balanced Boolean Functions: A Combinatorial Characterization
3.1 Nonlinearity Strictly Greater Than 2n-1 - 2n2 + nlb(n2)
3.2 Deriving Specific Conditions for n=8, 10, 12 and 14
4 Comparison with Existing Results ch20MS03,ch20SM00
4.1 On Characterization by Maity and Maitra ch20MS03
4.2 On Characterization by Sarkar Et Al. ch20SM00
5 Construction Method of Highly Nonlinear Balanced Functions from Bent Functions
5.1 Studying the Specific Conditions for n=8, and Explaining Some Non-existence Issues
5.2 Studying the Cases for n = 10, 12, 14
6 Conclusion
References
Revisiting BoolTest – On Randomness Testing Using Boolean Functions
1 Introduction
1.1 Organization and Contribution
1.2 Preliminaries
1.3 Brief Description of BoolTest by Sýs et al. ch21booltestspssecrypt2017
2 Critical Evaluations of Z-score
2.1 Z-Score for Data with All and Equal Frequency Inputs
2.2 Maximum Z-score for Frequencies s and s+1
2.3 Maximum Z-score When Some of the Patterns Arrive Only, and Only Once
3 Finding the Best Boolean Function to Have Maximum Z-score
3.1 Improving the Time and Space Complexity Further
4 Results
4.1 RC4
4.2 Comparison with Java Rand and AES
4.3 Cross-testing by the Generated Polynomials, i.e., Functions
5 Conclusion
References
Weightwise Almost Perfectly Balanced Functions: Secondary Constructions for All n and Better Weightwise Nonlinearities
1 Introduction
2 Preliminaries
2.1 Boolean Functions and Weightwise Considerations
2.2 Siegenthaler's Construction, Symmetric Functions
2.3 Parity of Binomial Coefficients
3 Special WAPB Functions and Secondary Constructions
3.1 Restricted Walsh Transform and Properties
3.2 Special WAPB Functions
3.3 Secondary Constructions of WAPB Functions
4 Concrete Constructions and Parameters
4.1 Building SWAPB Functions from CMR Construction
4.2 Building Other WPB Functions from LM Construction
4.3 Hybrid Function with High Weightwise Nonlinearity in WPB4
4.4 Computational Aspects
5 Conclusion
References
Quantum Cryptography and Cryptanalysis
Improved Quantum Analysis of SPECK and LowMC
1 Introduction
2 Prerequisite
2.1 Backdrop and Motivation
2.2 Related Works
2.3 Quantum Gates
2.4 NIST Security Levels
3 Target Ciphers
3.1 SPECK Family (32/64, 48/72, 48/96, 64/96, 64/128, 96/96, 96/144, 128/128, 128/192, 128/256)
3.2 LowMC Family (L1, L3, L5)
4 SPECK in Quantum
4.1 Quantum Adder for SPECK
4.2 Quantum Circuit for SPECK Using Parallel Addition
4.3 Architecture and Resource Requirement
5 LowMC in Quantum
5.1 Implementation of S-box
5.2 Implementation of Linear Layer and Key Schedule
5.3 Implementation of KeyAddition and ConstantAddition
5.4 Architecture and Resource Requirement
5.5 Corrected LowMC Implementation from Eurocrypt'20 (JNRV)
6 Estimating Cost of Grover's Key Search
7 Conclusion
References
A Proposal for Device Independent Probabilistic Quantum Oblivious Transfer
1 Introduction
1.1 Our Contribution
1.2 Notations and Definitions
1.3 Adversarial Model
1.4 Assumptions for Our Device Independent Proposal
2 Our Proposed DI-QPQ Scheme
3 Analysis of Our Protocol
3.1 Correctness of the Protocol
3.2 Parameter Estimation for Private Query Phase
3.3 Security of Our Protocol
4 Discussion and Conclusion
References
Quantum Attacks on PRFs Based on Public Random Permutations
1 Introduction
2 Preliminaries
2.1 Notations
2.2 Decomposition of Linear Mappings
2.3 The Security of qPRF Based on Public Random Permutations
2.4 Quantum Algorithms
3 Attack on Function with One Permutation Call
4 Pseudorandom Function with Two Permutation Calls
4.1 Attack on Pseudorandom Function with Two Parallel Permutation Calls
4.2 Attack on Pseudorandom Function with Two Serial Permutation Calls
5 Instantiations of Some PRFs
5.1 Xop Construction Instantiated with EM Construction
5.2 EDM Construction Instantiated with EM Construction
5.3 EDMD Construction Instantiated with EM Construction
6 Conclusion
A Proof of (f)1/2 in Subcase 3.2) in Sect.3
B Proof of Pr[test(u)=1]122n for Any u-.25ex-.25ex-.25ex-.25exU in Subcase 4.1) in Sect.4.1
C Proof of (f)7/8 in Subcase 4.2) in Sect.4.1
D Proof of (f)7/8 in Case 4) of Sect.4.2
References
On Security Notions for Encryption in a Quantum World
1 Introduction
1.1 Defining Security for Encryption Against Quantum Adversaries
1.2 Our Approach
1.3 Our Contributions
2 Preliminaries
2.1 Notations
2.2 Quantum Computing
2.3 Cryptosystems and Notions of Security
3 How to Record Encryption Queries in the Random World?
3.1 Ciphertext Decomposition
3.2 Oracle Variations
3.3 Recording Queries in the Random World
3.4 A Technical Observation
3.5 How to Answer Decryption Queries?
3.6 Notation
4 Quantum-Secure Symmetric Encryption
4.1 Definitions of Security
4.2 Feasibility of Quantum CCA2 Security
5 Quantum-Secure Public-Key Encryption
5.1 Definitions of Security
5.2 A Lifting Theorem: From IND-qCCA2 to qIND-qCCA2
References
Post Quantum Cryptography
A One-Time Single-bit Fault Leaks All Previous NTRU-HRSS Session Keys to a Chosen-Ciphertext Attack
1 Introduction
1.1 Fragility
1.2 Natural DRAM Faults
1.3 Contributions of This Paper
2 Fault Attacks
2.1 A Generic Fault Attack
2.2 Specializing, Optimizing, and Demonstrating the Generic Fault Attack
2.3 Natural-Fault Attacks
2.4 Algorithm Dependence in Natural-Fault Attacks
2.5 Comparison
2.6 The Cold-Boot Argument Against Error Correction
3 Chosen-Ciphertext Attacks and Defenses
3.2 Ciphertext Structure
3.3 Decryption
3.4 Exploiting Linearity for Chosen-Ciphertext Attacks
3.5 Feature 0: Hashing the Plaintext
3.6 Probing the Boundaries of Successful Decryption
3.7 Probing as an Attack Against the Secret Key
3.8 Feature 1: Rigidity
3.9 Feature 2: No Decryption Failures
3.10 Feature 3: Plaintext Confirmation
3.11 Feature 4: Implicit Rejection
3.12 Feature 5: Hashing the Ciphertext
3.13 Feature 6: Limited Ciphertext Space
3.14 Feature 7: Limited Plaintext Space
4 The NTRU-HRSS Attack
4.1 Attack Model
4.2 Attack Details
4.3 How Plaintext Confirmation Stops Analogous mceliece and sntrup Attacks
4.4 How Proofs Led ntruhrss to Remove Plaintext Confirmation
4.5 Countermeasures for NTRU-HRSS
References
An Efficient Key Recovery Attack Against NTRUReEncrypt from AsiaCCS 2015
1 Introduction
2 Preliminaries
2.1 Vector and Matrix Forms of NTRU
3 NTRU and Its Proxy Re-encryption Scheme
3.1 NTRU Cryptosystem
3.2 NTRUReEncrypt
4 Key Recovery Attack Against NTRUReEncrypt
4.1 Construction of Equations
4.2 Linearization
4.3 Solving the System of Linear Congruence Equations
4.4 Recovering Private Keys
5 Case of NTRU Scheme with Different Parameter Sets
5.1 Case of Certain Secret Polynomial Coefficients
5.2 Case of Uncertain Secret Polynomial Coefficients
6 Experiments
7 Conclusion
References
Two Remarks on the Vectorization Problem
1 Introduction
2 Vectorization, Parallelization and Hidden Shift
3 Non-equivalence of Vectorization and Parallelization
4 Systems of Linear Disequations and the Standard Approach to Hidden Shift Finding
5 Finding Hidden Shifts in 2t pk-torsion Groups
5.1 Kuperberg Sieve
5.2 Disequations
5.3 Kuperberg Sieve, Again
5.4 Algorithm Summary and Complexity
5.5 Hidden Shift Finding in Groups with Large 2tpk-torsion
6 Conclusion
References
Efficient IBS from a New Assumption in the Multivariate-Quadratic Setting
1 Introduction
2 Preliminaries
2.1 Notations and Background
2.2 Hardness Assumption
2.3 Identity-Based Signature
3 Revisiting the IBS of Chen et al.
4 Modified Construction and Its Security
4.1 Security Argument
5 On the Hardness Assumption
6 Concluding Remark
References
Revisiting the Security of Salted UOV Signature
1 Introduction
2 Preliminaries
2.1 Quadratic Polynomials and Their Matrix Representation
2.2 (Unbalanced) Oil-Vinegar Signature Schemes
2.3 Linear Subspace Interpretation of Oil-Vinegar Trapdoor
2.4 Syntax and Security of Signature Scheme
3 Revisiting the Security Reduction of Salted UOV
3.1 On the Simulation of Random Oracle and Salt
4 A Clean Security Reduction of Salted UOV
4.1 Homogeneous UOV Signature Scheme Using the Subspace Interpretation
4.2 Salted Homogeneous UOV
4.3 Uniformity of MQ-Systems
4.4 Security of Salted Homogeneous UOV Signature in CROM
5 Security of Salted Homogeneous UOV in QROM
6 Concluding Remark
A Signature Using Trapdoor Information
A.1 Algorithm for Solving the Public Key System Using Trapdoor Information
A.2 Signature Scheme
B Signature of Sakumoto et al.
References
Author Index