Survey on Applications of List Decoding to Cryptography
-
摘要: 列表译码自上世纪50年代提出以来，不仅在通信与编码等方面得到了广泛应用，也在计算复杂性理论和密码学领域有着广泛的应用。近年来，随着量子计算的发展，基于整数分解等传统困难问题设计的密码方案受到了巨大的威胁。由于编码理论中一些计算问题的NP困难性被广泛认为是量子概率多项式时间不可攻克的，建立在其上的基于纠错码的密码体制得到了越来越多的重视，列表译码也越来越引起人们的关注。该文系统梳理了列表译码在密码学中的应用，包括早期在证明任何单向函数都存在硬核谓词、设计叛徒追踪方案、以多项式重建作为密码原语设计公钥方案、改进传统基于纠错码的密码方案和求解离散对数问题(DLP)等方面的应用，以及近期，列表译码在设计安全通信协议、求解椭圆曲线离散对数问题、设计新的基于纠错码的密码方案等方面的应用。该文对列表译码的算法改进及其在密码协议设计和密码分析中的应用、新应用场景探索等方面的发展趋势进行了探讨。Abstract: Since the conception of list decoding is proposed in the 1950s, list decoding not only is applied to communication and coding theory, but also plays a significant role in computational complexity and cryptography. In recent years, with the rapid development of quantum computing, the traditional cryptographic schemes based on factorization and other difficult problems are greatly threatened. The code-based cryptosystems, whose security relies on the NP-hard problems in coding theory, are attracting more and more attention as a candidate of the post-quantum cryptography, and so does the list decoding algorithm. This paper systematically reviews the applications of list decoding to cryptography, including early applications in proving that any one-way function has hard-core bits, designing traitor tracing schemes, designing public key schemes using polynomial reconstruction as cryptographic primitives, improving the traditional code-based cryptosystems and solving Discrete Logarithm Problems (DLP), and recent applications to designing secure communication interactive protocols, solving the elliptic curve discrete logarithm problem, and designs new cryptographic schemes based on error correction codes. Finally, the new research issues of the algorithm improvement of list decoding, its application to the design of cryptographic protocol and cryptoanalysis, and the exploration of new application scenarios are discussed.
-
Key words:
- Public key cryptography /
- List decoding /
- Discrete logarithm /
- Post-quantum cryptography
-
表 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 + \dfrac{{(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 = \dfrac{{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)} = \displaystyle\sum\limits_{{j_2} = {j_4}}^s {\displaystyle\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
-
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 MCELIECE R J. A public-key cryptosystem based on algebraic coding theory[R]. DSN Progress Report 42–44, 1978: 114–116. ELIAS P. List decoding for noisy channels[R]. Technical Report 335, 1957: 94–104. GOLDREICH O and LEVIN L A. A hard-core predicate for all one-way functions[C]. The 21st Annual ACM Symposium on Theory of Computing, Seattle, USA, 1989: 25–32. doi: 10.1145/73007.73010. 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 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 GURUSWAMI V and SUDAN M. On representations of algebraic-geometric codes for list decoding[C]. The 8th Annual European Symposium, Saarbrücken, Germany, 2000: 244–255. doi: 10.1007/3-540-45253-2_23. GOPALAN P, KLIVANS A R, and ZUCKERMAN D. List-decoding Reed-Muller codes over small fields[C]. The 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, 2008: 265–274. doi: 10.1145/1374376.1374417. SUDAN M. List decoding: Algorithms and applications[C]. International Conference IFIP TCS 2000 Sendai, Japan, 2000: 25–41. doi: 10.1007/3-540-44929-9_3. BLUM M and MICALI S. How to generate cryptographically strong sequences of pseudo random bits[C]. The 23rd Annual Symposium on Foundations of Computer Science, Chicago, USA, 1982: 112–117. doi: 10.1109/SFCS.1982.72. AKAVIA A, GOLDWASSER S, and SAFRA S. Proving hard-core predicates using list decoding[C]. The 44th Annual IEEE Symposium on Foundations of Computer Science, Cambridge, USA, 2003: 146–157. doi: 10.1109/SFCS.2003.1238189. 王明强, 庄金成. 基于列表译码方法在查询访问模型下含错学习问题的分析[J]. 电子与信息学报, 2020, 42(2): 322–326. doi: 10.11999/JEIT190624WANG 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 MORILLO P and RÀFOLS C. The security of all bits using list decoding[C]. The 12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, USA, 2009: 15–33. 谢小容, 吕克伟, 王鲲鹏. ax + b mod p比特安全的列表译码证明[J]. 系统科学与数学, 2012, 32(11): 1366–1376.XIE Xiaorong, LÜ 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. DUC A and JETCHEV D. Hardness of computing individual bits for one-way functions on elliptic curves[C]. The 32nd Annual Cryptology Conference, Santa Barbara, USA, 2012: 832–849. doi: 10.1007/978-3-642-32009-5_48. FAZIO N, GENNARO R, PERERA I M, et al. Hard-core predicates for a Diffie-Hellman problem over finite fields[C]. The 33rd Annual Cryptology Conference, Santa Barbara, USA, 2013: 148–165. doi: 10.1007/978-3-642-40084-1_9. WANG Mingqiang, ZHAN Tao, and ZHANG Haibin. Bit security of the CDH problems over finite fields[C]. The 22nd International Conference on Selected Areas in Cryptography, Sackville, 2015: 441–461. KAWACHI A and YAMAKAMI T. Quantum hardcore functions by complexity-theoretical quantum list decoding[C]. The 33rd International Colloquium on Automata, Languages and Programming, Venice, 2006: 216–227. BONEH D and FRANKLIN M. An efficient public key traitor tracing scheme[C]. The 19th Annual International Cryptology Conference Santa Barbara, Santa Barbara, USA, 1999: 338–353. doi: 10.1007/3-540-48405-1_22. 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 FAZIO N, NICOLOSI A, and PHAN D H. Traitor tracing with optimal transmission rate[C]. The 10th International Conference on Information Security, Valparaíso, Chile, 2007: 71–88. doi: 10.1007/978-3-540-75496-1_5. PHAN D H. Traitor tracing for stateful pirate decoders with constant ciphertext rate[C]. The 1st International Conference on Cryptology in Vietnam, Hanoi, Vietnam, 2006: 354–365. doi: 10.1007/11958239_24. SIRVENT T. Traitor tracing scheme with constant ciphertext rate against powerful pirates[EB/OL]. https://eprint.iacr.org/2006/383, 2019. SILVERBERG A, STADDON J, and WALKER J L. Efficient traitor tracing algorithms using list decoding[C]. 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. 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 BARBIER M and BARRETO P S L M. Key reduction of McEliece's cryptosystem using list decoding[C]. 2011 IEEE International Symposium on Information Theory Proceedings, St. Petersburg, Russia, 2011: 2681–2685. doi: 10.1109/ISIT.2011.6034058. KIAYIAS A and YUNG M. Secure games with polynomial expressions[C]. The 28th International Colloquium on Automata, Languages, and Programming, Crete, Greece, 2001: 939–950. doi: 10.1007/3-540-48224-5_76. KIAYIAS A and YUNG M. Polynomial reconstruction based cryptography[C]. The 8th Annual International Workshop on Selected Areas in Cryptography, Toronto, Canada, 2001: 129–133. doi: 10.1007/3-540-45537-X_10. KIAYIAS A and YUNG M. Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice[C]. 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. 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 CHENG Qi and WAN Daqing. On the list and bounded distance decodibility of Reed-Solomon codes[C]. The 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy, 2004: 335–341. doi: 10.1109/FOCS.2004.46. CHENG Qi. On the bounded sum-of-digits discrete logarithm problem in finite fields[C]. The 24th Annual International Cryptology Conference, Santa Barbara, USA, 1999: 201–212. doi: 10.1007/978-3-540-28628-8_12. WANG Pengwei and SAFAVI-NAINI R. Interactive message transmission over adversarial wiretap channel Ⅱ[C]. IEEE INFOCOM 2017-IEEE Conference on Computer Communications, Atlanta, USA, 2017: 1–9. doi: 10.1109/INFOCOM.2017.8057120. ZHANG Fangguo and LIU Shengli. Solving ECDLP via list decoding[EB/OL]. https://eprint.iacr.org/2018/795.pdf, 2019. MÁRQUEZ-CORBELLA I and TILLICH J P. Using Reed-Solomon codes in the (U|U+V) construction and an application to cryptography[C]. 2016 IEEE International Symposium on Information Theory, Barcelona, Spain, 2016: 930–934. doi: 10.1109/ISIT.2016.7541435. ZHANG Fangguo and ZHANG Zhuoran. ECC2: Error correcting code and elliptic curve based cryptosystem[C]. The 11th International Symposium Cyberspace Safety and Security, Guangzhou, China, 2019: 214–229. ZHANG F, ZHANG Z, and GUAN P. ECC2: Error correcting code and elliptic curve based cryptosystem (full version)[J]. Submit to Information Science. GOPPA V D. Codes on algebraic curves[J]. Soviet Math Dokl, 1981, 24: 170–172. 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 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. 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 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 TRIFONOV P. On the root finding step in list decoding of folded Reed-Solomon codes[EB/OL]. http://arxiv.org/abs/1103.1958v3, 2019. 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 GURUSWAMI V and XING Chaoping. List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the singleton bound[C]. The 45th Annual ACM Symposium on Theory of Computing, Palo Alto, USA, 2013: 843–852. doi: 10.1145/2488608.2488715. NAOR M and PINKAS B. Oblivious transfer and polynomial evaluation[C]. The 21st Annual ACM Symposium on Theory of Computing, Atlanta, USA, 1999: 245–254. doi: 10.1145/301250.301312. BLEICHENBACHER D, KIAYIAS A, and YUNG M. Decoding of interleaved Reed Solomon codes over noisy data[C]. The 30th International Colloquium on Automata, Languages, and Programming, Eindhoven, The Netherlands, 2003: 97–108. doi: 10.1007/3-540-45061-0_9. AUGOT D and FINIASZ M. A public key encryption scheme based on the polynomial reconstruction problem[C]. International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, 2003: 229–240. doi: 10.1007/3-540-39200-9_14. CORON J S. Cryptanalysis of a public-key encryption scheme based on the polynomial reconstruction problem[C]. 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. 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 NIEBUHR R, CAYREL P L, BULYGIN S, et al. On lower bounds for information set decoding over Fq[C]. The 2nd International Conference on Symbolic Computation and Cryptography - SCC 2010, Egham, UK, 2010: 143–157. FAUGÈRE J C, OTMANI A, PERRET L, et al. Algebraic cryptanalysis of mcEliece variants with compact keys[C]. The 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, France, 2010: 279–298. doi: 10.1007/978-3-642-13190-5_14. OZAROW L H and WYNER A D. Wire-tap channel Ⅱ[C]. 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. 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 王琼, 罗亚洁, 李思舫. 基于分段循环冗余校验的极化码自适应连续取消列表译码算法[J]. 电子与信息学报, 2019, 41(7): 1572–1578. doi: 10.11999/JEIT180716WANG 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 王美洁, 郭锐. 极化码低时延列表连续删除译码算法[J]. 通信技术, 2016, 49(3): 270–273. doi: 10.3969/j.issn.1002-0802.2016.03.004WANG 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 HOOSHMAND R, SHOOSHTARI M K, EGHLIDO T, et al. Reducing the key length of McEliece cryptosystem using polar codes[C]. The 11th International ISC Conference on Information Security and Cryptology, Tehran, Iran, 2014: 104–108. doi: 10.1109/ISCISC.2014.6994031. SHRESTHA S R and KIM Y S. New McEliece cryptosystem based on polar codes as a candidate for post-quantum cryptography[C]. The 14th International Symposium on Communications and Information Technologies, Incheon, South Korea, 2014: 368–372. doi: 10.1109/ISCIT.2014.7011934. BARDET M, CHAULET J, DRAGOI V, et al. Cryptanalysis of the McEliece public key cryptosystem based on polar codes[C]. The 7th International Workshop, Fukuoka, Japan, 2016: 118–143. doi: 10.1007/978-3-319-29360-8_9. 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 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 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. MINDER L. Cryptography based on error correcting codes[D]. [Ph.D. dissertation], EPFL, 2007. FAURE C and MINDER L. Cryptanalysis of the McEliece cryptosystem over hyperelliptic codes[C]. The 11th international workshop on Algebraic and Combinatorial Coding Theory, Pamporovo, Bulgaria, 2008: 99–107. COUVREUR A, MÁRQUEZ-CORBELLA I, and PELLIKAAN R. A polynomial time attack against algebraic geometry code based public key cryptosystems[C]. 2014 IEEE International Symposium on Information Theory, Honolulu, USA, 2014: 1446–1450. doi: 10.1109/ISIT.2014.6875072. 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 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 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)
计量
- 文章访问数: 3357
- HTML全文浏览量: 1181
- PDF下载量: 175
- 被引次数: 0
