[Lecture Notes in Computer Science] Topics in Cryptology – CT-RSA 2020 Volume 12006 (The Cryptographers’ Track at the RSA Conference 2020, San Francisco, CA, USA, February 24–28, 2020, Proceedings) ||

This book constitutes the refereed proceedings of the Cryptographer's Track at the RSA Conference 2020, CT-RSA 2020, held in San Francisco, CA, USA, in February 2020. The 28 papers presented in this volume were carefully reviewed and selected from 95 submissions. CT-RSA is the track devoted to scientific papers on cryptography, public-key to symmetric-key cryptography and from crypto-graphic protocols to primitives and their implementation security. Preface Organization Contents Generic Attack on Iterated Tweakable FX Constructions 1 Introduction 1.1 Notations 1.2 Previous Works 1.3 Results 2 Cryptanalysis of 2-Round Tweakable FX 2.1 The Algorithm 2.2 Deriving the Constants 2.3 Constraints 3 Cryptanalysis of r-Round Tweakable FX 3.1 Constants and Complexity 3.2 Discussion References Universal Forgery Attack Against GCM-RUP 1 Introduction 1.1 Contributions 1.2 Related Works 1.3 Organization 2 Preliminaries 2.1 Notations and Operations 2.2 AE, Separated AE and TBC 3 Brief Description of GCM-RUP ch2gcmspsrup 3.1 Generic Construction with RUP Security ch2gcmspsrup 3.2 GCM-RUP ch2gcmspsrup 4 Partial Authentication Key Recovery for GCM-RUP 4.1 Properties of GHASH 4.2 Recovering K2 from Inner Collisions 4.3 Experimental Verification with Mini-GCM-RUP 5 Universal Forgery Attack of GCM-RUP 5.1 Almost Universal Forgery Attack 5.2 Universal Forgery Attack 6 Variant of GCM-RUP 7 Conclusion References My Gadget Just Cares for Me - How NINA Can Prove Security Against Combined Attacks 1 Introduction 1.1 Contributions 2 The Circuit Model and Secret Sharing 3 Security Definitions 3.1 Orders of Security 3.2 Composable Notions of Security 4 Combined Secure Duplicated Boolean Masking 4.1 Duplicated Boolean Masking 4.2 Duplicated Boolean Methodology 4.3 A Cascading Gadget 5 A Correcting Multiplication 6 Conclusion References Modeling Memory Faults in Signature and Authenticated Encryption Schemes 1 Introduction 2 Modeling Fault Resilience 2.1 Fault Types 2.2 Relations 3 Fault-Resilient Signatures 3.1 Fault-Resilient Signature Unforgeability 3.2 De-randomized Signatures Are Not Fault-Resilient 3.3 Combining Randomization and De-randomization 4 Fault-Resilient Authenticated Encryption 4.1 Fault-Resilient Security of Authenticated Encryption 4.2 SIV Is Not Fault-Resilient 4.3 SIV$: Randomness-Augmented SIV 5 Conclusion References Cryptanalysis of the Multivariate Encryption Scheme EFLASH 1 Introduction 1.1 Our Contribution 1.2 Organisation 2 Preliminaries 2.1 Description of EFLASH 2.2 Gröbner Basis Algorithms 2.3 Univariate and Multivariate Representation of Polynomials 3 Suggested First Fall Degree Bound 4 The First Fall Degree of EFLASH 4.1 The Effect of Removing Polynomials 4.2 First Fall Polynomials at D = 3 4.3 First Fall Polynomials at D = 4 5 Experimental Results 6 Security Estimation for EFLASH 7 Further Work 8 Conclusions References FPL : White-Box Secure Block Cipher Using Parallel Table Look-Ups 1 Introduction 1.1 Our Contribution 2 Preliminaries 2.1 Table-Based Block Cipher 2.2 Security Notions 3 FPL : Block Cipher Using Parallel Table Look-Ups 4 Probabilistic Construction of Secure Probe Functions 5 White-Box Security of FPL 5.1 Key Extraction Hardness of FPL 5.2 Space Hardness of FPL 5.3 Numerical Interpretation 6 FPLAES : Concrete Instantiation 6.1 Specification 6.2 Black-Box Security of FPLAES 6.3 Performance References Extending NIST's CAVP Testing of Cryptographic Hash Function Implementations 1 Introduction 2 Testing Within NIST's CAVP 2.1 Algorithm Functional Test (AFT) 2.2 Monte Carlo Test (MCT) 3 Common Hashing Interfaces 4 Vulnerability in Apple's CoreCrypto Library 4.1 Experimental Verification 5 Proposing the Large Data Test (LDT) 6 Discussion 7 Conclusion A The ccdigest_update() function of Apple's CoreCrypto References A Fast Characterization Method for Semi-invasive Fault Injection Attacks 1 Introduction 1.1 Related Work 1.2 Our Contributions 2 Preliminaries 2.1 Fault Injection Attacks 2.2 Supervised Machine Learning 2.3 Neural Networks and Deep Learning 3 Fast Characterization Methodology 3.1 Notations 3.2 Metrics Definition 4 Sensitivity Curve 4.1 Setting 4.2 Sensitivity Curve Generation 4.3 Sensitivity Curve Evaluation 5 Results 5.1 Experimental Setup 5.2 Characterization for the DES Encryption Attack 5.3 Characterization for the AES Encryption Attack 6 Conclusions and Future Work References Tightly Secure Two-Pass Authenticated Key Exchange Protocol in the CK Model 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Preliminaries 3 Tightly Secure AKE Protocol in the CK Model 3.1 The CK Model 3.2 Our Construction 4 MU-IND-CCACorr Secure TB-KEM 5 Instantiation and Comparisons A Concrete Instantiation References Symmetric-Key Authenticated Key Exchange (SAKE) with Perfect Forward Secrecy 1 Introduction 1.1 Related Work 1.2 Contributions 1.3 Our Approach 1.4 Outline of the Paper 2 Security Model 2.1 Execution Environment 2.2 Security Definitions of SAKE's Building Blocks 3 Our Symmetric-Key AKE Protocol with Perfect Forward Secrecy 3.1 Description of the Protocol 3.2 Notation 3.3 SAKE-AM: A Complementary Mode of SAKE 4 A Random-Free Variant of SAKE 5 Security and Soundness for SAKE 5.1 Soundness of SAKE 5.2 Security of SAKE 6 Comparison with the DH Paradigm 7 Conclusion References TMPS: Ticket-Mediated Password Strengthening 1 Introduction 1.1 Security Goals 1.2 Overview of TMPS 1.3 Related Work 1.4 Our Results 2 Preliminaries 2.1 Notation 2.2 Underlying Primitives and Functions 3 Ticket-Mediated Password Strengthening 3.1 TMPS Overview 3.2 Discussion 4 The Basic Protocol 4.1 Server Setup 4.2 Request: Protocol for Requesting Tickets 4.3 Unlock: Protocol for Unlocking a Ticket 5 Security Analysis 5.1 Proof of Theorem 1 5.2 Description of Simulator Sim 6 Performance and Implementation 6.1 Requesting a Ticket 6.2 Unlocking a Ticket 6.3 Storage 7 Conclusion and Open Questions A Definitions References Overdrive2k: Efficient Secure MPC over Z2k from Somewhat Homomorphic Encryption 1 Introduction 2 Preliminaries 2.1 The SPDZ2k Protocol 2.2 The BGV SHE Scheme and Associated Number Theory 3 Modified SHE Scheme 3.1 Our New Packing Technique 3.2 The BGV Encryption Scheme with Double Packing Set 4 OverDrive Global ZKPoKs 4.1 Bounded Linearly Homomorphic Predicates 4.2 Amortized Zero Knowledge Proof 5 Distributed Somewhat Homomorphic Encryption 5.1 Distributed Decryption Protocols 5.2 Generating Valid Ciphertexts 6 SPDZ2k from Somewhat Homomorphic Encryption - Pre-processing Phase 6.1 Weak Offline Protocol 6.2 From FwPrep to FPrep - Sacrificing 7 Communication Efficiency Analysis References SoK: A Consensus Taxonomy in the Blockchain Era 1 Introduction 2 Model and Definitions 2.1 Protocol Execution 2.2 The Consensus Problem 3 Network Assumptions 4 Setup Assumptions 5 Computational Assumptions 6 Consensus in the Point-to-Point Setting 7 Consensus in the Peer-to-Peer Setting 8 Ledger Consensus References Consensus from Signatures of Work 1 Introduction 2 Preliminaries 3 Signatures of Work 4 Applications 4.1 The Permissionless Model, Revisited 4.2 Public Transaction Ledger from Signatures of Work 4.3 Consensus from Signatures of Work References Faster Homomorphic Encryption is not Enough: Improved Heuristic for Multiplicative Depth Minimization of Boolean Circuits 1 Introduction and Related Works 2 Rewrite Operators 2.1 Preliminary Definitions 2.2 Multiplicative Depth-2 Path Rewriting 2.3 Multiplicative Depth-2 Cone Rewriting 2.4 Cone Rewriting 3 Improved Heuristic 3.1 Overview 3.2 Cone Selection Method 3.3 Reductions on Non-critical Circuits 4 Experimental Results 4.1 Multiplicative Depth Minimization 4.2 Homomorphic Execution Acceleration 5 Conclusion and Perspectives References Better Bootstrapping for Approximate Homomorphic Encryption 1 Introduction 1.1 Our Contribution 1.2 Road Map 2 Preliminary 2.1 Chebyshev Approximation 2.2 Full-RNS HEAAN 2.3 Bootstrapping for HEAAN 3 Full-RNS Variant of HEAAN 3.1 Scheme Description 3.2 Comparison 4 Better Homomorphic Sine Evaluation 4.1 Our Method 4.2 Homomorphic Evaluation of pn(t) 4.3 Hybrid Method 4.4 Overall Comparison 4.5 Put Everything Together 5 Implementation 5.1 Performance of Basic Homomorphic Operations. 5.2 Bootstrapping Performance 6 Conclusion A Correctness and Noise Growth of Homomorphic Multiplication References Improved Secure Integer Comparison via Homomorphic Encryption 1 Introduction 1.1 Our Contribution 1.2 Organization 2 Homomorphic Comparison of Integers 2.1 Preliminaries 2.2 Strategy Overview 2.3 Homomorphic Comparison of Small Integers 2.4 Homomorphic Comparison of Unbounded Integers 2.5 Efficiency 3 A Protocol for the Millionaires' Problem 3.1 Preliminaries 3.2 Protocol for Small Integers 3.3 Security of the Protocol for Small Integers 3.4 A Protocol for Large Integers 4 Security of the Protocol for Large Integers 4.1 Parameters 4.2 Efficiency 5 Conclusion References Efficient FPGA Implementations of LowMC and Picnic 1 Introduction 1.1 Contribution 1.2 Related Work 2 Preliminaries 2.1 LowMC 2.2 Picnic and ZKB++ 2.3 Picnic Instances and Parameters 3 Implementation 3.1 Optimized VHDL Implementation of LowMC 3.2 Pipeline versus State Machine 3.3 Optimized VHDL Implementation of Picnic 4 Evaluation 4.1 Hardware Utilization 4.2 Clock Cycles 4.3 Benchmarks 4.4 Comparison to FPGA Implementations of Other Signature Schemes 4.5 Evaluation of the LowMC Pipeline Design 5 Reducing the Hardware Utilizations 6 Conclusion References Traceable Ring Signatures with Post-quantum Security 1 Introduction 1.1 Our Results 1.2 Related Work 2 Preliminaries 2.1 Notations 2.2 Stern Protocols 2.3 Merkle-Tree-Based Accumulator 2.4 Traceable Ring Signatures 3 General Construction 3.1 Building Blocks 3.2 Our Construction 3.3 Correctness Analysis 3.4 Security Analysis 3.5 Constructions of Unique PRF with Intersection-Free Range 4 Traceable Ring Signature Schemes from Lattices 4.1 Efficient PRF in QROM 4.2 Stern Protocol for PRF 4.3 OR-Composition from Accumulators 4.4 Description of the Scheme References Post-quantum Provably-Secure Authentication and MAC from Mersenne Primes 1 Introduction 1.1 Motivation 1.2 Our Contribution 1.3 Related Works 1.4 Organization of the Paper 2 Preliminaries 2.1 Notation 2.2 Secret-Key Authentication Syntax 2.3 Security Models 2.4 Tag Sparsity Definition and Security 2.5 Security Against Sequential Man-in-the-Middle Adversary 2.6 Message Authentication Codes 2.7 Hash Functions 3 The MERS Problem 3.1 MERS Problem with Uniform Secret 3.2 Hardness and Concrete Parameters 4 Passively-Secure Authentication Based on MERS 5 ROR-CMA-Secure Authentication Based on MERS 6 S`-MIM-Secure Authentication Based on MERS 7 MAC from MERS 7.1 Proof of Theorem 7.1 A Proof of Lemma7.1 References Another Look at Some Isogeny Hardness Assumptions 1 Introduction 2 Mathematical Background 3 The One-More Isogeny Problem 3.1 Problem Statements 3.2 Basic Attack 4 Application to Jao-Soukharev's Construction 4.1 Jao-Soukharev Undeniable Signatures 4.2 Another Look at the Security Proof of ch21jao2014isogeny 5 Srinath and Chandrasekaran Undeniable Blind Signatures 6 Conclusion A Undeniable (Blind) Signature Schemes References How to Construct CSIDH on Edwards Curves 1 Introduction 1.1 Our Results 2 Preliminaries 2.1 Basic Mathematical Concepts 2.2 Montgomery Curves 2.3 Edwards Curves 3 CSIDH ch22CAS18 3.1 CSIDH Protocol 3.2 Evaluating the Class Group Action on Montgomery Curves ch22CAS18 4 Main Theorems Used for Our Algorithm 5 Evaluating the Class Group Action on Edwards Curves 6 Computational Costs 6.1 Comparing Computational Costs Theoretically 6.2 Implementations 7 Conclusion and Future Work 7.1 Conclusion 7.2 Future Work A Compute group operations and isogenies A.1 Montgomery curves A.2 Edwards curves References Policy-Based Sanitizable Signatures 1 Introduction 2 Preliminaries 3 Our Framework for P3Ss 4 Construction 5 Conclusion References Traceable Inner Product Functional Encryption 1 Introduction 2 Preliminaries 3 Traceable Functional Encryption 4 Our Inner-Product Functional Encryption 5 Black-Box Confirmation Traitor-Tracing 5.1 Notations 5.2 Tracing Algorithm References One-More Assumptions Do Not Help Fiat-Shamir-type Signature Schemes in NPROM 1 Introduction 1.1 Our Result 2 Preliminaries 2.1 Digital Signature Schemes 2.2 Generalized One-More Cryptographic Assumptions 2.3 Fiat-Shamir-type Signature Schemes 3 Security of Fiat-Shamir-type Signature Schemes Cannot Be Proven from Generalized One-More Assumptions in NPROM References Cut-and-Choose for Garbled RAM 1 Introduction 1.1 Our Results 1.2 Related Work 2 Our Techniques 2.1 Roadmap 3 Preliminaries 3.1 Garbled RAM Scheme 3.2 Garbled RAM Against Malicious Adversaries 4 Black-Box Garbled RAM 4.1 Uniform Circuits 4.2 Garbled RAM Scheme 5 Adaptive Secure Garbling Schemes 5.1 Adaptive Secure LEGO Garbling Scheme 5.2 Adaptive Secure Garbled RAM 6 Generating an Adaptive LEGO Garbled Circuit 6.1 The New LEGO Protocol 6.2 Analysis 7 Our Construction 7.1 Generating Partial Labels 7.2 Our Protocol References Universally Composable Accumulators 1 Introduction 1.1 Accumulator Applications 2 Revisiting Classical Accumulator Definitions 2.1 Notation and Algorithms 2.2 Security Definitions 3 Ideal Functionality for Accumulators 3.1 Modeling Decentralized Management 3.2 Modeling Non-adaptive Soundness 3.3 Adding Privacy Properties 3.4 Discussion: Incorrect Accumulator and Witness Values 4 Equivalence Argument 5 Demonstrations of Composition 5.1 Accumulator Composition: Braavos 5.2 Accumulators for Anonymous Credentials A Universally Composable Signatures References A Non-interactive Shuffle Argument with Low Trust Assumptions 1 Introduction 2 Preliminaries 2.1 FLSZ Shuffle Argument 3 Distributed Key Generation Protocol 3.1 Verification-Friendly Public Key 3.2 DKG Protocol for Verification-Friendly Keys 4 Transparent Shuffle Argument 5 Security in the CRS Model 6 Zero-Knowledge in the BPK Model 7 Implementation References Author Index