PQCrypto 2006の2回目をやるようだ. 詳しくはPQCrypto 2008 - The Second international Workshop on Post-Quantum Cryptographyを参照のこと. 今度はLNCSで本が出るそうな. 格子関係だとSilvermanとSzydloでNTRU寄りのようだ. 前回はRegevやらNguyenやら居…

参考:Gregory Neven's Home Page - An edited volume of IOS Press Cryptology and Information Security Series on Identity-Based Cryptography. IACRのカレンダーを見ていて気付いた. 納得の面子. どこかが邦訳に動いていることに期待.

Rosen and Segevで書き忘れてた。DCRAからIND-CCA PKE w/o ROはCramer-Shoupがそう。

Cryptology ePrint Archive: Report 2008/134 - A. Rosen and G. Segev “Efficient Lossy Trapdoor Functions based on the Composite Residuosity Assumption”Peikert and Waters (STOC '08, Cryptology ePrint Archive: Report 2007/279)で新しく提唱され…

暗号の安全性は一種の学習不可能性だよという話を先生からよく聞くのだが, 学習不可能性を暗号の安全性から示したのって, 格子系以外だと何かあったっけかな. 暗号→学習不可能性の話はECCC 2005辺りに載ってる筈. 逆はHBプロトコルの安全性やRegev05とかがそ…

Cryptology ePrint Archive: Report 2008/119 - B. Chevallier-Mames, D. Naccache, and J. Stern, “Linear Bandwidth Naccache-Stern Encryption”を流し読み. Naccache-Stern knapsack cryptosystem - Wikipedia, the free encyclopediaか. 英語版だと記事…

SCISのプログラムを適当にテキスト変換してアップした. ところで, F2mは, F_{2^m}なのかF_2^mなのか分かんないのでどうにかして欲しい. 2004以降のも適当にテキスト形式でアップすると思いますよ. 以下であってたorz ところで, SCIS 2003 15D-4↓が文字化けし…

以下を示せば12月時点からの改善になっているらしい.任意のと原点を通るk次元超平面Pについて, のPに対する垂直成分を考える. このとき, が任意ので成立する.これで近似度を大体√nくらい削れる. 反例の構成: 右下方向への射影でノルムが増えている.

真面目な解説記事を書きました. 詳しくは暗号と署名の話を見てください. 高木浩光＠自宅の日記 - 公開鍵暗号方式の誤り解説の氾濫をそろそろどげんかせんとを, すがさん (id:FTTH) にIDコールされたので見た.そういえば, IPA (情報処理推進機構) の問題でも…

高木浩光＠自宅の日記 - 公開鍵暗号方式の誤り解説の氾濫をそろそろどげんかせんとを見て. そういえばすずきひろのぶさんの記事についてメモを書いてあったので公開します. 格子暗号についての間違いの指摘です. (当方, 格子暗号を専門にしているので.) Oded…

何か新しいのが始まるそうで→ISS square - 研究と実務融合による高度情報セキュリティ人材育成プログラム - 修士課程のプログラムらしい.

Qi Cheng and Daqing Wan “On the List and Bounded Distance Decodability of the Reed-Solomon Codes.” (FOCS 2004, SIAM J. Comp. 37). RS符号のリスト復号アルゴリズム (Guruswami-Sudan) の限界を超えた場合, リスト復号またはBDDが出来るかという問題…

Regev05やらGPVの公開鍵サイズをm=5nlog n, q=O(n^3)で見積もってみた. 大体n=512のときに鍵サイズが256Mbから1Gbか. Ajtai-Dworkのn=32のときにn^5 log nで160Mbとかにに比べればかなりの改善ということが分かる. 定数項が結構利いてくるものだ. 現実的には…

思い出すたびに内容が増えます 探索版で問題を定義しているのに問題はNP完全問題とあるプレゼンが二, 三件. (どなたの資料だったかは覚えていない.) H2NP WEB 出版のCRYPTOnnnnカンファレンス レポート. 一度読んだ覚えがある. 読み返してみると各所に勘違い…

On-the-fly (Girault, Poupard, Stern) で知識が漏れやすい場合ってあるじゃないですか. そういうときは証明者が何も送らなければいいんじゃないか? という発想が元だと思う.秘密鍵はm次元バイナリベクトルx. 公開鍵は格子ハッシュのインデックスであるZq要…

K. Bentahr, P. Farshim, J. Malone-Lee, N.P. Smart. “Generic Constructions fo Identity-Based and Certificateless KEMs” (Cryptology ePrint Archive: Report 2005/058) に載っているという話なので読んだ. 7章でOW-ID-CPA IBEとROを用いたIBKEMの構成…

IND-ID-CPAなIBEも出来たぽいヽ( ´ー｀)ノ 仮定が強いが, そこは勘弁.

Formal Methodってどんなんだろうね, と思ってDolev-Yaoを眺めてみた. 完全に安全な暗号系を最初に仮定するところが気になるが, まぁ, そういうものが存在するとして, 安全なプロトコルは可能か? という話らしい. Man-in-the-Middleを如何にして防ぐかという…

Y.-D. Zhao and W.-F. Qi “Small Private-Exponent Attack on RSA with Primes Sharing Bits.” (ISC 2007) ISC 2007 - Programに発表資料があるので見てた.N=pqとして, pまたはqの半分のビットが既知の場合 d

n=640, m=40の圧縮関数だけ作ってみた. Pollardの疑似乱数生成法を用いる. 底を2^{32}-1にして初期値54321で. さて, Hという行列を以下で構成する. としてhの巡回行列を作る. その上部分のm行だけ取り出して各要素をZ_{256}に入れたm×n行列がH. r, sを8mビッ…

PKC 2008のAccepted Paper List 杜撰さんのところから. 格子関係は3つ. P. Mol and M. Yung, “Recovering NTRU Secret Key From Inversion Oracles.” V. Lyubashevsky, “Lattice-Based Identification Schemes Secure Under Active Attacks.” T. Plantard, W…

Peikertのサイトに草稿があったので読んだ. とおく. nが2の冪のとき, はZ上既約. をの要素とする. Hを圧縮関数とし, 入力をmnビット列xとする. 入力xをm個のnビット列に分割 (をRの要素と見る) を出力とする 正確には違う. 各を計算する際に, DFTを使う a_i'…

C4Tのサイトを見ていて思ったこと. 3.3 Chosen Plaintext/Chosen Ciphertext Attack C4-1は, 選択平文/選択暗号文攻撃に対して強い: カオスの機能自身は一方向である. 鍵の処理装置は一方向である. 出力データは常に乱数である. 上記3項目により, 暗号化に利…

以前見かけた暗号関係の概要が微妙な書き方をしていた. 他はどんなもんだろうと思って適当に漁ってみた. とりあえず名前だけ並べておく. 2000年度 荻野 哲男 「安全な電子商取引を目的としたデータベースの新しい認証法の設計」 (上林 弥彦 PM) 奥富 秀俊 「…

SCIS 2008 プログラム 出てた. 全12頁のpdfだった. 字ちっさと思って文書のプロパティからサイズを見ると420x297であった。A3横で印刷しろということですか？

SWIFFT: A Modest Proposal for FFT Hashing Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, and Alon Rosen 何か名前付いてる. NISTのワークショップに出したのから変わったのかしら?

2006/08/29 - RSA署名の不味い実装の話らしいで取上げたDaniel Bleichenbacherによる攻撃を拡張したらしい.参考: T. Izu, T. Shimoyama, and M. Takenaka. "How to Forge a Time-Stamp Which Adobe’s Acrobat Accepts." (IMA CCC 2007) This paper shows how…

[私信]出来たと思うので確認中です.[/私信] 3日で一段落着いたか. 良かった良かった. 真面目に読めば火曜日には出来てたな, これ.

前に予告されていたPeikert and VaikuntanathanはGentryも入っていた. IBEで参加したぽい. C. Gentry, C. Peikert, V. Vaikuntanathan. "Trapdoors for Hard Lattices and New Cryptographic Constructions." (Cryptology ePrint Archive 2007/432) 書き直し…

V. Lyubashevsky "Lattice-based identification schemes secure under active attacks" PKC 2008 (To appear) PKC 2008のNotificationが今日なので出た様子. PKC 2008のサイトにはまだリストは無い. Feige-ShamirのOR constructionに乗せるとWIが言えるので…