Homomorphic-Encryption

任何 NIST PQC 是否具有“同態”公鑰,從任何兩個公鑰派生組合公鑰的意義上說?

  • November 18, 2019

背景

MathMesh 加密平台(參考底部)是一個新提出的技術堆棧,被有些厚顏無恥地稱為“網際網路安全大統一理論”。它的“元密碼學”模組依賴於 Discrete-log Diffie-Hellman 的以下屬性:

$ privKey: x, pubKey: X = x.P $

$ privKey: y, pubKey: Y = y.P $

因此,您可以通過組合兩個公鑰或兩個私鑰來派生“組合密鑰”。

$ Z=X \oplus Y = (x \otimes y).P $

對於一些適當的定義 $ \oplus $ 和 $ \otimes $ .

問題:

這會在向後量子不對稱 KEM 的過渡中倖存下來嗎?更具體地說,存在某種定義的可能性有多大 $ \oplus $ 和 $ \otimes $ 允許以這種方式將公鑰和私鑰“組合”用於格、程式碼、多變數和/或 SIKE 密鑰?

參考資料

不,這不會像在量子世界中那樣存在,因為所有離散對數方案(包括 Diffie-Hellman)都被破壞了。

更一般地說,這在量子世界中可能是不可能的先驗,因為它意味著具有群同態屬性,這受到 Shor 算法實際上由兩部分組成的事實的阻礙:

  • 將因式分解問題簡化為求序問題
  • 一種解決求序問題的量子算法

問題是順序查找部分意味著它允許找到組元素的順序,從而可以輕鬆打破離散對數。

從 2014 年開始,量子世界的群同態加密甚至出現了不可能的結果。它的核心思想基本上是你可以通過選擇兩條消息來贏得IND-CPA遊戲 $ m_0 $ 和 $ m_1 $ 這樣 $ m_0=e $ , 和 $ m_1\neq e $ , 為了 $ e $ 明文組中的標識元素,加密時將映射到密文組的標識元素,並且由於您可以使用 Shor 的順序查找部分計算元素的順序,因此您可以找到密文是否具有順序 1(在它對應於哪些情況 $ m_0 $ ) 或不。數字簽名或密鑰交換算法也會出現同樣的問題。

這也是為什麼很難提出量子安全的零知識證明的原因。

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