2007-10-01から1ヶ月間の記事一覧
2-color cyclic tag systemが計算万能性を有していることが知られているので，2,3-Turing machineでそれをエミュレートすることで万能性を示している． System 0が2,3-Turing machineで, 以下System 5まである. 5まで変形してそれで2-color cyclic tag syste…
招待講演がJonathan Katzで“Efficient Cryptographic Protocols Based on the Hardness of Learning Parity with Noise.” HBやHB+の話だと思う. Cryptology ePrint Archive 2006/326 - J. Katz, A. Smith “Analyzing the HB and HB+ Protocols in the ``Larg…
テキストで音楽が演奏できる、「メロディ再生記法」(MML記法)をリリースしました - はてなダイアリー日記ということなので, mml記法を使ってみる. 4年前に作った戦闘曲風のfor713.midをmml記法で. ライドシンバルの再現は出来ず. t120 バスドラム l8 @4 @n12…
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を元…
Daniel R. Simon. "Finding collisions on a one-way street: Can secure hash functions be based on general assumptions?" (EUROCRYPT 1998) *1 CRHFsとOWFsでの相対化の論文ってこれだったのか. あと関連論文で, Chun-Yuan Hsiao and Leonid Reyzin. "Fi…
NUMB3RS on CBS 2007/05/11の放送がDijkstra法ネタだったようだ. Dijkstra法をテレビでやるというのが凄い. We All Use Math Every Dayというサイトもある. 小中の教師向けの資料があるようだ.
