Post-Quantum-Cryptography
SVP算法和復雜性
我從西蒙斯研究所的展示文稿中拍攝了圖像。表中給出了根據近似因子的近似 SVP 問題的複雜性類別。我的問題是，這張圖片中藍色箭頭-Crypto-的含義是什麼？
基於格的密碼學基於某些格問題的難度（幾乎是重言式）。標記為“crypto”的區域表示近似因子的區域 $ \gamma $ 這樣：
- 我們知道如何構造密碼原語，假設硬度為 $ \mathsf{SVP}_\gamma $
- 有理由認為 $ \mathsf{SVP}_\gamma $ 很難（因為沒有已知的多時間算法）。