2008-02-13から1日間の記事一覧

On lattice-based cryptography and average-case/worst-case connections

Regev05やらGPVの公開鍵サイズをm=5nlog n, q=O(n^3)で見積もってみた. 大体n=512のときに鍵サイズが256Mbから1Gbか. Ajtai-Dworkのn=32のときにn^5 log nで160Mbとかにに比べればかなりの改善ということが分かる. 定数項が結構利いてくるものだ. 現実的には…