基于校验子解码问题的伪随机序列理论研究

Pseudo- random sequences are very important in stream cipher, communication technology, radar systems.For examples,they play important roles in delay measurement, radar ranging and noise generator etc, Especially they can be used for one-time-pad cryptosystems and been an important topic in cryptography. Two of the main desired features of such Pseudo- random sequence genarators(PRNG) are to be fast（at least as fast as block cipher scheme）and secure（as secure as particular difficult problems）， and have received much attention.Since the publication of SHor's algorithm in 1994, however, we know that those PRNGS(and other cryptographic applications) based on the problems of factoring and discrete logarithm are threatened by quantum computer attacks. SD problem based cryptography is conjectured to be secure against quantum computer attacks and has several other advantages. Our study focus on the syndroms decoding problems( SD-Problems) based pseudo-random generators. It includs the following: (1) show the efficient construction of the pseudo-random generators based on the intractability of an NP-complete problem from the area of error-correcting codes,it is proved as secure as a hard instance of the syndrome decoding problem. (2)show how to construct the SD-based pweudo-random wequences generators as fast as AES in counter mode. (3)show how to construct light weight generators with a security reduction (4) Attacking and defending syndrom decoding problems based pseudo-random generators.

伪随机序列在序列密码、通信技术、雷达系统等领域中有着重要的作用，如应用于延时测量、雷达测距、噪声产生器等方面。特别在密码系统中，作为密钥流的生成方式，伪随机序列生成器一直是密码工作者关注的重要研究课题，安全、高效、低耗的伪随机序列生成器构造是密码工作者的追求目标。1994年，Shor发表了量子计算攻击方法，这使得人们不得不寻找能够抵抗这些新型攻击的可证明安全的伪随机序列生成器(及密码算法)。基于校验子解码问题（SD问题）的伪随机序列生成器（及密码算法）被认为是能够抵抗这种量子计算攻击的有效方法之一。本项目研究基于校验子解码问题的伪随机序列生成器构造理论，主要内容包括:伪随机序列的安全性规约到校验子解码问题；高效伪随机序列生成器(生成速度不低于AES)设计理论；低耗存储资源的伪随机序列生成器设计理论(如:用于资源受限环境中等)；基于SD问题的伪随机序列生成器的攻击分析与防御技术。

伪随机序列在密码学中有着重要的应用，作为序列密码中密钥流的主要生成方式，伪随机序列的伪随机性决定了序列密码的安全性。此外，伪随机序列在云计算、物联网、区块链等领域有着广泛的应用。安全高效的伪随机序列生成器的构造一直是密码领域重要的研究内容之一。上世纪九十年代，Shor和Grover等量子攻击算法的出现对现有的密码技术造成了巨大的安全威胁，寻找能够抵抗量子攻击的可证明安全的伪随机序列生成器成为密码研究者重点关注的课题。基于校验子解码问题（SD问题）的伪随机序列生成器以及密码算法被认为是能够抵抗这种量子攻击的有效方法之一。本项目主要研究基于校验子解码问题的伪随机序列生成器的构造，主要内容包括：基于校验子解码问题的伪随机序列的安全性分析和规约、高效低耗的伪随机序列生成器设计、伪随机序列生成器的攻击和防御技术。.针对以上内容，经过四年的努力，课题组取得了一系列的研究成果，主要包括：1）基于海绵函数结构的伪随机序列构造方法。海绵函数通过对输入比特串进行吸收和挤压运算，输出不可预测的比特串。我们对海绵函数结构进行适当调整，降低了伪随机序列生成器在存储资源上的消耗，优化了生成器的运算速度和存储资源消耗。2）布尔函数作为伪随机序列生成器的滤波函数或者组合函数, 对密码算法及密码系统有着极其重要的作用。为了使构造的密码体制能够抵抗不同的攻击和适应不同的需求，需要构造具有优良密码学性质的布尔函数。我们对布尔函数的非线性度、代数次数和代数免疫度等密码学性质进行了研究，取得了有益的成果。3）伪随机序列作为密码学中的基础性理论和工具，具有广阔的用途，我们研究了伪随机序列在数字签名、云计算、密码协议和区块链中的应用，得到了一系列有价值的成果。.这些研究成果不仅在理论上对已有的伪随机序列生成技术进行了较为重要的改进，同时还丰富了基于编码的密码算法的研究内容和研究领域，为后量子密码的科研与实践奠定了坚实的基础。