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

今後の予定

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

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

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…

間違い

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

最近の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. 多変数多項…

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が書い…

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

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

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

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

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…

メモ

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…

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に通ったそうなので, 皆…

The SHA-3 song (@EUROCRYPT 2009)

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

配色

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

BRMの話

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

オペレーションズ・リサーチ 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…

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

Plantardの

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

ACNS 2009のリスト

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…

Overbeckの

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

Segevの

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を秘密鍵長とし…

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のサイトに名前だけ出ていて面白そうだなと思っていたの…

IEEE P1363.1D12 (NTRU)

D10で見つけたバグが直ってないや.

ある意味攻撃

概要 Koichiro Noro and Kunikatsu Kobayashi. “Knapsack Cryptosystem on Elliptic Curves.” (ePrint 2009/091)を軽く読んだ. 書き直してみたら拡張ElGamal暗号の改悪になってしまった. したがってこの論文の価値が消滅した. 面倒くさいので正しい構成は元…

コンピュータ代数ハンドブック作者: J.フォンツァガテン,J.ゲルハルト,山本慎,三好重明,原正雄,谷聖一,衛藤和文出版社/メーカー: 朝倉書店発売日: 2006/06メディア: 単行本 クリック: 28回この商品を含むブログ (2件) を見る Modern Computer Algebra作者: J…

メモ

ブックマークでやれと思った. Mihir Bellare and Thomas Ristenpart. “Simulation without the Artificial Abort: Simplified Proof and Improved Concrete Security for Waters" IBE Scheme.” (ePrint 2009/084, EUROCRYPT 2009) Brett Hemenway and Rafail…

ダメ論文に攻撃成功。何故かMS Wordで書かれた論文は攻撃しやすい。

Paillier暗号

Paillier暗号 - Wikipedia 英語から訳した. 後は詳しい人にお任せ.英語版の方だと岡本―内山暗号 (en:Okamoto-Uchiyama cryptosystem)やDamgård-Jurik暗号(en:Damgaard-Jurik cryptosystem)もある. Chor-RivestとOTUくらいは日本語版作るかね.

IEEE S&P

IEEE Symposium on Security and Privacy - Accepted Papers (via: topics I like: Accepted Papers IEEE Symposium on Security and Privacy)

STOC 2009

STOC 2009 - Accepted Papers (with Abstracts) 格子暗号は2件. Peikertだけかと思ったら, Gentryが凄いの出してきた. イデアル格子ベースの暗号でNC1の回路をシミュレートできるらしい. エラーが足されるせいで, O(log n)までなのかな. エラーを外せれば任…

多変数多項式暗号のワークショップ

総務省の研究プロジェクトに「量子コンピュータの出現に対抗し得る公開鍵暗号の研究」というのが通ったらしく,そういやSCISの一部の原稿にもSCOPEとか書いてあったなぁという話.で,J. Dingが日本に来るので東京と大阪で2回ワークショップを開くというのが…

SCIS終了

皆様、お疲れ様でした。 ナイトセッションの補足 RSAセキュリティ RSAセキュリティ - セキュリティニュース - Vol.115 Vol.118でも同様. たぶん, 他にもある. IPA 1 平成19年度春期テクニカルエンジニア(エンベデッドシステム)試験-午前問題 IPA 2 セキュ…

RSA仮定または双線形写像付きCDH仮定の下, 標準モデルで安全な署名

Cryptology ePrint Archive 2009/028 - Susan Hohenberger and Brent Waters “Realizing Hash-and-Sign Signatures under Standard Assumptions.” EUROCRYPT 2009に出るらしい. ポイントは署名者を状態付きにしていること (今, i番目の署名をつけたので次はi…

Reed-Muller符号のリスト復号

P. Gopalan, A.R. Klivans, and D. Zuckerman. “List-Decoding Reed-Muller Codes over Small Fields.” (STOC 2008) 中身読んでないのでメモだけ.r次のRM符号RM(r,m,2)のメッセージ空間は, m変数r次のF_2上多項式の集合. 符号が入っている空間はF_2^mの各要…

AGV09の話

A. Akavia, S. Goldwasser and V. Vaikuntanathan. “Simultaneous Hardcore Bits and Cryptography against Memory Attacks.” (TCC 2009) Vaikuntanathanのところから. Freezing attackは“cold-boot attack”のことであったことよ. 内容的にはRegev05とGPVの…

Eurocrypt 2009 (2)

はてなアンテナ > Eurocrypt 2009を含むアンテナ 適当にアンテナに放り込んでみて, 他に誰がアンテナに登録してあるんだろうと思って見てみた. 他に誰か奇特な人が居るらしい. あー,もう一人はきっとXXさんですね. Asiacrypt 2008で見ても2人だった.

今日のびっくり (Wikipedia)

RSA暗号とは、桁数が大きい合成数の素因数分解問題がNP困難であることを安全性の根拠とした公開鍵暗号の一つである。 暗号(Cipher)とデジタル署名(Digital signature)を実現できる方式として最初に公開されたものである。 うぉい. 誰だ素因数分解がNP困難だ…

GGH暗号について

GGH系の鍵生成は楽なんだが, Peikert08のGGH暗号と似ている. これだと一方向性をLWE仮定から証明できる. Gentry, Peikert, Vaikuntanathan (STOC 2008) の署名方式はGGH署名もどき. 前も書いたがパラメータの設定を頑張るとGapSVP仮定からいける Peikert08の…

pqcrypto.org

Post-quantum cryptography djbとTanja Lange. Bernsteinが纏めているらしい.. 量子計算, ハッシュ関数ベース, 符号ベース, 格子ベース, 多変数多項式ベースについて主要な論文を纏めてある. あと足りないのは, ナップサック系とか, グラフまたは計算量的な…