読者です 読者をやめる 読者になる 読者になる

mathjaxテスト

$a^{b^c}$

平均時・最悪時の話

djbがなんか言ってるのでメモ。 Often fascinating to see how bad science spreads: e.g. "lattice-based crypto is the only crypto with worst-case-to-average-case reductions."— Daniel J. Bernstein (@hashbreaker) 2013, 8月 14 @hashbreaker What a…

PS3の署名に対する攻撃の話

Chaos Computer Club (CCC) により開催されたハッカー・カンファレンス 27C3 において、Bushing 氏、Marcan 氏、Sven 氏の3名により PS3 の新たな exploit が公開されました。 PS3 では ECDSA と呼ばれる電子署名アルゴリズムが用いられているそうですが、そ…

CRT

考えるの面倒臭くなってmapとapplyで全て済ましたというメモ。 (define (ExGCD x y) ;;;Input: x, y in Z ;;;Output: a and b s.t. ax + by = gcd(a,b) (let loop ((r0 x) (r1 y) (a0 1) (a1 0) (b0 0) (b1 1)) (if (= r1 0) (values r0 a0 b0) (receive (q …

STOC 2010のY. Dodis, M. Pătraşcu, M. Thorupのが面白そうだとは思わんかね。 A[1...n] in {0,...,9}^nなるベクトルを考える。10進n桁の整数である。計算機上(PRAMでモデル化してる)で、各桁 A[i]を読み書きする機能を高速化しつつ保存容量をなるべく小さ…

2月中、書くの忘れてた。 博論が終わったので、色々読んでいる最中。 Toy soldiers楽しい. Tower Defenseに介入出来るだけでこんなに違うのね。 2010/121, 2010/127. 格子暗号でCCA2出来たよと言われましても、Peikert and Waters (STOC 2008) とPeikert (ST…

博論は最後の追い込み中らしい。卒業出来たら晴れて研究職です。 最初の半年は新人研修だとか。9-17なので研究出来るとか言われても。 SCIS中に査読1つ終えるとか。そしたらもう1個来るとかなんとか。 今年のナイトセッションではTwitter上の情報からソーシ…

予告

生きてます 年始に暇が出来たら最近の完全準同型暗号の話を纏めようかと。 年末は暇が無い...

今後の予定

ASIACRYPT 2009の参加登録は済 問題は、日曜日中に登録を済ませるか、月曜日に登録するか、のどちらが良いか、だ。 ICS 2010... 凄く行きたいのだが、1月4日〜7日と日程がきつい。暗号の論文もあるので要注目。

グラフ理論的言い換え

CS

この時間帯に書き直しました。 グラフ理論を知っている人用の書き方をすると 直径2かつk-正則グラフの頂点数nの最大値 直径2かつk-正則平面グラフの頂点数nの最大値 を求めたいという問題です。定義から平面グラフか一般のグラフか分からなかったので両方用…

本題とは関係無い。

b:id:harutabe あんま言いたくないけどこれがもし玻じゃなくて璽とか凹とかだったら「まあ、ルールだから」ってなるんじゃあないかと思うんですよ。その「ルール教徒」とは、あなたの想像上の存在にすぎないのでは? そういえば、璽も凹も常用漢字なので、両…

ついでに暗号関係のビデオ

IBM (via: Homomorphic Encryption by Luca Trevisan) RSA Conf. 2009のMillerとKoblitz

Gentryの博士論文

Craig Gentry's PhD Thesis まさかのFully Homomorphic Encryption単体でした. 200ページあるので皆さん頑張って読みましょう. 技術的なところだけで170ページ位あります. ちらっと見た限りでは, 鍵生成や暗号化の方法を変えることでイデアル格子のSIVPから…

Signcryptionの本が出るらしい.

Boyenのサイト見てたら, Xavier Boyen, Identity-Based Signcryption, invited chapter, to appear in (eds.) A. Dent, Y. Zheng, Practical Signcryption, Springer, 2009. というのがあった. 同様に, J. Baek and R. Steinfeld, Security for Signcryption…

フィボナッチ数の話

CS

素数体係数多項式の拡張GCDを書かないといけないのだが, それはさておき. ストリーム版が無いけど気にするな. ;;;素朴 (define (fib1 n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib1 (- n 1)) (fib1 (- n 2)))))) ;(time (fib1 30)) ; real 0.285 ; user …

間違い

プレゼン資料を見て唸ったが, 自分がハマったところと同じところにはまっているように思える. どうやって証明する気だったのだろうか?

最近のePrint

まぁ出自が出自なので公開鍵系しか読めませんけど。 R. P. Singh, A. Saikia and B. K.Sarma. “Little Dragon Two: An efficient Multivariate Public Key Cryptosystem.” (Cryptology ePrint Archive: Report 2009/488) まさかのLittle Dragon. 多変数多項…

うーん

CS

ツッコミに対する反応を見て余計分からなくなった. mixi日記で、突っ込まれた点について。 量子コンピュータはチューリングマシンでできることは全てできることが証明されているので、かけ算も当然できます。量子力学的重ね合わせを使わなければ、全ての量子…

論文用のmicroformatは無いの?

誰かやってるだろうと思ってmicroformatで探しても見つからんかった. bibtex準拠とかで広まると, 便利だと思うんですけどね.

IND-CCA2の定義

Bellare, Hofheinz, and Kiltz “Subtleties in the Definition of IND-CCA: When and How Should Challenge-Decryption be Disarrowed?” (ePrint 2009/418) 暗号のIND-CCA2安全性も定義によって強さが変わるという話. 敵がメッセージを2つ出す前に行った復号…

IDベース暗号

Introduction to Identity-Based Encryption (Information Security and Privacy Series)作者: Luther Martin出版社/メーカー: Artech House発売日: 2008/01メディア: ハードカバー クリック: 14回この商品を含むブログを見る VoltageのLuther Martinが書い…

ランダムな巡回行列の作用素ノルムの上限

すっきりと解決したのでメモ. {-1,0,+1}要素のランダムなn次元ベクトル (c_0,...,c_{n-1}) を考えて対応する巡回行列を確率変数としてP_nとおく. l_2-ノルムに対応する作用素ノルムの上限は固有値の絶対値の上限に等しい. (n次正方行列を考えるので.) 巡回行…

格子縮小アルゴリズムの進展

とはいえ多項式時間じゃなくって, 指数時間掛かる方ですけどね.Ajtai, Kumar, Sivakumar (STOC 2001) を真面目に解析したら時間計算量2^{5.9n}, 空間計算量2^{2.95n}だったよとNguyen and Vidickが報告したのが今年の話 (J. Math. Crypt. 2009). Voulgaris a…

SchemeでJacobi記号

誰の役に立つのか分からないけど. 分岐が意外と多い. Jacobi記号はLegendre記号の一般化になっているので, Legendre記号もこれで求められますよ. (define (Jacobi a n) (cond ((= a 0) 0) ((= a -1) (cond ((= (modulo n 4) 1) 1) ((= (modulo n 4) 3) -1)))…

一般ハードコア関数の証明とフーリエ変換

8月5日はハーコーということでハードコアの日だそうです. (ちゃんと日本記念日協会に届け出たそうで.)ということなのでハードコア関数の話をします. Goldreich-Levinハードコア述語とリスト復号の話はよく出るんですが, GLハードコア述語とフーリエ変換の話…

undecidable problems

CS

とりあえず10個かー. 授業で証明読んだもの 停止問題とそのヴァリアント ビジービーバー ライスの定理 L(PDA)?={0,1}^*, L(PDA1)?=L(PDA2) PCP (Postの方) 証明知らないもの ヒルベルトの第10問題 ワンのタイル 読みたいもの DBLPから見繕う. 群同型 en.wiki…

Signed QR

まぁ詳しくはR. Ficshlin and C.-P. Schnorr (JoC 200)を見ていただくとして, Hofheinz and KiltzがCRYPTO 2009で発表する論文がDennis Hofheinzのサイトから読めるようになったのでメモですよ.とりあえず, Nをnビットのブラム数とします. N=PQで, PとQはそ…

最近の格子話

2008年9月以降だとこんな感じですかね. 一般の格子 IND-CCA2 PKE (modular GGH) (STOC 2009) KDM-CPA PKE (CRYPTO 2009) EUF-CMA Sig w/o RO (Manuscript) SID-IND-ANON-CPA HIBE w/o RO (Manuscript) イデアル格子 IND-CCA2 PKE (modular GGH, w/ quantum r…

日誌

しばらくルジャンドル記号の話をしていたのに, ガウス和の絶対値が√pになる証明で詰まるのはどうだろう. 指標の計算で良く出てくる, ちょっとだけずらすテクニックをすっかり忘れていた. van Damの論文で確認した筈なのに. 某所に某ネタが通ったようなので準…

メモ

SAC 2009 R. Misoczki and P. S. L. M. Barreto “Compact McEliece Keys from Goppa Codes.” McEliece暗号の新種. Goppa符号の部分符号だけどコンパクトな符号を使うらしい. あと, Key-wrappingの話とReal Traceable Signaturesをチェックする. Cryptology e…

日誌

下のミスはミスでは無かったようなので計算したら落ち着くべきところに落ち着いた. たまには数論的なオブジェクトと戯れたいと思ったが, 今がまさにそれか. フーリエフーリエ. 新暗号技術(←基礎研究室 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の元はちょうど…