n=640, m=40の圧縮関数だけ作ってみた. Pollardの疑似乱数生成法を用いる. 底を2^{32}-1にして初期値54321で. さて, Hという行列を以下で構成する. としてhの巡回行列を作る. その上部分のm行だけ取り出して各要素をZ_{256}に入れたm×n行列がH. r, sを8mビッ…

PKC 2008のAccepted Paper List 杜撰さんのところから. 格子関係は3つ. P. Mol and M. Yung, “Recovering NTRU Secret Key From Inversion Oracles.” V. Lyubashevsky, “Lattice-Based Identification Schemes Secure Under Active Attacks.” T. Plantard, W…

SWIFFT読んでたら出てきた. そんな名前だったのか. 以下, 多項式と行列表示の話. 某所の発表でこれを説明しなければならないのが面倒臭くてしょうがないので, ここに書いておく. 線形符号を知っている人なら知っていると思うので読み飛ばし推奨.まずモニック…

Peikertのサイトに草稿があったので読んだ. とおく. nが2の冪のとき, はZ上既約. をの要素とする. Hを圧縮関数とし, 入力をmnビット列xとする. 入力xをm個のnビット列に分割 (をRの要素と見る) を出力とする 正確には違う. 各を計算する際に, DFTを使う a_i'…

ありがとうございます. 論文の中身が間違っていた気がして確認したがそんなことは無かったぜ (増田こうすけ風).

C4Tのサイトを見ていて思ったこと. 3.3 Chosen Plaintext/Chosen Ciphertext Attack C4-1は, 選択平文/選択暗号文攻撃に対して強い: カオスの機能自身は一方向である. 鍵の処理装置は一方向である. 出力データは常に乱数である. 上記3項目により, 暗号化に利…

以前見かけた暗号関係の概要が微妙な書き方をしていた. 他はどんなもんだろうと思って適当に漁ってみた. とりあえず名前だけ並べておく. 2000年度 荻野 哲男 「安全な電子商取引を目的としたデータベースの新しい認証法の設計」 (上林 弥彦 PM) 奥富 秀俊 「…

f(x)=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,17,17,17,17,17,17,17,17,17,17... となる関数を作成してください。 ・σ・)ノ

SCIS 2008 プログラム 出てた. 全12頁のpdfだった. 字ちっさと思って文書のプロパティからサイズを見ると420x297であった。A3横で印刷しろということですか？

(use srfi-1) (use text.tree) (use text.html-lite) (write-tree (html:dl (map (lambda (m) (html:dt #`",m") (html:dd "nnnnn")) (iota 10 1)))) という感じで <dl> <dt>1</dt> <dd>nnnnn</dd> <dt>2</dt> <dd>nnnnn</dd> ... <dt>10</dt> <dd>nnnnn</dd> </dl> というhtmlを生成しようと思ったのだが, <dl> <dd>nnnnn</dd> <dd>nnnnn</dd> ...…</dl>

SWIFFT: A Modest Proposal for FFT Hashing Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, and Alon Rosen 何か名前付いてる. NISTのワークショップに出したのから変わったのかしら?

2006/08/29 - RSA署名の不味い実装の話らしいで取上げたDaniel Bleichenbacherによる攻撃を拡張したらしい.参考: T. Izu, T. Shimoyama, and M. Takenaka. "How to Forge a Time-Stamp Which Adobe’s Acrobat Accepts." (IMA CCC 2007) This paper shows how…

寸゛さんの12月分*1を見て楽しそうなので買ってみた. DDRに慣れている（た）身としては譜が十六分かどうかを見極めるのに困った. 初見では厳しい. しかしPuzzle Questといいこれといい, なんで日本語が変なんだろう? Normalを注意とかLetterを手紙とか. *1:i…

学業関係 SCISに2本出した. 論文2は元ネタ読んでから結局20日か. あと, 某会議の発表順も組んだ. Lyubashevsky and MicciancioのTCC 2008の論文*1はイデアル格子問題ベースの使い捨て署名だった. 鍵サイズ/署名時間/検証時間と全部O~(n). ただ次元を大きめに…

内輪ネタです. 電通大に太田・國廣研という暗号関係の研究室がありまして, 太田先生と國廣先生がボスです. よくよく考えると, 太田國廣という画家も居るのでした. おまけとして太田国広という競艇選手も発見.

という前フリの元に太田・國廣 研究室 - 研究テーマ - 格子に関する研究というのを見つけたという報告でした. これを読む限りだとGGH系だなー. 今年のSCISでは何本か出るのかなー.

論文2はイントロ以外は纏まった 色々なところを省略した所為だ. あとで証明を足したヴァージョンも作らんとな. 資料2は出来た

404 Blog Not Found:アルゴリズム百選 - 迷ったらbenchmark ということでナイーブなべき乗演算や繰り返し二乗法が出てます. O(n)とかO(log n)とか出てますが, 掛け算をO(n)回とかO(log n)回しているということです. (基本的な演算のコストは今後無視する様子…

ポスターを印刷したので資料1は終了. 90*110とかならPowerPointで何とかなるもんだ. 資料2は前に作ったのを使いまわせそう. 資料1で作った図を使うようにしよう. 論文1は手直しすれば終わり. 論文2はまだ確認が必要. 〆切りはSCISなので際どいことよ. [私信]…

まぁ，私は日記上の説明が丁寧ではない方なので (直接会ってる人にはこの話について聞かれたときに丁寧に返答してる気ではいますが)，たぶん私と同じ主張をもっと丁寧に186さんがしてくれていると思いますので，そちらをご参照下さい． という指名を受けたの…

一応言っておくと, 例の記事はフォローとして書いた. オーダー記法の定義を伝えるのが一点. 計算量が正確に定義されていないがそれでもdankogaiの記事に意味を持たせるために関数の呼び出し回数を測っているんだよということを知らせるのが一点. (やっぱりと…

こういう過度にpedanticな姿勢が、どれだけ多くの潜在読者を遠ざけているか、つっこみを入れるみなさんは考えたことはあるのでしょうか。アルゴリズムを語る人は少なくないのに、本にまでなることは滅多にない事情はこのあたりに由来するのではないかと思い…

グローバルCOE「計算世界観の深化と展開」発足イベント ― Compview Project site そういえば東工大がGCOEを取ったらしいですよ. ということで発足イベントが12/12にあるそうです. 概要集があるので見てみたらType3フォントで読み辛いことこの上ない(;´Д｀) …

第二問の答え @00:35 gosh>(question2 (expt 10 10)) 546875 第三問の答え gosh>(question3 (expt 10 10)) 759375 アルゴリズムごと間違えていた. 直していたらlogの精度が足りないことに気付いたのでもう一度考え直し.@11:56 296875でした. 比較的ヒューリ…

論文書きと資料作りに戻ります. 帰りの電車で一様分布になることは確認. 適切に引いていけば証明しなくても済むという逆に困った話.

Challenge for Geeks - JGeek Log gosh> (fib2 1) 1 gosh> (fib2 2) 1 gosh> (fib2 3) 2 gosh> (fib2 1000) 43466557686937456435688527675040625802564660517371 78040248172908953655541794905189040387984007925516 929592259308032263477520968962323987…

京都で薄着過ぎた. 今日は演習なので学校に行く.

404 Blog Not Found:アルゴリズム百選 - フィボナッチ数列にO()を学ぶ 404 Blog Not Found:私ごときがアルゴリズム本を書くことにした訳 申し訳ないことをしたのでフィボナッチ数列で一ネタ書きます. 計算量解析の基礎で良く出てくる問題なので知っている人…

RADWIMPSの「最大公約数」より 僕は僕で君は君 その間には無限に あるはずだよ 二人だけの公約数 ないよ。僕と君が整数で、それぞれの有限性を仮定すると、公約数は有限。 二つ元を取ったときに公約数が無限存在しうるUFDはあるのかな。一意分解しなくていい…

アルゴリズム大募集! C&R研究所 - コンテンツ募集より. LLL algorithm ブレゼンハムの線分描画アルゴリズム（様々な高速化や誤差修正方法など） 線形計画法の代表的解法 モンテカルロ法 遺伝的アルゴリズム 動的計画法 αーβ枝刈りなどのゲームでよく使うアル…