格子に基づく暗号・暗号解析入門

2015 9 11 ( ) IEICE @ 2015 9 11 1 / 29 1 2 3 GGH Regev 4 RSA ( ) IEICE @ 2015 9 11 2 / 29 Nguyen CaLC2001 “The Two Faces of Lattices in Cryptology” 1 2 ( ) IEICE @ 2015 9 11 3 / 29 Rm n b1, . . . , bn L(b1, . . . , bn) = { n ∑ i=1 xibi | xi ∈ Z } B B = [b1, . . . , bn] ∈ Rm×n L(B) = {Bx | x ∈ Zn } U B′ = BU B′ B ( ) IEICE @ 2015 9 11 4 / 29 vol(L) = √ det(BBt) B | det(B)| Gaussian Heuristic λ(L) λ