Progress in Cryptology - INDOCRYPT 2002: Third International Conference on Cryptology in India Hyderabad, India, December 16-18, 2002 (Lecture Notes in Computer Science, 2551)

Lecture Notes in Computer Science
Springer
Progress in Cryptology – INDOCRYPT 2002
Preface
Organization
	General Co-chairs
	Program Co-chairs
	Program Committee
	Organizing Committee
	External Referees
	Sponsoring Institutions
Table of Contents
	Invited Talks
	Symmetric Ciphers
	New Public-Key Schemes
	Foundations
	Public-Key Infrastructures
	Fingerprinting and Watermarking
	Public-Key Protocols
	Boolean Functions
	Efficient and Secure Implementations
	Applications
	Anonymity
	Secret Sharing and Oblivious Transfer
Security of a Wide Trail Design
	Introduction
	The Wide Trail Design Strategy
		The Non-linear Step
		The Linear Steps
	Security
		Probability of Trails and Difference Propagations
		Motivation for the Propagation Probability Bounds
		Proven Bounds
	Performance
	Attempts at Cryptanalysis of Rijndael
		Differential and Linear Cryptanalysis
		Saturation Attacks
		Algebraic Structure
			Decomposition of the Round Transformation
			Structure within the S-Box
		Algebraic Attacks
			Continued Fractions
			XSL
			Embedding
	Efficient Hardware Implementations
	Conclusions
	References
Fast Algorithms for Determining the Linear Complexity of Period Sequences
	Introduction
	Fast Algorithms for Computing the Linear Complexity of Sequences with Period p^n and p^mq^n
	Fast Algorithms for Computing the Linear Complexity of Sequences with Period 2p^n
	Fast Algorithms for Computing the k-Error Linear Complexity of Sequences with Period p^n
	Conclusion
	References
A New Class of Stream Ciphers Combining LFSR and FCSR Architectures
	Introduction
	Generation of Eventually Periodic Binary Sequences with Feedback Shift Registers
		The LFSR Architectures  for Eventually Periodic Binary Sequences
		The 2-adic FCSR Architectures  for Eventually Periodic Binary Sequences
	Pseudo-random Generator with Compound FCSR  and LFSR Architecture
		Concatenation of LFSR and FCSR
		Design of the Pseudorandom Generator
			Public key:
			Private key:
			Statistic Quality of the Sequence
			Some Statistical Properties of 2-adic Division Boxes
			Linear Complexity of S

			Cryptanalysis of the Pseudorandom Generator
				Attack on the keys.
				2-adic attack.
				FCSR-Linear attack.
				Boolean functions attack.
	A New Self-synchronizing Stream Cipher
		Analysis of the Stream Cipher
	Conclusion
	References
Slide Attack on Spectr-H64
	Introduction
	Breaking One Round of Spectr-H64
	Applying Slide Attack on Spectr-H64
	Weak Keys and Fixed Points
	Conclusion
	References
	Appendix A: Description of Spectr-H64
On Differential Properties of Pseudo-Hadamard Transform and Related Mappings (Extended Abstract)
	Introduction
	Preliminaries and Notation
	Linear-Algebraic Viewpoint to Differential Probability
		Differential Probability in Language of Matrix Equations
		Algorithm for dp^F for F \\in L1
	The Pseudo-Hadamard Transform
		Generalization to 2 x 2 Matrices
		Analysis of PHT
	Application to Twofish
	Conclusions
	Acknowledgments and Further Work
	References
A Variant of NTRU with Non-invertible Polynomials
	A Generalization of NTRU
	Character Sums
	Uniformity of Distribution
	Remarks
	Acknowledgement
	References
Tree Replacement and Public Key Cryptosystem
	Introduction
	Preliminaries
		Definition A ranked alphabet Σ is a set together with a rank functionr
		Definition A tree domain D is a non emptysubset of strings over N satisfyingthe following conditions
		Definition A Σ-tree (for short, a tree) is a function t : D → Σ such that
		Definition Given a tree t and a tree address u in dom(t)
		Definition
		Definition Given t = (t1, t2, ..., tn) in TΣ(m, n) and s in TΣ(n, 1)
		Definition Given a tree t1, an address u in dom(t1)
		Definition A substitution is anyfunctio n h
		Definition A set of rules S over TΣ(X)
		Definition The congruence generated
		Definition Two trees t1 and t2
		Definition Given a set of rules S over a set of trees TΣ(X)
		Definition Given a tree replacement system (S,→)
		Definition A tree replacement system (S,→)
		Word problem
	Construction of PKC
		Encryption Consider a tree replacement system
		References
Never Trust Victor: An Alternative Resettable Zero-Knowledge Proof System
	Resettable Zero-Knowledge
		Case History
		Our Definition of Resettable Zero-Knowledge
	Commitment Schemes Based on Exponentiation
		DLP Assumption
		A Knowledgeable Perfectly Hiding Commitment Scheme
		A Perfectly Binding Commitment Schemes
	A new rZK Proof for Graph 3-Colorability
		Bounding the Probability of Failure
	Acknowledgments
	References
Asynchronous Unconditionally Secure Computation: An Efficiency Improvement
	Introduction
		The Model and Setting
	The Protocol Construction
		Preparation Phase
			Step-1: Generating  l Random Pairs (a,b)
			Step2: Generating c such that c=ab
			Step-3: Increasing the Degree of Sharings
			Verification
		Computation Phase
	Complexity Analysis
	Conclusion
	References
QPKI: A QoS-Based Architecture for Public-Key Infrastructure (PKI)
	Introduction
	Quality-of-Service Requirements of PKI Stakeholders
		QoS Concerns of Relying Parties
		QoS Concerns of Certificate Owners
		QoS Concerns of Certificate Issuers
	Limitations of Current PKI Architectures
	Proposed QPKI Architecture
		Recertification
		Active Certificates
		QPKI Architecture
	QoS Features of the QPKI Architecture
	Conclusion and Future Work
	References
Towards Logically and Physically Secure Public-Key Infrastructures
	Introduction
		Background
	A Model for Improved Integrity Verification In PKIs
		Problem Statement
		Goals of this Paper
		Nomenclature
		Specification of Procedures and Protocols
	Security Analysis
	Conclusion
	Acknowledgements
	References
Cryptanalysis of Optimal Differential Energy Watermarking (DEW) and a Modified Robust Scheme
	Introduction
		DEW Scheme
	Attacks On DEW Scheme
		Basic Attack
			Experimental Results
		Improved Cryptanalysis
	Modified DEW Scheme
		Watermark Embedding
		Watermark Extraction
		Experimental Results
	References
A 2-Secure Code with Efficient Tracing Algorithm
	Introduction
		Related Works
	Preliminaries
	A New Inner Code
		Properties of ColluderPair(M)
		Tracing Algorithm
		Faster Tracing
		Reducing the Code Length
	Construction from Traceability Codes
	Construction from Perfect Hash Families
	Comparison and Concluding Remarks
	Acknowledgement
	References
Reed Solomon Codes for Digital Fingerprinting
	Introduction
	Background
		Goals of Fingerprinting
		A Model for Fingerprinting
		Attacks on Fingerprint
		Properties of Reed Solomon Codes
	Our Contribution
		Bounds for Collusions
		The Length of Fingerprints
		Content Distribution Scheme
			The Encryption Scheme
			Tracing Scheme
		Pirate Strategies in Fingerprinting
		Performance Measure
	Conclusion
	Acknowledgement
	References
	Appendix
A Note on the Malleability of the  El Gamal Cryptosystem
	Introduction
		The El Gamal Cryptosystem
		Notation
		The Problem
	Our Results
		Some Preparation
		The Perfect Case
		Two Examples of Possible Approximations
		A Class of Hard Psi
			The Main Proposition.
	Conclusion
	Acknowledgement
	References
Authentication of Concast Communication
	Introduction
		Relevant Work
		Concast Scenario
	The Model
	Components of the System
		Communication Channel
		Signature Scheme
			Signature Generation
			Verification
		An Approach to Digital Multisignature
			Signature Generation
			Verification
	Scheme 1
		Security Issues
	Scheme 2
		Performance Issues
	Scheme 3
		Performance Issues
	Security
	Fast Screening for a Non-RSA Signature Scheme
		Signature Generation
	References
Self-certified Signatures
	Introduction
		Digital Signature and Certification
		Related Concepts
		Our Contributions
	Self-certified Signature
		Definition of SCS
		Attack Models against SCS
		General Implementation of SCS Based on DLP
		Comparison with Self-certified Key
		Distinguished Implementation of SCS
	Multi-certification Signature and PKI
		PKI and PMI Environments
		Multi-certification Signature
			General Implementation of MCS
		Efficiency
	Conclusion
	Acknowledgements
	References
Identity Based Authenticated Group Key Agreement Protocol
	Introduction
	Identity-Based Public Key Cryptosystem
	One-Way Function Trees
		Notations
		One-Way Function Tree (OFT) Algorithm for Key Establishment
		Tree-Based Group Diffie-Hellman Protocol (TGDH)
	The Weil Pairing
	ID-Based Authenticated Group Key Agreement (ID-AGKA)
		Assumptions
		System Settings
		Protocol
		Adding or Deleting a Member in the Key Tree
		Merge and Partition
	Security Analysis
	Conclusions and Future Work
	References
	Appendix A
		A. Applications of ID-Based Encryption
			A.1 Revocation of Public Keys
			A.2 Delegation of Decryption Capabilities
	Appendix B
		B. ID-Based Two Party Authenticated Key Agreement Protocol
			B.1 Protocol
	Appendix C
		C. Group Key Agreement Protocol Properties:
	Appendix D
		D. Performance Analysis
Construction of Cryptographically Important Boolean Functions
	Introduction
	Preliminaries
	Construction of Bent Functions
	Construction of 1-Resilient Functions
		Construction of 8-Variable 1-Resilient Functions with Nonlinearity 116
		Construction of 10-Variable (resp. 12-Variable) 1-Resilient Functions with Nonlinearity 488 (resp. 1996)
	Some General Results
	Conclusions
	Acknowledgement
	References
Evolving Boolean Functions Satisfying  Multiple Criteria
	Introduction
	Preliminaries
	Nonlinearity, Autocorrelation and Algebraic Degree
		Cost Functions and General Approach
		Experimental Results
	Constructing Correlation Immune Functions
		Motivation and Method -- The First Pass
		Change of Basis
			Comparison to Previous Works for 1st Order Correlation Immunity
		Transformation for Higher Order Correlation Immunity
		Linear Transformation for Propagation Characteristics
		CI and PC Together
	Conclusions
	References
Further Results Related  to Generalized Nonlinearity
	Introduction
	Preliminaries
	Group Action on Fn
	Functions of Repetitive Sequence
	Navigating between Different Representations
		A Nonlinear Transformation over Bn
	Conclusions
	Acknowledgment
	References
Modular Multiplication in GF(p^k)  Using Lagrange Representation
	Introduction
	Montgomery Multiplication in GF(p^k)
		Implementation
	Alternate Polynomial Representation
		Implementation
	Example
	Discussions
		Simplified Architecture
		Cryptographic Context
	Conclusion
	References
	Proof of Lemma 1
	Proof of Lemma 2
Speeding up the Scalar Multiplication in the Jacobians of Hyperelliptic Curves Using Frobenius Map
	Introduction
	Preliminaries
		Hyperelliptic Curves
		Jacobians of Hyperelliptic Curves
		Frobenius Map on the Jacobians
	Base-Ø Expansion
	Scalar Multiplication on the Jacobian
	Efficiency of the Base-Phi Expansion Method
	Example
	Conclusion
	References
Improved Elliptic Curve Multiplication Methods  Resistant against Side Channel Attacks
	Introduction
	Elliptic Curve Arithmetic
		Efficiency of Addition and Doubling Algorithms
	Scalar Multiplication and Side Channel Attacks
		SPA-Resistant Scalar Multiplication Methods
		Countermeasures against DPA
		Computing Architecture
	Window-Based Method
		Security Analysis
		Efficiency
	Montgomery-Type Method
		Security Analysis
		Efficiency
	Comparison
	References
	Appendix
		Computing ECDBL^J (left) and ECDBL^J,a=-3 (right)
		Computing ECADD^J (left) and ECADD^J,Z1=1 (right)
		Computing wECDBL^Jw
		Computing xECADDDBL (left) and xECADDDBL^a=-3 (right)
		Computing YRecovering
A Certified E-mail System  with Receiver\'s Selective Usage  of Delivery Authority
	Introduction
		Related Work
		Our Result
			Comparison
	Preliminaries
		Model and Assumptions
	Requirements
	The Proposal System
		On-Line Protocol
			Protocol
			Analysis of Properties
			Malicious Delivery Authority
		Optimistic Protocol
			Protocol
			Analysis of Properties
		Our Combined Proposal System
			Fee Collection
			The Relation with Existing Mail System
	Conclusion
	References
The Design and Implementation of Improved Secure Cookies Based on Certificate
	Introduction
	The Security Threat of Cookies
		Typical Cookies and Security Threats
		Related Works
	Design of Secure Cookies Based on Public Key Certificate
		Notation and Architecture of Secure Cookies
		Issuing Secure Cookies Set
		A Login Procedure through a Secure Cookies Set
		The Security of Proposed Secure Cookies Set
	Extension of Secure Cookies Set
		Authenticated Session Tracking in Single-Server
		An Authenticated Login in Multi-server
	An Implementation of Secure Cookies Set
		The Implementation Environment
		The Implementation Result and Performance
	Summary and Conclusion
	References
Spending Offline Divisible Coins  with Combining Capability
	Introduction
	The Eng-Okamoto Scheme
		Definitions
		The EO Protocol
		Properties
	Combining Mechanism
		Notation and Basic Mechanism
		One-tiered Combining
		Multi-tiered Combining
		The Modified EO Protocol for Combined Coins
	Properties of the Combined Coins
		Comparison of Cost
	Concluding Remarks
	References
Efficient Object-Based Stream Authentication
	Introduction
		Previous Stream Authentication Solutions
		Weakness in Block-Based Solutions
		Our Scheme
	Object-Based Scheme
		Notation
		Primitives
		Basic Authentication Protocol
		Re-synchronization
		Performance
			Tolerance of Packet Loss
			Overhead
			Security
	Application on Video Stream
		Overview of RTP and H.261 RTP Header The RTP header has the following format [6
			Timestamp: 32 bits
			ITU-T H.261
		Constructing Object Member
		Locking Object Identifier
		Unlocking Object Identifier
		Verifying Object
	Conclusion
	References
	Appendix:Example of Constructing identifier
The Security of a Mix-Center Based on a Semantically Secure Cryptosystem
	Introduction
		Previous Work and Applications of Mix-Nets
		Previous Results on Mix-Centers
		Contribution
	Notation and Definitions
	The Security of a Mix-Center
		Definitions
			A Definition of a Secure RMC.
		Results on the Security for an RMC
		Definition 6 is Not Sufficient for a Mix-Net
			Using Malleability to Break Anonymity.
			Using Malleability to Break Robustness.
	Conclusion and Future Work
	References
	Proofs
New Identity Escrow Scheme  for Anonymity Authentication
	Introduction
	Identity Escrow
		Composition and Step of Identity Escrow Scheme
		Requirements of Identity Escrow Scheme
	Conventional Scheme
		Method 1 -- Identity Escrow Scheme Using Group Signature
		Method 2 -- Identity Escrow Scheme Using ZKIP
		Method 3 -- Identity Escrow Scheme Using Blind Scheme
		Method 4 -- Identity Escrow Scheme Using E-cash Protocol
	Proposal Schemes
		Proposal Scheme I -- New Identity Escrow Mechanism
			System Parameters
			Protocol
				Step 1 Alice’s identity registration, verification and publicly verifiable anonymitycontrol step
					Phase 1 Process phase by Alice
					Phase 2 Process phase by Issuer
					Phase 3 Process phase by all party
				Step 2 Proxy signature information generation and verification step
					Phase 1 Process phase by Issuer
					Phase 2 Process phase by Alice
				Step 3 Anonymity authentication information generation and verification step
					Phase 1 Process phase by Alice
					Phase 2 Process phase by service provider
				Step 4 Anonymity control step
					Phase 1 Process phase by service provider
					Phase 2 Process phase by lawenf orcement agency
		Proposal Scheme II -- Advanced Identity Escrow Mechanism for Contents Transmission
			System Parameters
			Protocol
				Step 1 Key agreement step
					Phase 1 Process phase by Alice
					Phase 2 Process phase by service provider
				Step 2 Encrypted communication step
		Proposal Scheme III -- Advanced Identity Escrow Mechanism Supporting Key Recovery
			System Parameters
			Protocol
				Step 1 Key agreement and encrypted communication step
					Phase 1 Process phase by Alice
					Phase 2 Process phase by Bob
				Step 2 Key recovery step
					Phase 1 Process phase by lawenf orcement agency
		Comparison and Analysis
	Conclusion
	References
On Unconditionally Secure Distributed Oblivious Transfer
	Introduction
	The Distributed Model
		Definitions
		A Formal Model
	Impossibility Result and Lower Bound for Existence
	Protocol Implementing (r,m)-DOT- (n1)
		Correctness and Security
		Efficiency
	General Access Structure Model for DOT- (n1)
		Definitions
	Condition for Existence
	General Access Structure Protocol for DOT- (n1)
		Correctness and Security
	Conclusions
	References
Non-perfect Secret Sharing  over General Access Structures
	Introduction
		General Non-Perfect Secret Sharing (NSS)
		Our Contributions
	On the Existence of Secret Sharing Schemes
	Generalized Monotone Span Programs (GenMSP)
	Relationship between GenMSP and NSS
	A Framework for the Construction NSS Schemes
	A Concrete Implementation
	Conclusion
	References
On Distributed Key Distribution Centers and Unconditionally Secure Proactive Verifiable Secret Sharing Schemes Based on General Access Structure
	Introduction
	Background
		Notations
		General Access Structure, Monotone Span Program and LSSS
		The Model of DKDC
	A VSS
		Distribution (Share) Phase
		Reconstruction Phase
	Proactivity
		Attack against Proactivity
			Renewal phase
		Modification of the Scheme
			Renewal phase
	A Proactive Verifiable DKDS
		Set Up Phase
		Key Request and Key Computation Phase
	Conclusions
	Acknowledgements
	References
Author Index