Post-Quantum Cryptography: 4th International Workshop, PQCrypto 2011, Taipei, Taiwan, November 29 - December 2, 2011, Proceedings (Lecture Notes in Computer Science, 7071)

This book constitutes the refereed proceedings of the 4th International Workshop on Post-Quantum Cryptography, PQCrypto 2011, held in Taipei, Taiwan, in November/December 2011. The 18 revised full papers presented were carefully reviewed and selected from 38 submissions. The papers cover a wide range of topics in the field of post-quantum public key cryptosystems such as cryptosystems that have the potential to resist possible future quantum computers, classical and quantum attacks, and security models for the post-quantum era.. Cover 1 Post-Quantum Cryptography, 4th International Workshop, PQCrypto 2011, Taipei, Taiwan, November 29 – December 2, 2011, Proceedings 4 ISBN 9783642254048 e-ISBN 9783642254055 5 Foreword 6 Organization 8 Table of Contents 10 General Fault Attacks on Multivariate Public Key Cryptosystems 12 Introduction 12 The Proposed Fault Attacks 13 Multivariate Public Key Cryptosystems 14 Basic Constructions of G 14 Variations of Basic G 17 Major Attacks 18 The Proposed Fault Attacks on MPKCs 19 Attack Model 19 Fault Attacks on G 20 Fault Attacks on r 24 Countermeasures 26 Conclusion 27 References 27 Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies 30 Introduction 30 Isogenies 31 Public-Key Cryptosystems Based on Supersingular Curves 32 Key Exchange 33 Public-Key Encryption 34 Algorithmic Aspects 34 Parameter Generation 35 Key Exchange 35 Isogenies of Montgomery Curves 36 Security 39 Complexity Assumptions and Security Proofs 39 Hardness of the Underlying Assumptions 41 Implementation Results and Example 42 Example 43 Conclusion 44 References 44 Full Cryptanalysis of the Chen Identification Protocol 46 Introduction 46 Basic Facts on Rank Distance 48 Definitions and Notation 48 Properties 48 Codes for the Rank Distance 49 Rank Distance and Cryptography 50 The Chen Protocol 50 Cryptanalysis 51 Flaws in Chen's Zero-Knowledge Proof 51 The Support Attack 52 Linear Attack 53 Countermeasures 55 Defense against the Support Attack 55 Defense against the Linear Attack 55 A New Protocol 55 Description of the Protocol 55 Zero-Knowledge Properties 56 Parameters, Improvements and Comparison 59 Parameters 59 Possible Improvements 60 Comparison with Other Protocols 60 Conclusion 60 References 61 Decoding One Out of Many 62 Introduction 62 The Decoding Problem in Cryptology 63 Generic Decoding Algorithms 63 Decoding One Out of Many Instances 64 A Generalized Information Set Decoding Algorithm 65 A Preview of the Analysis 66 Links With the Other Variants of Collision Decoding 66 Cost Estimation 67 Lower Bound 69 Some Numbers 69 Variations with the Parameter p 70 Decoding One Out of Many 70 Cost of Linear Algebra 71 Complexity Gain from Multiple Instances 72 Unlimited Number of Instances 74 Conclusion 76 References 77 On Provable Security of UOV and HFE Signature Schemes against Chosen-Message Attack 79 Introduction 79 Preliminaries 81 Existing Schemes and Their Analyses 82 UOV Signature Scheme 82 HFE Signature Scheme 84 Slightly Modified Schemes 86 Modified UOV Signature Scheme 86 Modified HFE Signature Scheme 88 Extension for HFEV Signature Scheme 90 Conclusions 90 References 90 Roots of Square: Cryptanalysis of Double-Layer Square and Square+ 94 Introduction 94 Achievement and Organisation 95 Notation 96 Double-Layer Square 97 MinRank Attack against Double-Layer Square 98 Square+ 101 Odd-Characteristic HFE Attack against Square+ 102 Solving MinRank for Square+ 104 Conclusion 106 References 107 An Efficient Attack on All Concrete KKS Proposals 109 Introduction 109 Terminology and Notation 111 The Kabatianskii-Krouk-Smeets Signature Scheme and Its Variant 111 Description of the Attack 112 An Auxiliary Code 113 Finding Low-Weight Codewords 114 Explaining the Success of the Attack 115 Exploiting a Signature for Extracting the Private Key 118 Analysis of the Attack 120 Preliminaries about Random Codes 120 Estimating the Complexity of Algorithm 1 122 Number of Operations of One Iteration 124 Experimental Results 124 Concluding Remarks 125 References 126 XMSS – A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions 128 Introduction 128 The eXtended Merkle Signature Scheme XMSS 129 Security 133 Forward Security 135 Efficiency 136 Implementation 137 References 139 On the Differential Security of Multivariate Public Key Cryptosystems 141 Introduction 141 Differential Symmetries and Invariants 142 Properties of General Linear Symmetries 144 Properties Relative to C* Monomials 145 Symmetries for Non-permutation Polynomials 147 Symmetries over Subspaces 147 Conclusion 152 References 152 Implementation of McEliece Based on Quasi-dyadic Goppa Codes for Embedded Devices 154 Introduction 154 Background on the McEliece Cryptosystem 155 Recommended Parameters and Key Sizes 156 Goppa Codes 156 Dyadic Goppa Codes 158 Quasi-Dyadic Goppa Codes 159 Scheme Definition of QD-McEliece 159 Parameter Choice and Key Sizes 161 Security of QD-McEliece 162 Conversions for CCA2-Secure McEliece Variants 162 Implementational Aspects 163 Field Arithmetic 163 Implementation of the QD-McEliece Variant 164 Implementation of the KIC- 167 Results 168 Conclusion and Further Research 171 References 172 Efficient Threshold Encryption from Lossy Trapdoor Functions 174 Introduction 174 Related Work 175 Our Contributions 175 Preliminaries 175 Tag-Based Encryption 176 Secret Sharing 177 Threshold Encryption 177 Strongly Unforgeable One-Time Signature 179 Main Construction 179 Proof of Lemma 2 181 Proof of Lemma 3 182 Selective-Tag CCA Secure TBE 182 Discussions and Comparisons 186 References 188 Monoidic Codes in Cryptography 190 Introduction 190 Coding Theory 192 Quasi-monoidic Codes 194 Monoidic Encryption and Signatures 199 McEliece Encryption Scheme 199 Parallel-CFS 200 Security Assessment 202 Parameters of Cryptographic Interest 203 Efficiency 204 References 205 Simplified High-Speed High-Distance List Decoding for Alternant Codes 211 Introduction 211 Review of Fast Arithmetic 213 Correcting Nearly $n$ Errors 215 Correcting Nearly $n$ Errors 220 Correcting More Errors 223 Application to Classical Goppa Codes 224 References 225 Statistical Decoding of Codes over Fq 228 Introduction 228 Preliminaries and Notation 229 Statistical Decoding 229 Binary Statistical Decoding 230 Statistical Decoding over Fq (for q > 2) 231 Exploiting Additional Structure 233 Experimental Results 234 Comparison with ISD 236 Conclusion 237 References 237 High-Speed Hardware Implementation of Rainbow Signature on FPGAs 239 Introduction 239 Background 241 Definitions 241 Overview of Rainbow Scheme 241 Proposed Hardware Design for Rainbow Signature 242 Overview of the Hardware Design 242 Choice of Irreducible Polynomial for the Finite Field 243 Efficient Design of Multiplication of Three Elements 243 Efficient Design of Partial Multiplicative Inversion 244 Optimized Gauss-Jordan Elimination 244 Designs of Affine Transformations and Polynomial Evaluations 249 Implementations and Experimental Results 250 Overview of Our Implementation 250 Implementation of Multiplier, Partial Inverter and LSEs Solver 251 Implementation of Transformations and Polynomial Evaluations 251 Comparison with Related Works 252 Conclusions 253 References 253 Wild McEliece Incognito 255 Introduction 255 An Extra Shield for Wild Goppa Codes 257 Attacks and Defenses 259 Challenges 260 Parameters 262 References 264 A New Spin on Quantum Cryptography: Avoiding Trapdoors and Embracing Public Keys 266 References 284 A Security Analysis of Uniformly-Layered Rainbow 286 Introduction 286 Birational Permutation Scheme 288 Attack against Birational Permutation Scheme 289 Sato-Araki Scheme 290 Attacks against Sato-Araki Scheme 290 Redefinition of HS Scheme 291 Non-commutative Rings 291 HS Scheme over L 292 Security Analysis of HS Scheme 293 Security against CSV Attack 293 Security against Coppersmith's First Attack 294 Security against Coppersmith's Second Attack 294 Reduction of HS Scheme to Rainbow 294 Original Rainbow and Its Analogue 294 Reduction of HS Scheme to Rainbow 296 Example of Reduction of HS Scheme 297 Security Analysis for Attacks against Rainbow 300 Efficiency of HS Scheme 301 Efficiency in the Case of Group Ring of Dihedral Group 302 Conclusion 302 References 303 Author Index 306 Front Matter....Pages - General Fault Attacks on Multivariate Public Key Cryptosystems....Pages 1-18 Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies....Pages 19-34 Full Cryptanalysis of the Chen Identification Protocol....Pages 35-50 Decoding One Out of Many....Pages 51-67 On Provable Security of UOV and HFE Signature Schemes against Chosen-Message Attack....Pages 68-82 Roots of Square: Cryptanalysis of Double-Layer Square and Square+....Pages 83-97 An Efficient Attack on All Concrete KKS Proposals....Pages 98-116 XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions....Pages 117-129 On the Differential Security of Multivariate Public Key Cryptosystems....Pages 130-142 Implementation of McEliece Based on Quasi-dyadic Goppa Codes for Embedded Devices....Pages 143-162 Efficient Threshold Encryption from Lossy Trapdoor Functions....Pages 163-178 Monoidic Codes in Cryptography....Pages 179-199 Simplified High-Speed High-Distance List Decoding for Alternant Codes....Pages 200-216 Statistical Decoding of Codes over $\mathbb{F}_q$ ....Pages 217-227 High-Speed Hardware Implementation of Rainbow Signature on FPGAs....Pages 228-243 Wild McEliece Incognito....Pages 244-254 A New Spin on Quantum Cryptography: Avoiding Trapdoors and Embracing Public Keys....Pages 255-274 A Security Analysis of Uniformly-Layered Rainbow....Pages 275-294 Back Matter....Pages -