是否有任何硬度假设不涉及数字理论问题的公钥密码系统？

评论

LWE是否算作数字理论问题？
从该文章的摘要中，似乎硬度假设至少部分地基于晶格问题，所以也许吗？它取决于问题是否很难解决，而与那些晶格问题无关。
McEliece呢？它的硬度基于对一般线性代码的解码。
那肯定很重要。
@ D.W。并非所有公共密钥加密都基于双射单向函数。哈希签名显然不是。甚至RSA也是一个陷阱门功能，而不是SDL所寻找的一种单向功能（除非您将私钥丢弃）

#1 楼

是。迄今为止，使用二进制Goppa码的McEliece密码系统经受住了密码分析的考验。它的硬度基于解码。我应该注意，对于某些类的代码来说，它已经被破坏了。不幸的是它被打破了。可能有可能基于背包问题构建安全的密码系统。我至少要提到这方面的工作。

#2 楼

除了McEliece（已经由Mike提到过）之外，还存在基于哈希的签名（例如该签名）。这些是签名算法，仅基于哈希函数的某些安全性假设（以及典型的哈希函数，尽可能远离数值理论问题）。

评论

$ \ begingroup $
哈希签名是我长期信任的唯一签名，因为它们仅涉及非结构化加密。
$ \ endgroup $
– CodesInChaos
16年6月27日在17:12


$ \ begingroup $
@CodesInChaos：是的，是的；因为我听说过的每个签名算法都以“散列消息”开始，所以他们仍然信任散列函数。使用基于哈希的签名，您就不会再相信其他任何东西了……
$ \ endgroup $
–雨披
16年6月27日在17:28
$ \ begingroup $
嗯... @CodesInChaos我不知道为什么比特币当时不选择HBS？考虑到它应该永远是安全的。
$ \ endgroup $
– Elliot Gorokhovsky
16年6月27日在20:05
$ \ begingroup $
@RenéG因为签名很大，所以大小对于比特币确实很重要。 ECDSA需要64个字节。一次性哈希签名需要数百个字节。可重用的无状态哈希签名，例如兆字节。
$ \ endgroup $
– CodesInChaos
16年6月27日在21:09
$ \ begingroup $
@CodesInChaos：“可重用的无状态哈希签名，例如兆字节”；实际上，Sphincs只需要40k（不是设计比特币时就知道Sphincs）；如果您需要一个可以为每个公钥生成十亿个签名的签名方法（并且不介意有状态），则可以在2k内完成
$ \ endgroup $
–雨披
16-6-27在21:19


#3 楼

这仅作为思想练习有用，但是Alice和Bob只能根据AES或其他一些私人密码的强度进行密钥交换：假设：执行$ 2 ^ {40} $操作将需要“一会儿”但可行的； $ 2 ^ {80} $运算已超出一个世纪的可能性范围。爱丽丝可以发布无法篡改的任意信息

爱丽丝生成$ 2 ^ {40} $ AES密钥（假设每个密钥都是128位密钥，即$ 2 ^ {44} $字节，也就是16 TB） ），并使用另一个随机AES密钥以及一个检查值对其进行加密。然后，她使用她选择的大多数密钥（除了40位以外的所有密钥）发布此数据集。假设校验值也是128位，那么我们现在谈论的是48 TB，因此，这再次仅作为思想实验有用。这需要$ O（2 ^ {40}）$步骤，并且需要大约相同的存储空间。将采取$ O（2 ^ {40}）$步）。鲍勃使用解密后的密钥向爱丽丝发送消息，该密钥再次具有校验值。然后，爱丽丝必须尝试所有$ 2 ^ {40} $键（这又需要$ O（2 ^ {40}）$步骤），直到她找到可以产生预期校验值的键为止，然后鲍勃和爱丽丝已经同意使用128位AES密钥。

夏娃将不得不强行使用所有消息（这将花费$ O（2 ^ {80}）$，这在没有量子计算机的情况下被认为是相当安全的）。

评论

$ \ begingroup $
这是Merkle拼图方案。 $，$ O（2 ^ {80}）$操作并没有像Foon希望的那样完全超出可能性范围。
$ \ endgroup $
–雨披
16年6月28日在17:05
$ \ begingroup $
在不到一周的时间内，所有比特币矿工一起计算2 ^ 80 SHA-256调用。
$ \ endgroup $
– CodesInChaos
16年6月28日在17:10
$ \ begingroup $
感谢您的名字poncho（旨在指出这是从我的密码教科书中找到的，我现在似乎无法援引……而且也只是为了引用CodesInChaos的观点（或指向包含引文的答案的链接：crypto.stackexchange.com/questions/13299/…提到2015年底的比特币挖矿每年做2 ^ 84.7 SHA-256）
$ \ endgroup $
–oon
16年6月28日在19:34

#4 楼

我目前正在查看“基于SAT的公钥密码方案”（PDF），其中提出了一个基于NP可满足的布尔可满足性问题的公钥密码方案。看起来非常有趣，并且指导者还在GitHub上提供了一个实现。公钥是由私钥满足的SAT公式。

评论

$ \ begingroup $
我大约一年前读过该论文，我记得它存在严重问题...我现在很忙，但请给我几天时间，我将再次阅读并记住攻击是什么。
$ \ endgroup $
– Elliot Gorokhovsky
16年6月28日在16:43