利用者:Roget/LatticeCryptosystem
出典: フリー百科事典『ウィキペディア（Wikipedia）』
[編集] 格子暗号についてのメモ
某***さんは格子暗号に(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による改良に近い.
- Ajtai-Dwork暗号 (STOC1996)
- 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の方も不味そうな.
- GGH暗号 (CRYPTO1999 だった筈)
