Topics in Cryptology -- CT-RSA 2003: The Cryptographers' Track at the RSA Conference 2003, San Francisco, CA, USA April 13-17, 2003, Proceedings (Lecture Notes in Computer Science, 2612)

These are the proceedings of CT-RSA 2003, the Cryptographers’ Track at RSA Conference 2003. The proceedings of CT-RSA 2001 and CT-RSA 2002 were published in Springer-Verlag’s Lecture Notes in Computer Science series as LNCS 2020 and LNCS 2271, respectively. The Cryptographers’ Track is one of the many parallel tracks of the RSA Conference. With many thousands of participants, the RSA Conference is the largest security and cryptography event of the year. There were 97 submitted contributions this year, of which 26, or 27%, were selected for presentation. The program also included two invited talks by Tom Berson (“Cryptography After the Bubble: How to Make an Impact on the World”) and by Adi Shamir (“RSA Shortcuts”). All submissions were reviewed by at least three members of the program committee. I am very grateful to the 21 members of the program committee for their hard and e?cient work in assembling the program. My thanks also go to the 78 external referees who helped in the review process in their area of exp- tise: Gail-Joon Ahn, Toru Akishita, Kazumaro Aoki, Gildas Avoine, Joonsang Baek, Olivier Benoit, Alex Biryukov, Alexandra Boldyreva, Antoon Bosselaers, Emmanuel Bresson, Eric Brier, Brice Canvel, Dario Catalano, Chien Yuan Chen, Donghyeon Cheon, Jung Hee Cheon, Olivier Chevassut, Kilsoo Chun, Mathieu Ciet, Christophe Clavier, Jean-S ́ebastien Coron, Reza Curtmola, Christophe De Canni`ere, Jean-Fran ̧cois Dhem, Xuhua Ding, Pierre-Alain Fouque, Jacques Fournier, Fabien Germain, Jovan Dj. Goli ́c, Philippe Golle, Louis Granboulan, Jorge Guajardo, D. J. Topics in Cryptology – CT-RSA 2003 Preface Organization Table of Contents Forward-Security in Private-Key Cryptography Introduction Forward-Secure Pseudorandom Bit Generators Standard Pseudorandom Bit Generators Forward-Secure Pseudorandom Bit Generators Alleged-RC4 Is Not Forward-Secure A Construction Based on Standard Generators A Construction Based on PRFs Number-Theoretic Constructions Forward-Secure Message Authentication Message Authentication Schemes Forward-Secure Message Authentication Schemes A General Construction Forward-Secure Audit Logs References Intrusion-Resilient Public-Key Encryption Introduction Our Contributions Definitions and Preliminaries Functional Specification Definition of Security Cryptographic Assumptions Construction Scheme Intuition Formal Description Efficiency Extensions Security of Our Scheme Security against Adaptive Chosen-Ciphertext Attacks TMAC: Two-Key CBC MAC Introduction Background Our Contribution Other Related Works Preliminaries Notation CBC MAC The Field with 2^n Points Basic Construction Universal Hash Functions TMAC-Family Comparison with XCBC Proposed Specification User Option Comparison with XCBC Security of TMAC-Family Security Definitions Theorem Statements Proof of Lemma 5.1 Discussion Advantages Limitations Conclusion Proof of Lemma 5.2 Montgomery Prime Hashing for Message Authentication Introduction Definition Form the Padded Message Compute the MPH Hash Compute the Hash Tag Encrypt the Hash Tag Implementation Considerations Security Bound Modulus Selection Definition of SQ Algorithm Uniformity Run Time Use with Key Agreement Schemes Nonuniform Distributions A MPH-MAC Example B Calculating N_\Omega C Calculating q_l D MR Iterations An Analysis of Proxy Signatures: Is a Secure Channel Necessary? Introduction The MUO Scheme and Its Analysis The PH Scheme and Its Analysis The KPW Scheme and Its Analysis The LKK Scheme and Its Analysis Comparison and Revisions Revision of the MUO Scheme Revision of the LKK Scheme Conclusion Invisibility and Anonymity of Undeniable and Confirmer Signatures Introduction Plan of the Paper Undeniable and Confirmer Signature Schemes Generalised Invisibility Anonymity Undeniable Signatures Based on RSA Attacks on Invisibility and Anonymity Preventing the Jacobi Symbols Attack Ensuring that Signature Length Does Not Reveal the Signer The New RSA-Based Scheme Invisibility of Revised RSA-Based Undeniable and Confirmer Signatures Anonymity between Signatures of Different Schemes A Proofs of Theorems 1 and 2 B Proof of Theorem 5 C Other Security Properties C.1 Unforgeability C.2 Convertibility A Secure Signature Scheme from Bilinear Maps Introduction Mappings with Algebraic Properties Security for Signature Schemes Previous Work The New Signature Scheme Concrete Signature Scheme Conclusion Access Control Using Pairing Based Cryptography Introduction Notation Access Control Based on Knowing a Secret Key Describing Access Control Policies Encryption Procedure Decryption Procedure Minimizing the Bandwidth Conclusion NTRUSign: Digital Signatures Using the NTRU Lattice Introduction NTRUSign: An Engineering Specification A View of NTRU: Background Mathematics NTRUSign Key Generation Completing the Basis Finding a Good Second Half for the Basis The Transpose NTRU Lattice Signing and Verification Reviewed The Case of No Perturbations (B=0) Perturbation Techniques NTRUSign with Perturbations Security against a Transcriptless Adversary Security of Private Keys Security against Forgery Transcript Leakage The Security of appr-CVP Based Signature Schemes Transcript Leakage by NTRUSign Conclusions and Open Problems Further Analysis of NTRU Algebra Security against Forgeries Further Transcript Analysis Experiments Hash Function Considerations Performance About the XL Algorithm over GF(2) Introduction Common Conventions and Notations The Basic Principle of XL The Necessary Condition for XL to Work An Evaluation for GF(2) General Theory and Moh's Comments on XL Our Computer Simulations The Behaviour of XL for D=3 The Behaviour of XL for D=4 The Behaviour of XL for D=5 The Behaviour of XL for D=6 Our Results on XL over GF(2) The Asymptotic Behaviour of XL Improved Versions of XL: FXL, XL' and XL2 The FXL Algorithm The XL' Algorithm The XL2 Algorithm Asymptotic Complexity of FXL, XL' and XL2 Conclusion An Evaluation of the Complexity of XL for D