高级搜索

列表译码在密码中的应用综述

张卓然 张煌 张方国

引用本文: 张卓然, 张煌, 张方国. 列表译码在密码中的应用综述[J]. 电子与信息学报, doi: 10.11999/JEIT190851 shu
Citation:  Zhuoran ZHANG, Huang ZHANG, Fangguo ZHANG. Survey on Applications of List Decoding in Cryptography[J]. Journal of Electronics and Information Technology, doi: 10.11999/JEIT190851 shu

列表译码在密码中的应用综述

    作者简介: 张卓然: 女,1995年生,博士生,研究方向为基于纠错码的密码学;
    张煌: 男,1988年生,博士生,研究方向为格密码和零知识;
    张方国: 男,1972年生,教授,研究方向为密码学理论及其应用,特别是椭圆曲线密码体制、安全多方计算、可证明安全性等
    通讯作者: 张方国,isszhfg@mail.sysu.edu.cn
  • 基金项目: 国家自然科学基金(61672550, 61972429),国家重点研发计划(2017YFB0802503)

摘要: 列表译码自上世纪50年代提出以来,不仅在通信与编码等方面得到了广泛应用,也在计算复杂性理论和密码学领域有着广泛的应用。近年来,随着量子计算的发展,基于整数分解等传统困难问题设计的密码方案受到了巨大的威胁。由于编码理论中一些计算问题的NP困难性被广泛认为是量子概率多项式时间不可攻克的,建立在其上的基于纠错码的密码体制得到了越来越多的重视,列表译码也越来越引起人们的关注。该文系统梳理了列表译码在密码学中的应用,包括早期在证明任何单向函数都存在硬核谓词、设计叛徒追踪方案、以多项式重建作为密码原语设计公钥方案、改进传统基于纠错码的密码方案和求解离散对数问题等方面的应用,以及近期,列表译码在设计安全通信协议、求解椭圆曲线离散对数问题、设计新的基于纠错码的密码方案等方面的应用。该文对列表译码的算法改进及其在密码协议设计和密码分析中的应用、新应用场景探索等方面的发展趋势进行了探讨。

English

    1. [1]

      BERLEKAMP E R, MCELIECE R J, and VAN TILBORG H C A. On the inherent intractability of certain coding problems (Corresp.)[J]. IEEE Transactions on Information Theory, 1978, 24(3): 384–386. doi: 10.1109/TIT.1978.1055873

    2. [2]

      MCELIECE R J. A public-key cryptosystem based on algebraic coding theory[R]. DSN Progress Report 42-44, 1978: 114–116.

    3. [3]

      ELIAS P. List decoding for noisy channels[R]. Technical Report 335, 1957: 94–104.

    4. [4]

      GOLDREICH O and LEVIN L A. A hard-core predicate for all one-way functions[C]. Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, Seattle, Washington, United States, 1989: 25–32. doi: 10.1145/73007.73010.

    5. [5]

      SUDAN M. Decoding of Reed Solomon codes beyond the error-correction bound[J]. Journal of Complexity, 1997, 13(1): 180–193. doi: 10.1006/jcom.1997.0439

    6. [6]

      GURUSWAMI V and SUDAN M. Improved decoding of Reed-Solomon and algebraic-geometry codes[J]. IEEE Transactions on Information Theory, 1999, 45(6): 1757–1767. doi: 10.1109/18.782097

    7. [7]

      GURUSWAMI V and SUDAN M. On representations of algebraic-geometric codes for list decoding[C]. Proceedings of the 8th Annual European Symposium, Saarbrücken, Germany, 2000: 244–255. doi: 10.1007/3-540-45253-2_23.

    8. [8]

      GOPALAN P, KLIVANS A R, and ZUCKERMAN D. List-decoding Reed-Muller codes over small fields[C]. Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, 2008: 265–274. doi: 10.1145/1374376.1374417.

    9. [9]

      SUDAN M. List decoding: Algorithms and applications[C]. Proceedings of International Conference IFIP TCS 2000 Sendai, Japan, 2000: 25–41. doi: 10.1007/3-540-44929-9_3.

    10. [10]

      BLUM M and MICALI S. How to generate cryptographically strong sequences of pseudo random bits[C]. Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, Chicago, USA, 1982: 112–117. doi: 10.1109/SFCS.1982.72.

    11. [11]

      AKAVIA A, GOLDWASSER S, and SAFRA S. Proving hard-core predicates using list decoding[C]. Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, Cambridge, USA, 2003: 146–157. doi: 10.1109/SFCS.2003.1238189.

    12. [12]

      王明强, 庄金成. 基于列表译码方法在查询访问模型下含错学习问题的分析[J]. 电子与信息学报, 2020, 42(2): 322–326. doi: 10.11999/JEIT190624
      WANG Mingqiang and ZHUANG Jincheng. Analysis of learning with errors in query access model: A list decoding approach[J]. Journal of Electronics &Information Technology, 2020, 42(2): 322–326. doi: 10.11999/JEIT190624

    13. [13]

      MORILLO P and RÀFOLS C. The security of all bits using list decoding[C]. Proceedings of the 12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, 2009: 15–33.

    14. [14]

      谢小容, 吕克伟, 王鲲鹏. ax + b mod p比特安全的列表译码证明[J]. 系统科学与数学, 2012, 32(11): 1366–1376.
      XIE Xiaorong, LV Kewei, and WANG Kunpeng. Proving the security of all bits of ax + b mod p using list decoding[J]. Journal of Systems Science and Mathematical Sciences, 2012, 32(11): 1366–1376.

    15. [15]

      DUC A and JETCHEV D. Hardness of computing individual bits for one-way functions on elliptic curves[C]. Proceedings of the 32nd Annual Cryptology Conference, Santa Barbara, USA, 2012: 832–849. doi: 10.1007/978-3-642-32009-5_48.

    16. [16]

      FAZIO N, GENNARO R, PERERA I M, et al. Hard-core predicates for a Diffie-Hellman problem over finite fields[C]. Proceedings of the 33rd Annual Cryptology Conference, Santa Barbara, USA, 2013: 148–165. doi: 10.1007/978-3-642-40084-1_9.

    17. [17]

      WANG Mingqiang, ZHAN Tao, and ZHANG Haibin. Bit security of the CDH problems over finite fields[C]. Proceedings of the 22nd International Conference on Selected Areas in Cryptography, Sackville, 2015: 441–461.

    18. [18]

      KAWACHI A and YAMAKAMI T. Quantum hardcore functions by complexity-theoretical quantum list decoding[C]. Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, Venice, 2006: 216–227.

    19. [19]

      BONEH D and FRANKLIN M. An efficient public key traitor tracing scheme[C]. Proceedings of the 19th Annual International Cryptology Conference Santa Barbara, Santa Barbara, USA, 1999: 338–353. doi: 10.1007/3-540-48405-1_22.

    20. [20]

      FERNANDEZ M and SORIANO M. Identification of traitors in algebraic-geometric traceability codes[J]. IEEE Transactions on Signal Processing, 2004, 52(10): 3073–3077. doi: 10.1109/TSP.2004.833858

    21. [21]

      FAZIO N, NICOLOSI A, and PHAN D H. Traitor tracing with optimal transmission rate[C]. Proceedings of the 10th International Conference on Information Security, Valparaíso, Chile, 2007: 71–88. doi: 10.1007/978-3-540-75496-1_5.

    22. [22]

      PHAN D H. Traitor tracing for stateful pirate decoders with constant ciphertext rate[C]. Proceedings of the First International Conference on Cryptology in Vietnam, Hanoi, Vietnam, 2006: 354–365. doi: 10.1007/11958239_24.

    23. [23]

      SIRVENT T. Traitor tracing scheme with constant ciphertext rate against powerful pirates[EB/OL]. https://eprint.iacr.org/2006/383, 2019.

    24. [24]

      SILVERBERG A, STADDON J, and WALKER J L. Efficient traitor tracing algorithms using list decoding[C]. Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security Gold Coast, Gold Coast, Australia, 2001: 175–192. doi: 10.1007/3-540-45682-1_11.

    25. [25]

      SILVERBERG A, STADDON J, and WALKER J L. Applications of list decoding to tracing traitors[J]. IEEE Transactions on Information Theory, 2003, 49(5): 1312–1318. doi: 10.1109/TIT.2003.810630

    26. [26]

      BARBIER M and BARRETO P S L M. Key reduction of McEliece's cryptosystem using list decoding[C]. Proceedings of 2011 IEEE International Symposium on Information Theory Proceedings, St. Petersburg, Russia, 2011: 2681–2685. doi: 10.1109/ISIT.2011.6034058.

    27. [27]

      KIAYIAS A and YUNG M. Secure games with polynomial expressions[C]. Proceedings of the 28th International Colloquium on Automata, Languages, and Programming, Crete, Greece, 2001: 939–950. doi: 10.1007/3-540-48224-5_76.

    28. [28]

      KIAYIAS A and YUNG M. Polynomial reconstruction based cryptography[C]. Proceedings of the 8th Annual International Workshop on Selected Areas in Cryptography, Toronto, Ontario, Canada, 2001: 129–133. doi: 10.1007/3-540-45537-X_10.

    29. [29]

      KIAYIAS A and YUNG M. Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice[C]. Proceedings of the 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, 2004: 401-416. doi: 10.1007/978-3-540-30539-2_28.

    30. [30]

      KIAYIAS A and YUNG M. Cryptographic hardness based on the decoding of Reed-Solomon codes[J]. IEEE Transactions on Information Theory, 2008, 54(6): 2752–2769. doi: 10.1109/TIT.2008.921876

    31. [31]

      CHENG Qi and WAN Daqing. On the list and bounded distance decodibility of Reed-Solomon codes[C]. Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy, 2004: 335–341. doi: 10.1109/FOCS.2004.46.

    32. [32]

      CHENG Qi. On the bounded sum-of-digits discrete logarithm problem in finite fields[C]. Proceedings of the 24th Annual International Cryptology Conference, Santa Barbara, USA, 1999: 201–212. doi: 10.1007/978-3-540-28628-8_12.

    33. [33]

      WANG Pengwei and SAFAVI-NAINI R. Interactive message transmission over adversarial wiretap channel Ⅱ[C]. Proceedings of IEEE INFOCOM 2017-IEEE Conference on Computer Communications, Atlanta, USA, 2017: 1–9. doi: 10.1109/INFOCOM.2017.8057120.

    34. [34]

      ZHANG Fangguo and LIU Shengli. Solving ECDLP via list decoding[EB/OL]. https://eprint.iacr.org/2018/795.pdf, 2019.

    35. [35]

      MÁRQUEZ-CORBELLA I and TILLICH J P. Using Reed-Solomon codes in the (U|U+V) construction and an application to cryptography[C]. Proceedings of 2016 IEEE International Symposium on Information Theory, Barcelona, Spain, 2016: 930–934. doi: 10.1109/ISIT.2016.7541435.

    36. [36]

      ZHANG Fangguo and ZHANG Zhuoran. ECC2: Error correcting code and elliptic curve based cryptosystem[C]. Proceedings of the 11th International Symposium Cyberspace Safety and Security, Guangzhou, 2019: 214–229.

    37. [37]

      ZHANG F, ZHANG Z, and GUAN P. ECC2: Error correcting code and elliptic curve based cryptosystem (full version)[J]. Submit to Information Science. (未找到本条文献信息, 请核对)

    38. [38]

      GOPPA V D. Codes on algebraic curves[J]. Soviet Math Dokl, 1981, 24: 170–172.

    39. [39]

      JANWA H and MORENO O. McEliece public key cryptosystems using algebraic-geometric codes[J]. Designs, Codes and Cryptography, 1996, 8(3): 293–307. doi: 10.1023/A:1027351723034

    40. [40]

      HØHOLDT T, VAN LINT J H, and PELLIKAAN R. Algebraic geometry codes[M]. LUISA B. Handbook of Coding Theory. Amsterdam: Elsevier Science Inc., 1998: 871-961.

    41. [41]

      SHOKROLLAHI M A and WASSERMAN H. List decoding of algebraic-geometric codes[J]. IEEE Transactions on Information Theory, 1999, 45(2): 432–437. doi: 10.1109/18.748993

    42. [42]

      WU Xinwen and SIEGEL P H. Efficient root-finding algorithm with application to list decoding of algebraic-geometric codes[J]. IEEE Transactions on Information Theory, 2001, 47(6): 2579–2587. doi: 10.1109/18.945273

    43. [43]

      TRIFONOV P. On the root finding step in list decoding of folded Reed-Solomon codes[EB/OL]. http://arxiv.org/abs/1103.1958v3, 2019.

    44. [44]

      MURALIDHARA V N and SEN S. Improvements on the Johnson bound for Reed-Solomon codes[J]. Discrete Applied Mathematics, 2009, 157(4): 812–818. doi: 10.1016/j.dam.2008.06.014

    45. [45]

      GURUSWAMI V and XING Chaoping. List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the singleton bound[C]. Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, Palo Alto, USA, 2013: 843–852. doi: 10.1145/2488608.2488715.

    46. [46]

      NAOR M and PINKAS B. Oblivious transfer and polynomial evaluation[C]. Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, Atlanta, USA, 1999: 245–254. doi: 10.1145/301250.301312.

    47. [47]

      BLEICHENBACHER D, KIAYIAS A, and YUNG M. Decoding of interleaved Reed Solomon codes over noisy data[C]. Proceedings of the 30th International Colloquium on Automata, Languages, and Programming, Eindhoven, The Netherlands, 2003: 97–108. doi: 10.1007/3-540-45061-0_9.

    48. [48]

      AUGOT D and FINIASZ M. A public key encryption scheme based on the polynomial reconstruction problem[C]. Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, 2003: 229–240. doi: 10.1007/3-540-39200-9_14.

    49. [49]

      CORON J S. Cryptanalysis of a public-key encryption scheme based on the polynomial reconstruction problem[C]. Proceedings of the 7th International Workshop on Theory and Practice in Public Key Cryptography, Singapore, 2004: 14–27. doi: 10.1007/978-3-540-24632-9_2.

    50. [50]

      JUSTESEN J and HOHOLDT T. Bounds on list decoding of MDS codes[J]. IEEE Transactions on Information Theory, 2001, 47(4): 1604–1609. doi: 10.1109/18.923744

    51. [51]

      NIEBUHR R, CAYREL P L, BULYGIN S, et al. On lower bounds for information set decoding over Fq[C]. Proceedings of the 2nd International Conference on Symbolic Computation and Cryptography - SCC 2010, Egham, UK, 2010: 143–157.

    52. [52]

      FAUGÈRE J C, OTMANI A, PERRET L, et al. Algebraic cryptanalysis of mcEliece variants with compact keys[C]. Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, 2010: 279–298. doi: 10.1007/978-3-642-13190-5_14.

    53. [53]

      OZAROW L H and WYNER A D. Wire-tap channel Ⅱ[C]. Proceedings of EUROCRYPT 1984 A Workshop on the Theory and Application of Cryptographic Techniques, Paris, France, 1984: 33–50. doi: 10.1007/3-540-39757-4_5.

    54. [54]

      TAL I and VARDY A. List decoding of polar codes[J]. IEEE Transactions on Information Theory, 2015, 61(5): 2212–2216. doi: 10.1109/TIT.2015.2410251

    55. [55]

      王琼, 罗亚洁, 李思舫. 基于分段循环冗余校验的极化码自适应连续取消列表译码算法[J]. 电子与信息学报, 2019, 41(7): 1572–1578. doi: 10.11999/JEIT180716
      WANG Qiong, LUO Yajie, and LI Sifang. Polar adaptive successive cancellation list decoding based on segmentation cyclic redundancy check[J]. Journal of Electronics &Information Technology, 2019, 41(7): 1572–1578. doi: 10.11999/JEIT180716

    56. [56]

      王美洁, 郭锐. 极化码低时延列表连续删除译码算法[J]. 通信技术, 2016, 49(3): 270–273. doi: 10.3969/j.issn.1002-0802.2016.03.004
      WANG Meijie and GUO Rui. Reduced-latency successive cancellation list decoding for polar code[J]. Communications Technology, 2016, 49(3): 270–273. doi: 10.3969/j.issn.1002-0802.2016.03.004

    57. [57]

      HOOSHMAND R, SHOOSHTARI M K, EGHLIDO T, et al. Reducing the key length of McEliece cryptosystem using polar codes[C]. Proceedings of the 11th International ISC Conference on Information Security and Cryptology, Tehran, Iran, 2014: 104–108. doi: 10.1109/ISCISC.2014.6994031.

    58. [58]

      SHRESTHA S R and KIM Y S. New McEliece cryptosystem based on polar codes as a candidate for post-quantum cryptography[C]. Proceedings of the 14th International Symposium on Communications and Information Technologies, Incheon, South Korea, 2014: 368–372. doi: 10.1109/ISCIT.2014.7011934.

    59. [59]

      BARDET M, CHAULET J, DRAGOI V, et al. Cryptanalysis of the McEliece public key cryptosystem based on polar codes[C]. Proceedings of the 7th International Workshop, Fukuoka, Japan, 2016: 118–143. doi: 10.1007/978-3-319-29360-8_9.

    60. [60]

      DRIENCOURT Y and MICHON J F. Elliptic codes over fields of characteristics 2[J]. Journal of Pure and Applied Algebra, 1987, 45(1): 15–39. doi: 10.1016/0022-4049(87)90081-8

    61. [61]

      CHENG Qi. Hard problems of algebraic geometry codes[J]. IEEE Transactions on Information Theory, 2008, 54(1): 402–406. doi: 10.1109/TIT.2007.911213

    62. [62]

      SIDELNIKOV V M and SHESTAKOV S O. On insecurity of cryptosystems based on generalized Reed-Solomon codes[J]. Discrete Mathematics and Applications, 1992, 2(4): 439–444.

    63. [63]

      MINDER L. Cryptography based on error correcting codes[D]. [Ph.D. dissertation], EPFL, 2007.

    64. [64]

      FAURE C and MINDER L. Cryptanalysis of the McEliece cryptosystem over hyperelliptic codes[C]. Proceedings of the 11th international workshop on Algebraic and Combinatorial Coding Theory, Pamporovo, Bulgaria, 2008: 99–107.

    65. [65]

      COUVREUR A, MÁRQUEZ-CORBELLA I, and PELLIKAAN R. A polynomial time attack against algebraic geometry code based public key cryptosystems[C]. Proceedings of 2014 IEEE International Symposium on Information Theory, Honolulu, USA, 2014: 1446–1450. doi: 10.1109/ISIT.2014.6875072.

    66. [66]

      COUVREUR A, MÁRQUEZ-CORBELLA I, and PELLIKAAN R. Cryptanalysis of McEliece cryptosystem based on algebraic geometry codes and their subcodes[J]. IEEE Transactions on Information Theory, 2017, 63(8): 5404–5418. doi: 10.1109/TIT.2017.2712636

    67. [67]

      PELLIKAAN R. On decoding by error location and dependent sets of error positions[J]. Discrete Mathematics, 1992, 106-107: 369–381. doi: 10.1016/0012-365X(92)90567-Y

    68. [68]

      PELLIKAAN R. On the existence of error-correcting pairs[J]. Journal of Statistical Planning and Inference, 1996, 51(2): 229–242. doi: 10.1016/0378-3758(95)00088-7

    1. [1]

      付向群, 鲍皖苏, 史建红, 李发达. 基于多离散对数问题的公钥密码. 电子与信息学报,

    2. [2]

      朱建锋, 安建平, 王爱华. 北斗导航信号BCH译码器中校正子辅助的列表译码算法. 电子与信息学报,

    3. [3]

      王明强, 庄金成. 基于列表译码方法在查询访问模型下含错学习问题的分析. 电子与信息学报,

    4. [4]

      朱士信, 虞艺超. 使用边际信息降低复杂度的分阶统计软判决译码法. 电子与信息学报,

    5. [5]

      张亚玲, 张璟, 王晓峰. 一个高效的基于身份和RSA的紧致多重数字签名方案. 电子与信息学报,

    6. [6]

      王保仓, 韦永壮, 胡予濮. 基于随机背包的公钥密码. 电子与信息学报,

    7. [7]

      李峥, 马智, 吕欣, 冯登国. 基于量子CSS纠错码的量子公钥密码和消息认证. 电子与信息学报,

    8. [8]

      张玉磊, 王欢, 马彦丽, 刘文静, 王彩芬. 可证安全的传统公钥密码-无证书公钥密码异构聚合签密方案. 电子与信息学报,

    9. [9]

      王彩芬, 许钦百, 刘超, 成玉丹, 赵冰. 无证书公钥密码体制→传统公钥基础设施异构环境下部分盲签密方案. 电子与信息学报,

    10. [10]

      梅其祥, 何大可, 郑宇. 基于Waters的ID加密的高效选择密文安全公钥密码体制. 电子与信息学报,

    11. [11]

      李元兴. 用BCH等线性分组码构造McEliece纠错码公钥密码体制. 电子与信息学报,

    12. [12]

      姜正涛, 柳毅, 王育民. 基于LFSR高次剩余问题构造公钥密码体制的研究. 电子与信息学报,

    13. [13]

      王衍波, 张凯泽, 王开华, 端木庆峰, 雷凤宇. 一种新的基于Lucas序列的公钥密码体制. 电子与信息学报,

    14. [14]

      王保仓, 胡予濮. 公钥密码Naccache-Stern的安全性分析. 电子与信息学报,

    15. [15]

      韩立东, 刘明洁, 毕经国. 两种背包型的公钥密码算法的安全性分析. 电子与信息学报,

    16. [16]

      王保仓, 胡予濮. 高密度背包型公钥密码体制的设计. 电子与信息学报,

    17. [17]

      眭晗, 吴文玲. 后量子对称密码的研究现状与发展趋势. 电子与信息学报,

    18. [18]

      李大兴, 李大为. 关于实多项式型公钥密码体制的破译和有关问题的探讨. 电子与信息学报,

    19. [19]

      姜正涛, 张京良, 王育民. 一种新的等价于大整数分解的公钥密码体制研究. 电子与信息学报,

    20. [20]

      刘焕平, 季振洲, 胡铭曾, 方滨兴, 杨义先. 基于离散对数的动态(k,n)-门限方案. 电子与信息学报,

  • 表 1  Guruswami-Sudan列表译码算法${\rm{ListDecode}}({\cal{C}},{{r}},t)$

     输入:有限域${\mathbb{F}_q}$,曲线${\cal{X}}$,除子$G = \alpha Q$和$D$,接受向量${{r} } = ({r_1},{r_2}, ··· ,{r_n})$ 以及错误重量上界$t$。
     初始化:
     (1) 设置表单${\Omega _r}: = \varnothing $;
     (2) 由$n,k,t$计算译码参数$l$,要求$l > \alpha $;一般地,设
      $r = 1 + \frac{{(2g + \alpha )n - 2gt + \sqrt {{{((2g + \alpha )n - 2gt)}^2} - 4({g^2} - 1)({{(n - t)}^2} - \alpha n)} }}{{2{{(n - t)}^2} - \alpha n}}$, $l = r(n - t) - 1$;
     (3) 固定${\cal{L}}(lQ)$的一组极基$\{ {\phi _{ {j_1} } }:1 \le {j_1} \le l - g + 1\} $,使得Q最多为${\phi _{{j_1}}}$的${j_1} + g - 1$次极点;
     (4) 对任意${P_i}$, $1 \le i \le n$,找${\cal{L}}(lQ)$的一组零基$\{ {\psi _{ {j_3} } }:1 \le {j_3} \le l - g + 1\} $,使得${P_i}$为${\psi _{{j_3},{P_i}}}$重数(至少)为${j_3} - 1$的零点;
     (5) 计算集合$\{ {a_{ {P_i},{j_1},{j_3} } } \in {\mathbb{F}_q}:1 \le i \le n,1 \le {j_1},{j_3} \le l - g + 1\} $,使得对任意i和${j_1}$,都有${\phi _{{j_1}}} = {\Sigma _{{j_3}}}{a_{{P_i},{j_1},{j_3}}}{\psi _{{j_3},{P_i}}}$。
     插值:
     令$s = \frac{{l - g}}{\alpha }$,找非零多项式$H \in {\cal{L}}(lQ)[T]$,它具有以下形式
     $H[T] = \displaystyle\sum\limits_{ {j_2} = 0}^s {\displaystyle\sum\limits_{ {j_1} = 1}^{l - g + 1 - \alpha {j_2} } { {h_{ {j_1},{j_2} } }{\phi _{ {j_1} } }{T^{ {j_2} } } } } $;
     其中,系数${h_{{j_1},{j_2}}} \in {\mathbb{F}_q}$满足:至少有一个${h_{{j_1},{j_2}}}$是非零的,且对任意$i \in [n]$,和满足${j_3} + {j_4} \le r$的${j_3} \ge 1,{j_4} \ge 0$,有
     $h_{{j_3},{j_4}}^{(i)} = \sum\limits_{{j_2} = {j_4}}^s {\sum\limits_{{j_1} = 1}^{l - g + 1 - \alpha {j_2}} {\left( \begin{array}{l} {j_2} \\ {j_4} \\ \end{array} \right)r_i^{{j_2} - {j_4}} \cdot {h_{{j_1},{j_2}}}{\alpha _{{x_i},{j_1},{j_3}}} = 0} } $
     求根:
     找到$H[T]$的所有根$h \in {\cal{L}}(\alpha Q) \subseteq {\cal{L}}(lQ)$。对每一个$h$,检查是否对至少$n - t$个$i \in \{ 1,2, ··· ,n\} $有$h({P_i}) = {r_i}$,即$d({{r} },{{c} }) \le t$。如果成立,
     将$h$加入${\Omega _r}$。
     输出:码字列表${\Omega _r}$。
    下载: 导出CSV
  • 加载中
计量
  • PDF下载量:  9
  • 文章访问数:  193
  • HTML全文浏览量:  73
文章相关
  • 通讯作者:  张方国, isszhfg@mail.sysu.edu.cn
  • 收稿日期:  2019-11-01
  • 录用日期:  2020-02-25
  • 网络出版日期:  2020-03-19
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章