海賊行為の話

そういえば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…

某人(アフリカに行っているかも)が使っているであろうはてなidを調べてみたら、そのidを使っている人はアラサー女子でありポエム日記なんか書いちゃったりしているので非常にびっくりした。あのidでそんな日記なんて。

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

Problem 237

問題の解き方は分かったのだが解いていない. Z/10^{8}の計算と行列を組み合わせれば何とかなるみたい.

数値を確かめてみたらIBIは難しそうということが分かった. 完全性との兼ね合いなのか. 仕方がないので双対取ってみるかどうするか. 藤田・塚田“クリエイティブ・コモンズ利用許諾の形式意味論” 推薦論文らしい.

午前5時の話

IBIを作れるかと思ったが, 非常に強い仮定または謎のサンプリング方法が必要となりそう. 解決すべき課題もなく作れてしまうと論文にならないので良いことではある. 正しくない暗号文のサンプリングねぇ. 人工的過ぎる. これが出来たら後は幾何分布と組み合わ…

Plantardの

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

11から12が後期入試だと思って学校に行ったら, 12から13だったので学校に入れず.

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

Problem 206

なんで今まで残しておいたんだろうか. 基本的には総当り. 1/50くらいのステップに出来るので刈り込んで20秒ちょい.

SCIS 2009のプログラム

そういえばscis.jpに移動してなかったなと思いだして, 2009のサイトからコピペしようと思ったのでローカルに保存した. HTMLを見たらなかなかひどいことになっていた. html要素とかbody要素とかまで纏めてコピペしちゃってたのね.

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で見つけたバグが直ってないや.

Problem 155

方針が間違っているので後で直さないといけないが, とりあえずハッシュの方が相当速いことが分かったのでメモ. a2の方が冗長なアルゴリズムだが, それでもa2の方が速い. n=18くらいまでは簡単にいける. (use gauche.collection) (define (a1 n) (define (f l…

Goldreichのブログ?

CS

my choices [Oded Goldreich] RSSが配信されているのでそっちで読んだ方が見易いかもしれません. 理想としてはWordpressに移行してTeXプラグインを入れて書いてほしい. TrevisanやTaoみたいに.

Problem 104

ようやく解けた. 現段階だと10分掛かってるのでもっと短くしよう.

ある意味攻撃

概要 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…

Problem 214

Problem70だかProblem72だかで使ったものを再利用して解いた. n=2〜4,000,000のphi(n)を求めるだけで60秒掛かっているのが難点か. もっと速くなる気もする.

Problem 203

なんで前回解けなかったのか分からない. 富豪的にgroup-collectionを活用しても, 0.072秒. Pen4からCore2Quadに変えた所為もありそうだが.

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

Problem 225

久し振りにProject Eulerを解く. 最近追加された中で一番楽そうだったものを選択. 某アルゴリズムを使わなくても13秒. 使うと3秒であった.

Paillier暗号

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

論文書き終了. 共著になった上, 向こうが殆ど編集してくれたので楽だった. まぁ5時まで起きてましたけど. 代数体の整数環に触れてしまった. そうそう使う機会も学ぶ機会も無いだろうと思っていたのだが. そんなところに行きたくはないんだが, 行かざるを得な…

論文書き

証明を書いて最後に辻褄が合うようにパラメータの計算をしていてえらい変なことになっている. 調べてみると先方の写し間違いだった. 元論文を探して修正したところ計算が合ったのでよしとする.

記号の使い方

既存の論文(主要な著者は4-5人程度) だと記号の使い方が引き継がれているのだが, 場合によって新しく記号をつけ直したりすると読み辛くてしょうがない. 数学系から格子に入ると横ベクトル主体で書く. 2000年以降の暗号から入ると縦. 符号も元々横ベクトルで…

IEEE S&P

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

計算量

2^{2n}回のZ_q上の操作または集合演算を, qn^2回の実数演算に落とせた. フーリエ変換は偉大である. これでn=1024でもテストできるようになった. 今までn=8でしか出来てなかったことに比べれば進歩だな. (nが大きければ大きい分だけ桁落ちが起きそうで, それ…

STOC 2009

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

どこかの話

面倒臭くってリンクする気が起きない. 非ゼロの整数に関しては素因数分解した結果の指数の列を無限次元ベクトルと考えると一意性が楽に示せますねと思いました. を 2^{Z^+}みたいに考えるというのが数学的には単純で宜しいと. 1は(0,0,...)と対応して良いと.…

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の高速化なのかしら?

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…

相反多項式

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

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

火閻魔人 (バーズコミックススペシャル)作者: 奥瀬サキ出版社/メーカー: 幻冬舎コミックス発売日: 2008/12/24メディア: コミック購入: 3人 クリック: 10回この商品を含むブログ (11件) を見る 『火閻魔人』と『支配者の黄昏』が一緒になって帰ってきた. 両方…

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

オードリー

決勝で春日さんが聴衆をマイムで表現しているというのは、演劇を知る人には理解しやすい。特にピスタチオの腹筋善之助(漢字あってんだっけか)を知る人なら尚更であろう。 と云うことを思いながら笑っていた。