列表譯碼在密碼中的應(yīng)用綜述
doi: 10.11999/JEIT190851
-
1.
中山大學(xué)數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院 廣州 510006
-
2.
廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室 廣州 510006
Survey on Applications of List Decoding to Cryptography
-
1.
School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006, China
-
2.
Guangdong Key Laboratory of Information Security, Guangzhou 510006, China
-
摘要: 列表譯碼自上世紀(jì)50年代提出以來,不僅在通信與編碼等方面得到了廣泛應(yīng)用,也在計(jì)算復(fù)雜性理論和密碼學(xué)領(lǐng)域有著廣泛的應(yīng)用。近年來,隨著量子計(jì)算的發(fā)展,基于整數(shù)分解等傳統(tǒng)困難問題設(shè)計(jì)的密碼方案受到了巨大的威脅。由于編碼理論中一些計(jì)算問題的NP困難性被廣泛認(rèn)為是量子概率多項(xiàng)式時(shí)間不可攻克的,建立在其上的基于糾錯(cuò)碼的密碼體制得到了越來越多的重視,列表譯碼也越來越引起人們的關(guān)注。該文系統(tǒng)梳理了列表譯碼在密碼學(xué)中的應(yīng)用,包括早期在證明任何單向函數(shù)都存在硬核謂詞、設(shè)計(jì)叛徒追蹤方案、以多項(xiàng)式重建作為密碼原語設(shè)計(jì)公鑰方案、改進(jìn)傳統(tǒng)基于糾錯(cuò)碼的密碼方案和求解離散對數(shù)問題(DLP)等方面的應(yīng)用,以及近期,列表譯碼在設(shè)計(jì)安全通信協(xié)議、求解橢圓曲線離散對數(shù)問題、設(shè)計(jì)新的基于糾錯(cuò)碼的密碼方案等方面的應(yīng)用。該文對列表譯碼的算法改進(jìn)及其在密碼協(xié)議設(shè)計(jì)和密碼分析中的應(yīng)用、新應(yīng)用場景探索等方面的發(fā)展趨勢進(jìn)行了探討。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})$ 以及錯(cuò)誤重量上界$t$。 初始化: (1) 設(shè)置表單${\Omega _r}: = \varnothing $; (2) 由$n,k,t$計(jì)算譯碼參數(shù)$l$,要求$l > \alpha $;一般地,設(shè)
$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$次極點(diǎn); (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}}}$重?cái)?shù)(至少)為${j_3} - 1$的零點(diǎn); (5) 計(jì)算集合$\{ {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 }$,找非零多項(xiàng)式$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} } } } } $;其中,系數(shù)${h_{{j_1},{j_2}}} \in {\mathbb{F}_q}$滿足:至少有一個(gè)${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)$。對每一個(gè)$h$,檢查是否對至少$n - t$個(gè)$i \in \{ 1,2, ··· ,n\} $有$h({P_i}) = {r_i}$,即$d({{r} },{{c} }) \le t$。如果成
立,將$h$加入${\Omega _r}$。輸出:碼字列表${\Omega _r}$。 下載: 導(dǎo)出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. 王明強(qiáng), 莊金成. 基于列表譯碼方法在查詢訪問模型下含錯(cuò)學(xué)習(xí)問題的分析[J]. 電子與信息學(xué)報(bào), 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]. 系統(tǒng)科學(xué)與數(shù)學(xué), 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 王瓊, 羅亞潔, 李思舫. 基于分段循環(huán)冗余校驗(yàn)的極化碼自適應(yīng)連續(xù)取消列表譯碼算法[J]. 電子與信息學(xué)報(bào), 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 王美潔, 郭銳. 極化碼低時(shí)延列表連續(xù)刪除譯碼算法[J]. 通信技術(shù), 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 -
計(jì)量
- 文章訪問數(shù): 3600
- HTML全文瀏覽量: 1252
- PDF下載量: 190
- 被引次數(shù): 0