NISTPQC论坛上DJB关于是否应对彩虹签名被Ward Beullens破解发出预警的辩述

[LIUJIN]

---------- Forwarded message ---------
From: D. J. Bernstein <d...@cr.yp.to>
Date: Mon, Feb 28, 2022 at 8:12 PM
Subject: Re: [pqc-forum] ROUND 3 OFFICIAL COMMENT: Rainbow
To: <pqc-co...@nist.gov>
CC: <pqc-...@list.nist.gov>

Quan Thoi Minh Nguyen writes:
> 2/ Equivalently important, NIST should revise NIST PQC finalist
> documentation and make clear the security risk of Rainbow. This is to avoid
> the case that people would make a *wrong* assumption that NIST PQC
> finalists have reasonable security while Rainbow doesn’t have enough
> security confidence.

Quan Thoi Minh Nguyen 写道：

> 2/ 一样重要的是：NIST应该修改NIST的PQC入围
> 文件，并明确说明彩虹签名Rainbow的安全风险。这是为了避免
> 一般人会做出一个错误的假设，他们会认为NIST的PQC
> 入围算法都具有合理的安全保障，但彩虹签名Rainbow却并没有足够多
> 的安全保障的信心。

I agree that there has to be a warning about the drop of security levels
for Rainbow. The issue isn't just the demonstrated attack on rainbow1a:
the new paper says 2^131 operations for rainbow3c and 2^164 operations
for rainbow5c, where the round-1 submission in 2017 says 2^217.4 and
2^275.4 respectively. (My impression is that the operations being
counted are of sufficiently similar types that a serious AT analysis
would show a security drop similar to what these numbers suggest.)

DJB回复说：我同意，应该要对彩虹签名Rainbow安全等级的下降提出预警！

鲁汶大学Ward Beullens在2022年破解彩虹签名的论文中，不仅仅是对安全等级为1a参数的彩虹签名Rainbow的破解示范。他在论文中谈到，对彩虹3C的操作为2^131，彩虹5C的操作为2^164。 他在更早的2017年提交的那篇论文中，彩虹3C和彩虹5C的操作数分别为2^217.4和2^275.4。

(我的印象是，这种类型的攻击有好几次，都是相似的一种攻击和破解，只要认真的进行一个严肃的破解类型研究分析，就会找到这种破解类型的特点，就会发现，只要通过这种破解，都会导致彩虹签名的安全性在下降）。

But surely NIST also has to catch up on issuing warnings about the drop
of security levels for lattice systems. One easy way to see the drop is
to rewind to "Better Key Sizes (and Attacks) for LWE-Based Encryption"
from Lindner and Peikert:

但是，这样一来，NIST肯定也必须要发布格算法的安全等级也下降了的警告。要看到格算法的这种严重下降，一个简单的方法是倒回到2010年，达姆实达特理工大学TU Darmstadt的Richard Lindner，和现Algorand首席密码学家Chris Peiker的论文"基于LWE格算法的更小密钥（和攻击破解）"。论文如下：
   https://eprint.iacr.org/2010/613.pdf

The Frodo submission says it's an "instantiation and implementation" of
that paper with modifications. The security levels conjectured for Frodo
and other lattice systems today are much lower than in that paper:

Frodo格算法团队提交的文件说，他们对上面的2010年的论文进行了"实例化和实施"的研究，还作了些修改。但现在，Frodo格算法团队，还有其他格算法，它们的安全等级假设，都比上面2010年的那篇由Lindner和Peikert的论文中的安全等级，要低得很多！

   * In that paper, Lindner and Peikert propose using dimension 256,
     giving matrix sizes of 400 kilobits, and, for the ring version,
     public keys of just 2 kilobits, i.e., 256 bytes. They evaluate
     attacks against these parameters as using "2^120 seconds" on a
     2.3GHz core, and conclude that these parameters "appear to be at
     least as secure as AES-128".

在上面的2010年论文里，Lindner和Peikert建议使用256维。矩阵大小为400kb。而对于环形版本的格算法。公钥只有2千比特，也就是256字节。他们评估了针对这些参数的攻击，如果在2.3GHz的计算机核心上运行，破解需要 "2^120秒"。他们得出结论，这些参数设计"似乎至少和AES-128一样安全"。

   * The current version of Frodo targeting the AES-128 security level
     uses much larger parameters for this, dimension 640, internally
     generating matrices on the scale of a megabyte. Similarly, the most
     aggressive Kyber parameters use dimension 512 and use 800-byte
     public keys, obviously far above 256 bytes.

12年后的现在，同样针对AES-128安全级别的Frodo的格算法版本，却使用了更大参数，其维度是640，内部产生的矩阵大小为100万字节。类似的，更激进的Kyber格算法，其参数使用维度512，以及使用800字节的公钥，显然都远远高于256字节。

If there's supposed to be a dividing line saying that Rainbow needs a
warning and lattices don't, let's hear a clear definition of this
dividing line and an explanation of why the dividing line is justified.
By default I would think that warnings are required for both.
如果要有一条分界线，说明彩虹签名Rainbow需要全球警告，而格算法却不需要警告。那么，让我们看看，听听这分界线的明确定义。解释一下，为什么这种警告分界线是合理的。
如果要默认，我认为这两者都需要警告。

As an analogy, imagine a report comparing QKD to public-key cryptography
and saying that one can't trust the security of public-key cryptography.
Exhibit A is an attack demonstrated against a NISTPQC finalist. The
report would also be obliged to point out the terrible security track
record of QKD, right?

做个类比，设想！如果有一份报告，它将量子密钥交换技术QKD，与包涵了“抗量子计算机破解算法PQC”，和当前全球正在使用的“不抗量子计算机破解的算法”的整个的公钥密码学算法，进行了一番比较，然后这份报告说：不能相信整个公钥密码学算法的安全性。证据A是，针对NISTPQC的入围算法彩虹签名Rainbow，在全球演示的一次破解！所以，量子密钥分发QKD从业者说：整个公钥密码学有问题。如果是这样，这份报告也有义务指出量子密钥分发QKD技术，所过往发生的糟糕的安全记录。

 

对吗？

 

DJB
---D. J. Bernstein