Flexible Quasi-Dyadic Code-Based Public-Key Encryption and Signature.
Kazukuni Kobara · 2009
Abstract. Drawback of code-based public-key cryptosystems is that their public-key size is lage. It takes some hundreds KB to some MB for typical parameters. While several attempts have been conducted to reduce it, most of them have failed except one, which is Quasi-Dyadic (QD) public-key (for large extention degrees). While an attack has been proposed on QD public-key (for small extension de-grees), it can be prevented by making the extension degree m larger, specifically by making q(m(m1)) large enough where q is the base filed and for a binary code, q = 2. The drawback of QD is, however, it must hold n << 2m t (at least n 2m1) where n and t are the code lenght and the error correction capabil-ity of the underlying code. If it is not satisfied, its key generation fails since it is performed by trial and error. This condition also prevents QD from generat-ing parameters for code-based digital signatures since without making n close to 2m t, 2mt=(nt) cannot be small. To overcome these problems, we propose “Flex-ible ” Quasi-Dyadic (FQD) public-key that can even achieve n = 2m t with one shot. Advantages of FQD include 1) it can reduce the public-key size further, 2) it can be applied to code-based digital signatures, too.