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

Matsumoto, Ryutaroh; Kurosawa, Kaoru; Itoh, Toshiya; Konno, Toshimitsu; Uyematsu, Tomohiko

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

Authors

Description

Let $N(d,d^\perp)$ denote the minimum length $n$ of a linear code $C$ with $d$ and $d^{\bot}$, where $d$ is the minimum Hamming distance of $C$ and $d^{\bot}$ is the minimum Hamming distance of $C^{\bot}$. 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