Survey on Applications of List Decoding to Cryptography

Zhuoran ZHANG; Huang ZHANG; Fangguo ZHANG

doi:10.11999/JEIT190851

Volume 42 Issue 5

Jun. 2020

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2020 > 42(5): 1049-1060

Zhuoran ZHANG, Huang ZHANG, Fangguo ZHANG. Survey on Applications of List Decoding to Cryptography[J]. Journal of Electronics & Information Technology, 2020, 42(5): 1049-1060. doi: 10.11999/JEIT190851

Citation:

Zhuoran ZHANG, Huang ZHANG, Fangguo ZHANG. Survey on Applications of List Decoding to Cryptography[J]. Journal of Electronics & Information Technology, 2020, 42(5): 1049-1060. doi: 10.11999/JEIT190851

Citation:

PDF( 609 KB)

Survey on Applications of List Decoding to Cryptography

doi: 10.11999/JEIT190851

1.
School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006, China
2.
Guangdong Key Laboratory of Information Security, Guangzhou 510006, China

Funds: The National Natural Science Foundation of China (61672550, 61972429), The National Key R & D Program of China (2017YFB0802503)

Received Date: 2019-11-01
Rev Recd Date: 2020-02-25

Available Online: 2020-03-19

Publish Date: 2020-06-04

Abstract

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.
- Public key cryptography,
- List decoding,
- Discrete logarithm,
- Post-quantum cryptography

FullText(HTML)

References(68)

References

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/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

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. ECC²: 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. ECC²: 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 F_q[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/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

王美洁, 郭锐. 极化码低时延列表连续删除译码算法[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

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

Relative Articles

Supplements(0)

Cited By

Proportional views