A Hybrid Algorithm for the Regular
Syndrome Decoding Problem
报告专家：张俊 教授（首都师范大学）
报告时间：2月6日（周五）09:00-10:00
报告地点：四川大学数学学院西303
报告摘要：
Regular Syndrome Decoding (RSD) is a variant of the traditional Syndrome Decoding (SD) problem, where the error vector is divided into consecutive, equal-length blocks, each containing exactly one nonzero element. Recently, RSD has gained significant attention due to its extensive applications in cryptographic constructions, including MPC, ZK protocols, and more. The computational complexity of RSD has primarily been analyzed using two methods: Information Set Decoding (ISD) approach and algebraic approach. In this talk, we introduce a new hybrid algorithm for solving the RSD problem. Our new algorithm demonstrates superior performance across a wide range of concrete parameters compared to previous methods, including both ISD and algebraic approaches, for parameter sets over both large fields and binary fields.
专家简介：
张俊，首都师范大学数学科学学院教授，博士生导师，主要研究方向为编码理论与密码学。本科毕业于南开大学陈省身数学试点班，博士毕业于南开大学陈省身数学研究所，曾获留学基金委资助赴美国加州大学欧文分校联合培养，以及美国俄克拉荷马大学学术访问。研究成果主要发表在国内外学术期刊《Math. Ann.》、《IEEE Trans. Info. Theory》、《IEEE TCOM》、《Finite Fields Appls》、《中国科学：数学》等以及国际会议亚密会2025、IEEE ISIT等上。主持国家自然科学基金原优青项目、专项项目、面上项目、青年项目及北京市教委项目等。
邀请人：洪绍方