Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / boolean function, linear code

Date: received 24 Jun 2005, last revised 12 Jun 2006

Contact author: ryutaroh at it ss titech ac jp

Available formats: PDF | BibTeX Citation

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.

Version: 20060612:081747 (All versions of this report)

Discussion forum: Show discussion | Start new discussion