Coding Theory and Cryptology

The following sections are included:

• Contents

• Foreword

• Preface

This article is concerned with properties of codes as packings of metric spaces. We present a selection of results on extremal problems of geometric coding theory.

An overview of various types of synchronous stream ciphers is presented. Basic cryptographic properties of synchronous stream ciphers are described, as are some of the most common types of attack. Implementation issues for stream ciphers, including hardware and software efficiency, and resynchronisation proposals are considered. LILI-II, a new stream cipher that is both efficient and secure against known attacks, is described.

Quantum error correction is one of the important requirements in both quantum computing and quantum communication. The mathematical theory of quantum codes (QC) has been formulated in 1996-1998 and developed rapidly since then. In these lecture notes we introduce the basic concepts on QC, mathematical methods to construct good QC and some related topics.

The following sections are included:

• Introduction

• Foundations
  • What is a PKI?
  • Public key cryptography
  • Misconceptions about digital signatures
  • Electronic signatures
  • Certificates
  • Certification authorities
  • Registration authorities
  • Time stamping

• PKI Standards
  • X.509 – ISO |IEC/ITU-T 9594-8
  • PKIX
  • SPKI
  • PKCS
  • Legal matters
  • Qualified certificates
  • Summary

• Points of Policy
  • Key generation and storage
  • Naming
  • Validity
  • Revocation
  • Formal methods and PKIs
  • Summary

• PKI as a Solution
  • Secure email
  • Non-repudiation
  • Access control
  • Digital identity cards
  • Legal assurance
  • Trust
  • The PKI paradox

• Summary
  • Acronyms
  • Certificate Types

• References

These notes informally review the most common methods from computational number theory that have applications in public key cryptology.

This note describes two correlated topics in cryptography. The first topic is the entity exclusion, or how to distribute a cryptographic key over a broadcasting shared by n entities so that all but d excluded entities can get a group key. In a system such as Pay-TV, Internet multicasting and group mobile telecommunication, a dishonest user or an unauthorized terminal should be excluded as quickly as possible. We discuss the points of evaluation and history of the field followed by concrete schemes smartly enabling the entity exclusion. The second topic is how to discover the existence of a “clone,” that is, another entity with the same ID and the same secret key as the original. This problem is rather hard to solve in general. However, depending on environmental conditions there are approaches for solving the problem. We suggest some effective ways for the clone discovery.

Algebraic function fields are important in several areas of information theory such as coding theory and cryptography. These tutorial lecture notes provide a quick introduction to the theory of algebraic function fields. The focus is on finite constant fields since this is the only case of interest for applications to information theory. The subject is approached from the viewpoint of valuation theory. The main topics covered in these lecture notes are valued fields, valuations of algebraic function fields, divisors, the Riemann-Roch theorem, the zeta function of an algebraic function field, and the Hasse-Weil bound.

These notes introduce optimal authentication schemes, both without and with arbitration. We describe how the construction of optimal authentication schemes is reduced to the construction of certain combinatorial designs. Then based on rational normal curves over finite fields, a new family of optimal authentication schemes with three participants is constructed.

The following sections are included:

• Introduction

• Exponential Sums — Basic Notions
  • Getting started
    • Exponential sums — What are they?
    • Exponential sums — What do we want from them?
    • Exponential sums — How do we classify them?
  • Timeline
    • Johann Carl Friedrich Gauss, 1801
    • Hermann Klaus Hugo Weyl, 1916
    • Godfrey Harold Hardy and John Edensor Littlewood, 1920
    • Louis Joel Mordell, 1932
    • Ivan Matveevich Vinogradov, 1935
    • Loo-Keng Hua, 1940
    • André Weil, 1948
    • Pierre Deligne, 1914
    • You, ????
  • Some terminology
    • Rational exponential sums
    • Complete and incomplete exponential sums

• Simplest Bounds and Applications
  • The basic case — Linear sums
  • Nice result almost for free
  • Gaussian sums
  • Linear sums once again
  • Distribution of functions modulo p

• More Sophisticated Methods
  • Extend and conquer
  • Clone, extend and conquer
  • Mordell's bound
  • Shorter sums … but large bound

• Some Strongest Known Results
  • Weil's kingdom
  • Exponential functions
  • More applications
  • What else can we estimate?

• Twin Brothers of Exponential Sums — Character Sums
  • Definitions
  • Polya—Vinogradov bound again
  • Let's push it down!—Other methods are helpful as well

• Applications to Coding Theory
  • Direct applications
  • Less obvious applications: Dimension of BCH codes
    • Definitions
    • Preparations
    • Main result
    • Discussion: Some lessons to learn

• Applications to Cryptography
  • Distribution of some cryptographic primitives
    • Security of exponentiation with precomputation
    • Diffie-Hellman triples and RSA pairs
  • Lattices and exponential sums
    • Introduction and notation
    • Hidden number problem and lattices
    • Extended hidden number problem, lattices and exponential sums
    • Bit security of the Diffie-Hellman secret key
    • Attack on the digital signature algorithm
    • Other applications and open questions

• Applications to Algorithms
  • Primitive roots
  • Pseudorandom regular graphs
  • Polynomial factorisation
  • Complexity lower bounds

• Tutorial Problems

• References

Design and management of authorization policies and service in distributed systems pose several challenges in practice. In this paper, first we discuss some of the key architectural principles involved in the design of a distributed authorization service. We consider the different types of authorization information involved, the ways of propagating them and their verification and management. Then we consider a language based approach to policy specification and outline the constructs of a simple language that can be used to specify a range of commonly used access policies. Then we propose a distributed authorization architecture and outline the various components involved in the provision of the authorization service. We discuss the issues involved in formulating a policy management framework and highlight the various design options and alternatives in a mechanism independent manner. Finally we apply this framework to a specific case of role based access control to illustrate its applicability.

Goppa's construction of algebraic geometry codes is introduced in this paper. Some basic results on Goppa geometry codes are presented. Following Goppa's construction, we introduce two more constructions of linear codes based on curves over finite fields. These two constructions allow us to use closed points of higher degree. One interesting consequence is that many new codes are found from these two constructions.