オーダー記法の問題 - 186 @ hatenablog
1+2+...+n = O(n) となることをいまから証明しますが，もちろんこれは間違っています． (真実は 1+2+...+n = n(n+1)/2 なので．) どこがまちがっているでしょう？というのがクイズです． 証明 nに関する数学的帰納法． n=1のとき，左辺は1で右辺はO(1)．1=O(1)なので成立． n>1のときを考えると，1+2+...+n=(1+2+...+(n-1))+n = O(n-1)+n = O(n)+n = O(n)． ここで，「1+2+...+(n-1)=O(n-1)」という帰納法の仮定を用いた． 証明終 このクイズはいろいろ示唆に富んでると思うのです．考えてみてください． (誰に向かって言ってるのか不明ですが．) 回答は作ったがコメントアウトしておく. 演習問題で出すと面白そう. >
新しいAjtai-Dwork暗号 - 186 @ hatenablog
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を元にパラメータを変更して解析を良くしたり, 1ビット暗号だったのをlビット暗号に変更している. MicciancioやRegevが導入したガウス分布の格子上のフーリエ解析から得られる結果を武器に解析を行い, 仮定をO~(n^2)-uSVPの最悪時の困難性にまで下げている*2. 次元をnのままにするのではなくn+lに変えているらしい. 解析が良くなったので, 公開鍵のサイズはO~(n^5)
秀逸なタイトル - 186 @ hatenablog
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. "Finding Collisions on a Public Road, or Do Secure Hash Functions Need Secret Coins?" (CRYPTO 2004) *2 ってのもある. *1:Springer - EUROCRYPT 1998 - Finding collisions on a one-way street: Can sec
グミ指の参考文献を探してみる - 186 @ hatenablog
セキュリティ自由研究：この夏、グミ指を作ってみないか − ＠IT はてなブックマーク - セキュリティ自由研究：この夏、グミ指を作ってみないか − ＠IT HiromitsuTakagi プロとしての礼儀作法, 上野宣, また上野宣か, ハカークオリティ, bad 参考文献くらい書けよ。大学院出てんだろ？修士課程で何を学んだんだ。 kmachu security 確かに参考文献は載せるべき。 参考文献は出して然るべきだなぁと思ったので辿ってみた. 横国の松本研の結果というのを覚えていたので, 一発. レシピ付きの論文は T. Matsumoto, H. Matsumoto, K. Yamada, and S. Hoshino. "Impact of artificial "gummy" fingers on fingerprint systems." SPIE 2002. 「週刊バイオ」第
Koblitzの自伝. - 186 @ hatenablog
Notices of the American Mathematical Society - September Issue - Neal Koblitz. "The Uneasy Relationship Between Mathematics and Cryptography" (pdf)を読んだ. in theory: The Swift-Boating of Modern Cryptographyから知る. 下書き In recent years...以降を削ればいいと思いました. Chairやった時に文化圏の差を知ったことでオチてるし. それはそうとAnother Look at "Provable Security", I and IIは書き方が嫌らしい点とランダムオラクル故の結果に突っ込んでいる点を抜けば示唆に富んだ内容だと思います. 帰着のtightnessの話 (Blum
PeikertとWatersの新しい論文. - 186 @ hatenablog
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安全な公開鍵暗号 IND-CCA2安全な公開鍵暗号 OT IND-CCA2安全な公開鍵暗号については, lossy TDFからNIZKを使わずに標準モデルでBlack-Boxに構成出来る*1. 応用としてNIZKを使わずに格子の最悪時から (量子帰着を許せば) IND-CCA2安全なn-bit暗号が出来るという結果(!) が出ている *2. Regev05暗号ではなく, Re
勘違い - 186 @ hatenablog
()がn次元実数空間の基底になっているとして, としていた. 危ない危ない. が直交基底でないと任意のgについて言えない. 慌てて論旨を確認した. 大丈夫だったので一安心. あと, 線形代数に関する勘が鈍り過ぎている. 研究室の人に話してフィードバックを貰えるので有難い.
重み一定符号化 - 186 @ hatenablog
先日の問題の一部をどう書く？orgで見つけた. 「組合せ型の最小完全ハッシュ関数」の逆関数 どう書く？orgが下のdecodeの話になっている. パスカルの三角形をテーブルで持つとnがでかいときに遅すぎる. Fishcer and Sternのアルゴリズム *1 を実装して投稿した. 暗号の立場から言うと一部のナップサック暗号やNTRUを実装する時に必要になる関数. ウォーミングアップ 俺が知っている問題から一つ. 暗号に使われるので知っている. 長さnのビット列の中でも1の個数がちょうどmのものを考える. とする. するとS(n,m)の要素数はである. 問題: 以下の二つのプログラムを与えよ. encode 入力: 出力: decode 入力: 出力: *1:元論文のアルゴリズムをベタに実装すると上手く動かないよ
問題紹介 - 186 @ hatenablog
2004年くらいから毎年STOC, FOCS, SODAに名前を連ねるMihai Pătraşcuというすごい博士課程の学生が居る. Pătraşcuは加法的組み合わせ論をCSの方に上手く使っているらしい. WebDiarios de Motocicleta: Bijective Combinatoricsに例とその問題があるので読んで解いてみた. 例2のデコードは分かったが, エンコードで諦めた. 誰かお願い. 以下, 問題. ウォーミングアップ 俺が知っている問題から一つ. 暗号に使われるので知っている. 長さnのビット列の中でも1の個数がちょうどmのものを考える. とする. するとS(n,m)の要素数はである. 問題: 以下の二つのプログラムを与えよ. encode 入力: 出力: decode 入力: 出力: 実装して分かったが問題を持ってきた論文に載っているアルゴリズムは間違って
訃報 - 186 @ hatenablog
R. D. Wingfield Rodney D. Wingfield was the English author of several mystery novels about Detective Inspector Jack Frost. He died on the 31st of July 2007 after battling cancer for a number of years.
最近の俺 - 186 @ hatenablog
研究 やっとスタートラインに立ったところ. ただ今日確認してみたら制限を付けた方の証明はすっと通った. 何か変なのであとで調べる. 特にChernoff boundを適用するあたり. 制限を付けていない方は前提条件から整理していかないといけないので大変. 夏休み中に終わると良いことよ. 字間 txfontsでboldでSchemesと書くと, eとmとeの間が空き過ぎる気がする. メモ パンダの尻尾は白い *1. パンダ描きへ伝言. 音楽 Aerialsが気に入ったのでSystem of a down買った. あとthe band apartを全部揃えた. ACIDMANはCCCDだが買った. 久し振りにCCCD見たよ. あとで調べたら, iTunes Storeで1500円だったorz. Toxicity アーティスト: System of a Down出版社/メーカー: Sony発売日
チェッカーの解法 - 186 @ hatenablog
昨日日経新聞に出てた. J. Schaeffer, N. Burch, Y. Björnsson, A. Kishimoto, M. Müller, R. Lake, P. Lu, S. Sutphen. "Checkers Is Solved " -- Science 最善手を打ち続けると両者引き分け. 1989年から回し続けてたらしい. 概要を読むと引き分けと書いてあるが, これAIの論文じゃないか? 本当に引き分けなのだろうか. Science読むか (面倒臭い). Chinook - World Man-Machine Checkers Championに実装されている. Publicationsの項から2005年のを流し読みした. このときはある開始状態からの探索を全て行ったらしい. 2007年に全ての定石を調べた終わったということか. 一般化チェッカーと一般化オセロの複雑さにつ
出張終了 - 186 @ hatenablog
面白い話が色々聞けた( ´ー｀) コスモアイル羽咋 グレイとキノコはシュール過ぎるだろ, 土産屋. 一般化ラミーの盤面判定問題は分岐が非常に多いのでNP完全くらいになる気がするんだけどどうなんだろう? 学生セッションで186::Diary - [結] 2006年10月 - 結城浩の日記 - ルソー展と陣取りゲーム・クイズのトーラス版やら四次元版とかの話をしようと思っていたのを忘れていた. コメントについては猛省. すっかり忘れていて何も用意してなかったのが失敗.
今日知ったネタ - 186 @ hatenablog
Computational Complexity: An Open Problem wiki!からOpen Problem GardenをたどってLonely Runner Conjectureというのを見つけた. 詳細は以下. 長さ1のトラックがある. このトラックの上をk人のランナーr_1,...,r_kがスタート地点から一斉にそれぞれ一定の速度c_1,...,c_kで走り出すものとする. ランナーr_iを一人固定する. このランナーが他の全てのランナーから1/k以上離れているような時間が存在する. ちょっと考えるとわかるけど, ディオファントス近似の逆で整数からいかに離れるかという話. k=2のときは自明. 実は発表されてからk=3,4,5,6と進んでまだ7辺りで止まっているらしい. 一般的に解けても良さそうなもんなのにね. あとCai-Cusick暗号のCusickはディオファント
計算量に関して - <a href="http://itpro.nikkeibp.co.jp/article/COLUMN/20070618/275029/">矢沢久雄の情報工学“再”入門</a>を祝す - 186 @ hatenablog
2007/07/01 改稿. NP問題の定義を追加. 家で勉強してた. 符号のリスト復号に詳しくなった. 矢沢久雄の情報工学“再”入門 第1回 アルゴリズムと計算量---「計算量理論」を理解し，アルゴリズムを評価するという記事を見て, 後半がダメダメなので突っ込み. なんかこういうツッコミしか日記にしないのはどうかと思うが, ブックマークもちらほらされているので誤解を広めないためにもツッコミを入れておく. 概要 前半のページ1とページ2は分かりやすく導入としては良い教材であると思う. *1 矢沢氏の文章ではNP問題およびNP完全問題の定義が曖昧である. 用語が不正確な為, 奇妙なことを書いている. (矢沢氏が定義を間違って覚えている可能性もある.) 引用 解けない「巡回セールスマン問題」 アルゴリズムとは問題を解く手順である。これを裏返すと，アルゴリズムの計算量は，問題の複雑性を示す尺度だ
手芸の時間 - はてな手拭い作った - 186 @ hatenablog
はてなアイデア - はてな新ロゴデザインが「青海波」に似ていて実は和風なので「はてなてぬぐい」を作るといいと思います。「しなもん」柄などのバリエーションもあったらきっとかわいい！ 聴く耳を持たない(片方しか) 2007/06/06 はてなてぬぐい欲しい！ rikuoさんの図案を作ってみようということで. 素人でも出来そうな に挑戦. クリエイティブ・コモンズの継承により, 画像は全て表示 - 非営利 - 継承 - Creative Commonsで. 携帯で撮ったので写真が汚い. 手拭いのサイズは35cm×90cmくらいらしい. 100cm幅や110cm幅の布を切って作ると端の処理が上手くいかないので, 元から36cm幅である9mのさらしを購入. 95cmくらい切り取って作ってみる. まずは樹脂で染め抜く部分を保護する作業. 菱形の型紙を作ると作業が楽. ただ, 型紙が大きすぎたのとレイア
情報処理技術者試験の問題 - 186 @ hatenablog
情報処理推進機構の情報処理技術者試験の過去問を見ていたら, ディジタル署名を生成するときに，発信者がメッセージのハッシュ値を暗号化するのに使うものはどれかというような文章が散見される. 大体の試験で1問しか出ていないのだが, こういうところから誤解が広まっていくのだなと思った. 初心者向けの説明としては分かりやすいけどさー. ElGamal署名やDSSの場合どうするんだろうね? RSA系でもFiat-Shamir変換から作るものとかも. そういえば, 2ch*1でも見た覚えがあった問題を発見. これはひどい. 問47 公開鍵暗号方式を用いて文書のディジタル署名を行う場合，鍵の関係に関する記述のうち，適切なものはどれか。 ア 暗号化鍵は公開しないが，復号鍵は公開する。 イ 暗号化鍵は公開するが，復号鍵は公開しない。 ウ 暗号化鍵，復号鍵とも公開しない。 エ 暗号化鍵，復号鍵とも公開する。 正
<a href="http://www.business-i.jp/news/ind-page/news/200703200016a.nwc">FujiSankei Business i. 産業／東芝、暗号メッセージ３分の１に圧縮</a> - 186 @ hatenablog
これか. 電子情報通信学会 2007総会から発見. A-7. 情報セキュリティ 3月22日 9:30〜11:30 共通講義棟南 S504講義室 A-7-4 ◎米村智子・村谷博文（東芝）代数的トーラス上の暗号系―圧縮伸長写像の計算コスト―
Rogue脱出判定問題 - 186 @ hatenablog
組合せゲーム・パズル ミニプロジェクト 第２回ミニ研究集会 2007/03/16に豊橋技術科学大学だそうで. Rogue脱出判定問題のPSPACE完全性：新井滋、武永康彦（電気通信大学） Rogueはキャラクタ端末のディスプレイでよく親しまれていた、コンピュータ上のアドベンチャーゲームである。残り体力のないキャラクターが魔物のいる部屋から脱出できるかという問題が、空腹度のパラメータを設定した場合PSPACE完全であることを示す。 へぇー（ ´・∀・｀） Rogueの脱出判定問題：武永康彦（電気通信大学） Rogueはキャラクタ端末のディスプレイでよく親しまれていた、コンピュータ上のアドベンチャーゲームである。残り体力のないキャラクターが魔物のいる部屋から脱出できるかというパズルがデュードニーの「コンピュータレクリエーション」で紹介されているが、その一般化がNP完全であることを証明する。 空
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
仮名遣いと書法 - 186 @ hatenablog
