日誌

下のミスはミスでは無かったようなので計算したら落ち着くべきところに落ち着いた. たまには数論的なオブジェクトと戯れたいと思ったが, 今がまさにそれか. フーリエフーリエ. 新暗号技術(←基礎研究室 2008年度勉強会) えーとまぁなんでCAB暗号を取り上げた…

日誌

だいたいの場合, 1日に1つでも言いたいことがあれば良いのでtwitterの方で賄えていることよ. 東京には市が沢山あるんだなということを認識した. 計算ミスを発見し, 1つはリカバリしたものの, 1つはリカバリ出来なさそうで困ったところ.

Gentry暗号の簡単な解説

抽象的なことしか書きません. 詳しいことはACMに$10払うかフルヴァージョンを待つかしましょう. Gentryの論文は格子の説明が無く初学者に厳しいので, その部分を補うためのノートに使ってください. ただし線形代数と多項式環の知識は仮定します. (といっても…

返信

期待されているようなので, Gentryの暗号 (STOC 2009) については簡単な解説を後日書きます. 今のところフルヴァージョンは公開されていないので, 詳しいテクニックはぼかして書く方向で. 乗法的準同型性, 加法的準同型性, 制限付き加法的準同型性, 制限付き…

最近の格子ネタ

お久しぶりです. C. Gentry. “Fully homomorphic encryption using ideal lattices.” (STOC 2009) えーとね, あんまり細かく読む気が起きてないんだけど. 安全性に関してはぱっと見それNTRU以下だろうという感じ. どうなんだろうね. うーん, mod qを取らない…

なんでROMでの証明を俺が書いてんだって話ですよ, 本当に. RO嫌いな方なのに理解が進む進む. Benny Applebaum, David Cash, Chris Peikert, Amit Sahai “Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems” (C…

BDD, uSVP, GapSVP.

Lyubashevskyが, Peikertのテクニックを用いることで, 近似度をO(√n)分悪くすることでuSVPはGapSVPに帰着できることを示していましたが (ePrintにある), BDDについても出来るということをMicciancioとの共著で書いてます. CRYPTO '09に通ったそうなので, 皆…

Wolfram|Alpha

CS

簡易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とかは因数分解してくれない

アルゴリズムの名前

CS

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

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

The SHA-3 song (@EUROCRYPT 2009)

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には配色というものがあり…

BRMの話

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

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

古野まほろ

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

20 Pandaについて

css

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

宣伝

CS

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

オペレーションズ・リサーチ 3月号 Vol.54 No.3 2009

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

Paillierの話

適当に調べ物をしていたら, 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

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制限付き環準同型暗号の話が更新されてた. 安全性証明をつけたらしいが, 読んでいない.

Problem 237

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

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

午前5時の話

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

Plantardの

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