基于可满足性问题的非对称密码方案设计

孙 瑞，黄佳文，孙学贵

（上饶师范学院，江西 上饶 334001）

1 研究背景

公钥加密(非对称加密）体制是保障用户信息传输安全的重要工具,其构造往往基于一些难解的困难性问题以保障加密体制的安全性。 可满足性问题(SAT）是著名的NPC问题,相对于其他问题假设来说是应用在密码方案里较少的类型,由于其在一定条件下的难解性,我们考虑以此为基础建立密码系统。Schmittner［1］首先基于 SAT 问题构造了一个同态加密算法, 但安全性并未严格的证明。 而 Thomas 和Chaudhari［2］结合基于 SAT 与 RSA 算法的优点提出了混合密码协议,虽然加密过程更简便了,但所满足的安全级别并未给出。

另一方面,值得关注的是,布尔表达式的临界值决定了其可满足性与难解性。 Zhou 等人［3］在前人方法的基础上详细证明了(k,s）- SAT临界值的更为精确的取值范围。 我们的算法就是基于以上理论前提来构造的,下面我们将介绍此算法的详细加、解密过程,接着针对方案来证明过程是正确的,并且是选择明文攻击安全的,最后总结此算法的优缺点以及未来的研究方向。

2 方案介绍

3 方案分析

3.1 正确性分析

3.2 安全性分析

这一节,我们将分情况具体分析此密码方案将会遇到的挑战以及其安全性。

3.2.1 挑战阶段

攻击者随机抽取不同明文M0,M1发送给模拟器,模拟器通过硬币随机在其中选择一个密文Mb(b∈｛0,1｝） 对其加密,攻击者获得密文后猜测一个值b′。

3.2.2 猜测阶段

在询问加密机阶段,多项式时间内所获得的明文-密文对是有限的。

(1）设在挑战阶段生成的密文与在询问阶段所获密文相同的概率为P1。 已知F所包含的变量组合项数为而每个Ck的项数在1 至8 项之间；除此之外,fk中的项数为1 项至(2N-3-1） 项,从而Ckfk将包含 1 项至 8(2N-3- 1） 项。 因此,式子的项数是m至 8(2N-3- 1）m项。

因此,攻击者猜对b′的可能性是可以忽略的函数。另外,由于本方案的相变点恰当的设置足以保证实例的难解性,从而能够证明此方案符合选择明文攻击安全(IND-CPA 安全）。

4 结语

这里我们基于(3,s）- SAT的困难性问题提出了一个非对称密码系统。 相比方案［1］,文章改进了SRR(N,k,s） 模型,同时将约束密度控制在使得(3,s）- SAT合取范式难解的范围,由此提升了算法的安全级别。 但其方案仍然存在不足,就是虽然确保了算法的安全性,但存在低效的弊端。 所以,如何既提升其安全性又能提高效率以及通过相关密码学方法使其满足同态性等良好的性质是接下来需要考虑的问题。