n=2^k,q:素数かつ2n|q-1,D={0,1}とする. wはZ_q^*の位数2nの部分群を生成するものとする. 簡単のためにn=4,q=17とする. このときw=2が取れる. さらにZ_q[X]/X^n+1を考える. X^n+1=(X-2)(X-8)(X-15)(X-9)となり, この環のイデアルはこの4つの1次多項式の積で…

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

NguyenとこのAn LLL Algorithm with Quadratic Complexity (2009) *SIAM Journal on Computing*, to appear が気になるなぁという話. LLLの高速化なのかしら?

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

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

何か適当に考えていたら相反多項式に当たったのでメモ. 以下, とする.を考える. これとを同一視する. について, (縦ベクトル) と対応付ければ良い. 次にと関数rを定義する. 一回だけ回すイメージ. 更に関数Rをとして定義する. R(a)はfがのとき巡回行列. fが…

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の各要…

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の…