2chのスレッドで反応するのは良くないなぁと思ったので, ここにメモを残しておきます. まぁそもそも仮定につっこむのもアレですが. 格子の被覆半径を計算する問題がNPに属することをわしが証明したら、 V. Guruswami, D. Micciancio, and O. Regev "The comp…

誤差付き計算を扱うことになった. 色々と調べたいのだが, どうしたもんだか. xの誤差が±2^{-k}であるとき, exp(-x)の誤差はどれだけ広がるのか? また誤差を±2^{-k/2}に収めるアルゴリズムがあるとしてその計算時間はいかほどか? 精度保証付き数値計算で調べ…

scis.jpでは過去のプログラムを勝手にアーカイブしてます. つきましては, SCIS 2000以前のプログラムまたはSCIS 2002のdocファイルをお持ちの方, 御連絡下さい.

構成は理解した. 何をやっているかは理解したので, 次は安全性の証明. しかし複雑なことになっている. PIR + ECC + RS-ECC + PKEとか止めて欲しい.

q : 素数, n, m : 整数 のとき、 を示せ。0 < n < q^m とします。 逆にした方が分かり易いんじゃないでしょうか. 証明 Z/qZ上で, 恒等式が成立すれば題意が言える.まずZ/qZでを示す. これは割と簡単に言えて, の係数は. 0 < a < qについてとなるのでOK. (\bi…

ref:FOCS 2008 - Accepted Papers Tali Kaufman and Shachar Lovett. Worst Case to Average Case Reductions for Polynomials Stefan Dziembowski and Krzysztof Pietrzak. Leakage-Resilient Cryptography in the Standard Model Dan Boneh, Periklis Papa…

p:素数, p|nとする. を示せ. 某講義ノートに証明無しで書かれていて困った. p≠nは必要ない. イコールの場合は両辺ともに1なので問題なし Hさんの解答 である. もしpがnの最小の素因数であれば, 右側のn/p以外の項の分子からnを除いても良い (modulo nで考え…

とりあえずpdfを落とした. 明日は昼に歯医者に行ってそのままゼミの準備をしようと思うので, 学校行きません.

ref:M. S. Lee and S. G. Hahn “Analysis of the GGH Cryptosystem” (SCC 2008). 予稿のコピーを頂いたので読んだ. GGH暗号 (CRYPTO 1997) の復習. セキュリティパラメータ (格子の次元) をnとする. (n=200〜400を想定する.) 鍵生成 Rを比較的直交している基…

今年はR. M. Karpだそうで. リチャード・マニング・カープ Richard Manning Karp - 第24回(2008)京都賞 先端技術部門ref:Computational Complexity: Karp Wins Kyoto Prize!

辞書を電子化することのメリットとして関連語へのリンクが作れるというのがある. 一方, 紙の辞書だと周囲の情報も入ってきてそれはそれで良いわけだ. だから電子化された辞書も周囲の情報を見せると良いと思うのだが, 誰かやってないものか.Google Mapが出て…

家で結果を纏めているところ. 書くの面倒くさい(;´Д｀) ePrintの方にCRYPTO 2008に出るものがちらほら [0806.2947] A Syntactico-Semantical Bi-Polar Disorder FLP Paradox Implies SAT is NOT NP-complete, P vs. NP does not exist, and ZFC is Inconsist…

B1-2向け.DFA用のポンピング補題は割と簡単に証明が出来ます. 状態数以上の文字列をDFAに入力として与えたときには, 鳩ノ巣原理より, 必ずどこかの状態を2回通っているということが直観です. 反復補題とも言われる様子 (→正規言語の反復補題 - Wikipedia)ポ…

結婚式二次会に出席. 鯖味噌定食を食べ, 深泥池に行く. 携帯で接写出来るのは面白いなぁ.深泥池にて トンボにピントが合わない(;´Д｀) バス停付近にて

WCC 2001で発表されているもの. http://dx.doi.org/10.1016/S1571-0653(04)00192-1 P. Solé, C. Charnes, and B. Martin “A lattice-based McEliece scheme for encryption and signature” (Electronic Notes in Discrete Mathematics, Volume 6, April 2001…

正確には解読ではなく, 秘密鍵を求めたいようです. なので, 実質, 素因数分解したいらしい. カスペルスキー、恐喝ウイルスの暗号解読を目指す大規模な取り組みを開始へ:ニュース - CNET Japan 2年前に登場してた人のファイルを勝手に暗号化しちゃうコンピュ…

Cryptology ePrint Archive: Report 2008/260 - D. Aggarwal and U. Maurer “FACTORING IS EQUIVALENT TO GENERIC RSA.” arXiv.orgの方でちょっと前にblack-box ringの話が出ていて, そっちの方だとimplicitにFact=GenericRSAを言っていたような気がする. ge…

HatenarMaps - はてな村勢力地図 kawasaki, hatenadiary, otsune, rikuo, SeiSaguruに囲まれてる(;´Д｀) ボロノイ図の構成とかk-Clustringとか色々アルゴリズムを使っているそうなので実装の詳細を読んで想像してみると面白いと思います→はてな村の地図『Hat…

SCC 2008の会議録とか出ないのかなぁと思って検索していると, SCC 2008 - ISIT 学会参加報告を発見. GGH暗号に対する攻撃の詳細が知りたかったのでありがたい. タイトルだけだとどういう状況での攻撃なのか分からなかった.

ref:「解読不能は数学的に証明済み」、RSAを超える新暗号方式とは − ＠ITということで6/6に追記あり. 技術的な詳細は無く, 進捗情報が書かれている. 仕様が公開されるとピアレビューが進みそうなので, さくっと公開して欲しいなぁと思いました.例のウェブサ…

Cryptology ePrint Archive 2007/083: B. Hemenway, R. Ostrovsky “Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code.” なんかCRYPTO 2008に載るらしい. 前のバージョンだとΦ-Hiding仮定によってたけど, 今度のだ…

グーグルのキャッシュが消えたようで. (どっかに魚拓が残っていたりしてね) 事業計画書.pdfを消し損ねているんですが, 大丈夫でしょうか?以下メモをコメントアウト. >

コンカレント安全なIDベース認証 (in ROM) できたヽ( ´ー｀)ノ

B3の頃は「自分の名前が付いた暗号方式を作る」とか思っていたのだが, 最近は認証やら署名の方につっこんでばっかだなぁ. なんでこうなったんだか. まぁ面白いからいいんだけど.

ref:スラッシュドット・ジャパン | MITMアタックを完全に防止可能な「蒸発鍵」方式を実用化? HW形式のOTP作成器を配布しておいて通信中も適切な周期でOTP認証を行っているのではないかという適当な予想.