利用者:Roget/LatticeCryptosystem

格子暗号についてのメモ

某***さんは格子暗号に(ry 俺の研究のネタが(ry

• 1 bit
  • Ajtai-Dwork暗号 (STOC1996)
    • n^11-uSVP(だと思う). 一部の人はpoly(n)-uSVPと言ってるけど.
  • Regev暗号 (STOC2003)
    • n^{1.5} poly(log n)-uSVP
  • Regev暗号 (STOC2005)
    • SVP_{n^{1/2} poly(log n)}, SIVP_{n^{1/2} poly(log n)}
    • ただし帰着が量子
  • Ajtai暗号 (STOC2005)
    • 特殊なn^{1/2+c}-uSVP (証明はFull Paper待ち)
    • GGH暗号のMicciancioによる改良に近い.
• n bit
  • GGH暗号 (CRYPTO1999 だった筈)
    • CVPベースだが帰着が無い
    • Micciancioによる改良 (CaLC)
      • Smith Normal Formの利用. 公開鍵のサイズをO(n^3 log n)からO(n^2 log n)に.
      • 元々のGGH暗号の安全性に帰着.
    • PKCで出てた改良
      • 多項式を利用. 帰着は無い.
    • GGHベースの署名がある. Nguyen and Regev (EuroCrypt 2006) で, 破られた.
  • NTRU暗号
    • NTRU Lattice上のSVPベースだが帰着が無い
    • NTUR暗号の一方向性を仮定するとMessage Paddingを用いてROモデル上でIND-CCA2まで
    • NTRUベースの署名がある→NTRUSign. NSSは既に破られている. NTRUSignもNguyen and Regev (EuroCrypt 2006)で, そろそろ危なげ? 弱いヴァージョンの251bitの方が実験的に破られている.
    • 研究が進むと現行の, 約500bitの方も不味そうな.