新闻来源连结： https://bit.ly/3A6sUDG 新闻本文： Researchers at Technology Innovation Institute (TII) in the United Arab Emirates have improved the feasibility of a new class of algorithms to protect blockchain applications against quantum computing cryptographic attacks. This builds on the considerable research already underway across the cryptographic community in developing better protocols for improving zero-knowledge proofs. 阿拉伯联合大公国技术创新研究所 (TII) 的研究人员提高了一类新算法的可行性，以保 护区块链应用程序免受量子计算密码攻击。这建立在整个加密社区已经进行的大量研究的 基础上，该研究旨在开发更好的协议以改进零知识证明。 The specialised area of cryptography has been gaining significant interest since zero-knowledge proofs are widely used in techniques like blockchain, smart contracts, and identity verification. 由於零知识证明广泛用於区块链、智能合约和身份验证等技术，密码学的专业领域引起了 人们的极大兴趣。 The most popular approaches have involved using matrix computations. However, there is some concern that future research may find new and improved ways to compromise these protocols. So, researchers are always looking for promising alternatives to provide multiple types of protection against future cryptographic attacks. 最流行的方法涉及使用矩阵计算。然而，有人担心未来的研究可能会找到新的和改进的方 法来破坏这些协议。因此，研究人员一直在寻找有前途的替代方案，以提供多种类型的保 护以防止未来的密码攻击。 Need for alternative approaches 需要替代方法 The various types of quantum-resistant problems and algorithms built on them are considered safe at the present time, because no one has demonstrated a credible quantum computer attack against them. Emanuele Bellini, Lead Cryptographer at TII, said: “We are in the early stages of understanding what is quantum-resistant and what is not. The safest approach is to build the quantum-resistant scheme based on many different problems so that if one is broken, you are still hopeful that the others are not.” 目前，各种类型的抗量子问题和建立在它们之上的算法被认为是安全的，因为没有人证明 过可信的量子计算机攻击它们。 TII 的首席密码学家 Emanuele Bellini 说：“我们正 处於了解什麽是量子抗性、什麽不是的早期阶段。最安全的方法是基於许多不同的问题构 建抗量子方案，这样即使一个被破坏，你仍然希望其他的没有。” Most of the work on quantum-resistant protocols for zero-knowledge proofs has been based on lattices. Lattices are very flexible and are one of the most malleable cryptographic mathematical structures that can be applied across the board. The TII team has focused on alternatives to lattices based on the Rank Syndrome Decoding problems, which, although promising, still need more research to make them a credible solution. 用於零知识证明的抗量子协议的大部分工作都基於格。晶格非常灵活，是可以全面应用的 最具延展性的加密数学结构之一。 TII 团队专注於基於 Rank Syndrome Decoding 问题 的格子替代方案，虽然前景广阔，但仍需要更多研究才能使它们成为可靠的解决方案。 Cryptography is a bit of a cat-and-mouse game, where researchers are constantly finding enhanced solutions to break protocols and more effective ways to implement them. It is not even necessary to completely break an approach to reduce its attractiveness. Bellini said, “If someone discovers an attack to the lattice problem that just slightly improves the previous attack, it means that the lattice parameters would have to become larger, and then other approaches would become relatively more efficient.” 密码学有点像猫捉老鼠的游戏，研究人员不断寻找增强的解决方案来破坏协议以及更有效 的实施方法。甚至没有必要完全打破一种方法来降低其吸引力。贝里尼说，“如果有人发 现对格子问题的攻击只是稍微改进了之前的攻击，这意味着格子参数必须变大，然後其他 方法会变得相对更有效。” The importance of zero-knowledge proofs 零知识证明的重要性 “Zero-knowledge” has recently become the most popular keyword in cryptographic papers presented at conferences. The popularity of these protocols grew in response to the enthusiasm around blockchain since this is the most common use case. In these applications, the goal is to be able to prove a statement is true without the rest of the blockchain understanding information about the exchange. The simplest implementations of zero-knowledge protocols are often used for identity verification. “零知识”最近成为会议上发表的密码论文中最受欢迎的关键词。由於区块链是最常见的 用例，因此这些协议的受欢迎程度随着对区块链的热情而增长。在这些应用程序中，目标 是能够证明一个陈述是真实的，而无需区块链的其余部分理解有关交换的信息。零知识协 议的最简单实现通常用於身份验证。 A zero-knowledge-proof protocol organised the interaction between two parties in which one is the prover and the other the verifier. The two parties exchange information, and after the exchange, the prover can confirm the truthfulness of the statement, such as whether someone has enough money in a blockchain wallet for a transaction without knowing the total in the wallet. This is also done in a way that hides information from third-party observers. 零知识证明协议组织了两方之间的交互，其中一方是证明者，另一方是验证者。双方交换 信息，交换後，证明者可以确认陈述的真实性，例如某人在区块链钱包中是否有足够的钱 进行交易，而无需知道钱包中的总数。这也是以向第三方观察者隐藏信息的方式完成的。 Initially, the zero-knowledge-proof community focused on using classical cryptographic algorithms based on discrete logs or factorisation problems. The community has recently started exploring quantum-resistant zero-knowledge proofs. 最初，零知识证明社区专注於使用基於离散日志或分解问题的经典密码算法。社区最近开 始探索抗量子零知识证明。 Classical algorithms were inefficient, and the quantum-resistant implementations are even less so because they require larger keys. They also require larger parameters such as the size of the proof, the number of bits that need to be communicated between prover and verifier, and the amount of work each party must perform to build the proof. These quantum-resistant protocols might take minutes or hours to run compared to a few seconds for the protocols built on classical algorithms. 经典算法效率低下，而抗量子实现的效率更低，因为它们需要更大的密钥。它们还需要更 大的参数，例如证明的大小、证明者和验证者之间需要通信的比特数以及各方为构建证明 而必须执行的工作量。与基於经典算法的协议相比，这些抗量子协议可能需要几分钟或几 小时才能运行。 Rank Syndrome Decoding problem Rank Syndrome 解码问题 TII’s researchers studied the Rank Syndrome Decoding problem, an evolution of another technique called the Syndrome Decoding problem. Other popular quantum techniques have included the shortest vector problem, the NTRU problem, the isogenies problem, and the multivariate quadratic problem. TII 的研究人员研究了 Rank Syndrome Decoding 问题，这是另一种称为 Syndrome Decoding 问题的技术的演变。其他流行的量子技术包括最短向量问题、NTRU 问题、同构 问题和多元二次问题。 These different classes of problems organise numbers into a particular structure that is best suited for verifying a zero-knowledge proof built on top of the problem. The shortest vector and NTRU are similar and use lattices to encode the numbers to compute the problem’s answer. Multivariate problems use a system of polynomials to organise the calculation. The Syndrome Decoding Problem uses a linear code. The Rank Syndrome Decoding problem is similar to the Syndrome Decoding problem but organises the linear codes more efficiently. 这些不同类别的问题将数字组织成一个特定的结构，最适合验证建立在问题之上的零知识 证明。最短向量和 NTRU 相似，使用格子对数字进行编码以计算问题的答案。多元问题使 用多项式系统来组织计算。Syndrome Decoding问题使用线性代码。 Rank Syndrome Decoding 问题类似於 Syndrome Decoding 问题，但可以更有效地组织线 性代码。 Emanuele Bellini, Lead Cryptographer at the TII, said: “The Rank Syndrome Decoding problem is not something we invented. However, it is a newer problem than Syndrome Decoding and the lattice problems, so it is less studied.” TII 的首席密码学家 Emanuele Bellini 说：“Rank Syndrome Decoding 问题不是我们 发明的。然而，它是一个Syndrome Decoding和格问题更新的问题，因此研究较少。” More efficient and adaptable 更高效、适应性更强 TII’s researchers improved the efficiency of RSD and implemented it in a way that is more adaptable to different use cases. Their implementation is 60% smaller, and the parameters are 1% of the size compared to the state-of-the-art Syndrome Decoding implementation for a given proof. It is also considerably faster, solving one benchmark proof in 47 ms compared to 5,000 ms for Syndrome Decoding. TII 的研究人员提高了 RSD 的效率，并以更适合不同用例的方式实施。对於给定的证明 ，与最先进的Syndrome Decoding实现相比，它们的实现小了 60%，参数大小只有其大小的 1%。它也快得多，与 Syndrome Decoding 的 5,000 ms 相比，它在 47 ms 内解决了一个 基准证明。 A key building block of this new construction is a commitment scheme that essentially requires one party to commit to a statement, such as having executed a certain amount of work, which can be verified later as part of a transaction. 这种新结构的一个关键构建区块是一个承诺方案，它本质上要求一方承诺一个声明，例如 执行了一定数量的工作，稍後可以作为交易的一部分进行验证。 TII researchers also demonstrated how this commitment scheme could be built into any kind of circuit, which is a fundamental building block for cryptographic transactions. Prior research had examined how RSD could be applied to signature schemes based on identification protocols using zero-knowledge proofs. However, the TII research is the first demonstration of how RSD could apply to any arbitrary circuit that could be used across many different applications. TII 研究人员还演示了如何将这种承诺方案构建到任何类型的电路中，这是加密交易的基 本构建区块。先前的研究已经研究了如何将 RSD 应用於基於使用零知识证明的识别协议 的签名方案。然而，TII 研究首次展示了 RSD 如何应用於可用於许多不同应用的任意电 路。 An arbitrary circuit in cryptography is analogous to an electrical circuit in a computer chip in which bits are logically combined using gates that perform logical operations such as executing AND, OR, and NOT statements. Bellini said: “if you have enough of these gates, you can build any function.” 密码学中的任意电路类似於计算机芯片中的电路，其中使用执行逻辑运算（例如执行 AND 、OR 和 NOT 语句）的门对位进行逻辑组合。贝里尼说：“如果你有足够多的这些门，你 就可以构建任何功能。” The proof size required for verifying the statement grows at a quasi-linear rate. This means that larger statements require more computation to prove but not nearly as much as would be needed if the proof size grew at a quadratic or exponential rate. 验证语句所需的证明大小以准线性速率增长。这意味着更大的语句需要更多的计算来证明 ，但如果证明大小以二次或指数速度增长，则没有所需的那麽多。 Reducing the cheating probability 降低作弊概率 A zero-knowledge proof is not the same as a mathematical proof. A mathematical proof is a deterministic process that allows someone to assert whether a statement is true or false based on certain assumptions. In contrast, a zero-knowledge proof is a probabilistic proof in which a statement is proved with a certain degree of probability. The probability of making a mistake is called the soundness error or cheating probability since it represents the risk that someone might be cheating but not caught. 零知识证明与数学证明不同。数学证明是一个确定性的过程，它允许某人根据某些假设断 言一个陈述是真是假。相比之下，零知识证明是一种概率证明，其中一个陈述以一定的概 率被证明。犯错的概率被称为可靠性错误或作弊概率，因为它代表了某人可能作弊但未被 抓住的风险。 This error can be made as small as possible by repeating the calculation multiple times. The current implementation’s cheating probability is 2/3 on the first pass, which is insufficient to convince a verifier. However, by repeating the proof 219 times, the cheating probability drops to 1/2128, which is extremely low. “The fact that it is wrong is less probable than a meteor will fall on your head this afternoon,” said Bellini. 通过多次重复计算，可以使这个误差尽可能小。当前实现的第一遍作弊概率为 2/3，不足 以说服验证者。但是，通过重复证明219次，作弊概率下降到1/2128，非常低。贝里尼说 ：“这件事是错误的，远比今天下午流星落在你头上的可能性要小。” Future research is looking at how to reduce the soundness error of the fundamental building blocks even further. But this needs to be approached cautiously since it may reduce the probability by creating a much longer proof that takes more time to execute. Bellini expects this to be doable since there are already examples of reducing the likelihood from 2/3 to 1/2 when using RSD for identification protocols. This would mean the researchers would only need to repeat the process 128-times rather than 219-times! 未来的研究将着眼於如何进一步降低基本构建区块的可靠性误差。但这需要谨慎处理，因 为它可能会通过创建需要更多时间来执行的更长的证明来降低概率。 Bellini 预计这是 可行的，因为在使用 RSD 进行识别协议时，已经有将可能性从 2/3 降低到 1/2 的例子。 这意味着研究人员只需要重复这个过程 128 次而不是 219 次。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 112.78.82.243 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/DigiCurrency/M.1633434604.A.CAF.html ※ 编辑: s256988452 (112.78.82.243 台湾), 10/05/2021 21:14:21