簡易Mathematicaとしては便利なんじゃないでしょうか. 例: (a+b)^2 x^2+2x=y^2+3 factor 2x^5 - 19x^4 + 58x^3 - 67x^2 + 56x - 48 factor x^110+1 in GF(5) 素数位数の体なら因数分解できる factor x^10-1 in Z/44Zとかは因数分解してくれない

今回の内容は以前当ブログに書いた「diff with C++」の記事をもっと濃くした感じになっていて、編集距離やLCS、SESの解説に始まり、Subversionのdiffエンジンや拙作のdtlで使われているO(NP)という差分アルゴリズムについて解説しています。 O(NP)や、それに…

終わらせてないのがある. 1つはフーリエ変換がえぐいことになるので見たくない. 解析的数論とか知るかー. しかも既存方式より効率が良くないっていう. なんか別のと組み合わせるべきか. ただ別のも帰着がうまくいかないのでどうしようもない. ぬぅ. 決定性に…

EUROCRYPT2009ランプでのSHA-3替え歌：exploit&ac：So-net blogから. ビリー・ジョエルのWe didn't start the fireの替え歌ですね.

格子点の個数がわからない 僕は組合せの話は知らない／分からないのですが、なぜか次のタイプの問題にしばしば遭遇します； R^nの第1象限 {(x_1, ..., x_n)∈R^n | x_1≧0, ..., x_n≧0 } の範囲で、非負整数kに対して、 方程式 x_1 + ... + x_n = k 不等式 x_1…

黒地に黄色字という配色をやや見かけます. また, 深い青色を地にして白文字というのもあります. たまーにですね, 適切なテーマを使わずに, そういう色遣いをボックス毎に自分で全部指定している人が見受けられます.さて, Powerpointには配色というものがあり…

Eurocrypt 2009 rump session - Dodis... ADW09でやってた認証, 署名, 鍵交換以外に, ADWW09と1人増えて, 暗号とIDベース暗号でも出来たという話. Gentry's IBEから出来るそうですよ.>

ようやく一つ証明を終えた. パラメータを評価するためだけに証明するってのも面倒くさくて厭ですねぇ. 大体想像通りの帰着効率になるので, あとは代入して決めていけば良いんだけど, 6日までに終わるかしら.

天帝シリーズを全部読んだ. 上辺を取っ払うと実は真っ当なパズル物ってのがいいですね. 上辺も結構酷くって (褒め言葉), 4作目で限定状況どう作るかと思ったら, まさかの***ですよ. パズル系だと正しい方向性の1つなんだろうか. ふむ. ある意味, 野尿描きた…

h2部分を無駄に消していたのを忘れていた. 直したい場合は, .day h2 .title {display: inline;} で.

4/24発売だそうです。 確率と計算 ―乱択アルゴリズムと確率的解析―作者: Michael Mitzenmacher,Eli Upfal,小柴健史,河内亮周出版社/メーカー: 共立出版発売日: 2009/04/24メディア: 単行本購入: 2人 クリック: 32回この商品を含むブログ (11件) を見る 目次…

杜撰な研究者の日記: 2009/04/16 - 暗号議論の解説論文一覧から國廣先生のTurorial (解説記事を集めたもの) を読んで思い出したのでメモ. ちょっと前のOR学会の機関紙で暗号特集をやっていました. 特集 意外と身近な存在、情報化社会の暗号技術 特集にあたっ…

適当に調べ物をしていたら, Partial Discrete Logarithm Problemってものを見つけたのでメモ.N=pqをsafe primeの積とします (p=2p'+1, q=2q'+1). GをQR(N^2)とします. N^2を法とした平方剰余が成す巡回群. するとGの位数はpp'qq'. また, 位数Nの元はちょうど…

そういえばWeb2.0という悪しき名の影響下にPirate 2.0という攻撃法がEUROCRYPT 2009で提案されるのでした. 2.0って名が体を表してないから嫌なんですけど, まぁそれをいったらCCA2 (chosen-ciphertext attack 2) も同じよね. CCA1.5ってのも見た覚えがあるし…

今度のEUROCRYPT 2009に出る, Hofheinz and Kiltzの素因数分解仮定からIND-CCA2暗号を作る論文がHofheinzのサイトに出ていた. BBS擬似乱数生成器+チェック機能でIND-CCA2KEMを作るってのがポイントみたい. また今度のEUROCRYPT 2009に出るHohenberger and Wa…

某人（アフリカに行っているかも）が使っているであろうはてなidを調べてみたら、そのidを使っている人はアラサー女子でありポエム日記なんか書いちゃったりしているので非常にびっくりした。あのidでそんな日記なんて。

AAECC-18 Program (via topics I like) プログラム出てた. 日本人が居るなぁと思ったら, Nagata, Nemenzo, Wada “On Self-Dual Codes over Z16”以外は全部今井先生が共著者に入ってた.

2009/133 J. Katz “Signature Schemes with Bounded Leakage Resilience.” 格子暗号 (Akavia, Goldwasser, Vaikuntanathan (TCC 2009)), 共通鍵暗号 (Y. Dodis, Y. Tauman Kalai, S. Lovett (STOC 2009)), 数論系暗号 (Naor, Segev, 2009/105)と来たら署名で…

2008/378 t制限付き環準同型暗号の話が更新されてた. 安全性証明をつけたらしいが, 読んでいない.

問題の解き方は分かったのだが解いていない. Z/10^{8}の計算と行列を組み合わせれば何とかなるみたい.

数値を確かめてみたらIBIは難しそうということが分かった. 完全性との兼ね合いなのか. 仕方がないので双対取ってみるかどうするか. 藤田・塚田“クリエイティブ・コモンズ利用許諾の形式意味論” 推薦論文らしい.

IBIを作れるかと思ったが, 非常に強い仮定または謎のサンプリング方法が必要となりそう. 解決すべき課題もなく作れてしまうと論文にならないので良いことではある. 正しくない暗号文のサンプリングねぇ. 人工的過ぎる. これが出来たら後は幾何分布と組み合わ…

2009/03/11に見つけたACNS 2009に出るT. Plantard and W. Susilo. ”Broadcast Attacks against Lattice-based Cryptosystems”がPlantardのサイトからダウンロード可能だったので読んだ. HåstadのRSAに対する同報通信用攻撃をナップサックや格子でもやってみ…

11から12が後期入試だと思って学校に行ったら, 12から13だったので学校に入れず.

ACNS 2009 - Accepted Papers [topics I like: ACNS "09] なんか変なのあるんですよね. T. Plantard and W. Susilo. “Broadcast Attacks against Lattice-based Cryptosystems.” あとNTRUはまた新しいパラメータ設定をするらしい(;´д｀) P. Hirschhorn, J. H…

ShamirのPKP用ゼロ知識とCFS署名をくっ付けてブラインド署名を構成. アイデアは面白くって, メッセージのダイジェストをマスクするんじゃなく公開鍵をマスクするというもの. その上で鍵の関係間を示そうというらしい. 一瞬ブラインド性無い気がしたので, 後…

Moni Naor and Gil Segev “Public-Key Cryptosystems Resilient to Key Leakage” (Manuscript, 2009). Akavia, Goldwasser, and Vaikuntanathan (TCC 2009) で定義されたKey Leakage Attackについての話をすでにしている. DDHから構成して, Lを秘密鍵長とし…

なんで今まで残しておいたんだろうか. 基本的には総当り. 1/50くらいのステップに出来るので刈り込んで20秒ちょい.

そういえばscis.jpに移動してなかったなと思いだして, 2009のサイトからコピペしようと思ったのでローカルに保存した. HTMLを見たらなかなかひどいことになっていた. html要素とかbody要素とかまで纏めてコピペしちゃってたのね.

Cryptology ePrint Archive: Report 2009/098 - Martin Albrecht and Craig Gentry and Shai Halevi and Jonathan Katz “Attacking Cryptographic Schemes Based on ‘Perturbation Polynomials’” Katzのサイトに名前だけ出ていて面白そうだなと思っていたの…