[新聞] 零知識證明的抗量子協議以加強區塊鏈安全

[s256988452 (♥)]

新聞來源連結：

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://www.ptt.cc/bbs/DigiCurrency/M.1633434604.A.CAF.html
→ VONeternal: 好奇SHA256不是已經是quantum resistant了嗎
→ DarkerDuck: 這是指ECDSA簽章的部分吧
→ s256988452: 零知識證明是零知識證明 簡單來說用處就是隱私保護
→ s256988452: 用來保護區塊鏈應用程序
→ DarkerDuck: 傳統上是使用公鑰證明簽章有效性，但也給了量子電腦
→ DarkerDuck: 破解的可能性
推 hphphp456: 零知識證明不是已經有mina了？
→ VONeternal: 哦哦誤解 感謝!
※ 編輯: s256988452 (112.78.82.243 臺灣), 10/05/2021 21:14:21
推 GarySu1104: 只要量子電腦運算速度愈快，任何密碼都可以破解吧
→ DarkerDuck: 首先量子電腦只有在量子類型的演算法才具有壓倒性優勢
→ DarkerDuck: 假如那個演算法找不出量子等價的演算法就沒啥用
→ DarkerDuck: 而且量子電腦速度要數量級提升主要是量子位元數要增加
→ VONeternal: 量子電腦幾十年內不可能吧
→ VONeternal: 還不如擔心能源危機環團抗議關礦場
推 john801110: 就算真的發明出來了要擔心的是傳統金融業