Progress in Cryptology – LATINCRYPT 2021: 7th International Conference on Cryptology and Information Security in Latin America, Bogotá, Colombia, ... 2021, Proceedings (Security and Cryptology)

This book constitutes the proceedings of the 7th International Conference on Cryptology and Information Security in Latin America, LATIN 2021, which was held in October 2021. The conference was originally planned to take place in Bogota, Colombia, but changed to a virtual event due to the COVID-19 pandemic. The 22 full papers included in this volume were carefully reviewed and selected from 47 submissions. They were organized in topical sections as follows: quantum cryptography; post-quantum cryptography; asymmetric cryptanalysis; cryptanalysis and side-channel analysis; distributed cryptographic protocols; and multiparty computation. Preface Organization Contents Quantum Cryptography Tight Bounds for Simon's Algorithm 1 Introduction 2 Amplitude Amplification 3 Simon's Algorithm 3.1 Algorithm Description 3.2 Analysis with Periodic Permutations 3.3 Limitations of Simon's Algorithm 3.4 A General Criterion 3.5 With Random Functions 4 Exact Variant of Simon's Algorithm 4.1 The Algorithm of Brassard and Høyer 4.2 Our Improved Variant 5 Grover-meets-Simon 5.1 Algorithm Description 5.2 Cost Analysis 6 The Offline Simon's Algorithm 6.1 Algorithm Description 6.2 Cost Analysis 7 Applications in Cryptanalysis 7.1 Landscape of Known Simon-Based Attacks 7.2 Cost Estimates in Practice 8 Conclusion References Constructions for Quantum Indistinguishability Obfuscation 1 Introduction 1.1 Overview of Results and Techniques 1.2 More on Related Work 1.3 Open Questions 2 Preliminaries 2.1 Basic Classical Cryptographic Notions 2.2 Classical Circuits and Algorithms 2.3 Classical Indistinguishability and Obfuscation 2.4 Basic Quantum Notions 2.5 Norms and Pseudo-distance 2.6 Quantum Indistinguishability 3 Indistinguishability Obfuscation for Quantum Circuits 4 Quantum Indistinguishability Obfuscation for Clifford Circuits 4.1 qiO for Clifford Circuits via a Canonical Form 4.2 qiO for Clifford Circuits via Gate Teleportation 5 Obfuscating Beyond Clifford Circuits 5.1 Single-Qubit Circuits 5.2 qiO via Gate Teleportation for all Quantum Circuits 6 Quantum Indistinguishability Obfuscation with Respect to a Pseudo-Distance 6.1 Approximately Equivalent Quantum Circuits 6.2 Indistinguishability Obfuscation for Approximately Equivalent Quantum Circuits 6.3 qiOD for Circuits Close to the Gottesman-Chuang Hierarchy References On Forging SPHINCS+-Haraka Signatures on a Fault-Tolerant Quantum Computer 1 Introduction 2 Preliminaries 2.1 The SPHINCS+ Signature Scheme 2.2 Quantum Computing 2.3 Grover's Algorithm on Preimage Resistance 2.4 Fault-Tolerant Resource Estimation 3 Reversible Implementations 3.1 Haraka 3.2 SHAKE-256 4 Attacking the SPHINCS+ Signature Scheme 4.1 Forging a SPHINCS+ Signature on the XMSS component 4.2 Forging a SPHINCS+ Signature on the WOTS Component 5 Fault-Tolerant Cost 5.1 Haraka 5.2 SHAKE-256 6 Conclusion References Post-quantum Cryptography Post-quantum Key-Blinding for Authentication in Anonymity Networks 1 Introduction 1.1 Our Contributions and Paper Structure 1.2 Related Work 2 Background 2.1 Onion Services 2.2 Key-Blinding Signature Scheme Definitions 3 Unlinkability of Signature Schemes with Key-Blinding 4 A Lattice-Based Key-Blinding Scheme 4.1 blDilithium-QROM Description 4.2 blDilithium-QROM Security 4.3 Key-Blinding Dilithium 5 An Isogeny-Based Key-Blinding Scheme 6 A Number-Theoretic Key-Blinding Scheme 7 Implementation Details 8 Conclusion References Implementing and Measuring KEMTLS 1 Introduction 2 Post-quantum Cryptography in TLS 1.3 2.1 Reviewing the TLS 1.3 Protocol 2.2 PQTLS: Signed Post-quantum TLS 1.3 2.3 KEMTLS: KEMs Everywhere 2.4 KEMTLS-PDK: Reducing Round Trips 3 Implementation Details 3.1 Implementation in Go 3.2 A Testbed Network 4 Measurement Experiment and Discussion 4.1 Experiment Setup 4.2 Measurements 4.3 Discussion 4.4 Optimizations 5 Conclusions References A Monolithic Hardware Implementation of Kyber: Comparing Apples to Apples in PQC Candidates 1 Introduction 1.1 Contributions 2 Preliminaries 2.1 Symbol Definition 2.2 The Kyber Protocol 2.3 Polynomial Multiplication 3 Proposed Architecture 3.1 Keccak Core 3.2 Rejection Sampling 3.3 Binomial Sampling 3.4 Configurable Butterfly Core 3.5 Area/Performance Trade-Offs 4 Implementation Results And Comparisons 5 Conclusion References Attribute-Based Access Control for Inner Product Functional Encryption from LWE 1 Introduction 2 Preliminaries 2.1 Attribute-Based Inner Product Functional Encryption 2.2 Lattice Preliminaries ch7boneh2014fully,ch7abdalla2020inner 2.3 Homomorphic Evaluation Procedures 3 Our Construction of ABIPFE from LWE 4 Generic Construction of ABMIPFE from ABIPFE 5 Conclusion References Asymmetric Cryptanalysis Classical Attacks on a Variant of the RSA Cryptosystem 1 Introduction 2 Preliminaries 2.1 The Scheme of Murru and Saettone 2.2 Continued Fraction 2.3 Lattices and Coppersmith's Method 3 Useful Lemmas 4 Application of Continued Fractions 4.1 The Attack 4.2 A Numerical Example 5 Application of Coppersmith's Method 5.1 The Small Inverse Problem 5.2 The Attack with Small k 5.3 The Attack with Small d 5.4 Experimental Results 6 Conclusion References Improved Attacks Against Key Reuse in Learning with Errors Key Exchange 1 Introduction 2 Background 2.1 Fluhrer's Key Reuse Attack on DXL RLWE-Based Key Exchange 3 Sparse Signal Collection 4 Improvements to Existing Key Reuse Attacks 4.1 Determining Sparse Signal Collection Parameters 4.2 Description of the Improved Attack 4.3 Success Probability 4.4 Query Complexity 4.5 Experimental Results 5 Attack on DBS Reusable-Keys Protocol 5.1 High-Level Idea of the Attack 5.2 The Complete Attack 5.3 Distribution of the Error Terms 5.4 Distribution of the Known Term 5.5 Query Complexity 5.6 Success Probability 5.7 Experimental Results 5.8 Analysis of the Claimed Proof Showing Robustness 5.9 Application to Seyhan et al. Reusable Keys Protocol 6 Extension to Authenticated Key Exchange Protocols References Cryptanalysis and Side-Channel Analysis Differential-ML Distinguisher: Machine Learning Based Generic Extension for Differential Cryptanalysis 1 Introduction 2 Comparison with the Previous Work 3 Block Ciphers: SPECK32, SIMON32, and GIFT64 3.1 Description of SPECK32 3.2 Description of SIMON32 3.3 Description of GIFT64 4 Differential Cryptanalysis 4.1 Classical Differential Distinguisher 4.2 Differential Distinguisher Using Machine Learning 5 Differential-ML Distinguisher: Extending Classical Differential Distinguisher Using Machine Learning 6 Experimental Results 6.1 Differential-ML Distinguisher: SPECK32 6.2 Differential-ML Distinguisher: SIMON32 6.3 Differential-ML Distinguisher: GIFT64 6.4 Comparison with the Classical Differential Distinguishers 7 Conclusion References Train or Adapt a Deeply Learned Profile? 1 Introduction 2 State-of-the-Art on Deep Learning Techniques for SCA 3 On Transferring Side-Channel Model Knowledge 3.1 Approach 3.2 CNN Architecture 3.3 CNN Training 3.4 Evaluation Metrics and Targeted Value 4 Transferring Between EM Probe Position and Type 4.1 Experimental Results 5 Transferring Between Power and EM 5.1 Experimental Results 6 Transferring Between Different Devices 6.1 Experimental Results 7 Conclusion References Autocorrelations of Vectorial Boolean Functions 1 Introduction 2 Preliminaries 2.1 Walsh Transform, Bent Functions, AB Functions and Plateaued Functions 2.2 Differential Uniformity and APN Functions 2.3 The DLCT and the Autocorrelation Table 3 Properties of the Autocorrelation Table 3.1 Links Between the Autocorrelation and the Walsh Transform 3.2 Links Between the Autocorrelation and the DDT 3.3 Bounds on the Absolute Indicator 3.4 Divisibility of the Autocorrelation 3.5 Invariance Under Equivalence Relations 3.6 Autocorrelation of Plateaued, AB and APN Functions 4 Autocorrelation Spectra and Absolute Indicator of Special Polynomials 4.1 Monomials 4.2 Quadratic Functions and Their Inverses 5 Conclusion References Automatic Search for Bit-Based Division Property 1 Introduction 1.1 Related Work 1.2 Our Contribution 2 Preliminaries 2.1 Notations 2.2 Definitions 3 Propagation of Bit-Based Division Property 3.1 Modeling the Sbox 3.2 CNF from Division Trail 4 Input Division Property and Output Division Property 4.1 Input Division Property 4.2 Output Division Property 4.3 Automatic Algorithm for Finding Division Properties 4.4 Reduction of Data Complexity 5 Application to the KNOT Permutation 5.1 Specification 5.2 Application of Our Model 5.3 Finding the Longest Division Properties 5.4 More Efficient Distinguishers 6 Other Results 7 Proving the Non-Existence of Longer Division Trails 7.1 Further Reduction of the Search Space for Lout 7.2 Checking Polynomials 7.3 Application on the KNOT 8 Conclusion References TEDT2 – Highly Secure Leakage-Resilient TBC-Based Authenticated Encryption 1 Introduction 1.1 Leakage-Resilient Authenticated Encryption 1.2 Research Questions 2 Preliminaries 3 Design Rationale 4 Definition of TEDT2 5 Security Model 5.1 Notion for Authenticity 5.2 Notions for Confidentiality 6 Authentication Security Analysis of TEDT2 7 Encryption Security Analysis of TEDT2 8 Discussion and Future Work References Distributed Cryptographic Protocols Weight-Based Nakamoto-Style Blockchains 1 Introduction 1.1 Overview of Our Results 1.2 Related Work 2 Our Generic Framework for Weight-Based Analysis 2.1 Blockchain Model 2.2 Basic Definitions 2.3 Bounds on Produced Weight 2.4 Proving Bounds from Properties of the Weight Functions 3 Proving Chain Properties 3.1 Chain Growth 3.2 Chain Quality 3.3 Common Prefix 4 Applying the Framework to Capped Weight Functions 4.1 Definitions and General Results 4.2 Examples of Capped Weight Functions 5 Conclusions and Directions for Future Work A Weight-Based Chain Quality and Common Prefix References LOVE a Pairing 1 Introduction 1.1 Related Work 2 Preliminaries 2.1 Pairings 3 Delegating Pairings with Online Public Inputs 3.1 Modeling Offline/Online Pairing Delegation Protocols 3.2 Di Crescenzo et al.'s Protocol 4 Our Protocol for LOVE a Pairing 5 Implementation Results 5.1 Timings for Operations in Pairing Groups 5.2 Timings for Delegated Pairing Computation 6 Conclusions References Implementing Secure Reporting of Sexual Misconduct - Revisiting WhoToo 1 Introduction 1.1 Contributions 1.2 Related Work 2 Preliminaries 2.1 WhoToo: An Introduction 2.2 WhoToo+ Overview 3 Building Blocks 3.1 Distributed Operations 3.2 Distributed Group Signatures 3.3 Privacy-Preserving Multisets 4 Two Issues in WhoToo 4.1 Securely Evaluating Quorum in WhoToo 4.2 Identifying Duplicate Accusations 5 Improving WhoToo 5.1 Duplicate Revision 5.2 Matching Accusations 5.3 The Full WhoToo+ Description: 6 Security Analysis 7 Efficiency Analysis References Stronger Notions and a More Efficient Construction of Threshold Ring Signatures 1 Introduction 1.1 Application: Whistleblowing 1.2 Our Contributions 1.3 Fully Compact Threshold Ring Signatures 1.4 Related Work 1.5 Outline 2 (Threshold) Ring Signature Definitions 2.1 Ring Signature Definitions 2.2 Threshold Ring Signature Definitions 3 Our Threshold Ring Signature Construction 3.1 Unique Ring Signature Definitions 3.2 A Unique Ring Signature Scheme 3.3 A Threshold Ring Signature Scheme References Improved Threshold Signatures, Proactive Secret Sharing, and Input Certification from LSS Isomorphisms 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 LSS Isomorphisms and Bilinear Maps 2.1 Linear Secret Sharing 2.2 LSS over Vector Spaces 2.3 LSS Isomorphisms 2.4 LSSS with Bilinear Maps 3 Threshold Signature Schemes 3.1 The PS Signature Scheme 3.2 Threshold PS Signatures 4 Applications to Proactive Secret Sharing 4.1 Proactive Secret Sharing 4.2 Partial PSS 4.3 Simple and Efficient PSS with Abort 5 Applications to Input Certification 5.1 Certifying Inputs with PS Signatures 6 Implementation and Benchmarking 6.1 Certified Inputs References Multiparty Computation Full-Threshold Actively-Secure Multiparty Arithmetic Circuit Garbling 1 Introduction 2 Preliminaries 3 Full-Threshold Active Security 3.1 Overview 3.2 Secret-Sharing-Based Wire Mask Arithmetic 3.3 Wire Mask/Global Difference Products 3.4 The Complete Garbling and Evaluation Protocols 4 Selector Gate 4.1 New Selector Gate 5 Evaluation in Comparison to Previous Work 6 Conclusion References The Cost of IEEE Arithmetic in Secure Computation 1 Introduction 2 Preliminaries 2.1 MPC-Black Box 2.2 IEEE-754 2.3 Secure-Floats via Fp-Arithmetic 2.4 Fixed Point Representation 3 Generating Circuits for IEEE Arithmetic 4 Converting Between Representations 5 Experimental Results References Honest Majority MPC with Abort with Minimal Online Communication 1 Introduction 1.1 Our Contribution 1.2 Overview of Our Techniques 1.3 Related Work 2 Preliminaries 2.1 Notation 2.2 Security Definition 2.3 Linear Secret-Sharing 2.4 Reconstruction Protocols 2.5 Sampling Shares of Random Values 2.6 Correct Multiplication 3 Optimizing the Online Phase 3.1 Masked Secret-Sharing 3.2 General Overview 3.3 Main Protocol 4 Removing the Extra Parties from the Output Phase 4.1 General Overview 4.2 Full Protocol Description References Author Index