Paper 2009/635

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

Kazukuni Kobara

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 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
public-keydigital signaturelinear codedyadic
Contact author(s)
kobara_conf @ m aist go jp
History
2010-05-21: revised
2010-01-01: received
See all versions
Short URL
https://ia.cr/2009/635
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/635,
      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{https://eprint.iacr.org/2009/635}},
      url = {https://eprint.iacr.org/2009/635}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.