Book contents
- Frontmatter
- Contents
- Preface
- Restricted colorings of graphs
- Polynomials in finite geometries and combinatorics
- Models of random partial orders
- Applications of submodular functions
- Weighted quasigroups
- Graphs with projective subconstituents which contain short cycles
- On circuit covers, circuit decompositions and Euler tours of graphs
- Slicing the hypercube
- Combinatorial designs and cryptography
Combinatorial designs and cryptography
Published online by Cambridge University Press: 16 March 2010
- Frontmatter
- Contents
- Preface
- Restricted colorings of graphs
- Polynomials in finite geometries and combinatorics
- Models of random partial orders
- Applications of submodular functions
- Weighted quasigroups
- Graphs with projective subconstituents which contain short cycles
- On circuit covers, circuit decompositions and Euler tours of graphs
- Slicing the hypercube
- Combinatorial designs and cryptography
Summary
Abstract
In this expository paper, we describe several applications of combinatorics (in particular, combinatorial designs) to cryptography. We look at four areas in cryptography: secrecy codes, authentication codes, secret sharing schemes, and resilient functions. In each of these areas, we find that combinatorial structures arise in a natural and essential way, and we present several examples of combinatorial characterizations of cryptographic objects.
Introduction
Recent years have seen numerous interesting applications of combinatorics to cryptography. In particular, combinatorial designs have played an important role in the study of such topics in cryptography as secrecy and authentication codes, secret sharing schemes, and resilient functions. The purpose of this paper is to elucidate some of these connections. This is not intended to be an exhaustive survey, but rather a sampling of some research topics in which I have a personal interest.
Some other related surveys include applications of error-correcting codes to cryptography (Sloane [60]), applications of finite geometry to crpytography (Beutelspacher [6]) and applications of combinatorial designs to computer science (Colbourn and Van Oorschot [16]).
In this introduction we will define the relevant concepts from design theory that we will have occasion to use. Beth, Jungnickel and Lenz [4] is a good general reference on design theory.
Let 1 ≤ t ≤ k < v. An Sλ(t, k, v) is defined to be a pair (X, β), where X is a v-set (of points) and β is a collection of κ-subsets of X (called blocks), such that every t-subset of points occurs in exactly λ blocks. An Sλ(t, k, v) is called simple if no block occurs more than once in β.
- Type
- Chapter
- Information
- Surveys in Combinatorics, 1993 , pp. 257 - 287Publisher: Cambridge University PressPrint publication year: 1993
- 5
- Cited by