不平衡油醋系統
在密码学中，非平衡油醋架構（Unbalanced oil and vinegar scheme，UOV）是法國數學家雅克·帕塔林（J.Patarin）修改油醋架構（oil and vinegar scheme）後的新数字签名协议，屬於一種多变數密码学（multivariate cryptography）。 该签名方案的安全性基于NP數學難題。创建和验证签名時，必须解最小具有变量的個二次方程組。虽然如果比大得多或小得多，问题就很容易解决 …
标签：#后量子密码学
共 7 篇文章
格罗弗算法
格罗弗算法（）是一種量子算法，於1996年由電腦科學家洛夫·格罗弗提出。假設現在有一個未知的函數，格罗弗算法只需測試此未知的函數O(\sqrt{N})次，其中N為此未知函數的定义域的大小，即可以很高的概率找到一特定的輸入值，此輸入值能使此未知函數輸出特定的值。 同樣的問題在經典運算下，需要至少做 O(N) 次測試（因為在最壞的情況下，可能第N個定義域裡的值才是正確答案）。在格罗弗發表他的算法前後，Bennett, Bernstein, …
秀爾演算法
秀爾演算法（）是一個于1994年發現的，以數學家彼得·秀爾命名，針對整數分解題目的的量子演算法（在量子計算機上面運作的演算法）。不正式地說，它解決的題目是：給定一個整數 N，找出它的質因數。在一個量子計算機上面，要分解整數N，秀爾演算法的運作需要多項式時間（時間是 \log N的某個多項式這麼長，\log N 在這裡的意義是輸入的檔案長度）。准确来说，该演算法花費 O((\log N)^{3}) 的時間，展示出質因數分解問題可以使用量子…
后量子密码学
后量子密码学（，缩写：），又称為防量子、量子安全、抗量子计算，是密码学的一个研究领域，专门研究能够抵抗量子计算机進行密码分析攻擊的加密算法（特别是公钥加密算法）。计算机与互联网领域广泛使用的公钥加密算法均基于三个计算难题：整数分解问题、离散对数问题或椭圆曲线离散对数问题。然而，这些难题均可使用量子计算机并应用秀尔算法破解，或是比秀爾算法更快，需求量子位元更少的其他演算法破解。 雖然到2023年為止，量子電腦的電腦性能還無法破解一般使用的…
超奇异椭圆曲线同源密钥交换
超奇异同源迪菲-赫尔曼密钥交换（Supersingular isogeny key exchange, SIDH 或 SIKE）是一種不安全的後量子加密演算法提案，用來在不信任的通訊通道上建立雙方之間的秘密金鑰。 它类似于狄菲-赫爾曼密钥交换，但為了抵抗擁有量子電腦的對手的密碼分析攻擊，而改為基于超奇异同源图（supersingular isogeny gragh）中的行走。 在被破解之前，SIDH 是所有後量子密鑰交換中最小的密鑰大小…
容错学习问题
容错学习问题或是LWE问题（，）是一个机器学习领域中的怀疑难解问题。由Oded Regev在2005年提出，他因此赢得2018年哥德尔奖。这是一个极性学习问题的一般形式。Regev同时证明了LWE问题至少比几个最坏情况下的格问题要难。这个问题在最近被用作一种难度假设以创建后量子公钥密码系统，例如Peikert提出的容错环学习密钥交换。 简述 虽然来自机器学习领域，错误学习问题实际上是理论计算机科学中的计算复杂度问题。 一个简单易懂的例子…
格规约
格基归约（）在数学中的目标是给出一个整数格基作为输入，找出一个向量较短且近似正交的基。有许多不同算法可以实现格规约，运行时间至少是格的维数的指数次。 參考資料 *