Public Key Cryptography - PKC 2003: 6th International Workshop on Theory and Practice in Public Key Cryptography, Miami, FL, USA, January 6-8, 2003, ... (Lecture Notes in Computer Science, 2567)

PKC 2003 was the Sixth International Workshop on Practice and Theory in Public Key Cryptography and was sponsored by IACR, the International As- ciation for Cryptologic Research (www.iacr.org). This year the workshop was organized in cooperation with the Department of Computer Science, Florida State University. The General Chair, Mike Burmester was responsible for local organization, registration, etc. There were 105 submitted papers which were considered by the Program Committee. This is an increase of 52% compared to PKC 2002, which took place in Paris, France, February 2002, and which was incorrectly identi?ed on the cover of the proceedings as being the fourth workshop. Due to the large number of submissions, some papers that contained new ideas had to be rejected. Priority was given to novel papers. Of the 105 submissions, 26 were selected for the proceedings. These contain the revised versions of the accepted papers. Each paper was sent to at least 3 members of the program committee for comments. Revisions were not checked for correctness of their scienti?c aspects and the authors bear full responsibility for the contents of their papers. Some authors will write ?nal versions of their papers for publication in refereed journals. I am very grateful to the members of the Program Committee for their hard work in the di?cult task of selecting roughly 1 out of 4 of the submitted papers. Lecture Notes in Computer Science Springer Public Key Cryptography PKC 2003 Preface PKC 2003 Sixth International Workshop on Practice and Theory in Public Key Cryptography Table of Contents Diffie-Hellman Based Schemes Threshold Cryptography Reduction Proofs Broadcast and Tracing Digital Signatures Specialized Multiparty Cryptography Cryptanalysis I Elliptic Curves: Implementation Attacks Implementation and Hardware Issues New Public Key Schemes Elliptic Curves: General Issues Cryptanalysis II Efficient Construction of (Distributed) Verifiable Random Functions Introduction Definitions Verifiable Random Functions and Friends Diffie-Hellman Assumptions Constructions Building PRFs Building VRFs Distributed VRF Acknowledgments References An Identity-Based Signature from Gap Diffie-Hellman Groups Introduction Our Identity-Based Signature Scheme Gap Diffie-Hellman (GDH) Groups Computation Diffie-Hellman Problem (CDHP) Decisional Diffie-Hellman Problem (DDHP) The Scheme Setup Extract Sign Verify Relationship with BF-IBE GDH Parameter Generator Gap Diffie-Hellman Assumption A Variant of Setup Security Proof Attack Model for ID-based Signature Schemes Our Signature Scheme and CDHP Implementation Issues Bilinear Maps Hash Functions Performance Conclusion Acknowledgements References Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme Introduction Background Robust Proactive Threshold GDH Signature Scheme The GDH Multisignature Scheme The Blind GDH Signature Scheme Acknowledgements References An Efficient Two-Party Public Key Cryptosystem Secure against Adaptive Chosen Ciphertext Attack Introduction Related Work Preliminaries Definition and Basic Theory of Σ-Protocols S-CS System Decryption Protocol Security for S-CS References On the Bit Security of NTRUEncrypt Introduction Preliminaries Main Results Concluding Remarks and Open Questions References Equivalence between Semantic Security and Indistinguishability against Chosen Ciphertext Attacks Introduction Preliminaries A New Security Notion: Non-dividability Equivalence among ND-ATK, SS-ATK and IND-ATK Conclusion Acknowledgement References Randomness Re-use in Multi-recipient Encryption Schemeas Introduction Definitions Not Every SRS Scheme is Secure Security of Multi-recipient Schemes Reproducibility Test and Theorem Analysis of Specific Schemes Acknowledgements References Public Key Trace and Revoke Scheme Secure against Adaptive Chosen Ciphertext Attack Introduction Notations and Basic Facts Definition of Broadcast Encryption Scheme Security of Revocation Revocation Schemes z-Resilience against CPA Attack z-Resilience against gCCA2 Attack z-Resilience against CCA2 Attack Acknowledgments References The Cramer-Shoup Strong-RSA Signature Scheme Revisited Introduction A Modification of the Cramer-Shoup Protocol Original Cramer-Shoup Signature Scheme Key Generation Signing Verification Modified Cramer-Shoup Signature Scheme Key Generation Signing Verification Performance Comparison Security Proof Efficient Stateful Signatures Description Key Generation Signing Verification Performance Comparison Security Proof "Lightweight'' Anonymous Group Identification Description Security Acknowledgments References Strong Key-Insulated Signature Schemes Introduction Overview of the model Our contributions Related work The Model Basic key insulation Secure key updates Strong key insulation Generic, Perfectly Key-Insulated Signature Scheme (t, N)-Key Insulation under the DLA Perfectly Key-Insulated Signature Schemes Relation to Identity-Based Signature Schemes References A Verifiable Secret Shuffle of Homomorphic Encryptions Introduction Homomorphic Commitments and Encryption Commitments Homomorphic property Root opening Few polynomial roots Multicommitments Encryptions Compatibility of Commitments, Multicommitments and Encryptions Proof of a Shuffle of Known Contents Proof of commitments containing a shuffle of known contents Initial challenge Multiplication Proof Proof of a Shuffle Proof of shuffle of ciphertexts Initial message First challenge First answer Speed, Space and Tricks References Round-Optimal Contributory Conference Key Agreement Introduction Related Work Protocols of Tzeng and Tzeng Outline of Paper Communications Model Security Secure Encryption Schemes Secure Signature Scheme The Protocol Security Proof Signature Forger Encryption Attacker Conclusion References Attack on Tzeng and Tzeng's Second Protocol Security Analysis of the MOR Cryptosystem Introduction Framework and Definitions The MOR System MOR Using SL(2, ZZ_p) x_θ ZZ_p Attacking MOR Using SL(2, ZZ_p) x_θ ZZ_p MOR Using SL(2, ZZ_p) x_θ ZZ_p is not Harder than MOR Using SL(2, ZZ_p) Ciphertext-Only Attacks with Known Centralizer Elements Attacks when Exponents are Used Multiple Times Attack with Known Centralizer Attack without Centralizer Elements Conclusion References General Results for Matrix Groups Computing Centralizers in GL(2, ZZ_p) The Conjugacy Problem in GL(2, ZZ_p) and SL(2, ZZ_p) A Practical Attack on Some Braid Group Based Cryptographic Primitives Introduction Braid Groups The Δ-Normal Form The Conjugacy Problem in B_n A Heuristic Approach to the Conjugacy Problem The Algorithm Discussion of the Algorithm The Multiple Simultaneous Conjugacy Problem Braid Groups in Cryptography Commutator Based Key Agreement Protocol Public information Private key Public key Shared key A Diffie-Hellman Type Key Agreement Protocol and a Public Key Cryptosystem Public information Private key Public key Shared key Conclusion References A Refined Power-Analysis Attack on Elliptic Curve Cryptosystems Introduction Mathematical Background Parametrizations of Elliptic Curves General (affine) Weierstraß Form Projective Coordinates Simplified (affine) Weierstraß Forms Montgomery Form Hessian Form Usual SPA Countermeasures Classical Binary Method Algorithm 1 Binary method (from the most significant bit) Algorithm 2 Double-and-add-always (from the most significant bit) Algorithm 3 Montgomery’s method Our New Power Analysis Attack The Strategy of the Attack Application to Three Usual DPA-Countermeasures Practical Applications Computation of the "Special'' Point Cardinality of the Elliptic Curve Conclusion References Validation of Elliptic Curve Public Keys Introduction Elliptic Curve Cryptographic Schemes One-Pass ECDH ECIES One-Pass ECMQV ECDSA Public Key Validation Invalid-Curve Attacks Invalid-Curve Attack on One-Pass ECDH Invalid-Curve Attack on ECIES Invalid-Curve Attack on One-Pass ECMQV Analysis Invalid-Curve Attack on a Key Agreement Protocol Proposed to IEEE 802.15 Preventing Invalid-Curve Attacks Conclusions References Exceptional Procedure Attack on Elliptic Curve Cryptosystems Introduction Elliptic Curves Standard Addition Formula Coordinate System Scalar Multiplication Exceptional Procedure Attack Basic Idea Exceptional Procedure in Standard Formula Exceptional Procedure Attack against Standard Formula Relation to Other Attacks Brier-Joye's Addition Formula Brier-Joye's Addition Formula Exceptional Procedure in Brier-Joye's Formula Finding Collision Points Self-Collision Polynomial Attack to the ElGamal-Type Encryption Concluding Remarks Acknowledgments References Numerical Examples Self-Collision Points Self-Collision Polynomial fm(x) Proof of Proposition 3 On Montgomery-Like Representations for Elliptic Curves over GF(2^k) Introduction Elliptic Curves over F_2^k Curve Definition Curve Arithmetic Exponentiation (or Scalar Multiplication) The Montgomery Representation Additive Montgomery Formulae Multiplicative Montgomery Formulae Recovery of the y-Coordinate Exponentiation, Aka Scalar Multiplication Lucas Chains The Binary Algorithm Single Exponentiation Double Exponentiation Montgomery's Euclidean Algorithm Double Exponentiation Single Exponentiation without Precomputation Twofold Exponentiation Summary Conclusion Acknowledgements References A Dedicated Sieving Hardware Introduction The Sieving Step in the NFS Algebraic Side Rational Side A Sieving Device Schimmler's Sorting Algorithm left-to-right right-to-lef snakelike Sieving with a Fast Sorting Hardware The Sieving Algorithm Hardware Requirements Performance Handling Small Primes and Testing Smoothness Improvements and Further Work Conclusions Acknowledgement References A Fast and Secure Implementation of Sflash Introduction Structure of the Smart Card Basis Structures and Variables Used in Sflash Main Structures The Private Key of Sflash Fast Implementation of the Operations over the Fields The Implementation of K How to Compute A=f^-1(B) in Sflash ? Special Operations Involved in the Computation of f^-1: The Performance Data Protecting Sflash against Side-Channel Attacks Protecting against SPA-Like Attacks Protecting against DPA-Like Attacks Algorithmic Considerations Computations Added Compared to an Unprotected Version Digital Signatures on a Smart Card -- a Comparison Conclusion References A Practical Public Key Cryptosystem from Paillier and Rabin Schemes Introduction Our Results Some Previous Schemes and Related Trapdoor Permutations Rabin Function Blum-Williams Function Rabin-Williams Function RSA-Paillier Function New Trapdoor Permutation Based on Factoring A New Trapdoor Permutation The New Scheme Key Generation Encryption Decryption Security Analysis One-Wayness Semantic Security Acknowledgements References A Lattice Based Public Key Cryptosystem Using Polynomial Representations Introduction Description of the GGH System The GGH System Why Is |det(T)|=1 Needed? Lattice Generated by Representations of Polynomial Rings Representation of a Polynomial Ring Direct Applications of Polynomial Representations Cryptosystem : Scheme I Key Generation Encryption and Decryption Security Other Representations Conclusion References Appendix A : Scheme II Appendix B : IND-CCA2 Appendix C : Experimental Results The Security of DSA and ECDSA Bypassing the Standard Elliptic Curve Certification Scheme DSA and ECDSA Public Parameters Secret Key Public Key Dedicated Attacks Signature Manipulation in ECDSA Bleichenbacher Attack against the Pseudorandom Generator Restart Attack Parameter Validation Public Keys Certificate p and q Validation g Validation Provable Security Necessary Conditions Brickell Model Pointcheval-Vaudenay Model Brown Model Elliptic Curve Validation Elliptic Curves with Same j-Invariant Bypassing the Scheme in the Characteristic Two Case Prime Fields Case A Possible Tweak for ECDSA Curves over Fp with p > 3 Prime Curves over Fq of Characteristic 2 Conclusion Acknowledgments References Number of Field Representations Side-Channel Attacks on Textbook RSA and ElGamal Encryption Introduction Decryption Oracles Notation Modeling the Oracles Attacking the LSB-Oracle Attacking the MSB-Oracle Attacking the Size-Checking Oracle Selection of Parameters Improvements Attacking ElGamal Encryption Practical Impact HBCI OSCI Early Version of PEM Conclusion Acknowledgment References On the Security of HFE, HFEv- and Quartz Introduction Notations Known Attacks on HFE and Its Variants Attacks on ”Basic HFE” State of the Art on the Modified Versions of HFE General Methods for Solving Systems of Multivariate Polynomial Equations Solving Systems with Gröbner Bases Algorithms The Special Case of Signing Applying Gröbner Bases to HFE Our Methodology Critical Parameters for Quartz The Simulations on HFEv- Randomness ~ Security The Impact of the Perturbations "Vinegar" and "Minus" Some Conclusions for Quartz Quantitative Effect of "Vinegar" and "Minus" Our Estimation of the Security of Quartz Attacks on the Internal Sub-Component HFE Including the Conjectured Effects of the Perturbations Our Estimation of the Security of Quartz Remark Is It Necessary to Repair Quartz? The Speed of Quartz Conclusion References Generic Attacks and the Security of Quartz Introduction Multivariate Quadratic Trapdoor Functions Feistel-Patarin Construction Generic Threats Remark Removing Existential Forgeries Security Remark Extending to any Number of Inverses Extending to m = n The Signature Length Is It Possible to Prove the Security of Quartz ? Conclusion References Black-Box Reductions For No-Message Attacks The Black-Box Reduction Security Arguments Assumption A.2.1 (Super-Strong One-Wayness of HFEv-) Theorem A.2.2 Corollary A.2.3 Applications, K=1, Consequences on Flash and Sflash Corollary A.3.1 (Exact Security of Flash and Sflash) Applications with K ≥ 2, Differential Signature Scheme Differential Signatures Corollary A.4.1 Application to Quartz and Similar Schemes Chosen-Message Security Author Index

This book constitutes the refereed proceedings of the 6th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2003, held in Miami, Florida, USA in January 2003.

The 26 revised full papers presented were carefully reviewed and selected from 105 submissions. The papers are organized in topical sections on Diffie-Hellman based schemes, threshold cryptography, reduction proofs, broadcast and tracing, digital signatures, specialized multiparty cryptography, cryptanalysis, elliptic curves: implementation attacks, implementation and hardware issues, new public key schemes, and elliptic curves: general issues.