Paper 2005/194

Primal-Dual Distance Bounds of Linear Codes with Application to Cryptography

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

Abstract

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.

Note: We added a table for the shortest input length of Boolean functions of EPC(l) of order k by the Kurosawa-Satoh construction in the revised version. Two authors were added. To appear in IEEE Trans. Inform. Theory, Sept. 2006.