作者简介:赵博(1988-),男,博士研究生.研究方向:图像处理,信息安全. E-mail:wolfers509@126.com
通过引入“半陷门单向函数”的概念来构造公钥密码,与陷门单向函数不同,由于半陷门单向函数是“半可逆”的,所以不能单独用来构造公钥密码。为此本文提出了一种基于半陷门单向函数的公钥密码构造方法。并结合SSP(子集和问题)的难解性和易解性,构造了“半超递增背包向量”,并基于半超递增背包向量对半陷门单向函数进行了具体实现。在此基础上,给出了一种新的公钥密码方案STOF_PKC。该方案在分类上属于背包密码,因而具有抗量子计算的潜力。
In this paper, we introduce the concept of Semi-trapdoor One-way Function (STOF) to implement the Public Key Cryptosystem (PKC), which is different from the One-way Function. STOF is semi-invertible, so it can be directly used to implement the PKC. For this characteristic we develop a method to construct a PKC based on the STOF. Combined with the difficulty and solvability of the Subset Sum Problem (SSP), we can construct a Semi-supper Increasing Knapsack (SSIK). Based on SSIK a scheme of STOF is designed and realized. ON this basis, we propose two new knapsack public key schemes, STOF_PKC. STOF_PKC belongs to knapsack cryptosystem, thus has the potential to resist quantum attack.
1976年, Diffie和Hellman[1]发表了著名文章《密码学的新方向” , 文章引入了“ 公钥密码” 的概念, 并提出基于“ 陷门单向函数(Trapdoor one-way function)” 来构造公钥密码的思想。不久, 第一批公钥密码方案便被提了出来, 它们分别是Merkle和Hellman基于背包问题的MH密码体制[2]以及Rivest、Shamir和Adelman基于整数分解问题的RSA密码体制[3]。随后Rabin、ElGamal、ECC等公钥密码体制也相继问世。
进入到21世纪, 现有公钥密码(RSA、ElGamal、ECC等)日益受到量子计算的威胁[4, 5], 为了应对挑战, 国际密码学界提出了“ 后量子密码学(Post-quantum cryptography, PQC)” 的新学科方向。PQC的主要目标便是研究能抵抗量子计算的公钥密码(Quantum resistant public key cryptography), 目前主要基于量子计算机不擅长计算的数学难题(比如NPC问题)来设计密码, 该类密码主要有如下几个研究方向:基于格上困难问题的密码[6]、基于纠错码译码问题的密码[7]、基于多变量的密码[8]、基于辫子群(Braid Group)的密码[9]以及基于背包问题的密码[2, 10]。
但目前所提出的抗量子计算公钥密码方案中的绝大多数都已被证明是不安全的。尽管不断有新方案被提出, 但从构造方法来看, 这些方案不外乎两大类:其一是基于“ 陷门单向函数” , 这类公钥密码占绝大多数, 其关键在于如何设计陷门。其二则是基于“ 非对称密钥交换” , 其关键在于如何实现非对称的密钥交换, 这往往要用到“ 单向函数” 。一般说来, 寻找单向函数要比寻找陷门单向函数容易得多, 但单向函数不可逆, 故不能直接用来实现公钥密码。而利用陷门单向函数虽可直接实现公钥密码, 但由于“ 陷门性” 和“ 单向性” 的固有矛盾, 使得二者很难兼顾。为了构造陷门, 就必然要牺牲单向性; 反之亦然。
本文重点研究了如何设计实现半陷门单向函数, 以及如何基于半陷门单向函数来构造公钥密码。
为了同时兼顾陷门性和单向性, 本文引入了“ 半陷门单向函数(Semi-trapdoor one-way function, STOF)” 的概念, 其定义如下:
定义1 “ 半陷门单向函数” 是一族“ 半可逆” 的陷门函数:ft:X→ Y, 满足:
(1)已知ft和x∈ X, 计算y=ft(x)是容易的。
(2)已知ft、y=ft(x), 计算x=
(3)已知ft、y=ft(x)、t(陷门), 计算x=
由于半陷门单向函数分别涉及单向性和陷门性, 所以在设计时要同时对二者进行构思, 这就需要选择合适的困难问题。为便于描述, 文中常用的术语和基本符号如表1所示。
“ 子集和问题(Subset sum problem, SSP, )” 是“ 0-1背包问题” 的一个特例。其定义如下:
定义2(SSP) 给定A=(a1, a2, …, an)∈
SSP是著名的NPC问题。大多数背包密码都是基于SSP来构造的。为了保证解密的唯一性, 公钥背包向量还必须满足USS(Unique Subset Sum), 即唯一子集和条件。但已有的的背包密码通常无法抵御“ 低密度攻击” , 背包向量的“ 密度” 定义如下:
定义3 A=(a1, a2, …, an)∈
由文献[11-13], 若DA> 1, 则A通常不满足USS条件。事实上, 很多USS背包向量的密度都≪1。早期算法[14]可破解密度小于0.6463的背包密码, 改进后算法[15]则可破解密度小于0.9408的背包密码。故为了抵御低密度攻击, 公钥背包除应满足USS条件外, 还应具有高密度(大于0.9408), 但这二者往往很难兼顾, 这也是设计背包密码的难点所在。
若DA< 1∧ DA≈ 1, 则A中SSP通常有唯一解。而若DA> 1∧ DA≈ 1, 则A中SSP通常有多解。这两种情形均易受到基于格的攻击[16, 17]。只有当DA≈ 1时, 对A中SSP无有效的解法。Impagliazzo和Naor亦证明, 当DA=1时, 求解A中SSP是最困难的[18]。多年来, 对SSP最快的通用解法仍是Schroeppel和Shamir在1981年提出的[19], 算法的时空复杂度分别为O(n· 2n/2)和O(n· 2n/4)。最近才有人对其进行了优化[20], 但改进算法仍是指数级的, 只是将时间复杂度降为O(n· 2n/3)。
若在[1, 2n]中均匀随机选择A=(a1, …, an), 则A通常是难解的。实验发现, 如此得到的A通常不满足USS条件。实际上, 当DA≈ 1时, 判定A是否满足USS条件亦是NPC问题[21]。
可基于SSP的难解和易解性来设计半陷门单向函数。为此引入“ 半超递增背包向量” 的定义如下:
定义4 若A=(a1, a2, …, a2n)∈
显然, 对于半超递增背包向量, 可快速求出其SSP解的后半部, 且易证如下定理:
定理1 若A=(a1, …, a2n)∈
(1)A中SSP易解当且仅当A
(2)A为USS背包当且仅当A
(3)若A
基于半超递增背包向量, 可得半陷门单向函数ft:{0, 1}2n→ N的设计方案如下:
(1)选择安全参数n;
(2)在[1, 2n]中均匀随机选择(a1, …, an)∈
(3)随机选取rj∈
(4)随机选取M, W∈ N+, 其中:
(5)随机选取(1, 2, …, 2n)的置换π , 并用(π , M, W)对A模乘变换得B=(b1, b2, …, b2n), 其中 bπ (i)=Wai(modM);
(6)以t=(A, π , M, W-1)为陷门(A不用全保存, 仅保存A[n+1, 2n]即可), 并将B公开;
(7)对于x∈ {0, 1}2n, 定义ft(x)=
由A
ft的安全性取决于两种攻击的难度:其一是由(B, ft(x)=
首先分析对ft的第一种攻击:这与DB密切相关, 由于(a1, a2, …, an)是在[1, 2n]中均匀随机选择, 将[1, 2n]分成等长的n段
由此推出M和W的阶(Order)均为O(n· 22n), 即有估值公式:DB≈
对于第二种攻击:其主要目标是由B破解(M', U), 然后由(B, M', U)求出A'(
例如, 令A=(13, 9, 4, 29, 78, 147), π =
虽然A″非半超递增背包向量, 但却做成了“
定义5 A=(a1, a2, …, an)∈
式中:m为满足1< m< n和式(1)的最大者。
由(2), 可得π '=
由式(3)可得等价的陷门t'=(A″, π ', M', U), 从而完全破解ft, 其中:
π '=
由于B是直接由A经模乘变换所得, 故可基于Lenstra关于固定变元数量的整数规划问题可在多项式时间内求解, 以及A的“ 半超递增” 性来破解(M', U)[14, 22]。而ft在该攻击下是不安全的。
改进思路是使(xπ (n+1), …, xπ (2n))不是由(xπ (n+1), …, xπ (2n))∈ {0, 1}n直接经模乘变换得到, 而是由无明显特征的背包向量经模乘变换得到, 如此可使上述攻击无效, 改进方案如下:
(1)选择安全参数n。
(2)在[1, 2n]中均匀随机地选择(a1, a2, …, an)∈
(3)随机选取rj∈
(4)随机选取M, W∈ N+, 其中M为奇数, 且
(5)随机选取Δ =(δ 1, δ 2, …, δ 2n)∈ {-1, 0, 1}2n, ω ∈ ZM; 并用(M, Δ , ω )对A进行变换得C=(c1, c2, …, c2n)=A+Δ · ω (modM), 即:
ci=(ai+δ iω )(modM)(i=1, 2, …, 2n)。
(6)随机选取(1, 2, …, 2n)的置换π , 并用(π , M, W)对C模乘变换得B=(b1, b2, …, b2n), 即:bπ (i)=Wci(modM) (i=1, 2, …, 2n)。
(7)以t=(A, Δ , ω , π , M, W)为陷门(仅需保留A
(8)对于x∈ {0, 1}2n, 定义ft(x)=
选择奇数模M, 是为不暴露ci(i=1, 2, …, 2n)的奇偶性。对于x=(x1, x2, …, x2n)∈ {0, 1}2n, 令SC=
(1)计算SC=W-1y(modM)=
(2)For k=-n2 To n1 Do
S:=(SC-kω )(modM);
For i=2n Downto (n+1) Do
If(S≥ ai) Then
xπ (i):=1;
S:=S-ai;
Else
xπ (i):=0;
EndIf
EndFor
Xk:=(xπ (n+1), …, xπ (2n));
If(S≤
输出Xk;
EndIf
EndFor
(3)所输出者即为
上述算法所输出的候选解至多有(n1+n2+1)组, 且
-K2≤ k-
实验表明, 虽然无法唯一确定
下面再来分析改进后ft的安全性, 由于DB的取值并未受改进的影响, 所以对ft的第一种攻击与改进前类似, 不再赘述。而对ft的第二种攻击, 则要面临两种不确定性:其一, π 的存在使得攻击者只能对B和A各分量之间的对应关系进行猜测。其二, 由于在模乘变换之前先对A做了不确定变换C=(A+Δ · ω )(modM), 其中Δ 和ω 分别有32n和M种可能取值, 故C是不确定的, 且不再具有半超递增属性, 这使得针对模乘变换背包密码的攻击方法不再奏效。但这种改进则是以牺牲对
由于半陷门单向函数不能单独用来构造公钥密码。所以我们的方案构思是:以(ft, g)为公钥, t为私钥。这里ft:X→ Y是半陷门单向函数, 而函数g:X→ Z则应满足:
(1)由g和x∈ X, 计算z=g(x)是容易的。
(2)由(ft, g, y=ft(x), z=g(x)), 计算x∈ X使x=
(3)由(ft, g, y=ft(x), z=g(x), x'=
问题的关键是:对于给定的半陷门单向函数ft, 如何构造满足上述条件的函数g。
基于上述思路, 本文给出了一种新的公钥密码方案, 即STOF_PKC。STOF_PKC是基于第1节所构造的半陷门单向函数ft, 以及F2上一个n× 2n矩阵G来实现的, 方案由密钥生成、加密、解密三个算法构成, 具体如下:
2.2.1 密钥生成算法:
(1)选择安全参数n;
(2)构造半陷门单向函数ft, 其陷门t=(A, Δ , ω , π , M, W), 输出参数为B;
(3)由B计算向量(g1, 1, …, g1, 2n)∈
G1=
G2=
(4)令G=
(5)以t为私钥, (B, G)为公钥。
2.2.2 加密算法:
明文消息为x=(x1, x2, …, x2n)∈ {0, 1}2n\{0}, 发送方对x加密过程如下:
(1)获得接收方的公钥(B, G);
(2)计算y=ft(x)=
z=
(3)将密文(y, z)发送给接收方。
2.2.3 解密算法:
(1)接收方求出
(2)For i:=1 To m Do
将Xi代入方程组:G1· Xi'+G2· Xi=z, 可唯一解出Xi'∈
EndFor
(3)算法结束, 所输出者即为候选明文(集)。
其中X:=Merge(Xi, Xi')表示将两个n位候选解Xi和Xi'合并为一个2n位候选解X∈
由STOF_PKC的解密算法, 易知:
(1)若明密文之间是一对一的, 则密文经解密后可唯一确定明文。
(2)若明密文之间是多对一的, 则密文经解密后能得到一个明文集合, 且该集合恰好包含与给定密文对应的所有明文。
(3)若密文不对应任何明文, 则密文解密后得空集。
理想情形是每一个密文都仅对应唯一的明文, 此时不仅可提高解密效率, 还可保证解密的唯一性。令明文空间P={0, 1}2n\{0}, 则STOF_PKC满足解密唯一性的充要条件是:不存在x, x'∈ P(x≠ x')使ft(x)=ft(x')∧ G· x=G· x'。
设B的所有22n-1种非零子集和共有n_ss种取值, 其中只与唯一子集和对应的取值共有n_uss种, 则n_uss≤ n_ss, 且B满足USS条件当且仅当n_uss=n_ss。显然, 若B满足USS条件, 则STOF_PKC必满足解密唯一性。但这是NPC问题, 无有效的判定算法。所以通过实验来对此进行分析, 实验对不同的n, 独立生成10 000个ft实例, 然后对DB、n_ss、n_uss计算平均值, 并统计B满足USS条件的出现数量, 结果见表2。
由实验结果, 可以看出:
(1)随着n的增大, B满足USS条件的概率迅速减小, 但B中满足USS的子集和所占比例
(2)DB均值与估值公式DB≈
由B的n_ss和n_uss取值可知, 密文空间V=ft(P)中共有n_uss个密文, 按明密之间的对应关系, 可将V划分为
对z∈ {0, 1}n, 定义Gz={
若明文x∈ P1, 则密文(y, z)=(ft(x), G· x)必满足解密唯一性。反之, 若x∈ P2, 则还要看是否有(
令
y=
由此得(
首先给出Semi-SSP(半子集和问题)的定义:
定义6 给定A=(a1, …, a2n)∈
(1)1≤ i1< i2< …< in≤ 2n。
(2)令{j1, …, jn}={1, …, 2n}\{i1, …, in}, 则存在(
SSP和Semi-SSP的区别在于, 前者对每个背包分量都要精确判定其是否属于给定的“ 子集和” , 而后者只需对一半背包分量进行精确判定。若SSP可解, 则Semi-SSP必可解, 反之亦然。即Semi-SSP也是NPC问题。关于STOF_PKC的安全性, 有:
定理2 破解STOF_PKC等价于求解B中的Semi-SSP。
证明:若能求解B中的Semi-SSP, 则必能破解STOF_PKC。反之, 若不能求解B中的Semi-SSP, 则对x∈ {0, 1}2n的密文(y)=
式(6)的解(
Δ (
Δ (
下式为对部分Δ (
对于n> 16, 由
Δ (
k=16, …, n-1
可得:
Δ (
Δ (
Δ (
又G∈
(1-Δ (
而n与k相差足够大(否则最多2n-k次猜测便可破解B中的Semi-SSP), 故在现实中可认为恒有Rank(G')=n, 即有
本文引入了“ 半陷门单向函数” 的概念, 并给出了基于半陷门单向函数来构造公钥密码的思路。在此基础上, 给出了一种新的背包密码方案STOF_PKC, 并证明了破解STOF_PKC等价于求解B中的Semi-SSP。因此, 若B中的Semi-SSP是难解的, 则STOF_PKC便是安全的。但尚有一些新问题有待解决, 比如是否存在其他实现半陷门单向函数的方法、是否存在其他基于半陷门单向函数的公实现签名等, 需要进行更深入的探索。
The authors have declared that no competing interests exist.