Paper 2009/635

Flexible Quasi-Dyadic Code-Based Public-Key Encryption and Signature

Kazukuni Kobara


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 degrees), it can be prevented by making the extension degree $m$ larger, specifically by making $q^(m (m-1))$ 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 << 2^m - t$ (at least $n \leq 2^{m-1}$) where $n$ and $t$ are the code lenght and the error correction capability 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 generating parameters for code-based digital signatures since without making $n$ close to $2^m - t$, $2^{mt}/{n \choose t}$ cannot be small. To overcome these problems, we propose ``Flexible'' Quasi-Dyadic (FQD) public-key that can even achieve $n=2^m - t$ with one shot. Advantages of FQD include 1) it can reduce the publi-key size further, 2) it can be applied to code-based digital signatures, too.

Note: Fixed some typos.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
public-keydigital signaturelinear codedyadic
Contact author(s)
kobara_conf @ m aist go jp
2010-05-21: revised
2010-01-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kazukuni Kobara},
      title = {Flexible Quasi-Dyadic Code-Based Public-Key Encryption and Signature},
      howpublished = {Cryptology ePrint Archive, Paper 2009/635},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.