2007-10-12から1日間の記事一覧
See also g:lab:keyword:現代暗号史_格子 with worst-case/average-case reductions Ajtai-Dwork *1 AD-I and AD-II AD-III AD-GGH *2 AD-KTX *3 AD07 *4 Regev03 *5 R03-KTX *6 Regev05 *7 R05-KTX *8 R05-PW *9 R05-PVW *10 without worst-case/average-ca…
1+2+...+n = O(n) となることをいまから証明しますが，もちろんこれは間違っています． (真実は 1+2+...+n = n(n+1)/2 なので．) どこがまちがっているでしょう？というのがクイズです． 証明 nに関する数学的帰納法． n=1のとき，左辺は1で右辺はO(1)．1=O(…
Miklos Ajtai, Cynthia Dwork "The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence." (ECCC TR07-097) 96年以降話題となったAjtai-Dwork暗号*1が生まれ変わりましたという論文. TR96-065の方のAjtai-Dwork暗号IIIを元…
