RSS订阅信息安全技术跟踪与研究:技术、平台、会议、论文、产业
你现在的位置:首页 / 技术积累 / 正文

52知识点之六:NP理论

0 技术积累 | 2015年4月27日
转载申明:本站原创,欢迎转载。但转载时请保留原文地址。
原文地址:http://www.vonwei.com/post/6outof52.html

 

52 Things: Number 6: How can we interpret NP as the set of theorems whose proofs can be checked in polynomial time?

Posted by Dan Martin

原文链接:http://bristolcrypto.blogspot.com/2014/11/52-things-number-6-how-can-we-interpret.html

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. We continue the Complexity Theory section with an alternative definition of NP...

 

This question is very much a follow up question to the previous one. Last week Guy answered the question of ``What is meant by the complexity class NP?'', while this week I will be answering the related question of ``How can we interpret NP as the set of theorems whose proofs can be checked in polynomial time?''.

 

Now to me this is a more intuitive definition of what it means for a problem to be in NP. Not only is it a more intuitive definition but it should (hopefully) also be clearer as to why this is a complexity class that is useful both for cryptography and the wider world. Now before we go into what we can use the class of problems for, the definition is as follows:

NP is the class of languages that have polynomial time verifiers.

OK but what does this actually mean? Basically if we have an element x and we want to know if xL (where L is some NP language) we have a prover P which given xoutputs a witness w, this may take exponential time to find w given x. Then if we give xand w to our verifier VV can tell if xL in polynomial time.

This definition seems very different from the one given last week but they are in fact equivalent. Informally they are equivalent because the witness w can just be the sequence of decisions the NDT made at each branching point to show that xL. For a (slightly) more formal proof of their equalence [1] is a reasonable online source (with references to textbooks).

这周的问题与上周介绍的NP复杂类问题密切相关。在开始之前,先以问题类的方式对NP进行定义,如下:NP是一个语言类,拥有多项式时间验证者。如何理解这个定义呢?如果我们拥有一个元素x,我们想知道是否x属于语言L(这里L是某个NP语言)。我们有一个证明者P,针对给定x可以输出一个证据w,给定x找到w可能要花掉指数级的时间。那么,如果我们将xw告诉我们的验证者VV可以在多项时间内告诉是否x属于L。这个定义看上去比知识点5中的要难以理解,不过本质上是等价的。证据w可以看成是NDTM在每个分支点的决定构成的序列,来证明是否x属于L。关于如何通过形式化方法来证明两个定义等价,可以上网找参考,如[1]

 

So why might this be useful in cryptography? Well essentially we have a class of languages which can take exponential time to check if you do not know a witness but with a witness it can be done in polynomial time. This has the ``feel'' of a lot of cryptographic algorithms - take Encryption (formalisation to follow in future weeks' blogs) for example; you want it to be exponentially hard to get the message from ciphertext without the key (similar to a witness) but with the key you want it to be efficient (polynomial time) to extract the message.

A warning: While it sounds like a good move to use an NP problem for cryptography it may not be as simple as it first appears. This is because languages are in NP based on the worse case complexity where as for encryption we need it to be hard on average. For example we may have an NP language which has one element that takes exponential time to solve but all others are really efficient to solve - this will not make a good basis for an encryption scheme because we want encryption to be secure for all messages not just one.

通过上面的介绍,我们拥有一个语言类,如果你不知道证据w可能花费指数级时间,而如果拥有一个证据其可以在多项式时间内解决。这和很多密码算法的感觉是非常相似的:以加密为例,没有密钥(类似证据w)时想从密文中获取原文消息可能需要指数级的时间;但是如果拥有密钥,你可以在多项式时间内解获原文消息。这或许描述了为什么NP问题在密码系统中如此有用的契机。一个警告:在密码机制中使用NP问题是很自然的事情,但并不是所有的NP问题都能用。因为NP中语言是基于最糟糕的情况,而加密机制需要平均程度上都是困难的。例如,如果一个NP语言中,只有一个元素需要花费指数级时间去解决,而其它都可以有效解决,这显然不适合加密机制。加密机制最好保证所有消息的安全,而不是仅仅只针对一个。

 

Now I am aware that integer factorization isn't known to be NP-complete and isn't known to be in P (See Ryan's blog here for a description) but it makes for a nice example of the point I am trying to make about choosing your NP instances carefully. In general finding a factor of a number is easy (half of them are divisible by two!) but if we choose something sensible we can make it hard to factor. Let us focus on numbers of the form N=p?q for p,q prime (a.k.a numbers with only two proper factors). Now if either of these numbers is small then it is again easy, so we want the numbers to be of equal size (this is what we do for RSA). From this it is possible to build an encryption scheme over the top.

       整数分解问题还不清楚是否NP完全,也不清楚是否属于P,不过可以作为一个很好的例子来教你选择NP实例。通常来说找到一个数的因子是很简单的,一半整数拥有因子2,但是如果选择不一样,可以使得整数分解变得非常困难。看看N=p*qpq为素数,如果两个素数都很大,最好拥有相近的规模(RSA就是这么做的),这样就可以构建一个加密机制。

 

[1] - http://en.wikipedia.org/wiki/NP_(complexity)#Equivalence_of_definitions



  • ------------------分隔线----------------

  • 如果感兴趣,欢迎关注本站微信号,跟踪最新博文信息,手机微信扫一扫下面的二维码,即可关注!
  • 微月信公众号
  • 推荐您阅读更多有关于“ 52知识点   ”的文章

    请填写你的在线分享代码
    上一篇:52知识点之五:非确定型图灵机、NP复杂类下一篇:模糊提取器:Fuzzy Extractor and Secure Sketch

    猜你喜欢

    评论列表:

    发表评论

    必填

    选填

    选填

    必填,不填不让过哦,嘻嘻。

    记住我,下次回复时不用重新输入个人信息

    本站介绍
    最近发表
    本年最热文章
    本月最热文章
    网站分类
    文章归档