我们是否允许/是否允许并行化(例如GPU编程)进入加密字段？后果是什么？

Question

对于GPU编程这个术语，我指的是一般高度并行的计算。

最后，我已经建立了一些密码学的背景。因此，我开始怀疑GPU编程是否适用于密码学。我认为，在大多数用例中，它将提供很少或根本不具有优势的情况，因为密码算法是围绕在并行化方面提供很少或不具有优势的概念构建的，因为这可能需要考虑替代的安全模型，而且在某些情况下我们希望存在数据依赖关系。例如，在分组密码或流密码(例如AES或Salsa)中，不管并行化在密码块链接中可能提供一个小的优势。但另一方面，大多数现代处理器体系结构(如x64或ARMv8)已经为一轮AES或某些散列函数内置了指令，而且它们也有在某些情况下可以提供帮助的SIMD指令。但我们不要局限于我们的范围，密码学不仅仅是关于这些方案和这些原语。不对称密码学原语呢？还有，“新生”领域，如FHE，MPC，ZKP，或基于格的密码学呢？

概括地说：

• 我们是否允许/是否允许并行化进入加密字段？如果是，这是否需要我们重新考虑安全模式？
• 哪些是最常见的可设计并行的密码原语？
• 那么“新生”领域，如FHE、MPC、ZKP或基于格的密码学呢？

Answer 1

密码算法是围绕在并行化方面提供很少或根本没有优势的概念而建立的，因为这可能需要考虑其他的安全模型。

这不是真的。有些算法是您所描述的(通常使用名称，例如固有的顺序算法、时间锁谜题或可验证的延迟函数)，但它绝不是该领域的大多数算法。

在大多数情况下，诚实方计算的算法是非常有效的，并且使它们更高效(例如通过并行化)根本不影响安全性。

重要的是密码分析在并行化方面的表现。不过，即使这样，也会很好地并行化。许多密码分析算法(如数字域筛法或格型算法的变体)通常被称为“令人尴尬的并行”，因为大多数算法都很容易并行化。有时这里的估计是错误的，导致攻击(LogJam是一个著名的例子)，但在大多数情况下，参数的设置假设已经完成了某种程度的并行化。

所以，答案是

1. 是。忽略特殊情况(我前面已经描述过)，这不会对安全定义产生太大影响。
2. 在这里，我不能说给出了一个全面的答案，但是基于格的原语通常是高度并行的，而且现在已经相当普遍了。
3. 如前所述，基于格的原语(因此也是FHE)具有高度可并行性。不过，我不能对其他方面发表评论。

Answer 2

• 我们有并行散列
  • NIST SP 800-185 - ParallelHash：

ParallelHash的目的是通过利用现代处理器中可用的并行性来支持非常长的字符串的高效散列。

- Blake3 is another parallel hash.

• 加密模式；CTR本质上高度并行，对磁盘加密模式的要求。
• 建造彩虹桌。
• FHE实现；FHE已经是一种资源和时间消耗。并行实现它们是必须的；
  • 由于FHE语义安全的本质，分选已经建立在并行排序的基础上。
  • 私人信息检索
  • AES评价
  • 另外，其他的(已经有FPGA/GPU实现)

• 分解算法包括许多并行子程序，如高斯消除。例如，CADA性能取决于核心的数量；
• 模的GCD攻击可能瘫痪。
• Pollard用于离散日志的袋鼠算法是支持GPU的瘫痪算法。
• 格算法和攻击本质上是并行的。
• 量子计算模拟从本质上来说，这是必须的。
• 强制执行:虽然像AES这样的现代算法不能强制执行，但在DES上已经执行了并行密钥搜索。这个回答上列出的所有饼干都是并行化的。
• ZKP的某些部分可以是准化。
• 密码散列；并行化是要求在2015年举行比赛。这为并行搜索提供了一些缓解措施，请参阅哈希猫。

我们是否允许/是否允许并行化进入加密字段？如果是，这是否需要我们重新考虑安全模式？

我们可以看到它已经在里面了。安全模型实际上取决于情况。

哪些是最常见的可设计并行的密码原语？

• 天生的蛮力
• 天生的

注意，在ASIC/FGGA中实现算法在密码学中是非常丰富的。CHES和会议是这一主题的先驱。

Answer 3

GPU的使用(以及一般的并行性)是密码分析中的标准。有两个著名的例子：

• 2017年：SHAtteredSHA1 1上的碰撞攻击。
• 2009年：波拉德-利用PlayStation 3控制台集群攻击112位ECDLP。