• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Progress in cryptology-AFRICACRYPT 2009 >Reducing Key Length of the McEliece Cryptosystem
【24h】

Reducing Key Length of the McEliece Cryptosystem

机译：减少McEliece密码系统的密钥长度

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The McEliece cryptosystem is one of the oldest public-key cryptosystems ever designed. It is also the first public-key cryptosystem based on linear error-correcting codes. Its main advantage is to have very fast encryption and decryption functions. However it suffers from a major drawback. It requires a very large public key which makes it very difficult to use in many practical situations. A possible solution is to advantageously use quasi-cyclic codes because of their compact representation. On the other hand, for a fixed level of security, the use of optimal codes like Maximum Distance Separable ones allows to use smaller codes. The almost only known family of MDS codes with an efficient decoding algorithm is the class of Generalized Reed-Solomon (GRS) codes. However, it is well-known that GRS codes and quasi-cyclic codes do not represent secure solutions. In this paper we propose a new general method to reduce the public key size by constructing quasi-cyclic Alternant codes over a relatively small field like F_(2~8). We introduce a new method of hiding the structure of a quasi-cyclic GRS code. The idea is to start from a Reed-Solomon code in quasi-cyclic form defined over a large field. We then apply three transformations that preserve the quasi-cyclic feature. First, we randomly block shorten the RS code. Next, we transform it to get a Generalised Reed Solomon, and lastly we take the subfield subcode over a smaller field. We show that all existing structural attacks are infeasible. We also introduce a new NP-complete decision problem called quasi-cyclic syndrome decoding. This result suggests that decoding attack against our variant has little chance to be better than the general one against the classical McEliece cryptosystem. We propose a system with several sizes of parameters from 6,800 to 20,000 bits with a security ranging from 2~(80) to 2~(120).
机译：McEliece密码系统是有史以来最古老的公钥密码系统之一。它也是第一个基于线性纠错码的公钥密码系统。它的主要优点是具有非常快速的加密和解密功能。然而，它具有主要缺点。它需要一个很大的公钥，这使得在许多实际情况下很难使用。一种可能的解决方案是由于其紧凑的表示而有利地使用准循环码。另一方面，对于固定级别的安全性，使用最佳代码（例如最大距离可分离代码）可以使用较小的代码。具有有效解码算法的MDS代码家族中，几乎唯一已知的一类是广义Reed-Solomon（GRS）代码。但是，众所周知，GRS码和准循环码不代表安全解决方案。在本文中，我们提出了一种通过在相对较小的字段（如F_（2〜8））上构造准循环交替码来减小公钥大小的新方法。我们介绍了一种隐藏准循环GRS码结构的新方法。这个想法是从在大域上定义的准循环形式的里德-所罗门代码开始的。然后，我们应用三个保留准循环特征的变换。首先，我们随机阻止缩短RS码。接下来，我们将其转换为广义Reed Solomon，最后将子字段子代码放在较小的字段上。我们证明所有现有的结构性攻击都是不可行的。我们还介绍了一个新的NP完全决策问题，称为准循环综合症解码。这一结果表明，针对我们的变体的解码攻击几乎没有机会比针对经典McEliece密码系统的一般攻击更好。我们提出了一种系统，它具有从6,800到20,000位的几种不同大小的参数，安全范围从2〜（80）到2〜（120）。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号