标准密码假设是什么？我想
分解：给定一个正整数$ n $，求素数分解。
二次残差问题（QRP）：给定一个奇数复合整数$ n $和带有Jacobi符号$（a | n）= + 1 $的$ a $决定$ a $是二次余数还是伪平方模$ n $。
通常被认为是困难的，因此“标准密码假设”。为什么通用汽车可以证明是安全的？但是RSA问题（RSAP）呢？
给定一个正整数$ n $，它是两个不同的奇质数$ p $和$ q $（一个正整数）的乘积$ \ gcd（e，（p-1）（q-1））= 1 $和整数$ c $的$ e $。找到一个整数$ m $，使$ m ^ e \ equiv c \ pmod n $。
RSAP通常也很难吗？因此，RSA是否证明是安全的？
#1 楼
我正在努力理解“标准密码假设”的含义。
“标准假设”广义上是指已经经受了许多智能密码分析家对详细信息进行仔细审查的假设。很久。例如：
我们认为，对于均匀的随机1024位素数$ p $和$ q $，求解$ y = x ^ 3 \ bmod pq $即可给定$ pq $和$ y $很难获得$ x $。
为什么？任何人都能够弄清楚如何做到这一点的最佳方法是通过分解$ n $来恢复$ p $和$ q $，而最著名的方法（ECM和NFS）的成本要高于任何人的预算。 br />
我们认为，给定$ x $和$ y $很难求解统一随机$ k $的$ y = \ operatorname {AES} _k（x）$。
为什么？任何人都能够弄清楚如何做到这一点的最佳方法实质上是通过常规搜索，而最著名的方法（并行彩虹表，并行可分辨点）的成本要高于任何人的预算。
半例：
基于对的加密。配对在会议上的学术密码学中非常流行，但在现实世界中，除了奇特的加密货币应用程序外，很少使用。配对友好的椭圆曲线的安全性远不及更传统的DLOG应用程序（如Diffie-Hellman密钥协商和Schnorr签名）的椭圆曲线的安全性。SVP，LWE和其他点阵问题。晶格是后量子密码技术的一个有前途的领域，但是存在一个庞大的设计空间，其复杂的安全故事尚未稳定下来-不管克里斯·佩克特和丹·伯恩斯坦有多少关于平均情况/最坏情况的完全令人费解的论点
非示例：
编织组中的共轭搜索。编织密码学尚未得到密码学家的广泛研究，而大多数现有建议却被打破。
SIMON和SPECK。这些分组密码在试图加入国际标准化的间谍中很受欢迎，但是事实证明，标准机构如今已经不愿意在没有技术依据的情况下接受“欺骗”一词，而且小于128位的分组大小也是愚蠢的。 br />
Goldwasser–Micali系统（GM）上的Wikipedia文章中写道：“ GM的区别在于它是第一个概率性公钥加密方案，该方案在标准密码假设下可证明是安全的。” br />
这是学术混淆的一个例子，有证据表明Wikipedia是学习密码术的可怕资源。它的意思是：
我们证明了一个定理1，该定理涉及漂亮数论2和渐近增长曲线！3
1这可证明的安全性是什么这并不意味着该定理具有任何现实世界的后果。2这就是“标准假设”在这里的含义：不允许诸如倒置DES这样的丑陋问题，但是却允许诸如分解统一随机质数的乘积之类的漂亮问题。3尚未正式表述：我们只对问题系列的攻击成本的渐近增长曲线感兴趣，因此DES被双重取消资格，因为它很丑陋，因为只有一个DES，而您可以考虑因数分解作为规模函数的问题的因素。 （直到十年后，在Bellare和Rogaway的帮助下，带有具体参数选择的“可证明的安全性”处理方法才被称为“精确安全性”。）
，GM论文有助于建立一些形式化形式，例如用于公钥加密的语义安全性，该形式基本上等同于我们今天使用的现代密文可区分性标准。但是GM加密方案？即使有一个定理，也完全没用。
这种迷惑和对数字理论的美化很迷恋，使人们走上了令人遗憾的道路，例如采用Dual_EC_DRBG，该方法仅凭基于数字理论的推动就接受了“基于数字理论的安全性”的证据作为主要的国家密码标准。由像丹·布朗（Dan Brown）这样的前批评家，他的主要专长是混淆了没人能通过的大量分析性散文中的后门。因此，RSA证明是安全的吗？
RSA问题-计算$ e ^ {\ mathit {th}} $根以大秘密素数的乘积为模，通常很难解决。有一些基于RSA的公共密钥加密方案和公共密钥签名方案，例如RSAES-OAEP，RSA-KEM，RSASSA-PSS，RSA-FDH，这些定理在说明破解难度方面甚至很有用。加密系统的安全性（区分密文，伪造签名）以计算$ e ^ {\ mathit {th}} $的根为模，计算出大秘密素数的乘积。
但是我建议您远离“可证明的安全性”这个不诚实的术语，因为它掩盖了您的实际意思，尤其是以“ X是可证明的安全性”的形式掩盖的。
方案是否具有“可证明的安全性”或对于构建系统的用户或工程师而言，这不是无关紧要的-密码分析家关于什么密码技术将承受攻击的结论与他们有关。 “可证明的安全性”实际上是指导密码分析者集中精力。将AES-CTR与AES分开进行分析是没有意义的，因为（a）取决于滥用CTR，（b）基于AES的本质是排列而不是任意函数，或者（c）打破AES-CTR的任何方法。 ）表示对AES的攻击。这是因为存在一个有用的定理，它将对AES-CTR的任何攻击与对AES本身的攻击相关联。
同样，在不尝试计算$ e ^ {\ mathit {th}} $根的情况下伪造RSA-FDH签名也没有多大意义，因为（由于有用的定理）我们知道，对一个问题所做的任何工作都会立即转化为另外，只要哈希函数不会以任何有趣的方式与RSA交互（这将非常惊人）。因此，密码分析人员可以忽略RSA-FDH的详细信息，而专注于计算$ e ^ {\ mathit {th}} $根，从而使我们对RSA-FDH的安全性充满信心。
评论
$ \ begingroup $
为什么要谈论“渐近安全性”？即使在可证明的安全性中使用安全性参数非常普遍，但这也不是重点。而且您可以证明安全性而无需使用任何“渐近参数”：
$ \ endgroup $
–伊夫让尼
19年11月7日15:04
$ \ begingroup $
@Ievgeni我在说这是因为这就是GM文件的全部内容。是的，也有具体可证明的安全性文献，但是直到后来才出现。
$ \ endgroup $
–吱吱作响的s骨
19年11月7日在15:14
$ \ begingroup $
@SEJPM我并不是说这些定理是没有用的。我是说“可证明的安全性”一词无济于事-尤其是将其用作对完全无效的渐进式密码系统家族（如GM）的广告。一个具体密码系统的安全性合同是真正重要的，其中包括安全使用限制。安全使用限制是来自ECM / NFS成本评估还是来自Oracle归约定理，对工程师而言并不重要！
$ \ endgroup $
–吱吱作响的s骨
19年11月7日15:16
$ \ begingroup $
@SqueamishOssifrage好吧……您的句子“可提供的安全性与用户或工程师有关构建系统的决策无关。”是有争议的，如果您在“工程师对建筑系统做出决策”类别中考虑“ NIST”，那将是非常有争议的...
$ \ endgroup $
–伊夫让尼
19年11月7日15:21
$ \ begingroup $
@Ievgeni不仅如此，“可证明的安全性”还涵盖了无用的定理。我可以为1位通用散列验证器“证明安全性”，即信息理论上的“安全性”，但是在学术理论之外的任何有意义的意义上，“ 1/2”的伪造概率边界都不能用作“安全性”是否有一个定理。
$ \ endgroup $
–吱吱作响的s骨
19年11月7日在15:28
#2 楼
没有标准假设的正式定义，但是我们通常说假设是一个标准假设，前提是该假设已经在多种加密方案中使用，并且在加密社区中被广泛接受。通常也暗示着一些研究人员试图解决问题，但找不到有效的解决方法，因此，如果我们正确设置参数，就没有已知的快速解决问题的方法。例如，假设RSA问题很棘手是一个标准假设。可证明的安全性（在这种情况下）仅意味着假设基本问题难以解决，就可以证明该方案满足某些安全性概念（例如CPA安全性）。但是，如果根本问题不是标准的，那么该方案仍然可以证明是安全的。
评论
我相信，在谈论标准密码假设时，我们将从密码标准模型的角度来看一个密码系统。在密码标准模型中，对手（其目标是破坏密码系统）受时间和计算能力的限制。嗯，“非标准”假设通常是作者不喜欢的任何假设。
我认为作者试图提出的观点更多是这样的：从第一个概率加密方案的意义上讲，GM系统是第一个可证明是安全的（具有合理的假设，例如，“我的系统不是安全的假设”）。 （RSA是确定性的，因此不是可证明的CPA /语义安全），这是第一个，因为在文献中从字面上描述了RSA，并引入了安全性概念，没有人偶然在“偶然”之前构造出CPA安全的。 >
仅供参考，所谓的“标准模型”通常是学术密码学家通过保留术语“标准模型”来掩盖现实世界中使用散列函数（示例）的每个人的方式，对于那些是完全不切实际的，并且从未使用过，然后用听起来很可怕的术语“随机预言模型”来表征每个人的实际操作（更多细节）。
@SqueamishOssifrage在ROM中没有安全的方案，但是在oracle的任何实例化下都不安全吗？这听起来像是一个实际问题，而不仅仅是“投射阴影”。