Zero Knowledge Proof

最近发现 Dr Dobb’s 这个站上有不少不错的文(要说我火星的下面排队)。比如下面这篇,让我又一次意识到自己的智商比较成问题了。。。
http://drdobbs.com/architecture-and-design/232300619
注意第二页是答案了。记住解答里需要有一个交互的过程,注意到这点的话应该不会太难了。

那篇附带在reading里的paper还是有点难看懂的,部分涉及用于密码学的数论问题。总的来说这个技术基本是通过 NP问题 来展示的,因为那个是所谓的多项式时间可验证的问题,一般的证明都会提供一个解答以供验证,这便是证明方提供的的多余的知识了。所谓零知识的证明就是通过随机数和交互的方式基本避免证明方提供多余知识。需要注意的是验证方的知识处理能力一般会被限制在多项式时间复杂度上。

顺便玩了会数独。似乎解题的算法基本还是得靠直觉优化的递归/遍历。

Advertisements
This entry was posted in Science. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s