Progress in Cryptology - INDOCRYPT 2000: First International Conference in Cryptology in India, Calcutta, India, December 10-13, 2000. Proceedings (Lecture Notes in Computer Science, 1977)

✍ Scribed by Bimal Kumar Roy (editor), Eiji Okamoto (editor)

• Publisher: Springer
• Year: 2000
• Tongue: English
• Leaves: 306
• Category: Library

✦ Synopsis

The field of Cryptology witnessed a revolution in the late seventies. Since then it has been expanded into an important and exciting area of research. Over the last two decades, India neither participated actively nor did it contribute sig­ nificantly towards the development in this field. However, recently a number of active research groups engaged in important research and developmental work have crystalized in different parts of India. As a result, their interaction with the international crypto community has become necessary. With this backdrop, it was proposed that a conference on cryptology - INDOCRYPT, be organized for the first time in India. The Indian Statistical Institute was instrumental in hosting this conference. INDOCRYPT has generated a large amount of enthu­ siasm amongst the Indians as well as the International crypto communities. An INDOCRYPT steering committee has been formed and the committee has plans to make INDOCRYPT an annual event. For INDOCRYPT 2000, the program committee considered a total of 54 pa­ pers and out of these 25 were selected for presentation. The conference program also included two invited lectures by Prof. Adi Shamir and Prof. Eli Biham. These proceedings include the revised versions of the 25 papers accepted by the program committee. These papers were selected from all the submissions based on originality, quality and relevance to the field of Cryptology. Revisions were not checked and the authors bear the full responsibility for the contents of the papers in these proceedings.

✦ Table of Contents

Lecture Notes in Computer Science 1977
Progress in Cryptology – INDOCRYPT 2000
Preface
Program Co-chairs
Organizing Committee
Table of Contents
The Correlation of a Boolean Function with Its Variables
Introduction
Some Lemmas
Case of 1 <= k <= 4
Case of 5 <= k <= 8
On Choice of Connection-Polynomials for LFSR-Based Stream Ciphers
Introduction
Some Results on Sparse-Multiples of Polynomials
On Trinomial Multiples
On 4-nomial Multiples
On Degrees of Sparse-Multiples of Primitive-Polynomials
Conclusions
On Resilient Boolean Functions with Maximal Possible Nonlinearity
Introduction
Preliminary Concepts and Notions
Upper Bound for the Nonlinearity of Resilient Functions
On Linear and Quasilinear Variables
A Method of Constructing
Optimization of Siegenthaler's Inequality for Each Individual Variable
Decimation Attack of Stream Ciphers
Introduction
Decimation of LFSR Sequences
The Decimation Attack
Description of the Algorithm
Simulation Results
Decimation Attack Resistance Criterion
Comparison with Previous Known Attacks
Canteaut and Trabbia Attack
Chepyzhov, Johansson and Smeets Attack
Cryptanalysis of the A5/1 GSM Stream Cipher
Introduction
A Description of A5/1
Previous Work
Our Basic Attack
Trick or Treat?
Summary
Acknowledgments
On Bias Estimation in Linear Cryptanalysis
Introduction
Experiments with RC5
Experiments with Feistel Ciphers
Design
Approximations with Single Active S-Box
Approximations with Multiple S-Box
Approximations with Expansion
Other Approximations
Discussion on the Results
Stabilization of the Bias
Alternative Methods for Bias Estimation
Correlation Matrices
Linear Hulls and Correlation Matrices
Estimation by Sampling
Conclusions
Chabaud-Vaudenay Theorem on Max. Non-Linearity
Fundamental Theorem of Linear Hulls
On the Incomparability of Entropy and Marginal Guesswork in Brute-Force Attacks
Introduction
Preliminaries
Entropy: The Uncertainty of Description
Marginal Guesswork: The Uncertainty of Searching
When Marginal Guesswork and Exponentiated Entropy Agree
The Main Result
Discussion: Shannon's Axioms
Improved Impossible Differentials on Twofish
Introduction
The 6-Round Attack on Twofish with 128-bit Keys
Ferguson's Analysis
Our Analysis
The 6-Round Attacks on Twofish with 192-bit and 256-bit Keys
192-bit Keys
256-bit Keys
The 7-Round Known Plaintext Attacks on Twofish with 192-bit and 256-bit Keys
192-bit Keys
256-bit Keys
The Subkey Computation in a Unit of Time
An Online, Transferable E-Cash Payment System
Introduction
The e-Payment System
Setup and Notations
Coin Exchange Protocol
Withdrawal/Deposit Protocols
Resolution Protocol
Features
Anonymity
Fairness
Transferability
Extensions/Optimizations
Payment with Multiple Coins
Fungibility
Organization of Verifying Authority
Conclusions
Anonymity Control in Multi-bank E-Cash System
Introduction
Signatures of Knowledge
A Generic Fair Off-Line Electronic Cash System in the Multiple Bank Model
System Setup and Making Subprotocol
Procedure to Construct the Generic Fair Cash System
The Implementation of the Generic Fair Electronic Cash System in the Multiple Bank Model
System Setup
The Protocol W
The Withdrawal Protocol
The Payment Protocol
Anonymity Revocation
Efficiency and Security
Conclusion
Efficient Asynchronous Secure Multiparty Distributed Computation
Introduction
Towards Efficient Asynchronous Secure Protocols
The Protocol Construction
Agreement on a Common Subset
Input Sharing and Output Reconstruction
Linear Combination and Multiplication
Degree Reduction
Segment Fault Localization
The Top-Level Protocol
Complexity Analysis of our Protocol
Conclusions
Tolerating Generalized Mobile Adversaries in Secure Multiparty Computation
Introduction
Contributions of this Paper
The Approach
Non-threshold Proactive (Verifiable) Secret Sharing
Initial Secret Sharing
Non-Threshold Proactive Verifiable Secret Sharing: The Combined Protocol
Secure Multiparty Computation
Conclusion
Codes Identifying Bad Signatures in Batches
Introduction
Background
The Model
Properties of Id-Codes
Constructions of Id-Codes
Hierarchical Identification
Hierarchical Identification with Infinite F
Hierarchical Batching with a Single IC(v,t)
Conclusions
Distributed Signcryption
Introduction
Preliminaries
Digital Signcryption
ElGamal Encryption Scheme
Distributed Encryption
Construction of A Group
Distributed Encryption
Distributed Signcryption
Extension
The Protocol
Conclusion
Fail-Stop Signature for Long Messages (Extended Abstract)
Introduction
Preliminaries
Fail-Stop Signature Schemes
Authentication Codes
Construction of FSS from Linear A-Codes
Construction of Linear A-Codes
Efficiency Measures of FSS Schemes
Conclusion
Power Analysis Breaks Elliptic Curve Cryptosystems Even Secure against the Timing Attack
Introduction
Recent Works for Protecting against Power Attacks on ECC
Our Contributions
Applied Elliptic Curve Cryptosystems without the y-Coordinate
Power Attacks
Power Analysis Attacks on Known ECC-Schemes
The Point of DPA Attack
Analysis of Montgomery-Variants
Our Proposed Implementation
Analysis of the Security
Analysis of the Efficiency
Performance of Our Proposed Implementation
Comparison to Other Algorithms
Efficient Construction of Cryptographically Strong Elliptic Curves
Introduction
Cryptographically Strong Elliptic Curves
The Algorithm
Examples and Running Times
High-Speed Software Multiplication in 2m
Introduction
Polynomial Basis Representation
The ``Shift-and-Add'' Method
Proposed Method
Performance Comparison
Timings
Applications
Conclusions
Acknowledgments
On Efficient Normal Basis Multiplication
Introduction
Preliminaries
Normal Basis Representation
Normal Basis Multiplication
A New Multiplication Algorithm
Type-I Optimal Normal Basis Multiplication
Composite Field Multiplication Algorithm
Concluding Remarks
Symmetrically Private Information Retrieval (Extended Abstract)
Introduction
Preliminaries
The Basic Scheme
Iterative Bit SPIR Scheme
Block Retrieval SPIR Scheme
Conclusion
Two-Pass Authenticated Key Agreement Protocol with Key Confirmation
Introduction
AK Protocols
MTI/A0
Two-Pass Unified Model
Two-Pass MQV
New Key Agreement Protocols
AK Protocol
AKC Protocol
Two-Pass Unilateral AKC Protocol
Comparison
Concluding Remarks
Anonymous Traceability Schemes with Unconditional Security
Introduction
Preliminaries
A3-Codes
Asymmetric Tracing
Anonymous Tracing
A Coin System
Construction of Coins
Security of Coins
The Number of Coins under One Registration
Anonymity and Unlinkability
An Example
Conclusions
New Block Cipher DONUT Using Pairwise Perfect Decorrelation
Introduction
Preliminaries
Frame Structure
Frame Structure of New Cipher
Security of Frame Structure
New Block Cipher DONUT
Structure
Efficient Implementation
Conclusion
Generating RSA Keys on a Handheld Using an Untrusted Server
Introduction
Timing Cryptographic Primitives on the PalmPilot
Preliminaries
Overview of RSA Key Generation
Unbalanced RSA Keys
Generating an Unbalanced RSA Key with the Help of Untrusted Servers
Generating Keys with the Help of Two Servers
Generating Keys with the Help of a Single Server
Generating Standard RSA Keys
Experiments and Implementation Details
Experiments
Conclusions
A Generalized Takagi-Cryptosystem with a Modulus of the Form prqs
Introduction
Our Result
Description of the Proposed Cryptosystem
Key Generation
Encryption
Decryption
The Efficiency of the Proposed Cryptosystem
The Complexity of the Decryption
The Security of the Proposed System
Factorization of n=pr qr+1
Proper Choices for r in n=pr qr+1 to Defeat LFM
Optimal Number of Prime Factors of n to Defeat Both of ECM and NFS
Choices for t=r+s for n=prqs That Gives the Same Security as the Given RSA Modulus N
Conclusion
Author Index
Author Index