P/NP/NPC/NPH问题和多项式/指数/阶乘时间复杂度、非多项式级复杂度,fuzzy vault安全性

多项式/指数/阶乘时间复杂度、非多项式级复杂度,fuzzy vault安全性"/>

P/NP/NPC/NPH问题和多项式/指数/阶乘时间复杂度、非多项式级复杂度,fuzzy vault安全性

多项式时间复杂度指的是解决问题需要的时间与问题的规模之间是多项式关系。

多项式关系形如，k为某个常数，n是问题的输入规模(例如n个未知数）。例如，时间复杂度为 O ( n l o g ( n ) ) 、 O ( n 3 ) O(nlog(n))、O(n^3) O(nlog(n))、O(n3)都是多项式时间复杂度。时间复杂度为 O ( n l o g ( n ) ) 、 O ( 2 n ) O(n^log(n))、O(2^n) O(nlog(n))、O(2n)是指数时间复杂度，O(n!)是阶乘时间复杂度。像O(a^n)和O(n!)型的时间复杂度，它是非多项式级的，其复杂度计算机往往不能承受。

各类问题描述

• NP与P的关系
  目前，人类还未解决的问题是：是否所有的NP问题都是P类问题，即P=NP?。这就是注明的世界七大数学难题之首。虽然这个问题尚未解决，但是，一个总的趋势和大方向是人们普遍认为，P=NP不成立，也就是说，多数人相信，存在至少一个不可能有多项式级复杂度的算法的NP问题。
  人们如此坚信P≠NP是有原因的，就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题（Non-deterministic Polynomial Complete Problem），也即所谓的 NPC问题。正是NPC问题的存在，使人们相信P≠NP。

• NPC问题的约化
  约化(Reducibility/“归约”（Reduction）： 如果能找到这样一个变化法则，对任意一个程序A的输入，都能按这个法则变换成程序B的输入，使两程序的输出相同，那么我们说，问题A可约化为问题B，即可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。 如：一元一次方程可以“归约”为一元二次方程。

  约化的性质：
  约化具有一项重要的性质：约化具有传递性。如果问题A可约化为问题B，问题B可约化为问题C，则问题A一定可约化为问题C。

  约化的意义：
  问题A可约化为问题B”有一个重要的直观意义：B的时间复杂度高于或者等于A的时间复杂度。也就是说，问题A不比问题B难。

  约化的要求：
  我们所说的“可约化”指的是可“多项式时间地”约化(Polynomial-time Reducible)，即变换输入的方法是能在多项式的时间里完成的。约化的过程只有用多项式的时间完成才有意义。

• 第一个NPC问题
  逻辑电路问题是第一个NPC问题。逻辑电路问题指的是这样一个问题：给定一个逻辑电路，问是否存在一种输入使输出为True。

  逻辑电路问题属于NPC问题。这是有严格证明的。它显然属于NP问题，并且可以直接证明所有的NP问题都可以约化到它（不要以为NP问题有无穷多个将给证明造成不可逾越的困难）。证明过程相当复杂，其大概意思是说任意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出（想想计算机内部也不过是一些0和1的运算），因此对于一个NP问题来说，问题转化成了求出满足结果为True的一个输入（即一个可行解）。

• 有了第一个NPC问题后，一大堆NPC问题就出现了，因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。后来，Hamilton回路成了NPC问题，TSP问题（旅行商问题）也成了NPC问题。现在被证明是NPC问题的还有很多，任何一个NPC问题找到了多项式算法的话所有的NP问题都可以完美解决了。因此说，正是因为NPC问题的存在，P=NP变得难以置信。P=NP问题还有许多有趣的东西，有待大家自己进一步的挖掘。攀登这个信息学的巅峰是我们这一代的终极目标。现在我们需要做的，至少是不要把概念弄混淆了。

Fuzzy vault 安全性

Gopalan, Parikshit, Subhash Khot, and Rishi Saket. “Hardness of reconstructing multivariate polynomials over finite fields.” SIAM Journal on Computing 39.6 (2010): 2598-2621.

给定一个多项式，n个数据点和对应的映射之后的值，允诺有一个d次的多项式，与1-e数据相符.
结论：
基于多余 1 − 2 − d + δ 1-2^{-d}+\delta 1−2−d+δ比例的数据点，寻找这样一个多项式是NPH问题。

在fuzzy vault中，Chaff point 越多， 1 − 2 − d + δ 1-2^{-d}+\delta 1−2−d+δ就符合越好，计算安全就越高。但是注意的是，fuzzy vault安全性不取决d, 取决于Chaff points.

The security of our fuzzy vault construction depends on the number of chaff points r − t r-t r−t in the target set R R R. The greater the number of such points, the more “noise” there is to conceal p p p from an attacker. As many chaff points are added to R , R, R, there begins to emerge a set of spurious polynomials that look like p , p, p, i.e., polynomials that have degree less than k k k and agree with exactly t t t points in R R R. Briefly stated, the more chaff points there are, the greater the probability that some set of t t t of these chaff points (and/or real points) align themselves by chance on some polynomial of the desired degree. In the absence of additional information, an attacker cannot distinguish between the correct polynomial p p p and all of the spurious ones. Thus, p p p is hidden in an informationtheoretically secure fashion in R R R, with security proportional to the number of spurious polynomials. Note that the security of the vault V A V_{A} VA​ depends exclusively on the number of such polynomials, and not on the length of the secret key κ \kappa κ; the vault is often weaker than the secret κ \kappa κ it protects (which is acceptable for the applications we describe). The following lemma proves that with high probability many polynomials degree less than k k k agree with the target set R R R in t t t places, i.e.that there are many spurious polynomials. This lemma and its proof are based on similar results of Dumer et al. [9] .

Recall that the locking algorithm Lock picks t t t points according to a given p p p of degree less than k k k and r − t r-t r−t random points ( x i , y i ) \left(x_{i}, y_{i}\right) (xi​,yi​) in F × F \mathcal{F} \times \mathcal{F} F×F and outputs this set in random order as a vault hiding p ( p( p( i.e., κ \kappa κ ). Recall that q q q denotes the cardinality of F \mathcal{F} F. The following lemma is parameterized by r , k , r, k, r,k, and t t t and a small real number μ . \mu . μ. Proof of the lemma may be found in the appendix.

Lemma 4. 4 . 4. For every μ > 0 , \mu>0, μ>0, with probability at least 1 − μ , 1-\mu, 1−μ, the target set R R R generated by the algorithm Lock on polynomial p p p and locking set A A A satisfies the following condition: There exist at least μ 3 q k − t ( r / t ) t \frac{\mu}{3} q^{k-t}(r / t)^{t} 3μ​qk−t(r/t)t polynomials p ′ p^{\prime} p′ of degree less than k k k such that R R R includes exactly t t t points of the form ( x , p ′ ( x ) ) ∈ F × F \left(x, p^{\prime}(x)\right) \in \mathcal{F} \times \mathcal{F} (x,p′(x))∈F×F.

Reference:

.html