Symmetric

研究問題:新發現的對稱密鑰密碼系統的用處

  • February 29, 2020

我和我的合作者都是純數學家,在密碼系統研究方面只有切線經驗,所以如果這個問題不清楚或不屬於這裡,請告訴我。我為這個問題的長度道歉,在必要的背景之後,我的問題出現在最後一部分。

如前所述,我和我的合作者是純粹的數學家,在接下來的幾個月裡,我們將發表關於我們發現的一類新數學系統的工作(它涉及數學的許多不同領域,細節並不重要)這個問題)。我的一位合作者指出,該系統的某些特性使其非常適合用於密碼學,事實上,經過進一步分析,這就是我們所發現的。

使用 Alice/Bob/Eve 類比,這種密碼系統的基本區別特性如下。因為這是一個對稱密鑰系統,Alice 和 Bob 必須見面以生成他們的隨機密鑰。一旦 Alice 和 Bob 希望發送消息,他們就會公開隨機選擇一種特定類型的數學對象,稱之為 $ T $ (數學對象的類型並不重要),並將其與它們的鍵一起使用來生成一組座標點,每個座標點將唯一地映射到 0 或 1。

這樣,Alice 可以向 Bob 發送這些座標的一個子集(每個座標映射到 0 或 1),並且由於 Bob 具有相同的座標集,他可以“解密”座標消息以獲得 Alice 希望共享的位串.


到目前為止,這個描述似乎沒有提供任何新內容,事實上,如果 Alice 希望只向 Bob 發送一條消息,這相當於一次性密件。當然,一次性便箋和類似系統的問題是使用相同密鑰發送多條消息會導致洩漏,因此對於每條新消息,Alice 和 Bob 都必須使用新密鑰,這當然意味著首先共享密鑰困難的地方。

這一數學發現提供的密碼系統的獨特(我們認為)屬性是,只要 Alice 和 Bob 公開選擇一個新的特定數學對象( $ T $ )在每條消息發送之前應用他們的密鑰(其中有一個連續的選擇 $ T $ ),他們可以使用最初選擇的相同密鑰來發送任意數量的消息,因為我們可以證明,如果使用這種方法,Eve 在數學上是不可能確定密鑰的。

事實上,我們也可以證明,只要 Alice 和 Bob 公開選擇一個新的 $ T $ 對於每條消息,在 Alice 和 Bob 之間發送給 Eve 的每條座標消息都是隨機的,因此密碼分析不會起作用。

此外,我的一位合作者在量子計算方面具有(淺)背景,並且非常確信該系統不易受到來自量子電腦(更不用說經典電腦)的暴力攻擊。我們還注意到,這種加密方案是高效的,其加密/解密時間複雜度僅與所選密鑰的大小呈線性關係(加密的複雜性與加密密鑰的長度呈指數關係)。


我的問題如下。具有這種特性的密碼系統是否已經存在?表現出這些屬性的密碼系統對社區有任何可能的用途嗎?即使沒有(即類似的系統已經存在),我們是否應該在期刊上發表該方法?如果是這樣,這裡的任何人都可以推薦任何期刊,以及在密碼學中發表時需要注意的事項嗎?

我知道我在討論數學系統的細節時非常謹慎,因為目前我不能提供太多,但我希望這些資訊足以為問題提供一般性的答案。

非常感謝大家的時間和幫助。

具有這種特性的密碼系統是否已經存在?

出於所有實際目的,這看起來像 CPA 安全對稱加密,這在實踐中是一個已解決的問題,並且出於實際目的,只有當它設法(平均)在少於 5 個 CPU 週期內加密一個字節時,這樣的結果才會有意義現代 CPU。

表現出這些屬性的密碼系統對社區有任何可能的用途嗎?

如果這個加密方案是無條件安全的1它似乎被描述為,那麼它的存在證明 $ P\neq NP $ . 這確實會引起理論研究界的極大興趣。這 $ P\neq NP $ 從鏈中得出的證據表明,對稱加密意味著 PRGs ( PDF ) 並且 PRGs 是普通的加密 OWF,並且加密 OWF的存在意味著 $ P\neq NP $ .

上述論文對加密系統的要求很簡單:

  1. 假設 Alice 和 Bob 共享一個共同的秘密 $ k $ .
  2. 愛麗絲可以使用 $ k $ 和一些隨機性來創建密文 $ c $ Bob(具有可選隨機性)至少可以成功解密 $ 0.9 $ .
  3. 對於一個隨機 $ \ell(n)>n $ 位消息 $ m $ , 一個隨機 $ \ell(n) $ -少量 $ r $ 和加密 $ m $ 在共享密鑰下 $ c\gets E(k,m) $ 對於所有機率多項式時間圖靈機 $ M $ 它認為 $ |\Pr[M(1^n,c,m)\to 1]-\Pr[M(1^n,c,r)\to 1]|\leq \varepsilon(n) $ 對於一些可以忽略的功能 $ \varepsilon $ .

顯然,審閱者會意識到這樣一個密碼系統將證明 $ P\neq NP $ 因此將對任何此類結果持懷疑態度。

如果是這樣,這裡的任何人都可以推薦任何期刊,以及在密碼學中發表時需要注意的事項嗎?

密碼學出版通常通過 IACR 和會議進行,與此類工作相關的可能是三個主要的CryptoEurocryptAsiacrypt以及區域會議TCC,儘管也有Journal of CryptologyToSC作為預印本的ePrint

1:這裡的“無條件安全”意味著滿足安全定義而不依賴於未經證實的假設,例如 $ P\neq NP $ .

引用自:https://crypto.stackexchange.com/questions/77891