1+2+...+n = O(n) となることをいまから証明しますが，もちろんこれは間違っています． (真実は 1+2+...+n = n(n+1)/2 なので．) どこがまちがっているでしょう？というのがクイズです． 証明 nに関する数学的帰納法． n=1のとき，左辺は1で右辺はO(1)．1=O(…

連休中にアイデアが出た. 簡単な証明で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暗号の新しい使い方が書かれている. 鍵サイズ全体のサイズのオーダー…

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

数論をやらずに公開鍵暗号を研究するという目標を立てこの二年間研究を行ってきたわけだが, 結局数論を学ぶ破目に. なんてこった. そういえば2月くらいも円分多項式を見ていた気がするなぁ.

Cryptology ePrint Archive: Report 2007/279 - C. Peikert, B. Waters "Lossy Trapdoor Functions and Their Applications" 流し読みした Lossy trapdoor functions (lossy TDF) という新しい概念を導入する. lossy TDFから以下が作れる OWTF CRHF IND-CPA…

先日の問題の一部をどう書く？orgで見つけた. 「組合せ型の最小完全ハッシュ関数」の逆関数 どう書く？orgが下のdecodeの話になっている. パスカルの三角形をテーブルで持つとnがでかいときに遅すぎる. Fishcer and Sternのアルゴリズム *1 を実装して投稿し…

2004年くらいから毎年STOC, FOCS, SODAに名前を連ねるMihai Pătraşcuというすごい博士課程の学生が居る. Pătraşcuは加法的組み合わせ論をCSの方に上手く使っているらしい. WebDiarios de Motocicleta: Bijective Combinatoricsに例とその問題があるので読ん…

ボストンへの手紙 直交の場合はOK (もう少し計算が必要だけど). 関数空間やら関数同士の内積がイメージ出来るようになったのでもうちょっと計算を続ける予定. Rigui Zhou "Quantum Probability Distribution Network"っての見つけて名前受けしたのでメモ. S.…

某所でネタになっているのだが, セッティングを間違えた所為で状況によってはモンティ・ホール問題になっていない. なんてこった. エイプリル・フールだった. わかりづれぇ.

組合せゲーム・パズル ミニプロジェクト 第２回ミニ研究集会 2007/03/16に豊橋技術科学大学だそうで. Rogue脱出判定問題のPSPACE完全性：新井滋、武永康彦（電気通信大学） Rogueはキャラクタ端末のディスプレイでよく親しまれていた、コンピュータ上のアド…

上既約な2次多項式は上既約でない (). 一般に, 上既約なn次多項式fが既約な体はどうやって求めたものだろう. 位数pはnの多項式で上から抑えられるんだろうか. 具体的にはnを素数としたときの, がどんな体上で既約なのかに興味があるんだが. Eisensteinの判定…

前回の発表で, Fさんのコメントを受け掘り進めた話. 色々と考えると, 上手くいくことが分かったのでお伺いを立てる. 師匠に話すと, 基本的には組み合わせか. メインは××を発掘してきて上手く適用したこと?と微妙そうな顔をする. 先生に話すと, それは面白い.…

hyperrefでしおりを上手く作れない. \usepackage[dvipdfm,bookmarks=true,bookmarksnumbered=true,bookmarksopen=true]{hyperref} とすると変な風にしかしおりが出ない. Package hyperref Warning: bookmark level for unknown title defaults to 0. Package…

どっかに論文が通ったら5ということか. 師匠が4だった. 論文が通ったので数が付くのは確定. 師匠は3だったので, 俺が4.

某社の間で話題になっているらしいので, 某社の人の過去ログを全部読んだ (去年の5月に見つけてから読んでなかったので, 20ヶ月分全部).

符号 Singleton限界とRS, RM, Hadamardを話した. 今度BCH符号. 未だにデコードの話が出てこない. ROMと証明の話 HさんとNyさんの話を横で聞いていたのでメモ. 署名の安全性を証明するときにROMで以下のセッティングを考える. 署名オラクルとランダムオラクル…

会議の投稿がきっちり予定時刻に締め切られたので, ちょっとびっくり.

これはぼくの推測だが、彼らはこれほどのスピードでウェブが発展するとは当時全く思わなかったんじゃないか。もし未来が見えていたなら、この問題はノード数の加速度的な時間発展が加わるとNP完全くさいぞということに気がついて、まともなコンピュータサイ…

想定締切が今朝だったので、研究室のほぼ全員が泊まり込みという事態に。本来の締切は金曜日なのだが。

昨日の話. Macでemacs使いのYs君がreftex使ってなかった. それでemacsを2つ起動してたのかと得心. 来年の頭には研究室でtex講習会した方が良い気がする. で, ネタを論文にまとめている. 片方は, 格子暗号で出来ることは確認したけどまだ細かいところまで計算…

普通のTuring Machineだと移動先はL, Rの二つ. Lを左リセットに変えるとどうなるかって問題があるので, Lを左リセットでエミュレートしてみた. 終わって画像を見ると結構無駄が多い. 直すか. プログラムも大事だけどチューリングマシンもね (大体の人は授業…

ARTIFACT@ハテナ系 2006/10/21 デジタルオーディオにおいてデータは劣化しないが音は変化する 劣化と言っていいかどうか知らんが, 元の場合と音が変わり得る. CD-DAだとRS系の符号 (CIRC) が入っていて, エラー訂正できない場合は線形補完だったか何だかの補…

d.y.d. 23:51 06/10/19 ランダム生成 Impagliazzoの"A Personal View of Average-Case Complexity" (CoCo 1995, ps file) とかかなぁと思ってみたけどランダムなインスタンス生成の話はあんまりしてませんでした. ECCC辺りを漁れば出てくるかな? と適当な反…

トーラスや円筒形は二次元かという話はさておき, 分類表. 先生に話したら某研究会のネタになるよと話していたので, 円筒形奇数*奇数, メビウスの輪, n次元辺りを分類すると卒論のネタになるんじゃないでしょうか. 円筒形 偶数*偶数 後手必勝 (先手の取り方で…

while the # of #P is pronounced sharp (some textbooks also list pound or number as acceptable, but I've never heard the latter two used in real life). #PはNumber P, ♯PだったらSharp-Pと読むのが自然な気がする. ちなみにGarey and Johnsonの本の…

[ゲーム] 陣取りゲームをしませんか。 http://www.hyuki.com/d/200610.html#i20061009222222 自分の番になったとき、空いているマス目（自分の陣地でも相手の陣地でもないマス目）の中からいくつか選んで「自分の陣地」にすることができる。一度に自分の陣地…