Progress in Cryptology – LATINCRYPT 2023: 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023, Quito, Ecuador, October 3–6, 2023, Proceedings

Preface
Organization
Contents
Symmetric-Key Cryptography
On the Algebraic Immunity of Weightwise Perfectly Balanced Functions
1 Introduction
2 Preliminaries
2.1 Boolean Functions and Weightwise Considerations
2.2 Families of WPB Functions
2.3 Symmetric Functions and Krawtchouk Polynomials
3 General Results on the Algebraic Immunity of WPB Functions
3.1 Lower Bound on the Algebraic Immunity of Secondary Constructions
3.2 Minimal Algebraic Immunity of WPB Functions
3.3 Algebraic Immunity Distribution
4 Constructions of WPB Functions with Bounded Algebraic Immunity
4.1 Construction with Upper Bounded AI
4.2 Porcelain WPB Functions
4.3 WPB Functions from ch1C2SI:GM
4.4 Functions with Lower Bounded AI
5 Conclusion and Open Questions
References
ACE-HoT: Accelerating an Extreme Amount of Symmetric Cipher Evaluations for (High-order) Avalanche Tests
1 Introduction
1.1 Background and Motivation
1.2 Our Contribution
1.3 Related Works
1.4 Outline of this Work
2 Avalanche Tests
2.1 The Avalanche Probability Vector
2.2 Avalanche Criteria
3 High-Order Avalanche Tests
3.1 High-Order Avalanche Probability Vector
3.2 High-Order Avalanche Criteria
4 Parallelization Strategies and Multi-GPU Implementation
4.1 Determining the Workload
4.2 Parallelization Techniques Overview
4.3 Choosing the Parallelization Technique
4.4 Use Cases
5 Implementation Challenges
5.1 Avoiding CPU Bottleneck
5.2 Synchronization and Communication
5.3 Distributing the Workload
6 Detailed Results in the ASCON Use Case
6.1 High-Order Avalanche Tests on ASCON
6.2 Time and Speedup of 4 x A100 w.r.t. 8xTITAN GPU
6.3 Note on the Inverse of ASCON
7 Results for the Most Popular Ciphers
8 Discussion
9 Conclusion
References
Multi-party Computation
On Fully-Secure Honest Majority MPC Without n2 Round Overhead
1 Introduction
1.1 Our Contribution
1.2 Related Work
1.3 Overview of Our Techniques
1.4 Notation
2 Robust Secret-Sharing
3 Efficient Reconstruction
3.1 Towards Efficient Reconstruction
3.2 Batched Verification
References
Privacy-Preserving Edit Distance Computation Using Secret-Sharing Two-Party Computation
1 Introduction
2 Preliminaries
2.1 The Edit Distance Problem
2.2 Multi-party Computation and Secret-Sharing Schemes
2.3 Domain Conversions and Comparisons
3 A Privacy-Preserving Solution Using Secret Sharing
3.1 Arithmetic Part
4 Automatic Generation of Formulas for Edit Distance
5 Experiments
5.1 The Effect of the Box Size,
5.2 Comparison Between Garbled Circuits and Secret-Sharing
5.3 Comparison with Protocols Based on Homomorphic Encryption
6 Conclusion
References
Broadcast-Optimal Two Round MPC with Asynchronous Peer-to-Peer Channels
1 Introduction
1.1 Our Contributions
1.2 Terminology
1.3 Technical Overview
1.4 Organization
2 P2P-BC
2.1 Lower Bounds
2.2 Upper Bounds
References
Isogeny-Based Cryptography
Effective Pairings in Isogeny-Based Cryptography
1 Introduction
2 Preliminaries
2.1 Isogeny-Based Cryptography
2.2 Building Blocks in Isogeny-Based Cryptography
2.3 Pairing-Based Cryptography
2.4 Field Arithmetic
3 Optimizing Pairings for Composite Order
3.1 An Abstract View on Pairings
3.2 Reducing the Cost per Subroutine of Miller's Loop
3.3 Reducing the Number of Subroutines in the Miller Loop
3.4 Multiple Pairing Evaluations
3.5 Summary of Costs
4 Applications of Pairings to Isogeny Problems
4.1 Verification of Full-Torsion Points
4.2 Pairing-Based Supersingularity Verification
4.3 Finding Full-Torsion Points
4.4 Concrete Cost for CSIDH-512
5 Applications of Pairing-Based Algorithms
References
Fast and Frobenius: Rational Isogeny Evaluation over Finite Fields
1 Introduction
2 Background
3 Evaluating Isogenies
3.1 The Isogeny Evaluation Problem
3.2 The Costello-Hisil Algorithm
4 Accelerating Vélu: Faster Iteration over the Kernel
4.1 Kernel Point Enumeration and Differential Addition Chains
4.2 Additive Kernel Point Enumeration
4.3 Replacing xADDs with xDBLs
4.4 Multiplicative Kernel Point Enumeration
4.5 Stepping Through Cosets
4.6 The Remaining Primes
4.7 (In)Compatibility with Vélusqrt
5 Irrational Kernel Points: Exploiting Frobenius
5.1 The Cost of Frobenius
5.2 Galois Orbits
5.3 Enumerating Representatives for the Galois Orbits
6 Applications to Key Exchange
6.1 CSIDH and Constant-Time Considerations
6.2 CRS Key Exchange
References
Towards a Quantum-Resistant Weak Verifiable Delay Function
1 Introduction
2 Preliminaries
2.1 Elliptic Curves and Their Representation
2.2 Isogenies
2.3 Isogenies Between Abelian Surfaces
2.4 Weak VDFs
3 The VDF
3.1 The Conditions in Setup
3.2 The Size of p
3.3 Curves with Unknown Endomorphism Ring
3.4 The Role of the Security Parameter
4 Correctness
5 Soundness
6 Sequentiality
6.1 The Parallel FFT
6.2 Computing a Point of Order
6.3 Computing the Kernel Polynomial
7 Conclusion
A Factoring the -Division Polynomial
References
Discrete Logarithm Problem
Making the Identity-Based Diffie–Hellman Key Exchange Efficiently Revocable
1 Introduction
1.1 Our Contribution
1.2 Related Works
1.3 Technical Overview
2 Definition of RIB-AKE
2.1 Syntax of RIB-AKE
3 Our Construction
3.1 Sub-algorithms for Our Construction
3.2 Our Construction of RIB-AKE
3.3 Correctness
3.4 Efficiency
4 Security Model of RIB-AKE
4.1 Session
4.2 Adversary
4.3 Freshness
4.4 Security Experiment
5 Security Analysis for Our Protocol
References
On the Discrete Logarithm Problem in the Ideal Class Group of Multiquadratic Fields
1 Introduction
2 Notation
3 Background on Class Group and Discrete Logarithm Computation in Number Fields
3.1 Ideal Class Group Computation
3.2 Discrete Logarithm Problem in the Ideal Class Group of Number Fields
4 Square Root Computation for Decomposed Ideals
4.1 Square Root Computation in Cyclic Groups
4.2 Saturation Technique
4.3 Square Root of Decomposed Ideal by Reducing to Cyclic Groups
5 Discrete Logarithm Computation in the Ideal Class Group of Multiquadratic Fields
6 Implementation
6.1 Class Group Computation
6.2 Discrete Logarithm Computation
References
Cryptographic Protocols
Stronger Lower Bounds for Leakage-Resilient Secret Sharing
1 Introduction
1.1 Our Contribution
1.2 Other Related Works
2 Preliminaries
2.1 Leakage-Resilient Secret Sharing
3 Lower Bound
4 Leakage-Resilience of Shamir's Secret Sharing
4.1 Shamir's Secret Sharing Scheme
4.2 Noisy Leakage-Resilience
References
Folding Schemes with Selective Verification
1 Introduction
1.1 Our Contributions
1.2 Applications
1.3 Related Work
2 Definitions
2.1 Folding Schemes
2.2 Folding Schemes with Selective Verification
3 Bootstrapping Construction for Folding Schemes
3.1 Construction
3.2 Selective Verifiability of the Bootstrapped Construction
4 Folding Schemes from Interactive Public Coin Protocols
References
Composable Oblivious Pseudo-random Functions via Garbled Circuits
1 Introduction
1.1 Contribution
1.2 Related Work
2 Preliminaries
3 Construction
3.1 The Main Construction
3.2 Some Remarks on the Construction
4 Comparison of Concrete Efficiency
5 On the Ideal OPRF Functionality
5.1 Existing OPRF Functionalities
5.2 Relation Between [OPRF] and [OPRF]F
6 Conclusion
References
Real-World Cryptography
Quotable Signatures for Authenticating Shared Quotes
1 Introduction
2 Related Work
3 Quotable Signatures
3.1 Security Model
3.2 Merkle Trees
3.3 A Quotable Signature Scheme
3.4 Performance
4 Quotable Signatures and Fake News
5 Future Work
References
Post-quantum Hybrid KEMTLS Performance in Simulated and Real Network Environments
1 Introduction
2 Background
2.1 Transport Layer Security
2.2 Post-quantum Cryptography
2.3 Hybrid PQC
2.4 KEMTLS
3 Hybrid KEMTLS Proposed Design
3.1 Inherited Security Analysis
3.2 Modelling Cost of the Instantiations
4 Evaluation Methodology
5 Hybrid KEMTLS Evaluation
5.1 Hybrid Penalty in Geographical-Distant Servers
5.2 Hybrid Penalty in Simulated Environment
5.3 Hybrid KEMTLS Compared to Hybrid PQTLS
5.4 Summarizing Results
6 Conclusions
References
Zero-Knowledge Proofs
Physical Zero-Knowledge Proofs for Five Cells
1 Introduction
1.1 Zero-Knowledge Proof
1.2 Related Work
1.3 Our Contribution
2 Verifying Connected Area
2.1 Cards
2.2 Pile-Shifting Shuffle
2.3 Chosen Pile Cut Protocol
2.4 Sea Formation Protocol
3 Verifying Border Condition
3.1 Enhanced Matrix
3.2 Double-Scramble Shuffle
3.3 Rearrangement Protocol
3.4 Neighbor Counting Protocol
4 Putting Together
5 Optimization
5.1 Color Shifting Protocol
5.2 Optimized Protocol
6 Proof of Correctness and Security
7 Future Work
A Alternative ZKP Protocol for Five Cells
A.1 Printing Protocol
A.2 Main Protocol
References
Testudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup
1 Introduction
1.1 Contributions
1.2 Related Work
2 Preliminaries
2.1 Notation
2.2 Cryptographic Assumptions
2.3 PST Polynomial Commitments
2.4 Sumcheck
2.5 Spartan Overview
3 A Generalized MIPP Protocol
4 Testudo-Comm: Our PCS with Square Root Trusted Setup
5 Testudo: Our Construction
6 Practical Considerations
6.1 Parallelization and Aggregation of Testudo Proofs
7 Implementation and Evaluation
7.1 Implementation
7.2 Testudo Commitment
7.3 Testudo Groth16 Constraints
7.4 Testudo on Data-Parallel Circuits
References
Set (Non-)Membership NIZKs from Determinantal Accumulators
1 Introduction
2 Preliminaries
2.1 Universal NIZK Arguments
2.2 CLPØ NIZK
3 General Non-membership NIZK Argument System
4 Determinantal Accumulators
4.1 Determinant Verification
5 The New Determinantal Accumulator AC*
6 New Set (Non-)Membership NIZK
7 On Handling Group Elements with CLPØ
References
Benchmarking the Setup of Updatable Zk-SNARKs
1 Introduction
2 Preliminaries
2.1 Updatable, Universal and Subversion-Resistant Zk-SNARKs
2.2 Assumptions
3 SU and SV Algorithms for Updatable Zk-SNARKs
3.1 SU and SV Algorithms for Sonic
3.2 SU and SV Algorithms for Marlin
3.3 Batched SRS Verification Algorithms
4 Performance Analysis and Identifiable Security
4.1 Implementation Results
4.2 Identifiable Security in the Updatable SRS Model
5 Conclusion
References
Author Index