4
研究人员确定密码学背后的“主问题”
source link: https://www.solidot.org/story?sid=71175
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
研究人员确定密码学背后的“主问题”
只要人们还在发送加密信息，密码学家就一直在玩这种猫捉老鼠的游戏——创造密码并破解密码。康奈尔科技学院和康奈尔大学的密码学家 Rafael Pass 表示：“几千年来，人们一直想弄清楚，‘我们可以打破这个循环吗？’”五十年前，密码学家朝着这个方向迈进了一大步。他们证明只要有“单向函数”，你就可以创建被证明是安全的密码。单向函数是一种很容易计算的函数，但很难逆运算。从那时起，研究人员设计出各种候选单向函数，从基于乘法的简单运算到更复杂的几何或对数运算都有。
今天负责传输信用卡号和数字签名等任务的互联网协议依赖于这些函数。以色列海法理工学院的密码学家 Yuval Ishai 表示：“现实世界中使用的绝大多数加密都可以基于单向函数。”但这一进步没有终结这场猫捉老鼠的游戏——只是更加突出了它的焦点。现在密码学家不必担心加密方案各个方面的安全性，只要关注其核心的函数即可。但是目前使用的函数中没有一种被明确证明是单向函数——我们甚至不确定真正的单向函数是否真的存在。密码学家证明，如果它们确实不存在，那么安全加密就是不可能的。
在缺乏证据的情况下，密码学家只能希望能在攻击中幸存下来的函数是安全的。Ishai 表示，研究人员没有统一的方法来研究这些函数的安全性，因为每种函数都“来自不同的领域，来自不同的专家组”。长期以来，密码学家们一直想知道是否有一种不那么特别的方法。Pass 问道：“是否存在着某个问题，只有一个主问题，告诉我们密码学是否可行？”
现在他和康奈尔大学的研究 生Yanyi Liu 证明答案是肯定的。他们证明，真正单向函数存在与否取决于计算机科学另一个领域中最古老也最核心的问题之一，这个领域被称为复杂性理论或计算复杂性。这个被称为Kolmogorov 复杂性的问题涉及区分随机数字字符串和包含某些信息的字符串之间的区别有多难。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK