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

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

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

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

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

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

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…

素数体係数多項式の拡張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 …

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

まぁ出自が出自なので公開鍵系しか読めませんけど。 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. 多変数多項…

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

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

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つ出す前に行った復号…

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…

誰の役に立つのか分からないけど. 分岐が意外と多い. 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ハードコア述語とフーリエ変換の話…

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

まぁ詳しくは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つはリカバリ出来なさそうで困ったところ.

抽象的なことしか書きません. 詳しいことは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…

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