1)随机生成素数p,随机选择Z上N次不可约多项式N(x);

2)对i=1,2,…,n,依次如下操作:

(i)独立从B_∞,N(2^N1/2-1)中随机选取S_i(x),计算G_i(x)=1+2S_i(x),要求对1≤j<i,均有gcd(G_i(x),G_j(x))=1且resultant(G_i(x),N(x))=p;

(ii)在环Z_p[x]上计算D_i(x)=gcd(G_i(x),N(x)),取D_i(x)的根α_i∈Z_p;

(iii)用有理数域上的最大公因子算法计算正系数多项式Z_i(x)=∑^N-1_k=0z_i,kx^k,满足Z_i(x)·G_i(x)=pmod N(x);

(iv)令B_i=z_i,0(mod 2p).

3)输出公钥C_PK=(p,α₁,α₂,…,α_n)和私钥C_SK=(p,B₁,B₂,…,B_n).

1)分解明文M=m₁ m₂…,m_n∈{0,1}ⁿ;

2)对i=1,2,…,n,进行如下步骤:

(i)从B_∞,N((N^1/2)/2)中随机选取R_i(x);

(ii)计算C_i(x)=m_i+2R_i(x);

(iii)c_i←C_i(α_i)mod p;

3)输出密文C=c₁,c₂…c_n.

1)分解密文C=c₁ c₂…c_n,私钥C_SK=(p,B₁,B₂,…,B_n);

2)对i=1,2,…,n,计算m_i=(c_i- c_i·B_i/p)(mod 2);

3)输出明文M=m₁ m₂…m_n.

1)分解C'=c'₁ c'₂…c'_n,C″=c″₁ c″₂…c″_n;

2)计算c_i=(c'_i+c″_i)mod p,i=1,2,…,n;

3)输出和密文C=C'+C″=c₁ c₂…c_n.

定理1 上述加密方案具有如下性质:

(i)在SPIP问题困难假设下,给定公钥恢复私钥是困难的;

(ii)在格上CVP问题困难假设下,给定密文恢复明文是困难的;

(iii)在PCP问题困难假设下,是语义安全的,即密文不可区分.

证明 当n=1时,方案与文献[6]的类似.尽管生成素数p和多项式G的方式有所不同,但p,N和G的关系是一样的,均为resultant(G(x),N(x))=p,所以加密方案具有相同性质.

(i)方案中的公钥实际上给出了一个次数为1的主理想的二元表示,私钥是该主理想的一个小生成元的逆元.故给定公钥恢复私钥是SPIP问题的一个示例.

(ii)给定密文恢复明文这个问题等价于:给定p和α,c∈Z_q,寻找x_i,i=1,2,…,N,使得存在整数k,满足∑^N_i=1x_i·αⁱ=c-k·pi,|x_i|≤N^1/2/2.令矩阵

H=(p

-α⁰ 1

 

-α^N-1 1),

考虑由H的行向量生成的格,则上式等价于(k,-x₁,-x₂,…,-x_n)·H=(c-x₀,-x₁,-x₂,…,-x_n).故问题相当于寻找与非格向量(c,0,…,0)最近的格向量(c-x₀,-x₁,-x₂,…,-x_n)的格上CVP问题.

(iii)假设存在算法A以ε的概率攻破上述加密方案的语义安全性,那么存在一个算法B,在和A相同的运行时间内,以ε/2的概率解决PCP问题.证明如下:算法B为算法A的挑战(r,p,α)创建一个挑战密文c←M_β(α)+2·r(mod p),这里M₀和M₁是A的两个挑战消息,β是B随机选择的挑战比特.A发送对β的挑战β',B返回ββ'.

PCP问题中,当b=0时,显然挑战密文c有正确的分布,所以B的优势与A相同,等于ε.当b=1时,r(mod p)是一致随机的,由于p是奇数,2r(mod p)也是一致随机的,因此A的优势为0,这意味着B解决PCP问题的整体优势为ε/2.

在PCP问题假设下,方案是语义安全的,即给定单比特消息通过加密方案加密得到的密文,无法区分该消息是0或1.

当n>1时,进行混合论证.给定n长比特串消息M⁰=m⁰₁ m⁰₂…m⁰_n 和M¹=m¹₁ m¹₂…m¹_n,记M^β_i(x)=x-m^β_i(β=0,1).构造一系列游戏H₀,…,H_n,证明相邻的游戏H_k-1和H_k是不可区分的,从而由n是多项式级的,得到H₀和H_n是不可区分的.

游戏H₀中,对(r,p,α₁,α₂,…,α_n),如下定义c=c₁ c₂…c_n,对i=1,2,…,n,令c_i=M⁰_i(α_i)+2·r(modp).

游戏H_n中,对(r,p,α₁,α₂,…,α_n),如下定义c=c₁ c₂…c_n,对i=1,2,…,n,令c_i=M¹_i(α_i)+2·r(modp).

游戏H_k(1≤k<n)中,对(r,p,α₁,α₂,…,α_n),定义消息M^k=m⁰₁ …m⁰_k m¹_k+1 …m¹_n 的密文c=c₁ c₂…c_n,对i=1,2,…,n,令c_i=M^k_i(α_i)+2·r(mod p).

对任意的k∈[n],考虑模拟算法S^Ο,这里预言O或回答M⁰_k(α_k)+2·r(mod p),或回答M¹_k(α_k)+2·r(mod p).分两种情形:对i<k,令c_i=M¹(α_i)+2·r(mod p); 对i>k,令c_i=M⁰(α_i)+2·r(mod p).

那么,对k∈[n],当预言O的回答为M⁰(α_k)+2·r(mod p)时,S^Ο的输出等同于H_k-1; 回答为M¹(α_k)+2·r(mod p)时,S^Ο的输出等同于H_k.

由于在PCP问题假设下单比特密文是无法区分的,故H_k-1与H_k无法区分.(证毕)

首先,给出不可逆陷门单向函数簇L的抽样算法:

1)随机生成GF(2)上的n×m阶矩阵A,其中前n列是单位矩阵,其余元素为零.

2)调用加密方案,重复地随机加密A的第1列到第m列,得矩阵C.

3)取二元[m,n]纠错码的生成矩阵G,对原像x∈{0,1}ⁿ,令x'=G'·x,定义像y=C·x'=C·(G^t·x).

4)输出函数索引C和函数陷门(C_SK,A,i₁,i₂,…,i_n).

那么,索引为C,陷门为(C_SK,A,i₁,i₂,…,i_n)的函数L的陷门求逆算法如下:

对函数值y∈Zⁿ_p,利用解密密钥C_SK调用解密算法,生成向量y'∈{0,1}ⁿ,然后在二元域上求解方程y'=A·(-overx),得解向量(-overx).再利用陷门信息i₁,i₂,…,i_n得到(-overx)的第i₁,i₂,…,i_n列,最后通过纠删码译码算法得到原像(-overx)'∈{0,1}ⁿ.

其次,给出第二原像抵抗的函数簇F的抽样算法:

1)随机选取n个整数i₁,i₂,…,i_n,其中 1≤i₁<i₂<…<i_n≤m.随机生成二元域上n×m阶矩阵A=(A₁,A₂,…,A_m),要求其第i₁,i₂,…,i_n列组成秩为n-1的方阵,其余元素为零.

2)调用上述加密方案,由密钥生成算法得到公私钥对(C_PK,C_SK),用加密算法分别重复地随机加密A的列向量A₁,A₂,…,A_m得到密文C₁,C₂,…,C_m.从而得到矩阵C=(C₁,C₂,…,C_m)∈Z^n×m_p.

3)取二元[m,n]纠错码的生成矩阵G,对原像x∈{0,1}ⁿ,令x'=G'·x,定义像y=C·x'=C·(G'·x).

4)输出函数索引C和函数陷门(C_SK,A,i₁,i₂,…,i_n).

定理2 上述所构造的函数簇(L,F)是一个缺损函数簇,满足

(i)函数簇L是不可逆的;

(ii)函数簇F是抗第二原像的;

(iii)函数簇L和F是不可区分的.

证明 利用加密方案的性质分析.

在SPIP问题困难假设下,加密方案给定公钥恢复私钥是困难的,这个性质保证了陷门信息的秘密性.

在格上CVP问题困难假设下,给定密文恢复明文是困难的,这个性质保证了函数L和F是无陷门求逆难的,得到结论(i).在PCP问题困难假设下,加密方案是语义安全的,等价于密文不可区分性,从而无法区分函数索引矩阵C对应的矩阵A是选自L或F,从而得到了结论(iii).函数簇L中矩阵A满秩,实现了一对一映射; 函数簇F中矩阵A的秩为n-1,实现了二对一映射,保证了第二原像的存在性.由结论(i)和(iii)可得(ii),否则如果F能够解出第二原像,由于L是一对一映射,第二原像是不存在的,那么通过是否存在第二原像,即可区分F和L,与(iii)矛盾.(证毕)