Primal-dual distance bounds of linear codes with application to cryptography

Abstract

Let $N(d,d^{\perp })$ denote the minimum length $n$ of a linear code $C$ with $d$ and $d^{\perp }$, where $d$ is the minimum Hamming distance of $C$ and $d^{\perp }$ is the minimum Hamming distance of $C^{\perp }$. In this paper, we show a lower bound and an upper bound on $N(d,d^{\perp })$. Further, for small values of $d$ and $d^{\perp }$, we determine $N(d,d^{\perp })$ and give a generator matrix of the optimum linear code. This problem is directly related to the design method of cryptographic Boolean functions suggested by Kurosawa et al.

6 pages, using IEEEtran.cls. To appear in IEEE Trans. Inform. Theory, Sept. 2006. Two authors were added in the revised version