代数操纵检测码及其应用

Algebraic manipulation detection (AMD) codes are a cryptographic topic of interest, and have attracted a lot of attention since 2008. AMD codes can detect algebraic manipulation without using keys, and can be used in many cryptographic applications including secret sharing schemes, secure multi-party computation, etc. The objective of this project is to: 1) investigate the properties of AMD codes, especially to derive and improve some theoretical bounds; 2) construct optimal AMD codes with respect to the theoretical bounds; 3) apply AMD codes in secret sharing schemes, secure multi-party computation, etc. Due to the close relations to other topics including combinatorial designs, algebra, error-correcting codes, frequency-hopping sequences, finite geometry, etc., this project is expected to contribute to not only the theory of cryptography, but also to combinatorics, communication systems, and cyber security.

代数操纵检测码是密码学的研究课题，最近几年吸引了国际众多研究者的注意。代数操纵检测码不引入任何密钥，而是通过编码的方式检测在信息传递中可能发生的代数改变，广泛应用于存在欺骗或第三方敌人篡改的密码学应用场景中，如秘密共享方案、安全多方计算等。本项目主要是运用组合设计等数学工具，研究代数操纵检测码的理论界性质，构造达到参数理论界的代数操纵检测码，并寻求代数操纵检测码在秘密共享方案、安全多方计算等的应用。由于代数操纵检测码与组合设计、代数、纠错码、跳频序列、有限几何等的紧密联系，该项目预期对密码学、组合设计、通信系统等诸多领域都有一定的理论和实际意义。

代数操纵检测码在2008年欧密会中首次被提出，可广泛应用于可能发生第三方敌手篡改存储、传递消息以及有欺骗行为发生的密码学场景中，例如安全多方计算、秘密共享方案等。本项目主要运用组合设计方法，研究代数操纵检测码的相关参数特性；构造达到或接近达到参数理论界的代数操纵检测码；构造相关的一些组合对象，推导新的不存在性结果；尝试应用于安全多方计算、密码共享方案等具体密码学场景中。本项目组成员较好地完成了既定各项任务目标，并对相关研究任务有一定拓展，在国际知名期刊发表论文10篇（SCI检索）、发表会议论文3篇（EI检索），引起国内外相关领域研究者的广泛关注。相关研究结果包括：.1. 新型LDPC码的构造：我们首次引入矩阵几何的方法构造了两类新型LDPC码，并对围长、维数、最小距离、阻止距离等参数进行了深入研究。仿真结果表明，这两类LDPC码具有优于随机LDPC码的良好性能；.2. 几类四元序列的研究：我们利用八阶分圆陪集构造了一类具有良好自相关值的四元序列，扩展了一类现有四元序列的构造，并确定了几类四元序列的线性复杂度；.3. 两类非交换几乎差集的构造：一是拓展McFarland差集构造思想，二是在Dihedral群中构造几乎差集。有猜想在Dihedral群中不存在差集，而我们通过具体构造给出了Dihedral群存在几乎差集的肯定回答；.4. 偏几何设计的构造：通过引入群作用，我们给出一种构造偏几何设计及分组设计的新方法；.5. Kasami指数置换在奇特征有限域上差分谱的确定：通过确定有限域上相关方程解的个数，我们完全确定了Kasami指数置换在奇特征有限域的差分谱，并证明该指数置换具有p+1差分一致性；.6. 特殊函数、线性码支撑无穷类t设计的构造：我们通过二次函数，以及两类线性码，分别构造了它们所支撑的2设计无穷类，并完全确定了相关的参数；.7. (m,n)-广义bent函数不存在性结果的推导：我们将群特征作用于用群环工具对(m,n)-广义bent函数刻画得到的等式，运用数论工具给出了关于(m,n)-广义bent函数新的不存在性结果；.8. 基于强边染色的放置传输表的构造：我们通过传输放置表与二分图强边染色的等价关系，给出了多种将两个或多个二分图的强边染色组合在一起的方法，从而构造了具有更优良参数的传输放置表。