• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Cryptanalysis of McEliece Cryptosystem Based on Algebraic Geometry Codes and Their Subcodes
【24h】

Cryptanalysis of McEliece Cryptosystem Based on Algebraic Geometry Codes and Their Subcodes

机译：基于代数几何代码及其子代码的McEliece密码系统的密码分析

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

摘要

We give polynomial time attacks on the McEliece public key cryptosystem-based either on algebraic geometry (AG) codes or on small co-dimensional subcodes of AG codes. These attacks consist in the blind reconstruction either of an error correcting pair (ECP), or an error correcting array (ECA) from the single data of an arbitrary generator matrix of a code. An ECP provides a decoding algorithm, that corrects up to (({d^{*}-1-g})/{2})((d∗−1−g)/2) errors, where d^{*}d∗ denotes the designed distance and gg denotes the genus of the corresponding curve, while with an ECA the decoding algorithm corrects up to (({d^{*}-1})/{2})((d∗−1)/2) errors. Roughly speaking, for a public code of length nn over mathbb {F}_{q}Fq , these attacks run in O(n^{4}log (n))O(n4log(n)) operations in mathbb F_{q}Fq for the reconstruction of an ECP and O(n^{5})O(n5) operations for the reconstruction of an ECA. A probabilistic shortcut allows to reduce the complexities respectively to O(n^{3+varepsilon } log (n))O(n3+εlog(n)) and O(n^{4+varepsilon })O(n4+ε) . Compared with the previous known attack due to Faure and Minder, our attack is efficient on codes from curves of arbitrary genus. Furthermore, we investigate how far these methods apply to subcodes of AG codes.
机译：我们对McEliece公钥密码系统进行多项式时间攻击，它基于代数几何（AG）代码或基于AG代码的较小共维子代码。这些攻击包括根据代码的任意生成器矩阵的单个数据进行的纠错对（ECP）或纠错阵列（ECA）的盲目重建。 ECP提供了一种解码算法，可校正多达（（{{d ^ {*}-1-g}）/ {2}）（（d ∗ −1-g）/ 2）个错误，其中d ^ {*} d ∗表示设计距离，gg表示相应曲线的类，而使用ECA时，解码算法最多可以校正（（{d ^ {*}-1}）/ {2}）（（d ∗ −1） / 2）错误。粗略地说，对于在mathbb {F} _ {q} Fq上长度为nn的公共代码，这些攻击以mathbb F_ {q中的O（n ^ {4} log（n））O（n4log（n））个操作运行} Fq用于重建ECP，O（n ^ {5}）O（n5）操作用于重建ECA。概率捷径可以将复杂度分别降低为O（n ^ {3 + varepsilon} log（n））O（n3 +εlog（n））和O（n ^ {4 + varepsilon}）O（n4 +ε） 。与先前因Faure和Minder造成的已知攻击相比，我们的攻击对任意属曲线上的代码有效。此外，我们研究了这些方法在多大程度上适用于AG码的子码。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号