O(f(n))={g(n) | ある定数Nと定数cが存在してならば}である. 以下の式があっているかどうかを○×で答えよ. こんなもんか.

ω-記法を用いるのは稀である。 無視できる関数を表記するときに使ったりしますけどね. はnについて無視できるとか.

404 Blog Not Found:アルゴリズム百選 - フィボナッチ数列にO()を学ぶ はてなブックマーク - 404 Blog Not Found:アルゴリズム百選 - フィボナッチ数列にO()を学ぶ 皆dankogaiが大好きだね. O記法の定義 O(f(n))={g(n) | ある定数Nと定数cが存在してならば}.…

昨日の話は出来ました. あとはアレと組み合わせた場合の解析です.

第3回折り紙の科学・数学・教育 研究集会 12/16日に白山で. 聴きに行こうかな (計算機幾何は初心者だけど).

[私信]出来たと思うので確認中です.[/私信] 3日で一段落着いたか. 良かった良かった. 真面目に読めば火曜日には出来てたな, これ.

公開デザイン「21 Prism」に投げた. 黒背景は落ち着くことよ.

前に予告されていたPeikert and VaikuntanathanはGentryも入っていた. IBEで参加したぽい. C. Gentry, C. Peikert, V. Vaikuntanathan. "Trapdoors for Hard Lattices and New Cryptographic Constructions." (Cryptology ePrint Archive 2007/432) 書き直し…

公開デザイン - 16 fungus-revisedに投げた. 番号が801.

V. Lyubashevsky "Lattice-based identification schemes secure under active attacks" PKC 2008 (To appear) PKC 2008のNotificationが今日なので出た様子. PKC 2008のサイトにはまだリストは無い. Feige-ShamirのOR constructionに乗せるとWIが言えるので…

私信: 数え上げ符号の話は, Fischer and Sternです. scheme処理系 (Gauche) がPARIより速かったつぅことで. 今日の名言 ナップサック暗号における鍵生成時のシフトは伝統芸. 120分掛けて作った鍵は大事に使うでしょ. 全くで.

TCC 2008の採択リストはまだ出てないけども発見. V. Lyubashevsky, D. Micciancio "Asymptotically efficient lattice-based digital signatures" (TCC 2008 (To appear)) だそうで.

Cryptology ePrint Archive 2007/419 - L. Dorrendorf, Z. Gutterman, B. Pinkas "Cryptanalysis of the Random Number Generator of the Windows Operating System" MSのWindows2000で使われているPRNGに対する攻撃. バイナリファイルを解析してアルゴリズ…

ホテルの予約状況だけ見た．あれー3人以上の部屋は既に残りが少ない(;´Д｀) 早めに予約した方が良さそうなので，明日にでも先生と相談することにしよう．

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というサイトもある. 小中の教師向けの資料があるようだ.

連休中にアイデアが出た. 簡単な証明でconcurrent secureまでいけるようだ*1. 久し振りに格子というか組み合わせ問題に戻った. リング署名も先行研究のアイデアを使うと出来る. 先行研究は論文の構成や証明が酷いので*2, アイデアだけもらっておく. 偽造不可…

セキュリティ自由研究：この夏、グミ指を作ってみないか − ＠IT はてなブックマーク - セキュリティ自由研究：この夏、グミ指を作ってみないか − ＠IT HiromitsuTakagi プロとしての礼儀作法, 上野宣, また上野宣か, ハカークオリティ, bad 参考文献くらい書…

ビットコミットメント - Wikipedia ビットコミットメント、コミットメントスキームとは、暗号理論における秘密情報を送る手法である。コミットメントスキームでは、その秘密情報は改ざん可能であるがそれを確かめることができる。 だったので英語版から翻訳…

暗号業界ではハッシユ関数またはランダムオラクルとしてH:{0,1}^*→Gを使う。 GがZ_NやZ_pの場合は普通のハッシュ関数を使えばいい。 一方、GがZ_p^*中の位数qの部分群であったり楕円曲線上の位数qの群の時はどうするのか? 場当たり的な解決方法として、内部…

Cryptology ePrint Archive 2007/348 - C. Peikert, V. Vaikuntanathan, B. Waters "A Framework for Efficient and Composable Oblivious Transfer" OTがメインらしい. 中を見るとRegev05暗号の新しい使い方が書かれている. 鍵サイズ全体のサイズのオーダー…

M 上にはM

GQ-IBSを自分で構成する。車輪の再発明。 署名や認証の事情を鑑みるに、ペアリングを使わないIBEは偉いなぁ。

そういえばドイツは新正書法を採用したので色々と大変だったようだ. 大学でドイツ語を学んだのが2000年以降なので既に新正書法だった. 教科書に新正書法対応と書いてあったのを覚えている. sssとsが三つ並ぶ単語を見て書くのが面倒くさいと思ったものだ. 書…