基于半陷门单向函数的公钥密码

引用本文

赵博, 秦贵和, 赵永哲, 杨文迪. 基于半陷门单向函数的公钥密码[J].吉林大学学报（工学版）, 2018,48(1): 259-267
ZHAO Bo, QIN Gui-He, ZHAO Yong-Zhe, YANG Wen-Di. Public key cryptosystem based on semi-trapdoor one-way function[J]. Journal of Jilin University Engineering and Technology Edition, 2018,48(1): 259-267 复制到剪切板

Doi:10.13229/j.cnki.jdxbgxb20161211
Permissions

基于半陷门单向函数的公钥密码

赵博¹, 秦贵和¹, 赵永哲¹, 杨文迪²

1.吉林大学计算机科学与技术学院,长春 130012

2.华东师范大学计算机科学与软件工程学院,上海 200062

通讯作者：赵永哲(1961-),男,教授,博士. 研究方向:信息安全. E-mail:yongzhe@jlu.edu.cn

作者简介:赵博(1988-),男,博士研究生.研究方向:图像处理,信息安全. E-mail:wolfers509@126.com

基金:吉林省科技发展计划项目(20150204034GX)

摘要

通过引入“半陷门单向函数”的概念来构造公钥密码,与陷门单向函数不同,由于半陷门单向函数是“半可逆”的,所以不能单独用来构造公钥密码。为此本文提出了一种基于半陷门单向函数的公钥密码构造方法。并结合SSP(子集和问题)的难解性和易解性,构造了“半超递增背包向量”,并基于半超递增背包向量对半陷门单向函数进行了具体实现。在此基础上,给出了一种新的公钥密码方案STOF_PKC。该方案在分类上属于背包密码,因而具有抗量子计算的潜力。

关键词: 计算机系统结构; 半陷门单向函数; 半超递增背包向量; 抗量子计算的公钥密码; 背包公钥密码

中图分类号:TP309.7 文献标志码:A 文章编号:1671-5497(2018)01-0259-09

Public key cryptosystem based on semi-trapdoor one-way function

ZHAO Bo¹, QIN Gui-He¹, ZHAO Yong-Zhe¹, YANG Wen-Di²

1.College of Computer Science and Technology, Jilin University. Changchun 130012, China

2.College of Computer Science and Software Engineering, East China Normal University, Shanghai 200062, China

Abstract

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.

Keyword: computer system organization; semi-trapdoor one-way function; semi-super increasing knapsack; quantum resistant public key cryptography; knapsack public key cryptosystem.

Show Figures

0 引言

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]}。

但目前所提出的抗量子计算公钥密码方案中的绝大多数都已被证明是不安全的。尽管不断有新方案被提出, 但从构造方法来看, 这些方案不外乎两大类:其一是基于“ 陷门单向函数” , 这类公钥密码占绝大多数, 其关键在于如何设计陷门。其二则是基于“ 非对称密钥交换” , 其关键在于如何实现非对称的密钥交换, 这往往要用到“ 单向函数” 。一般说来, 寻找单向函数要比寻找陷门单向函数容易得多, 但单向函数不可逆, 故不能直接用来实现公钥密码。而利用陷门单向函数虽可直接实现公钥密码, 但由于“ 陷门性” 和“ 单向性” 的固有矛盾, 使得二者很难兼顾。为了构造陷门, 就必然要牺牲单向性; 反之亦然。

本文重点研究了如何设计实现半陷门单向函数, 以及如何基于半陷门单向函数来构造公钥密码。

1 半陷门单向函数的设计与实现

为了同时兼顾陷门性和单向性, 本文引入了“ 半陷门单向函数(Semi-trapdoor one-way function, STOF)” 的概念, 其定义如下:

定义1 “ 半陷门单向函数” 是一族“ 半可逆” 的陷门函数:f_t:X→ Y, 满足:

(1)已知f_t和x∈ X, 计算y=f_t(x)是容易的。

(2)已知f_t、y=f_t(x), 计算x= $\begin{matrix} f_{t}^{- 1} \end{matrix}$ (y)和x'是困难的(其中x'是x的“ 一半” , 比如可令x'是x的后半段或x的所有偶数位)。

(3)已知f_t、y=f_t(x)、t(陷门), 计算x= $\begin{matrix} f_{t}^{- 1} \end{matrix}$ (y)是困难的, 但计算x'却是容易的(为了便于表示, 特记x'= $\begin{matrix} f_{t}^{- 1 / 2} \end{matrix}$ (y))。

由于半陷门单向函数分别涉及单向性和陷门性, 所以在设计时要同时对二者进行构思, 这就需要选择合适的困难问题。为便于描述, 文中常用的术语和基本符号如表1所示。

表1 基本符号

符号	含义
N₊	正整数集合
$\begin{matrix} N_{+}^{n} \end{matrix}$	N₊上n维向量的集合
F_q	q元有限域
$\begin{matrix} F_{q}^{n} \end{matrix}$	F_q上所有n维向量的集合
$\begin{matrix} F_{q}^{n \times m} \end{matrix}$	F_q上所有n× m矩阵的集合
S\S'	集合S减集合S'的差集

表1 基本符号

1.1 子集和问题与背包密码

“ 子集和问题(Subset sum problem, SSP, )” 是“ 0-1背包问题” 的一个特例。其定义如下:

定义2(SSP) 给定A=(a₁, a₂, …, a_n)∈ $\begin{matrix} N_{+}^{n} \end{matrix}$ , C∈ N₊; 求解x∈ {0, 1}ⁿ, 使C= $\begin{matrix} \overset{n}{\sum_{i = 1}} \end{matrix}$ x_ia_i。

SSP是著名的NPC问题。大多数背包密码都是基于SSP来构造的。为了保证解密的唯一性, 公钥背包向量还必须满足USS(Unique Subset Sum), 即唯一子集和条件。但已有的的背包密码通常无法抵御“ 低密度攻击” , 背包向量的“ 密度” 定义如下:

定义3 A=(a₁, a₂, …, a_n)∈ $\begin{matrix} N_{+}^{n} \end{matrix}$ 的密度定义为:D_A= $\begin{matrix} \frac{n}{lo g_{2} \max (A)} \end{matrix}$ 。其中max(A)是A中最大者。

由文献[11-13], 若D_A> 1, 则A通常不满足USS条件。事实上, 很多USS背包向量的密度都≪1。早期算法^[14]可破解密度小于0.6463的背包密码, 改进后算法^[15]则可破解密度小于0.9408的背包密码。故为了抵御低密度攻击, 公钥背包除应满足USS条件外, 还应具有高密度(大于0.9408), 但这二者往往很难兼顾, 这也是设计背包密码的难点所在。

若D_A< 1∧ D_A≈ 1, 则A中SSP通常有唯一解。而若D_A> 1∧ D_A≈ 1, 则A中SSP通常有多解。这两种情形均易受到基于格的攻击^{[16, 17]}。只有当D_A≈ 1时, 对A中SSP无有效的解法。Impagliazzo和Naor亦证明, 当D_A=1时, 求解A中SSP是最困难的^[18]。多年来, 对SSP最快的通用解法仍是Schroeppel和Shamir在1981年提出的^[19], 算法的时空复杂度分别为O(n· 2^n/²)和O(n· 2^n/⁴)。最近才有人对其进行了优化^[20], 但改进算法仍是指数级的, 只是将时间复杂度降为O(n· 2^n/³)。

若在[1, 2ⁿ]中均匀随机选择A=(a₁, …, a_n), 则A通常是难解的。实验发现, 如此得到的A通常不满足USS条件。实际上, 当D_A≈ 1时, 判定A是否满足USS条件亦是NPC问题^[21]。

1.2 基于SSP的半陷门单向函数

可基于SSP的难解和易解性来设计半陷门单向函数。为此引入“ 半超递增背包向量” 的定义如下:

定义4 若A=(a₁, a₂, …, a₂_n)∈ $\begin{matrix} N_{+}^{2 n} \end{matrix}$ 满足:A[1, n]不是超递增的(A[i, j]=(a_i, …, a_j))。 $\begin{matrix} \overset{j - 1}{\sum_{i = 1}} \end{matrix}$ a_i< a_j (n+1≤ j≤ 2n)。则称A为半超递增背包向量。

显然, 对于半超递增背包向量, 可快速求出其SSP解的后半部, 且易证如下定理:

定理1 若A=(a₁, …, a₂_n)∈ $\begin{matrix} N_{+}^{2 n} \end{matrix}$ 是半超递增背包向量, 则有:

(1)A中SSP易解当且仅当A $\begin{matrix} [1, n] \end{matrix}$ 中SSP易解。

(2)A为USS背包当且仅当A $\begin{matrix} [1, n] \end{matrix}$ 为USS背包。

(3)若A $\begin{matrix} [1, n] \end{matrix}$ 中SSP是难解的, 则求解A中SSP的前半部亦是困难的。

基于半超递增背包向量, 可得半陷门单向函数f_t:{0, 1}²ⁿ→ N的设计方案如下:

(1)选择安全参数n;

(2)在[1, 2ⁿ]中均匀随机选择(a₁, …, a_n)∈ $\begin{matrix} N_{+}^{n} \end{matrix}$ , 且使 $\begin{matrix} D_{(a_{1}, a_{2}, \dots, a_{n})} \end{matrix}$ ≈ 1;

(3)随机选取r_j∈ $\begin{matrix} [1, \overset{n}{\sum_{i = 1}} a_{i}] \end{matrix}$ , 并令a_j= $\begin{matrix} \overset{j - 1}{\sum_{i = 1}} \end{matrix}$ a_i+r_j (j=n+1, n+2, …, 2n), 得到A=(a₁, a₂, …, a₂_n);

(4)随机选取M, W∈ N₊, 其中:

$\begin{matrix} \overset{2 n}{\sum_{i = 1}} \end{matrix}$ a_i< M< 2 $\begin{matrix} \overset{2 n}{\sum_{i = 1}} \end{matrix}$ a_i∧ W∈ Z_M∧ gcd(M, W)=1;

(5)随机选取(1, 2, …, 2n)的置换π , 并用(π , M, W)对A模乘变换得B=(b₁, b₂, …, b₂_n), 其中 b_{π (}_i₎=Wa_i(modM);

(6)以t=(A, π , M, W^-¹)为陷门(A不用全保存, 仅保存A[n+1, 2n]即可), 并将B公开;

(7)对于x∈ {0, 1}²ⁿ, 定义f_t(x)= $\begin{matrix} \overset{2 n}{\sum_{i = 1}} \end{matrix}$ x_ib_i。

由A $\begin{matrix} [1, n] \end{matrix}$ 的难解性, 可知由(B, y=f_t(x))无法求出x= $\begin{matrix} f_{t}^{- 1} \end{matrix}$ (y), 但由(y=f_t(x), t)却可快速求出 $\begin{matrix} f_{t}^{- 1 / 2} \end{matrix}$ (y)=(x_{π (}_n+₁₎, …, x_{π (2}_n₎)。

1.3 f_t的安全性分析

f_t的安全性取决于两种攻击的难度:其一是由(B, f_t(x)= $\begin{matrix} \overset{2 n}{\sum_{i = 1}} \end{matrix}$ x_ib_i)求解x∈ {0, 1}2n的一半比特, 其二是由B破解陷门t=(A, π , M, W^-¹)。

首先分析对f_t的第一种攻击:这与D_B密切相关, 由于(a₁, a₂, …, a_n)是在[1, 2ⁿ]中均匀随机选择, 将[1, 2ⁿ]分成等长的n段 $\begin{matrix} [1, \frac{2^{n}}{n}] \end{matrix}$ , $\begin{matrix} [\frac{2^{n}}{n} + 1, 2 \cdot \frac{2^{n}}{n}] \end{matrix}$ , …, $\begin{matrix} [(n - 1) \cdot \frac{2^{n}}{n} + 1, 2^{n}] \end{matrix}$ , 则可认为(a₁, a₂, …, a_n)均匀分布在这n段中, 即每一段平均有一个, 由此推出(n-1)· 2^n-¹< $\begin{matrix} \overset{n}{\sum_{i = 1}} \end{matrix}$ a_i≤ (n+1)· 2^n-¹, 又由A $\begin{matrix} [n + 1, 2 n] \end{matrix}$ 的构造方法得:

$\begin{matrix} \begin{matrix} \overset{2 n}{\sum_{i = 1}} a_{i} = 2^{n} \cdot \overset{n}{\sum_{i = 1}} a_{i} + 2^{n - 1} \cdot r_{n + 1} + 2^{n - 2} \cdot r_{n + 2} + \\ \dots + 2^{2} \cdot r_{2 n - 2} + 2 \cdot r_{2 n - 1} + r_{2 n} \Rightarrow \\ 2^{n} \cdot \overset{n}{\sum_{i = 1}} a_{i} < \overset{2 n}{\sum_{i = 1}} a_{i} < 2^{n + 1} \cdot \overset{n}{\sum_{i = 1}} a_{i} \Rightarrow \\ (n - 1) \cdot 2^{2 n - 1} < \overset{2 n}{\sum_{i = 1}} a_{i} < (n + 1) \cdot 2^{2 n} \end{matrix} \end{matrix}$ (1)

由此推出M和W的阶(Order)均为O(n· 2²ⁿ), 即有估值公式:D_B≈ $\begin{matrix} \frac{2 n}{2 n + lo g_{2} n} \end{matrix}$ 。例如, 当n=128时, 则有D_B> 0.97, 故当n足够大时, 无法对B实施低密度攻击。

对于第二种攻击:其主要目标是由B破解(M', U), 然后由(B, M', U)求出A'( $\begin{matrix} a_{i}^{'} \end{matrix}$ =U· b_imodM'), 将A'各分量从小到大排序得A″, 若 $\begin{matrix} \frac{U}{M'} \end{matrix}$ 足够接近 $\begin{matrix} \frac{W^{- 1}}{M} \end{matrix}$ , 则A″必做成半超递增背包向量, 由此可求出与t等价的陷门t'=(A″, π ', M', U), 从而彻底破解f_t。

例如, 令A=(13, 9, 4, 29, 78, 147), π = $\begin{matrix} (\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 3 & 1 & 2 & 6 & 4 \end{matrix}) \end{matrix}$ , M=307, W=128, 则B=(205, 28, 231, 89, 129, 160), W^-¹=12。选取 $\begin{matrix} \frac{U}{M'} \end{matrix}$ = $\begin{matrix} \frac{1201}{30700} \end{matrix}$ , 则有:

$\begin{matrix} \{\begin{matrix} A' = (605, 2928, 1131, 14789, 1429, 7960) \\ A″ = (605, 1131, 1429, 2928, 7960, 14789) \end{matrix} \end{matrix}$ (2)

虽然A″非半超递增背包向量, 但却做成了“ $\begin{matrix} \frac{2}{6} \end{matrix}$ -超递增背包向量” , 所谓“ $\begin{matrix} \frac{m}{n} \end{matrix}$ -超递增背包向量” , 其定义如下:

定义5 A=(a₁, a₂, …, a_n)∈ $\begin{matrix} N_{+}^{n} \end{matrix}$ 称为“ $\begin{matrix} \frac{m}{n} \end{matrix}$ -超递增背包向量” , 若其满足:

$\begin{matrix} \overset{j - 1}{\sum_{i = 1}} \end{matrix}$ a_i< a_j, n-m< j≤ n

式中:m为满足1< m< n和式(1)的最大者。

由(2), 可得π '= $\begin{matrix} (\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 3 & 5 & 2 & 6 & 4 \end{matrix}) \end{matrix}$ , 令t'=(A″, π ', M', U), 则由(t', f_t(x))可快速求出x的2位(x₄和x₆), 这离完全破解f_t只差一步。而若选取 $\begin{matrix} \frac{U}{M'} \end{matrix}$ = $\begin{matrix} \frac{12001}{307005} \end{matrix}$ , 则有:

$\begin{matrix} \{\begin{matrix} A' = (4165, 29023, 9186, 147074, 13104, 78130) \\ A″ = (4165, 9186, 13104, 29023, 78130, 147074) \end{matrix} \end{matrix}$ (3)

由式(3)可得等价的陷门t'=(A″, π ', M', U), 从而完全破解f_t, 其中:

π '= $\begin{matrix} (\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 3 & 5 & 2 & 6 & 4 \end{matrix}) \end{matrix}$

由于B是直接由A经模乘变换所得, 故可基于Lenstra关于固定变元数量的整数规划问题可在多项式时间内求解, 以及A的“ 半超递增” 性来破解(M', U)^{[14, 22]}。而f_t在该攻击下是不安全的。

1.4 f_t的改进方案

改进思路是使(x_{π (}_n+₁₎, …, x_{π (2}_n₎)不是由(x_{π (}_n+₁₎, …, x_{π (2}_n₎)∈ {0, 1}ⁿ直接经模乘变换得到, 而是由无明显特征的背包向量经模乘变换得到, 如此可使上述攻击无效, 改进方案如下:

(1)选择安全参数n。

(2)在[1, 2ⁿ]中均匀随机地选择(a₁, a₂, …, a_n)∈ $\begin{matrix} N_{+}^{n} \end{matrix}$ , 且使 $\begin{matrix} D_{(a_{1}, a_{2}, \dots, a_{n})} \end{matrix}$ ≈ 1。

(4)随机选取M, W∈ N₊, 其中M为奇数, 且 $\begin{matrix} \overset{2 n}{\sum_{i = 1}} \end{matrix}$ a_i< M< 2 $\begin{matrix} \overset{2 n}{\sum_{i = 1}} \end{matrix}$ a_i∧ W∈ Z_M∧ gcd(M, W)=1。

(5)随机选取Δ =(δ ₁, δ ₂, …, δ ₂_n)∈ {-1, 0, 1}²ⁿ, ω ∈ Z_M; 并用(M, Δ , ω )对A进行变换得C=(c₁, c₂, …, c₂_n)=A+Δ · ω (modM), 即:

c_i=(a_i+δ _iω )(modM)(i=1, 2, …, 2n)。

(6)随机选取(1, 2, …, 2n)的置换π , 并用(π , M, W)对C模乘变换得B=(b₁, b₂, …, b₂_n), 即:b_{π (}_i₎=Wc_i(modM) (i=1, 2, …, 2n)。

(7)以t=(A, Δ , ω , π , M, W)为陷门(仅需保留A $\begin{matrix} [n + 1, 2 n] \end{matrix}$ 和 $\begin{matrix} \overset{n}{\sum_{i = 1}} \end{matrix}$ a_i), 并将B公开。

(8)对于x∈ {0, 1}2n, 定义f_t(x)= $\begin{matrix} \overset{2 n}{\sum_{i = 1}} \end{matrix}$ x_ib_i。

选择奇数模M, 是为不暴露c_i(i=1, 2, …, 2n)的奇偶性。对于x=(x₁, x₂, …, x₂_n)∈ {0, 1}2n, 令S_C= $\begin{matrix} \overset{2 n}{\sum_{i = 1}} \end{matrix}$ x_ic_i、S_A= $\begin{matrix} \overset{2 n}{\sum_{i = 1}} \end{matrix}$ x_ia_i、k= $\begin{matrix} \overset{2 n}{\sum_{i = 1}} \end{matrix}$ x_iδ _i, 则有S_C=S_A+kω ⇒ S_A=(S_C-kω )(modM), 令Δ 中1和-1的个数为n₁和n₂, 则-n₂≤ k≤ n₁, 由此可得求解 $\begin{matrix} f_{t}^{- 1 / 2} \end{matrix}$ (y)(y=f_t(x))的算法如下:

(1)计算S_C=W^-¹y(modM)= $\begin{matrix} (\overset{2 n}{\sum_{i = 1}} x_{π (i)} c_{i}) \end{matrix}$ (modM);

(2)For k=-n₂ To n₁ Do

S:=(S_C-kω )(modM);

For i=2n Downto (n+1) Do

If(S≥ a_i) Then

x_{π (}_i₎:=1;

S:=S-a_i;

Else

x_{π (}_i₎:=0;

EndIf

EndFor

X_k:=(x_{π (}_n+₁₎, …, x_{π (2}_n₎);

If(S≤ $\begin{matrix} \overset{n}{\sum_{i = 1}} \end{matrix}$ a_i) Then /* 一次过滤* /

输出X_k;

EndIf

EndFor

(3)所输出者即为 $\begin{matrix} f_{t}^{- 1 / 2} \end{matrix}$ (y)的所有候选解。

上述算法所输出的候选解至多有(n₁+n₂+1)组, 且 $\begin{matrix} f_{t}^{- 1 / 2} \end{matrix}$ (y)的合法解必为其中之一。令X_k=(x_{π (}_n+₁₎, …, x_{π (2}_n₎)(-n₂≤ k≤ n₁)是一个候选解, 则由k= $\begin{matrix} \overset{2 n}{\sum_{i = 1}} \end{matrix}$ x_{π (}_i₎δ _i, 可知k- $\begin{matrix} \overset{2 n}{\sum_{i = n + 1}} \end{matrix}$ x_{π (}_i₎δ _i= $\begin{matrix} \overset{n}{\sum_{i = 1}} \end{matrix}$ x_{π (}_i₎δ _i, 其中k和 $\begin{matrix} \overset{2 n}{\sum_{i = n + 1}} \end{matrix}$ x_{π (}_i₎δ _i已知, $\begin{matrix} \overset{n}{\sum_{i = 1}} \end{matrix}$ x_{π (}_i₎δ _i未知, 令(δ ₁, δ ₂, …, δ _n)中1和-1的个数为K₁和K₂, 则有:

-K₂≤ k- $\begin{matrix} \overset{2 n}{\sum_{i = n + 1}} \end{matrix}$ x_{π (}_i₎δ _i≤ K₁(4)

实验表明, 虽然无法唯一确定 $\begin{matrix} f_{t}^{- 1 / 2} \end{matrix}$ (y)的合法解, 但经两次过滤, 候选解的数量已大为减少。

下面再来分析改进后f_t的安全性, 由于D_B的取值并未受改进的影响, 所以对f_t的第一种攻击与改进前类似, 不再赘述。而对f_t的第二种攻击, 则要面临两种不确定性:其一, π 的存在使得攻击者只能对B和A各分量之间的对应关系进行猜测。其二, 由于在模乘变换之前先对A做了不确定变换C=(A+Δ · ω )(modM), 其中Δ 和ω 分别有3²ⁿ和M种可能取值, 故C是不确定的, 且不再具有半超递增属性, 这使得针对模乘变换背包密码的攻击方法不再奏效。但这种改进则是以牺牲对 $\begin{matrix} f_{t}^{- 1 / 2} \end{matrix}$ (y)求逆的“ 唯一性” 为代价的, 不过下面将会看到, f_t并非单独使用, 而是要与函数g合用, 所以可通过两者之间的“ 交叉验证” 来确定 $\begin{matrix} f_{t}^{- 1 / 2} \end{matrix}$ (y)。

2 基于半陷门单向函数的公钥密码

2.1 方案构思

由于半陷门单向函数不能单独用来构造公钥密码。所以我们的方案构思是:以(f_t, g)为公钥, t为私钥。这里f_t:X→ Y是半陷门单向函数, 而函数g:X→ Z则应满足:

(1)由g和x∈ X, 计算z=g(x)是容易的。

(2)由(f_t, g, y=f_t(x), z=g(x)), 计算x∈ X使x= $\begin{matrix} f_{t}^{- 1} \end{matrix}$ (y)=g^-¹(z)是困难的。

(3)由(f_t, g, y=f_t(x), z=g(x), x'= $\begin{matrix} f_{t}^{\frac{- 1}{2}} \end{matrix}$ (y)), 计算x∈ X使x= $\begin{matrix} f_{t}^{- 1} \end{matrix}$ (y)=g^-¹(z)是容易的。

问题的关键是:对于给定的半陷门单向函数f_t, 如何构造满足上述条件的函数g。

2.2 方案实现

基于上述思路, 本文给出了一种新的公钥密码方案, 即STOF_PKC。STOF_PKC是基于第1节所构造的半陷门单向函数f_t, 以及F₂上一个n× 2n矩阵G来实现的, 方案由密钥生成、加密、解密三个算法构成, 具体如下:

2.2.1 密钥生成算法:

(1)选择安全参数n;

(2)构造半陷门单向函数f_t, 其陷门t=(A, Δ , ω , π , M, W), 输出参数为B;

(3)由B计算向量(g_{1, 1}, …, g_{1, 2}_n)∈ $\begin{matrix} F_{2}^{2 n} \end{matrix}$ , 其中g_1,_i=b_i(mod2)(i=1, 2, …, 2n), 再随机选n-1个向量(g_{2, 1}, …, g_{2, 2}_n), …, (g_n_{, 1}, …, g_n_{, 2}_n)∈ $\begin{matrix} F_{2}^{2 n} \end{matrix}$ , 且这n个向量使如下矩阵G₁, G₂∈ $\begin{matrix} F_{2}^{n \times n} \end{matrix}$ 非奇异:

G₁= $\begin{matrix} [\begin{matrix} g_{1, π (1)} & g_{1, π (2)} & \dots & g_{1, π (n)} \\ g_{2, π (1)} & g_{2, π (2)} & \dots & g_{2, π (n)} \\ ⋮ & ⋮ & ⋮ \\ g_{n, π (1)} & g_{n, π (2)} & \dots & g_{n, π (n)} \end{matrix}] \end{matrix}$ ;

G₂= $\begin{matrix} [\begin{matrix} g_{1, π (n + 1)} & g_{1, π (n + 2)} & \dots & g_{1, π (2 n)} \\ g_{2, π (n + 1)} & g_{2, π (n + 2)} & \dots & g_{2, π (2 n)} \\ ⋮ & ⋮ & ⋮ \\ g_{n, π (n + 1)} & g_{n, π (n + 2)} & \dots & g_{n, π (2 n)} \end{matrix}] \end{matrix}$ ;

(4)令G= $\begin{matrix} [\begin{matrix} g_{1, 1} & g_{1, 2} & \dots & g_{1, 2 n} \\ g_{2, 1} & g_{2, 2} & \dots & g_{2, 2 n} \\ ⋮ & ⋮ & ⋮ \\ g_{n, 1} & g_{n, 2} & \dots & g_{n, 2 n} \end{matrix}] \end{matrix}$ 。

(5)以t为私钥, (B, G)为公钥。

2.2.2 加密算法:

明文消息为x=(x₁, x₂, …, x₂_n)∈ {0, 1}²ⁿ\{0}, 发送方对x加密过程如下:

(1)获得接收方的公钥(B, G);

(2)计算y=f_t(x)= $\begin{matrix} \overset{2 n}{\sum_{i = 1}} \end{matrix}$ x_ib_i,

z= $\begin{matrix} [\begin{matrix} z_{1} \\ ⋮ \\ z_{n} \end{matrix}] \end{matrix}$ =G· $\begin{matrix} [\begin{matrix} x_{1} \\ ⋮ \\ x_{2 n} \end{matrix}] \end{matrix}$ 。

(3)将密文(y, z)发送给接收方。

2.2.3 解密算法:

(1)接收方求出 $\begin{matrix} f_{t}^{- 1 / 2} \end{matrix}$ (y)的候选解集{X₁, …, X_m}。

(2)For i:=1 To m Do

将X_i代入方程组:G₁· X_i'+G₂· X_i=z, 可唯一解出X_i'∈ $\begin{matrix} F_{2}^{n} \end{matrix}$ ; X:=Merge(X_i, X_i'); If(y=f_t(x)) 输出;

EndFor

(3)算法结束, 所输出者即为候选明文(集)。

其中X:=Merge(X_i, X_i')表示将两个n位候选解X_i和X_i'合并为一个2n位候选解X∈ $\begin{matrix} F_{2}^{2 n} \end{matrix}$ 。

3 分析验证

3.1 STOF_PKC解密的正确性和唯一性分析

由STOF_PKC的解密算法, 易知:

(1)若明密文之间是一对一的, 则密文经解密后可唯一确定明文。

(2)若明密文之间是多对一的, 则密文经解密后能得到一个明文集合, 且该集合恰好包含与给定密文对应的所有明文。

(3)若密文不对应任何明文, 则密文解密后得空集。

理想情形是每一个密文都仅对应唯一的明文, 此时不仅可提高解密效率, 还可保证解密的唯一性。令明文空间P={0, 1}²ⁿ\{0}, 则STOF_PKC满足解密唯一性的充要条件是:不存在x, x'∈ P(x≠ x')使f_t(x)=f_t(x')∧ G· x=G· x'。

设B的所有2²ⁿ-1种非零子集和共有n_ss种取值, 其中只与唯一子集和对应的取值共有n_uss种, 则n_uss≤ n_ss, 且B满足USS条件当且仅当n_uss=n_ss。显然, 若B满足USS条件, 则STOF_PKC必满足解密唯一性。但这是NPC问题, 无有效的判定算法。所以通过实验来对此进行分析, 实验对不同的n, 独立生成10 000个f_t实例, 然后对D_B、n_ss、n_uss计算平均值, 并统计B满足USS条件的出现数量, 结果见表2。

表2 实验结果

n	B
n	D_B	n_ss	n_ss	$\begin{matrix} \frac{n_ss}{2^{2 n - 1}} \end{matrix}$	USS 数量
5	0.8034	992	961	0.9394	3140
6	0.8174	3973	3855	0.9414	2124
7	0.8280	15928	15484	0.9451	468
8	0.8390	63834	62173	0.9487	58
9	0.8466	255662	249319	0.9511	1
10	0.8554	1022747	997608	0.9514	0
11	0.8610	4104694	4016491	0.9576	0
12	0.8689	16465077	16156720	0.9630	0
13	0.8747	65944812	64813379	0.9658	0
14	0.8790	265381998	262341893	0.9773	0

表2 实验结果

由实验结果, 可以看出:

(1)随着n的增大, B满足USS条件的概率迅速减小, 但B中满足USS的子集和所占比例 $\begin{matrix} \frac{n_uss}{2^{2 n} - 1} \end{matrix}$ 则呈稳定及小幅增长的趋势。

(2)D_B均值与估值公式D_B≈ $\begin{matrix} \frac{2 n}{2 n + lo g_{2} n} \end{matrix}$ 非常吻合。

由B的n_ss和n_uss取值可知, 密文空间V=f_t(P)中共有n_uss个密文, 按明密之间的对应关系, 可将V划分为 $\begin{matrix} \{V_{1}, V_{2}\} \end{matrix}$ , 其中 $\begin{matrix} |V_{1}| \end{matrix}$ =n_uss, $\begin{matrix} |V_{2}| \end{matrix}$ =n_ss-n_uss, 且V₁中每个密文均对应唯一的明文, 而V₂中每个密文则至少对应2个明文。相应的, 亦可将P划分为 $\begin{matrix} \{P_{1} = f_{t}^{- 1} (V_{1}), P_{2} = f_{t}^{- 1} (V_{2})\} \end{matrix}$ , 且 $\begin{matrix} |P_{1}| \end{matrix}$ =n_uss, $\begin{matrix} |P_{2}| \end{matrix}$ =2²ⁿ-1-n_uss。

对z∈ {0, 1}ⁿ, 定义G_z={ $\begin{matrix} x| \end{matrix}$ x∈ $\begin{matrix} F_{2}^{2 n} \end{matrix}$ ∧ G· x=z}为方程组G· x=z的解集合。则由G· x=G₁· $\begin{matrix} (x_{π (1)}, \dots, x_{π (n)})^{T} \end{matrix}$ +G₂· $\begin{matrix} (x_{π (n + 1)}, \dots, x_{π (2 n)})^{T} \end{matrix}$ =z, 以及G₁和G₂非奇异, 可知(x_{π (1)}, …, x_{π (}_n₎)由(x_{π (}_n+₁₎, …, x_{π (2}_n₎)唯一确定, 且(x_{π (}_n+₁₎, …, x_{π (2}_n₎)∈ {0, 1}ⁿ取不同值, 则(x_{π (1)}, …, x_{π (}_n₎)亦取不同值。即对每个z∈ {0, 1}ⁿ, 均有 $\begin{matrix} |G_{z}| \end{matrix}$ =2ⁿ。易证, 全部2ⁿ个解集合{G_{(0, …, 0)}, G_{(0, …, 1)}, …, G_{(1, …, 1)}}做成{0, 1}²ⁿ的一个划分, 且G· x=G· x'当且仅当x和x'同属一个解集合。

若明文x∈ P₁, 则密文(y, z)=(f_t(x), G· x)必满足解密唯一性。反之, 若x∈ P₂, 则还要看是否有( $\begin{matrix} f_{t}^{- 1} \end{matrix}$ (y)∩ G_z)\{x}=φ , 若是, 则密文(y, z)满足解密唯一性, 否则不满足。

令 $\begin{matrix} |f_{t}^{- 1} (y)| \end{matrix}$ =k, 则k≥ 2, 且 $\begin{matrix} f_{t}^{- 1} \end{matrix}$ (y)中任意2个明文均不在同一解集合的概率为:

y= $\begin{matrix} \frac{2^{n} \cdot (2^{n} - 1) \cdot \dots \cdot (2^{n} - k + 1)}{(2^{n})^{k}} \end{matrix}$ =

$\begin{matrix} \frac{\prod_{i}^{=} (2^{n} - i)}{2^{(k - 1) \cdot n}} \end{matrix}$ (5)

由此得( $\begin{matrix} f_{t}^{- 1} \end{matrix}$ (y)∩ G_z)\{x}≠ φ 的概率≤ 1-y, 即x的密文不满足解密唯一性的概率≤ 1-y。实验发现, V₂中绝大多数的密文(> 95%)都刚好对应2个明文, 这可由 $\begin{matrix} \frac{|P_{2}|}{|V_{2}|} \end{matrix}$ = $\begin{matrix} \frac{2^{2 n} - 1 - n_uss}{n_ss - n_uss} \end{matrix}$ ≈ 2来间接印证(见表2), 这意味着对于绝大多数的x∈ P₂, 其密文(y, z)不满足解密唯一性的概率≤ 2^-n。因此, STOF_PKC可保证对绝大多数密文的解密唯一性。

3.2 STOF_PKC的安全性分析

首先给出Semi-SSP(半子集和问题)的定义:

定义6 给定A=(a₁, …, a₂_n)∈ $\begin{matrix} N_{+}^{2 n} \end{matrix}$ , C∈ N₊; 求解( $\begin{matrix} x_{i_{1}} \end{matrix}$ , …, $\begin{matrix} x_{i_{n}} \end{matrix}$ )∈ {0, 1}ⁿ, 且( $\begin{matrix} x_{i_{1}} \end{matrix}$ , …, $\begin{matrix} x_{i_{n}} \end{matrix}$ )满足:

(1)1≤ i₁< i₂< …< i_n≤ 2n。

(2)令{j₁, …, j_n}={1, …, 2n}\{i₁, …, i_n}, 则存在( $\begin{matrix} x_{j_{1}} \end{matrix}$ , …, $\begin{matrix} x_{j_{n}} \end{matrix}$ )∈ {0, 1}ⁿ, 使C= $\begin{matrix} \overset{n}{\sum_{k = 1}} \end{matrix} \begin{matrix} x_{i_{k}} \end{matrix} \begin{matrix} a_{i_{k}} \end{matrix}$ + $\begin{matrix} \overset{n}{\sum_{k = 1}} \end{matrix} \begin{matrix} x_{j_{k}} \end{matrix} \begin{matrix} a_{j_{k}} \end{matrix}$ 。

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)= $\begin{matrix} \overset{2 n}{\sum_{i = 1}} \end{matrix}$ x_ib_i, z=G· x, 不妨设由(B, y)只能精确求出x的k个分量( $\begin{matrix} x_{i_{1}} \end{matrix}$ , …, $\begin{matrix} x_{i_{k}} \end{matrix}$ )∈ {0, 1}^k(0≤ k< n, 1≤ i₁< i₂< …< i_k≤ 2n), 令{ $\begin{matrix} x_{j_{1}} \end{matrix}$ , …, $\begin{matrix} x_{j_{2 n - k}} \end{matrix}$ }={x₁, …, x₂_n}\{ $\begin{matrix} x_{i_{1}} \end{matrix}$ , …, $\begin{matrix} x_{i_{k}} \end{matrix}$ }, 则破译x等价于求解( $\begin{matrix} x_{j_{1}} \end{matrix}$ , …, $\begin{matrix} x_{j_{2 n - k}} \end{matrix}$ )∈ {0, 1}2n-k。而这仅由(B, y)已无法做到, 必须借助(G, z)才行, 又由(G, z)只能确定x的取值范围G_z, 其中哪些才是正确的x必须通过(B, y)判定。由于n足够大、 $\begin{matrix} |G_{z}| \end{matrix}$ =2ⁿ、且绝大多数密文都对应唯一明文, 故仅凭(G, z)来求解x不可行。因此, 由密文(y, z)求解明文x只能首先由(B, y)入手确定明文x的部分分量, 然后再将之代入方程组z=G· x求出x的候选解, 最后再通过(B, y)对所有候选解逐一判定。现( $\begin{matrix} x_{i_{1}} \end{matrix}$ , …, $\begin{matrix} x_{i_{k}} \end{matrix}$ )已确定, 故可将G_z中与( $\begin{matrix} x_{i_{1}} \end{matrix}$ , …, $\begin{matrix} x_{i_{k}} \end{matrix}$ )不符的明文全部排除, 令余下的明文所构成的集合为G'_z, 则G'_z即为x的候选解集合, 而其规模 $\begin{matrix} |G_{z}^{'}| \end{matrix}$ 便决定了破译x的难度。将( $\begin{matrix} x_{i_{1}} \end{matrix}$ , …, $\begin{matrix} x_{i_{k}} \end{matrix}$ )代入z=G· x, 可得F₂上的方程组:

$\begin{matrix} \begin{matrix} [\begin{matrix} g_{1, j_{1}} & g_{1, j_{2}} & \dots & g_{1, j_{2 n - k}} \\ g_{2, j_{1}} & g_{2, j_{2}} & \dots & g_{2, j_{2 n - k}} \\ ︙ & ︙ & ︙ \\ g_{n, j_{1}} & g_{n, j_{2}} & \dots & g_{n, j_{2 n - k}} \end{matrix}] [\begin{matrix} x_{j_{1}} \\ x_{j_{2}} \\ ︙ \\ x_{j_{2 n - k}} \end{matrix}] \\ = z + [\begin{matrix} g_{1, i_{1}} & g_{1, i_{2}} & \dots & g_{1, i_{k}} \\ g_{2, i_{1}} & g_{2, i_{2}} & \dots & g_{2, i_{k}} \\ ︙ & ︙ & ︙ \\ g_{n, i_{1}} & g_{n, i_{2}} & \dots & g_{n, i_{k}} \end{matrix}] [\begin{matrix} x_{i_{1}} \\ x_{i_{2}} \\ ︙ \\ x_{i_{k}} \end{matrix}] \end{matrix} \end{matrix}$ (6)

式(6)的解( $\begin{matrix} x_{j_{1}} \end{matrix}$ , …, $\begin{matrix} x_{j_{2 n - k}} \end{matrix}$ )∈ {0, 1}2n-k之数量即为 $\begin{matrix} |G'_{z}| \end{matrix}$ , 令(6)关于( $\begin{matrix} x_{j_{1}} \end{matrix}$ , …, $\begin{matrix} x_{j_{2 n - k}} \end{matrix}$ )的系数矩阵为G'∈ $\begin{matrix} F_{2}^{n \times (2 n - k)} \end{matrix}$ , 则 $\begin{matrix} |G'_{z}| \end{matrix}$ =2^n-k当且仅当Rank(G')=n(Rank(G')为G'的秩)。从G'中任选n列共可得到 $\begin{matrix} F_{2}^{n \times n} \end{matrix}$ 中 $\begin{matrix} C_{2 n - k}^{n} \end{matrix}$ = $\begin{matrix} \frac{(n + 1) \cdot (n + 2) \cdot \dots \cdot (n + n - k)}{(n - k)!} \end{matrix}$ 个矩阵, 这些矩阵中只要有一个非奇异, 即有Rank(G')=n。又 $\begin{matrix} F_{q}^{n \times n} \end{matrix}$ 中共有 $\begin{matrix} \prod_{i}^{=} \end{matrix}$ (qⁿ-qⁱ)个非奇异矩阵, 令 $\begin{matrix} F_{q}^{n \times n} \end{matrix}$ 中非奇异矩阵所占比率为Δ ( $\begin{matrix} F_{q}^{n \times n} \end{matrix}$ ), 则有:

Δ ( $\begin{matrix} F_{q}^{n \times n} \end{matrix}$ )= $\begin{matrix} \frac{\prod_{i}^{=} (q^{n} - q^{i})}{q^{n^{2}}} \end{matrix}$ =

$\begin{matrix} \frac{(q^{n} - 1) \cdot (q^{n} - q) \cdot \dots \cdot (q^{n} - q^{n - 1})}{q^{n^{2}}} \end{matrix}$ =

$\begin{matrix} \frac{(q - 1) \cdot (q^{2} - 1) \cdot \dots \cdot (q^{n} - 1)}{q \cdot q^{2} \cdot \dots \cdot q^{n}} \end{matrix}$ ⇒

Δ ( $\begin{matrix} F_{q}^{(n + 1) \times (n + 1)} \end{matrix}$ )=Δ ( $\begin{matrix} F_{q}^{n \times n} \end{matrix}$ )· $\begin{matrix} \frac{(q^{n + 1} - 1)}{q^{n + 1}} \end{matrix}$ (7)

下式为对部分Δ ( $\begin{matrix} F_{2}^{n \times n} \end{matrix}$ )的计算结果:

$\begin{matrix} \{\begin{matrix} Δ (F_{2}^{2 \times 2}) = 0.375 \\ Δ (F_{2}^{3 \times 3}) = 0.328125 \\ Δ (F_{2}^{4 \times 4}) = 0.3076171875 \\ ⋮ \\ Δ (F_{2}^{16 \times 16}) = 0.28879250168805531183021874034606 \end{matrix} \end{matrix}$ (8)

对于n> 16, 由

Δ ( $\begin{matrix} F_{2}^{k \times k} \end{matrix}$ )-Δ ( $\begin{matrix} F_{2}^{(k + 1) \times (k + 1)} \end{matrix}$ )= $\begin{matrix} \frac{Δ (F_{2}^{k \times k})}{2^{(k + 1)}} \end{matrix}$ (9)

k=16, …, n-1

可得:

Δ ( $\begin{matrix} F_{2}^{16 \times 16} \end{matrix}$ )-Δ ( $\begin{matrix} F_{2}^{n \times n} \end{matrix}$ )= $\begin{matrix} \overset{n - 1}{\sum_{i = 16}} \end{matrix} \begin{matrix} \frac{Δ (F_{2}^{i \times i})}{2^{i + 1}} \end{matrix}$ <

Δ ( $\begin{matrix} F_{2}^{16 \times 16} \end{matrix}$ )· $\begin{matrix} \overset{n - 1}{\sum_{i = 16}} \end{matrix} \begin{matrix} \frac{1}{2^{i + 1}} \end{matrix}$ < Δ ( $\begin{matrix} F_{2}^{16 \times 16} \end{matrix}$ )· $\begin{matrix} \overset{\infty}{\sum_{i = 16}} \end{matrix} \begin{matrix} \frac{1}{2^{i + 1}} \end{matrix}$ =Δ ( $\begin{matrix} F_{2}^{16 \times 16} \end{matrix}$ )· $\begin{matrix} \frac{1}{2^{16}} \end{matrix}$ ⇒

Δ ( $\begin{matrix} F_{2}^{n \times n} \end{matrix}$ )> $\begin{matrix} \frac{2^{16} - 1}{2^{16}} \end{matrix}$ · Δ ( $\begin{matrix} F_{2}^{16 \times 16} \end{matrix}$ )> 28.87%(10)

又G∈ $\begin{matrix} F_{2}^{n \times 2 n} \end{matrix}$ 是随机选择, 所以Rank(G')≠ n的概率Pr(Rank(G')≠ n)为:

(1-Δ ( $\begin{matrix} F_{2}^{n \times n} \end{matrix}$ )) $\begin{matrix} C_{2 n - k}^{n} \end{matrix}$ < 0.7113 $\begin{matrix} C_{2 n - k}^{n} \end{matrix}$ (11)

而n与k相差足够大(否则最多2^n-k次猜测便可破解B中的Semi-SSP), 故在现实中可认为恒有Rank(G')=n, 即有 $\begin{matrix} |G_{z}^{'}| \end{matrix}$ =2^n-k, 这意味着即使在已知( $\begin{matrix} x_{i_{1}} \end{matrix}$ , …, $\begin{matrix} x_{i_{k}} \end{matrix}$ )的情形下, 破译x仍需对G'中2^n-k个候选解逐个进行判定。这与通过蛮力试探来求解B中的Semi-SSP并无本质区别, 定理证毕。

4 结束语

本文引入了“ 半陷门单向函数” 的概念, 并给出了基于半陷门单向函数来构造公钥密码的思路。在此基础上, 给出了一种新的背包密码方案STOF_PKC, 并证明了破解STOF_PKC等价于求解B中的Semi-SSP。因此, 若B中的Semi-SSP是难解的, 则STOF_PKC便是安全的。但尚有一些新问题有待解决, 比如是否存在其他实现半陷门单向函数的方法、是否存在其他基于半陷门单向函数的公实现签名等, 需要进行更深入的探索。

The authors have declared that no competing interests exist.

参考文献

View Option

[1]	Diffie W, Hellman M E. New directions in cryptography[J]. IEEE Transactions on Information Theory, 1976, 22: 644-654. [本文引用:1]
[2]	Merkle R C, Hellman M E. Hiding information and signatures in trapdoor knapsacks[J]. IEEE Transactions on Information Theory, 1978, 24: 525-530. [本文引用:2]
[3]	Rivest R L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the Acm, 1983, 26: 96-99. [本文引用:1]
[4]	Shor P W. In algorithms for quantum computation: Discrete logarithms and factoring, foundations of computer Science[C]∥Proceedings on Symposium, Murray Hill, NJ, USA, 1994: 124-134. [本文引用:1]
[5]	Grover L K. A fast quantum mechanical algorithm for database search[C]∥Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, Philade lphia, PA, USA, 1996: 212-219. [本文引用:1]
[6]	Poulakis D. On the cryptographic long term security[J]. Journal of Applied Mathematics & Bioinformatics, 2013, 3(1): 1-15. [本文引用:1]
[7]	Courtois N, Finiasz M, Sendrier N. In how to achieve a mceliece-based digital signature scheme[C]∥ International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, 2001: 157-174. [本文引用:1]
[8]	Porras J, Baena J, Ding J Zhfe. A new multivariate public key encryption scheme[Z]. Post-Quantum Cryptogaphy, 2014: 229-245. [本文引用:1]
[9]	Dehornoy P. Using shifted conjugacy in braid-based cryptography[J]. Computer Science, 2006, 418: 65-73. [本文引用:1]
[10]	Okamoto T, Tanaka K, Uchiyama S. Quantum public-key cryptosystems[J]. International Journal of Theoretical Physics, 2011, 51: 912-924. [本文引用:1]
[11]	Elkies N D. An improved lower bound on the greatest element of a sum-distinct set of fixed order[J]. Journal of Combinatorial Theory, 1986, 41: 89-94. [本文引用:1]
[12]	Guy R K. Unsolved Problems in Number Theory[M]. New York-Berlin: Springer-Verlag, 2001: 17-35. [本文引用:1]
[13]	Kate A, Goldberg I. Generalizing cryptosystems based on the subset sum problem[J]. International Journal of Information Security, 2011, 10: 189-199. [本文引用:1]
[14]	Brickell E F. Breaking iterated knapsacks[C]∥Advances in Cryptology, Proceedings of CRYPTO’84, Santa Barbara, California, USA, 1984: 342-358. [本文引用:2]
[15]	Coster M J, Joux A, Lamacchia B A, et al. Improved low-density subset sum algorithms[J]. Computational Complexity 1999, 2: 111-128. [本文引用:1]
[16]	Joux A. A practical Attack Against Knapsack based Hash Functions (Extended )[M]. Berlin Heidelberg: Springer, 1994: 58-66. [本文引用:1]
[17]	Nguyẽn P Q, Stern J. Adapting density attacks to low-weight knapsacks[J]. Lecture Notes in Computer Science, 2005, 3788: 41-58. [本文引用:1]
[18]	Impagliazzo R, Naor M. Efficient cryptographic schemes provably as secure as subset sum[J]. Journal of Cryptology, 1996, 9: 199-216. [本文引用:1]
[19]	Schroeppel R, Shamir A. A T=O(2ⁿ^/2), S=O(2ⁿ/⁴) algorithm for certain NP-complete problems[J]. Siam Journal on Computing, 1981, 10(3): 456-464. [本文引用:1]
[20]	Li Qing-hua, Li Ken-li, Jiang Sheng-yi, et al. An optimal parallel algorithm for the knapsack problem[J]. Journal of Software, 2003, 14(14): 891-896. [本文引用:1]
[21]	Christos H Papadimitriou. On the complexity of unique solutions[J]. Journal of the ACM, 1984, 31(2): 392-400. [本文引用:1]
[22]	Shamir A. A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem[J]. IEEE Transactions on Information Theory, 1984, 30(5): 699-704. [本文引用:1]

1976

0.0

... 0 引言1976年,Diffie和Hellman^[1]发表了著名文章《密码学的新方向#cod#x0201d ...

1978

0.0

... 不久,第一批公钥密码方案便被提了出来,它们分别是Merkle和Hellman基于背包问题的MH密码体制^[2]以及Rivest、Shamir和Adelman基于整数分解问题的RSA密码体制^[3] ...

... PQC的主要目标便是研究能抵抗量子计算的公钥密码(Quantum resistant public key cryptography),目前主要基于量子计算机不擅长计算的数学难题(比如NPC问题)来设计密码,该类密码主要有如下几个研究方向:基于格上困难问题的密码^[6]、基于纠错码译码问题的密码^[7]、基于多变量的密码^[8]、基于辫子群(Braid Group)的密码^[9]以及基于背包问题的密码^[2,10] ...

1983

0.0

1994

0.0

... 进入到21世纪,现有公钥密码(RSA、ElGamal、ECC等)日益受到量子计算的威胁^[4,5],为了应对挑战,国际密码学界提出了#cod#x0201c ...

1996

0.0

... 进入到21世纪,现有公钥密码(RSA、ElGamal、ECC等)日益受到量子计算的威胁^[4,5],为了应对挑战,国际密码学界提出了#cod#x0201c ...

2013

0.0

2001

0.0

2014

0.0

2006

0.0

2011

0.0

1986

0.0

2001

0.0

2011

0.0

1984

0.0

... 早期算法^[14]可破解密度小于0 ...

... 性来破解(M',U)^[14,22] ...

1999

0.0

... 6463的背包密码,改进后算法^[15]则可破解密度小于0 ...

1994

0.0

... 这两种情形均易受到基于格的攻击^[16,17] ...

2005

0.0

... 这两种情形均易受到基于格的攻击^[16,17] ...

1996

0.0

... Impagliazzo和Naor亦证明,当D_A=1时,求解A中SSP是最困难的^[18] ...

1981

0.0

... 多年来,对SSP最快的通用解法仍是Schroeppel和Shamir在1981年提出的^[19],算法的时空复杂度分别为O(n#cod#x000b7 ...

2003

0.0

... 最近才有人对其进行了优化^[20],但改进算法仍是指数级的,只是将时间复杂度降为O(n#cod#x000b7 ...

1984

0.0

... 1时,判定A是否满足USS条件亦是NPC问题^[21] ...

1984

0.0

... 性来破解(M',U)^[14,22] ...