Progress in Cryptology – INDOCRYPT 2007: 8th International Conference on Cryptology in India, Chennai, India, December 9-13, 2007, Proceedings (Lecture Notes in Computer Science, 4859)

✍ Scribed by K. Srinathan (editor), C. Pandu Rangan (editor), Moti Yung (editor)

• Publisher: Springer
• Year: 2007
• Tongue: English
• Leaves: 437
• Category: Library

✦ Synopsis

This book constitutes the refereed proceedings of the 8th International Conference on Cryptology in India, INDOCRYPT 2007, held in Chennai, India, in December 2007. The papers and three invited lectures were carefully reviewed and selected. The papers are organized in topical sections on hashing, elliptic curve, cryptoanalysis, information theoretic security, elliptic curve cryptography, signature, side channel attack, symmetric cryptosystem, asymmetric cryptosystem, and short papers.

✦ Table of Contents

Title Page
Preface
Organization
Table of Contents
Linearization Attacks Against Syndrome Based Hashes
Introduction
The FSB Compression Function
Linearization Attack
The Selection of Alphabet in a Preimage Attack
Invertibility of Random Binary Matrices
Finding Collisions When $r$ = 2$w$
Larger Alphabets
Pre-image Search
Collision Search
Conclusions
Appendix: A Collision and Pre-image Example
A Meet-in-the-Middle Collision Attack Against the New FORK-256
Introduction
Description of New FORK-256
Observations
A Collision Attack
First Phase
Second Phase
Runtime Analysis
Further Work
Conclusion
Multilane HMAC— Security beyond the Birthday Limit
Introduction
Preliminaries
General Framework
Two-Lane NMAC
$L$-Lane NMAC (L \geq 3)
$L$-Lane HMAC
Performance Issues
Concluding Comments
On the Bits of Elliptic Curve Diffie-Hellman Keys
Introduction
Preliminaries
Partial Diffie-Hellman Bits
Algebraic Case with Low Degree Extensions
Elliptic Curves over Finite Field Extensions of Degree 2
Elliptic Curves over Extensions of Degree 3
Elliptic Curves over $\F_{q}$
Analytic Case
Our Conjecture on Character Sums
Relationship to an Error-Correcting Code
Proof of Our Conjecture on Average
Expander Graphs and Character Sums
Constructing the Graph $G_E$ and the Subgraph G'
Distributional Properties
A Result on the Distribution of Quadratic Residues with Applications to Elliptic Curve Cryptography
Introduction
El-Gamal Cryptosystem
Previous Results
Main Result
Proof of the Main Result
A Modified ECC
Key Generation
Encryption
Decryption
Randomizing the Distribution of Quadratic Residues in a Finite Field
Weil's Theorem
Related-Key Attacks on the Py-Family of Ciphers and an Approach to Repair the Weaknesses
Introduction
Description of the Stream Ciphers TPypy, TPy, Pypy and Py
Notation and Convention
Related-Key Weaknesses in the Py-Family of Ciphers
Propagation of the Weaknesses Through the Key Setup Algorithm
Propagation of the Weaknesses Through the IV Setup
Propagation of the Weaknesses Through the Round Function
The Distinguisher
Attacks with Shorter Keys
New Stream Ciphers -- RCR-32 and RCR-64
Security Analysis
Future Work and Conclusion
Related-Key Differential-Linear Attacks on Reduced AES-192
Introduction
Differential-Linear Cryptanalysis
Description of AES
Notations
A 5-Round Related-Key Differential-Linear Distinguisher
Attacking 7-Round
The Attack Procedure
Analysis of the Attack Complexity
Attacking 8-Round
Analysis of the Attack Complexity
Another Attack on 7-Round AES-192
Summary
Improved Meet-in-the-Middle Attacks on Reduced-Round DES
Introduction
Description of DES
An Alternative Description of DES and Notations Used
Meet-in-the-Middle Attack on 4-Round DES
A Meet-in-the-Middle Attack with One Known Plaintext
Using Multiple Known Plaintexts
Using Chosen Ciphertexts
Attack on 5-Round DES
Using Chosen Plaintexts
Attack on 6-Round DES
Conclusions and Open Problems
Probabilistic Perfectly Reliable and Secure Message Transmission – Possibility, Feasibility and Optimality
Introduction
Our Contribution
Network Model
Probabilistic Perfectly Reliable Message Transmission
Characterization for PPRMT
Lower Bound on Communication Complexity of Single Phase PPRMT Protocol
Single Phase Bit Optimal PPRMT Protocol
Multiphase PPSMT Protocol in Undirected Networks
Characterization for Multiphase PPSMT Protocol
Lower Bound on Communication Complexity of Multiphase PPSMT Protocol
Constant Phase Bit Optimal PPSMT Protocol
Conclusion
SECRET SWARM UNIT Reactive $k$−Secret Sharing (Extended Abstract)
Introduction
Swarm Settings
Reactive $k$-Secret Counting -- The Chinese Remainder Solution
Reactive $k$-Secret -- Counting/Multiplying Polynomial-Based Solution
Virtual Automaton
Conclusions
New Formulae for Efficient Elliptic Curve Arithmetic
Introduction
New Doubling Formulae
New Tripling Formulae
Mixed-Addition for Modified Jacobi-Quartic Coordinates
Alternative Base Points
Conclusion
A Graph Theoretic Analysis of Double Base Number Systems
Introduction
Background: Double Base Number System
Graphical Representation of Numbers: The DBNS Graphs
Some Special DBNS-Graphs
Operations on DBNS-Graphs
Generalization to More Than 2 Bases
A Partition of $S_n$
Integer Arithmetic Using DBNS-Graphs
Conclusion
Optimizing Double-Base Elliptic-Curve Single-Scalar Multiplication
Introduction
Edwards Curves
Fast Addition on Elliptic Curves
Background: Double-Base Chains for Single-Scalar Multiplication
New Results
Appendix: Quintupling on Edwards Curves
Transitive Signatures from Braid Groups
Introduction
Primitive of Transitive Signature and Related Constructions
Background of Braid-Based Public Key Cryptography
Contributions and Organizations
Preliminaries
Braid Group and Related Cryptographic Assumptions
Notations and Definitions
Transitive Signatures from Braid Groups
Security Level, Performance Evaluation and Parameters Suggestion
Conclusions
Proxy Re-signature Schemes Without Random Oracles
Introduction
Our Contribution
Paper Organization
Definitions
Bidirectional Proxy Re-signature
Bidirectional ID-Based Proxy Re-signature
Bilinear Maps
The Computational Diffie-Hellman Assumption (CDH)
Bidirectional Proxy Re-signature Schemes
$S_{mb}$: Multi-use $B$idirectional Scheme
$S_{id-mb}$: $ID$-Based $M$ulti-use $B$idirectional Scheme
Conclusions
First-Order Differential Power Analysis on the Duplication Method
Introduction
The Duplication Method
An Analytical Canvas for DPA Attacks
First-Order DPA Attacks
Soundness of a First-Order DPA Attack
Zero Attack When $\varphi$ Is Variable
Attack When $\varphi$ Is Constant
Countermeasures
Conclusion
Proofs
Proof of Proposition 2
Proof of Proposition 3
Solving Discrete Logarithms from Partial Knowledge of the Key
Introduction
Background
Generic Algorithms for Solving DLP
Side Channel Attacks
Scenario I -- Contiguous Bits of the Key Is Revealed
Case III -- Middle Part
Scenario II -- Partial Information About the Square and Multiply Chain Is Revealed
Concluding Remarks
Case I -- Left Part
Case II -- Right Part
Solving the Diophantine Equation
Computing $r$ and $k$
New Description of SMS4 by an Embedding over GF(2^8)
Introduction
Notation
A Brief Description of SMS4
An Extended Cipher of SMS4
Extension Maps
The ESMS4 Cipher
Multivariate Quadratic Equations
Solving the Equation System of SMS4 with the XSL Algorithm
Conclusion
Tweakable Enciphering Schemes from Hash-Sum-Expansion
Introduction
Preliminaries
The Security of Hash-Sum-Expansion
Main Theorem
Variants of HSE
Applications
Implementation Based on a Blockcipher
Other Implementations
Construction of a Double-Block-Length SPRP
Conclusion
Maurer's Methodology
Proof of Lemma 1
A Framework for Chosen IV Statistical Analysis of Stream Ciphers
Introduction
Preliminaries
Hypothesis Testing
Algebraic Normal Form of a Boolean Function
Computation of Algebraic Normal Form
Properties of a Random Boolean Function
A Framework for Chosen IV Statistical Attacks
A Generalized Approach
The Monomial Distribution Test
The Maximal Degree Monomial
Other Possible Tests
Experimental Results
Grain-128
Trivium
Decim
Conclusions
Linear Regression Model for $d$-Monomial Test of Grain
Public Key Encryption with Searchable Keywords Based on Jacobi Symbols
Introduction
Definitions and Preliminaries
Public-Key Encryption with Keyword Search
Our Construction
An Informal Discussion
Formal Description
Properties of Our Construction
Proof of Consistency
Proof of Security
A Certificate-Based Proxy Cryptosystem with Revocable Proxy Decryption Power
Introduction
Bilinear Pairings and Complexity Assumption
A CBPd Scheme with Revocable Proxy Decryption Power
Definitions
Our Scheme
Correctness
Security
How to Revoke Proxy Decryption Power
IND-CBPd-Rev-CCA
Discussion
Concluding Remarks
Proof of Theorem 1
Computationally-Efficient Password Authenticated Key Exchange Based on Quadratic Residues
Introduction
Security Model
Computationally-Efficient Password Authenticated Key Exchange Based on Quadratic Residues
Formal Security Analysis
Conclusion
On the $k$-Operation Linear Complexity of Periodic Sequences (Extended Abstract)
Introduction
Preliminaries
Notation for $k$ Operation Modification
Main Result
Conclusion
Trade-Off Traitor Tracing
Introduction
Related Works
Our Contribution
Model: Trade-Off Traitor Tracing
Concrete Construction of Trade-Off Traitor Tracing
Evaluation
Traceability
Evaluation on the Number of Dynamic Computations
Delayed Attack Resilience
Conclusion
X-FCSR – A New Software Oriented Stream Cipher Based Upon FCSRs
Introduction
Background on FCSRs and 2-Adic Sequences
Design of X-FCSR-128 and X-FCSR-256
Design Rationale and Security Analysis
Conclusion
Efficient Window-Based Scalar Multiplication on Elliptic Curves Using Double-Base Number System
Introduction
Double-Base Number System
Proposed Window-Based Method for Scalar Multiplication
Representation of $n$
Computation of $T^P$ and ${T_{all}^{P}}$
Comparison
Extended Multi-Property-Preserving and ECM-Construction
Introduction
Notation
An Example of Merkle-Damg{aa}rd Construction
Distribution of Merkle-Damg{aa}rd Construction
New Construction and MPP
Generalized Enveloped MPP Transformation
Design of a Differential Power Analysis Resistant Masked AES S-Box
Introduction
Design of Glitch Free Masked AND Gate
Data Dependent Glitch Free Masked $GF$(2^n) Multiplier
A Regular $GF$(2^n) Multiplier Architecture
The Masked Implementation of the $Generate Companion Matrix$
The Masked Implementation of the AND-XOR Plane
Experimental Set-Up and Results
Conclusion
LFSR Based Stream Ciphers Are Vulnerable to Power Attacks
Introduction
Preliminaries
LFSRs
Dynamic Power Consumption of an LFSR
The Proposed SCA Model
The Proposed Attack
Countermeasure to the SCA
Conclusions
An Update on the Side Channel Cryptanalysis of MACs Based on Cryptographic Hash Functions
Introduction
Cryptographic Hash Functions
NMAC/HMAC Functions
Side Channel Attacks on NMAC/HMAC
DPA and Reverse DPA Attack Models
Okeya's Analysis of NMAC/HMAC
Extending Okeya's Attack to Different Block/State Sizes
Partial Key Recovery of NMAC/HMAC with $f$^{(3)} / $f$^{(7)}
Hybrid MAC Proposals
Other MAC Proposals Based on Hash Functions
M-NMAC Function
Variants of M-NMAC
Side Channel Attacks on M-NMAC and Its Variants
Target Compression Functions in M-NMAC
DPA/RDPA Attacks on M-NMAC and Its Variants
Forgery Attacks on M-NMAC and Its Variants
Conclusion
12 Provably Secure PGV Compression Functions
Attacking the Filter Generator by Finding Zero Inputs of the Filtering Function
Introduction
Attack Principle
Bias Computation
Complexity Analysis
Experimental Results
Conclusion
Lemma Used in the Bias Computation
Efficient Implementations of Some Tweakable Enciphering Schemes in Reconfigurable Hardware
Introduction
The Schemes
Design Decisions
The Design Overviews
Implementation
Results
Conclusion
Author Index