Post Quantum Fuzzy Stealth Signatures and Applications

筆記

后續的研究方向

摘要

自比特幣問世以來，基于區塊鏈的加密貨幣中的私人支付一直是學術和工業研究的主題。隱形地址支付被提議作為一種改善用戶支付隱私的解決方案，事實上，它已被部署在當今的幾種主要加密貨幣中。該機制允許用戶接收付款，因此這些付款都不可鏈接到彼此或收款人。目前已知的隱形地址機制要么（1）在某些合理的對抗性模型中不安全，要么（2）在實踐中效率低下，要么（3）與許多現有貨幣不兼容。

在這項工作中，我們將該機制的底層加密抽象形式化，即具有正式游戲定義的隱形簽名。我們展示了我們的概念在Fast IDentity Online（FIDO）標準中定義的無密碼身份驗證中的驚人應用。然后，我們介紹了Spirit，這是第一個基于NIST標準化簽名和密鑰封裝方案Dilithium和Kyber的高效后量子安全隱形簽名構建。Spirit的基本形式僅在aweak安全模型中是安全的，但我們提供了一種保持效率的通用轉換，它增強了Spirit安全性，以保證本文中定義的最強安全概念。與現有技術相比，簽名大小提高了約800倍，同時使簽名和驗證的效率保持在0.2毫秒。

我們用模糊跟蹤功能擴展了Spirit，收件人可以將傳入交易的跟蹤外包給跟蹤服務器，滿足與最近在[CCS 2021]中引入的模糊消息檢測（FMD）類似的匿名概念。我們還在Spirit中引入了一個新的模糊跟蹤框架，稱為可伸縮模糊跟蹤。這個新框架可以被認為是FMD的對偶，因為它將跟蹤服務器的計算工作量減少到用戶數量的次線性，而不是FMD的線性。實驗結果表明，對于數百萬用戶來說，服務器只需要3.4毫秒過濾每個傳入消息，這是對現有技術的顯著改進。

引言

加密貨幣為不可信和可公開驗證的支付提供支持。付款的發送者將交易發布到稱為區塊鏈的公共賬本上。在最基本的形式中，交易指定了發送方和接收方各自的公鑰（或地址），并且交易由發送方通過與其公鑰對應的數字簽名進行授權。電子商務[48]、捐贈平臺[7，12，49]、游戲平臺[18]等只是加密貨幣及其無信任支付所支持的一些流行用例。例如，捐贈平臺接受加密貨幣支付形式的捐贈，為此，捐贈平臺會公布其地址，用戶可以在不需要任何當局許可的情況下向這些地址進行交易。

上述范式的一個關鍵弱點是，它在基本形式上缺乏可靠的匿名保證。用于執法目的的幾種去匿名技術[33，35，41-43]已被證明可以將區塊鏈上的地址與擁有它們的現實世界實體聯系起來。然而，這也導致了對用戶及其支付的審查形式存在問題[11]。

開發了一種稱為隱形地址的機制[13，17，50，51]來解決這些匿名問題。例如，捐贈平臺發布一個主地址，即所謂的隱藏地址，任何用戶都可以通過使用稱為一次性地址的隱藏地址的隨機重新分配版本向平臺發送捐贈。對于任何外部觀察者來說，這樣的一次性地址都與隱藏地址不可鏈接，因此，到這樣一個隱藏地址的事務看起來就像是隨機收件人（不一定是捐贈平臺）。此外，通過訪問其主秘密，捐贈平臺可以將這樣的一次性地址鏈接到其隱形地址，并進一步在本地動態生成相應的一次性秘密。使用這個一次性秘密，可以花費與一次性地址相關聯的硬幣。在這種情況下，收件人只需要發布其主地址，而不需要為每個潛在的發件人提供新的不可鏈接的地址。由于發件人的數量很可能有數百或數千人（如電子商務、捐贈等），這種機制帶來了一個可擴展的解決方案。

事實上，[51]中提出的隱形地址方案已經部署在許多主要貨幣中，如比特幣[17]、以太坊[20]和Monero[51]。該機制進一步直接應用于Blitz[4]等支付協議的隱私增強。由于[51]通過簽名方案實現了隱藏地址，我們將把[51]中機制的加密抽象稱為隱藏簽名。因此，我們今后將互換使用地址和公鑰這兩個術語。

最近的學術工作[25，27]啟動了對隱形簽名的正式處理，并觀察到[51]的構建不滿足所謂密鑰暴露下的安全性。粗略地說，這意味著，如果對手學習了他生成的一次性公鑰的相應一次性密鑰，那么他可以學習他為該特定主地址生成的所有一次性公鑰的所有一次性密鑰。

最近提出的隱形簽名方案[25，27]旨在安全地抵御此類密鑰暴露攻擊，其缺點是其方案使用了諸如配對[8]或格基委托[1]等重型工具。這些加密貨幣目前與目前存在的任何主要加密貨幣都不兼容。此外，隨著量子計算機的威脅迫在眉睫，包括[27，51]的量子前隱形簽名機制在內的加密貨幣支付仍然很脆弱。雖然[25]中提出了一種基于晶格的（因此似乎是后量子的）隱形特征構造，但這種構造依賴于上述晶格基委托。因此，他們的方案很可能效率太低，無法實際使用【正如[25]的作者在第1.1節中指出的那樣，他們的“公鑰和簽名大小太大，無法實際使用】。我們在表1中比較了我們的施工和相關工程。有關更多討論，請參閱附錄B。

這項工作的動機是以下兩個問題：

我們能否擁有一種有效的隱形簽名方案，該方案具有針對無限密鑰暴露的安全性，與Schnorr、ECDSA和其他主要用于當今貨幣的基于組的簽名方案兼容？

我們能有一個高效的隱形簽名方案嗎？該方案具有后量子安全的無界密鑰暴露安全性？

隱形地址機制的一個警告是，接收者（在線或離線）必須解析大量（每天數十萬）交易，以識別那些將硬幣發送到與其主地址對應的一次性地址的人。[51]中提出了一種變通方法，其中接收方可以將傳入付款的標識委托給稱為跟蹤服務器的半可信第三方服務器。為此，接收方可以根據其密鑰生成所謂的跟蹤密鑰，并將其提供給跟蹤服務器。跟蹤密鑰允許跟蹤服務器使用跟蹤密鑰來識別或跟蹤對接收者的所有傳入付款，并在稍后將這些確切付款通知接收者。另一方面，這樣的跟蹤密鑰不應該使跟蹤服務器能夠為相關的一次性地址生成一次性秘密。先前的工作[2，25，27]在隱形特征的形式化中省略了這一重要的跟蹤功能。

上述跟蹤方法的一個缺點是，我們完全放棄了跟蹤服務器的匿名性/不可鏈接性，跟蹤服務器準確地知道哪些付款是發給收件人的。雖然不可鏈接的匿名目標和可跟蹤的功能目標之間存在著自然而明顯的緊張關系，但Beck等人[6]最近的一項工作試圖在這些概念之間取得平衡。他們引入了模糊消息檢測（FMD）的概念，其中跟蹤服務器可以在不確定性程度可調的情況下大致檢測到收件人的消息。更具體地說，他們的檢測概念是模糊的，因為發給接收者的消息總是被正確識別的，但存在接收者控制的假陽性率（烘焙到模糊跟蹤密鑰中），這導致發給其他用戶的消息被錯誤地分類為發給接收者的。因此，跟蹤服務器不能確定檢測到的消息是否真的是針對接收方的。這種機制使得消息的發送者必須包括額外的模糊跟蹤信息，并且跟蹤服務器擁有模糊跟蹤密鑰。原則上，應用他們的技術來實現隱形簽名中一次性地址的模糊跟蹤是很簡單的。然而，依賴他們的計劃也有相當大的缺點。雖然他們的第一種方案（FMD2）是有效的，但它依賴于量子前DDH假設。他們的第二種方案（FMDfrac）依賴于諸如混亂電路之類的重型工具，這些工具會導致發送者的消息出現不可接受的放大。另一方面，有用于完全私有跟蹤而不是模糊跟蹤的信號檢測或檢索方案[26，31]，但所有這些方案都需要在服務器端進行線性工作，而服務器端不能擴展到數千或數百萬用戶。我們在附錄B中討論了他們的方案和我們的方案，并在表2中進行了比較。這讓我們不禁要問：

我們能有一個在后量子環境中具有高效模糊跟蹤并可擴展到數十萬（甚至數百萬）用戶的隱形簽名方案嗎？

貢獻

模塊化框架

我們介紹了Spirit（在第6.1節中），這是第一個在沒有密鑰泄露的情況下安全的實際有效的后量子隱形簽名方案【[2]最近的一項工作提出了一種重新隨機化簽名的構建，該簽名與隱形地址的概念相似。然而，需要注意的是，他們提出的功能不提供公共跟蹤支持，也不安全，無法抵御密鑰暴露攻擊。】。為了實現這一目標，我們考慮了基于晶格的Dilithium[30]簽名方案，它是NIST標準化競賽的獲勝者，也是最有可能被用于加密貨幣的候選者。在不以任何方式更改簽名方案的情況下，我們用額外的算法增強Dilithium以獲得Spirit，使其現在支持一次性密鑰推導和跟蹤。

接下來，我們展示了如何將（在第5節中）一個在沒有密鑰暴露的情況下安全的隱形簽名方案一般地轉換為一個在無限制密鑰暴露的條件下安全的方案。因此，我們可以將Spirit升級為一個具有無限密鑰暴露的實用高效和安全的Spirit。Spirit及其升級都與支持Dilithium簽名驗證的加密貨幣兼容，不需要額外的腳本。

此外，我們構造了一個隱形簽名方案（在全文[39]中），該方案與Schnorr和ECDSA等目前大多數貨幣中使用的基于組的方案兼容。然而，它只保證有界密鑰暴露的安全性：它容忍先驗數量的一次性密鑰泄漏。

模糊構造

然后，我們提出了兩個模糊隱形簽名方案（使用Spirit），這兩個方案都是第一個有效的后量子候選者。

在第一個構造中（在第6.2節中），我們采用了與[6]中的FMD類似的方法。但我們從𝑂(𝜆)通過新穎地使用密文壓縮技術，將每個信號的比特數提高到1比特[9]。此外，我們展示了如何在不需要像[6]中那樣的混亂電路之類的重型工具的情況下允許更精細的假陽性率。

然后，我們提出了一個新的模糊跟蹤可擴展框架（在第4.4節中），然后在隨機預言機模型中進行有效構建（在第6.3節中）。該框架可以被視為[6]中FMD機制的“雙重”版本。直觀地說，這是效率和可用性之間的權衡：通過限制用戶選擇假陽性率的能力，我們能夠將跟蹤服務器的計算工作量減少到用戶總數的次線性。這與以前相比非常有利工作，其中服務器需要對每個用戶的跟蹤密鑰進行線性掃描[6，26，31]。

實施

我們使用匿名開源代碼[38]實現了Spirit、后量子FMD和基于Dilithium、Kyber和Falcon的可擴展模糊跟蹤。我們在普通筆記本電腦上用不同的參數集對它們進行了測試，如表3和表4（附錄B）所示。實驗結果表明，我們的安全性最強的隱形簽名只產生4.09 KB的簽名，而驗證時間不到0.2毫秒。同樣，我們的可擴展模糊跟蹤機制只需要3.42毫秒就可以在數百萬用戶的環境中過濾每條傳入消息。

適用于FIDO

作為我們的最后貢獻，我們出人意料地將我們的隱形地址概念應用于FIDO2標準的無密碼身份驗證方案（在[5]中正式定義）。我們展示了制造商如何實現設備驗證器，這些驗證器不僅提供后量子安全性，而且需要有限的安全內存（一個主密鑰），支持全局吊銷（如[22]中所定義），多設備憑據[3]，并可用于實現異步遠程密鑰生成（[19]）。