Lectures on Data Security: Modern Cryptology in Theory and Practice (Lecture Notes in Computer Science, 1561)

✍ Scribed by Ivan Damgard (editor)

• Publisher: Springer
• Year: 1999
• Tongue: English
• Leaves: 257
• Category: Library

✦ Synopsis

In July 1998, a summer school in cryptology and data security was organized atthecomputersciencedepartmentofAarhusUniversity, Denmark.Thistook place as a part of a series of summer schools organized by the European Edu- tional Forum, an organizationconsisting of the researchcenters TUCS (Finland), IPA(Holland)andBRICS(Denmark, Aarhus).Thelocalorganizingcommittee consisted of Jan Camenisch, Janne Christensen, Ivan Damga? ard (chair), Karen Møller, andLouisSalvail.ThesummerschoolwassupportedbytheEuropean Union. Modern cryptology is an extremely fast growing ?eld and is of fundamental importance in very diverse areas, from theoretical complexity theory to practical electroniccommerceontheInternet.Wethereforesetouttoorganizeaschool that would enable young researchers and students to obtain an overview of some mainareas, coveringboththeoreticalandpracticaltopics.Itisfairtosaythat the school was a success, both in terms of attendance (136 participants from over20countries)andintermsofcontents.Itisapleasuretothankallofthe speakers for their cooperation and the high quality of their presentations. A total of 13 speakers gave talks: Mihir Bellare, University of California, San Diego; Gilles Brassard, University of Montreal; David Chaum, DigiCash; Ronald Cramer, ETH Zur ] ich; Ivan Damg? ard, BRICS; Burt Kaliski, RSA Inc.; Lars Knudsen, Bergen University; Peter Landrock, Cryptomathic; Kevin Mc- Curley, IBM Research, Almaden; Torben Pedersen, Cryptomathic; Bart Preneel, Leuven University; Louis Salvail, BRICS; Stefan Wolf, ETH Zur ] ich.

✦ Table of Contents

Lectures on Data Security
Preface
Table of Contents
Practice-Oriented Provable-Security
Introduction
Protocols, Primitives, Proofs and Practice
Protocols and Primitives: The Problem
Provable Security: Reductions
Practice-Oriented Provable Security
Using Block Ciphers
Concrete Security
Security Versus Attacks
The Random Oracle Model
New Notions: Session Key Distribution
What Provable Security Is and Isn't
On Limitations
On Assumptions
Proofs and Definitions
Going On
References
Introduction to Secure Computation
Secure Two-Party Computation
Oblivious Transfer and Match-Making
Historical Notes
Variations and Other Applications of OT
OT of Strings
Oblivious Common String Verification
A Reduction
Constructions of OT-Protocols
Necessity of Assumptions
Rabin-OT
OT Based on RSA
General Secure Two-Party Computation
Addition-Gates
Negation-Gates
Multiplication-Gates
Complexity of the Protocol
Security Discussion
Example
Dealing with Malicious Attacks
Notion of Security of Basic OT
A General Solution in the Cryptographic Scenario
Trapdoor One-Way Permutations.
Commitments.
Mutually Random Coins.
OT Secure against Malicious Attacks.
Oblivious Function Evaluation and Malicious Attacks.
A Generic Solution
Commitment Based on OT
Committed Oblivious Transfer (COT)
Other Work
General Secure Multi-party Computation
Introduction
Secret Sharing with Semi-Honest Participants
Verifiable Secret Sharing
Definition of Malicious Adversary
Definition of VSS
VSS Scheme
Commitments
Broadcast
VSS Protocol
Other Work
GMW: Achieving Robustness
Other Work
Information Theoretic Security
Introduction
Model
Results of CCD and BGW
Remark on Broadcast
Outline of this Part
Semi-Honest Case
Computing on Shared Secrets
Constants, Addition
Multiplication
Protocol for Semi-Honest Participants
Optimality of the Bound
Dealing with Malicious Attacks
Verifiable Secret Sharing Scheme
Linear Algebraic View on Shamir's Secret Sharing
Towards VSS
Pairwise Checking Protocol
General Protocol Secure against Malicious Attacks
Homomorphic Distributed Commitments
Maintaining the Invariant
Linear Secret Sharing Schemes
The Commitment Multiplication Protocol
Extensions
Other Work
Acknowledgements
References
Commitment Schemes and Zero-Knowledge Protocols
What's in this Article?
Commitment Schemes
Introduction
Defining Commitment Schemes
Examples of Commitment Schemes
Theoretical Results of Existence of Commitment Schemes
Zero-Knowledge Protocols
Introduction
A Simple Example
Definitions
Interactive Proof Systems and Proofs of Knowledge
Interactive Arguments
Zero-Knowledge
An Example
Known General Results and Open Problems
Results on Interactive Proofs and Arguments
Results on Zero-Knowledge
On Composition of Zero-Knowledge Protocols
Applications of Zero-Knowledge
Reference
Emerging Standards for Public-Key Cryptography
Introduction
A Survey of Standards Efforts
ANSI X9F1
IEEE P1363
ISO/IEC JTC1 SC27
NIST
Differences and Coordination
Related Efforts
A General Model for Public-Key Standards
Primitives
Types of Primitive
Examples
Implementation
Schemes
Types of Scheme
Example
Implementation
Are ``Strong Primes'' Needed for RSA?
1980s: Yes
Early 1990s: No
Late 1990s: Maybe?
Research Areas
Key Validation
New Encryption Schemes
New Signature Schemes
Provable Security
Conclusion
References
Contemporary Block Ciphers
Block Ciphers - Introduction
Modes of Operations
Security of Secret-Key Block Ciphers
Classification of Attacks
Theoretical Secrecy
Practical Secrecy
Cryptanalysis of Block Ciphers
Attacks on Iterated Ciphers
Differential Cryptanalysis
Higher Order Differentials
Truncated Differentials
Linear Cryptanalysis
Davies' Attack
Differential-Linear Attack
Other Variants
Interpolation Attack
Non-surjective Attack
Key Schedule Attacks
Related Key Attacks
Design of Block Ciphers
Block and Key Size
Resistance against Differential and Linear Attacks
Resistance against other Attacks
Enhancing the Strength of the DES
The Advanced Encryption Standard
Conclusion and Open Problems
References
Primality Tests and Use of Primes in Public Key Systems
Rabin-Miller's Primality Test
Introductory Results
Estimates
A Simple Deterministic Prime Generation Algorithm
Constructing Strong Probabilistic Primes
References
Signing Contracts and Paying Electronically
Introduction
Definition of Secure Digital Signatures
Security of Digital Signatures
Security of Practical Schemes
Public Key Infrastructure
Non-repudiation
Contract Signing
Gradual and Verifiable Release of Signature
Gradual and Verifiable Release of Evidence
Optimistic Protocols
Electronic Payments
Model
Cash-like Payment Systems
Blind Signatures
On-Line Coin System
Off-Line Coin System
Micropayment
Conclusion
References
The State of Cryptographic Hash Functions
Introduction
Definitions
One-Way Hash Function (OWHF)
Collision Resistant Hash Function (CRHF)
Universal One-Way Hash Function
Message Authentication Code (MAC)
Universal Hash Functions
Generic Constructions and Attacks
A General Model for Iterated Hash Functions
Generic Attacks
Attacks Independent of the Algorithm
Attacks Dependent on the Chaining
General Security Results
An Overview of Constructions
MDCs Based on a Block Cipher
Size of Hash Result Equal to the Block Length.
Size of Hash Result Equal to Twice the Block Length.
Size of Hash Result Larger than Twice the Block Length.
Other Constructions.
MDCs Based on Algebraic Structures
MDCs Based on Modular Arithmetic.
MDCs Based on Knapsack and Lattice Problems.
Incremental Hash Functions.
Custom Designed MDCs
Conclusions and Open Problems
References
The Search for the Holy Grail in Quantum Cryptography
Introduction
Overview
Content
Mathematical Background
Vectors and Vector Spaces
Dirac's Notation
Unitary Evolution
Relevant Operators
Space Extension
Quantum States
Maximal Tests
Pure States
Complete Measurements
Mixed States
Oblivious Encoding of Information
The BB84 Coding Scheme
BB84 Is Oblivious
BB84 as a Quantum Primitive
From BB84 to Quantum Oblivious Transfer
Security and Generalized Measurements
Classical vs. Quantum Cryptography
Quantum Bit Commitment
Purification
Purifying a Coin Toss
Purifying a Measurement
From One Purification to Another
Purifying a Quantum Protocol
Quantum Bit Commitment Is Impossible
Conclusion
Acknowledgements
References
Unconditional Security in Cryptography
Computational versus Information-Theoretic Security
Basic Concepts of Information Theory
Probability-Theoretic Preliminaries
Bar Kochba, Uncertainty, and Entropy
Conditional Entropy and Mutual Information
Graphical Representation of Information-Theoretic Quantities
Perfect Secrecy and Shannon's Pessimistic Theorem
Optimistic Results by Limiting the Adversary's 7.4mm0mmInformation
Wyner's Wire-Tap Channel
Broadcast Channels
The Power of Interaction
Interactive Secret-Key Agreement from Common 7.2mm0mmRandomness
The Scenario and the Secret-Key Rate
The Satellite Scenario and Phases of Secret-Key Agreement 9.4mm0mmProtocols
Advantage Distillation
Information Reconciliation
Privacy Amplification
Generalizing the Model
Arbitrary Random Variables
Secret-Key Agreement Secure against ACTIVE Adversaries
Concluding Remarks
References