前提 将棋盤(9×9のマス目を持つ盤)を使って二人が陣取りゲームをする。自分の番になったとき、空いているマス目（自分の陣地でも相手の陣地でもないマス目）の中からいくつか選んで「自分の陣地」にすることができる。一度に自分の陣地にできるのは、「1個」…

3B-4：全てのIVを利用可能なWEPに対する鍵復元攻撃 --- WEPに安全なIVは存在しない --- 藤川香顕 (神戸大学大学院自然科学研究科) 9B-5：制服を用いたソーシャルエンジニアリングの解決策の提案 ―生体認証による制服の起動― 青木洋之 (静岡大学大学院情報学…

たけしのコマネチ大学数学科で調和数の問題をやっていた (橋げたの話) 筈. もしかすると最適解と言っているかも知れないが, それは最適解ではないということが示されていた. 悲しいかな論文の題名を忘れてしまったので検索出来ない. ICALP 2006だと思ったん…

今年の5月位にはてなの認証APIんときに出てきてた話→2006/05/08 MAC_k(x)=MD5(k,x) としたときに不味い理由とかで. Cryptology ePrint Archive 2006/319 - S. Contini and Y. L. Yin "Forgery and Partial Key-Recovery Attacks on HMAC and NMAC Using Hash…

よく元ネタはガウスだって書いてあるけど, ほんまはラグランジュやでって, N. Gama, N. Howgrave-Graham, H. Koy, and P. Q. Nguyen "Rankin's Constant and Blockwise Lattice Reduction" (CRYPTO 2006)に書いてあったので調査中. 一般化したのはエルミート…

question:1157731166 ++[>++++++++++++++++<-]++++[>>++++++++++++++++<<-] ++++++[>>>++++++++++++++++<<<-]+++++++[>>>>+++++++ +++++++++<<<<-]>>+++++++++.>>+++.<<<.>>>+.<+++++++ +.---.>--.<.<<.>>---.>.<-.++++++++.+++++.--------. <<++++++++++.--…

(暗号学的)疑似乱数生成の話. 証明の手法としては, 識別機が存在すると, 一方向性が破れることを言う. HSSとかGRはこの一種か. hard-core predicate (function)を作る Blum-Blum-ShubとかGoldreich-Levinとか. List-decodingと関係してくる. フーリエ変換+Li…

横から勝手に. そういうときはWikipediaよりもComplexity Zooの方が信頼が置けます. Scott Aaronson先生作. NP完全とNP困難の違いというのは、その問題自身がNPに入ってるかどうかということですが、NPな問題から多項式時間で帰着できるのにそれ自身がNPじゃ…

某所で頂いたコメントより. R. Kumar, D. Sivakumar "On the unique shortest lattice vector problem" (TCS 2001) uSVPのexact versionのNP-hardnessについて. A. Frieze "On the Lagariaz-Odlyzko algorithm for the subset-sum problem" (SIAM J. of Comp…

前回詰まっていた帰着をいじっていると, 一次変換の話になって固有ベクトルの話が出てきて困ったという話. しかもC^nじゃなくって, (Z/qZ)^nで. そのせいで, n|q-1が必要. 何だそりゃ. で, 問題はZ/qZの元を要素とするn次正方行列があったときに, その固有ベ…

三日唸ってようやく思いついたので, やっと確率の評価が出来た. Impagliazzo and Zuckerman ``How to recycle random bits'' (FOCS '89) *1にRegularity Lemmaが載っているのでそれを使って何とか既存の証明を参考にしながらやりくり. 向こうの証明に難しい…

電子的に読めるようになったらしい. Coputational Complexity 2006/05/22 STOC Business Meeting, ACM STOC 2006 やっと気になっていた N. Bansal, M. Sviridenko "The Santa Claus problem"が読める(名前受け). Session 2B, 7B辺りを読むべきなんだろうけど…

無節操（；´Д｀） DLDHV, DLTDH, DITDH, DHTDHとか見てると, やり過ぎだと思えてくる.

『semi Black-Box reductionが存在するならmildly Black-Box reductionが存在する』は分かった. 『fully Black-Box reductionが存在するならsemi Black-Box reductionが存在する』の逆が正しいような気がしてしょうがなかったが, シミュレータの存在条件が違…

Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, Yangと大所帯. 1-3章をざっと読んだ限りだと, Canetti, Goldreich, and Haleviの"Random Oracle Model v.s. Real World"みたいなノリだなぁ. あれは, うまいこと二項関係を作って, 中が覗けないオラ…

STOC '98のじゃなくって, J. of ACMに載ったFull Paperの方. ゼミで3時間半かけてやった. 3時間半なので, 細かい証明は抜いて直観に訴えるようにしたのだけれども, 学部生は大丈夫だったのだろうか. 後で聞いてみよう. 反省点 当日になってFoilsでプレゼン用…

In Theory: P, NP, and Mathematics経由で. 数学科向けのP vs NP問題の話ぽい. イントロで出てくるのが, Diophantine equationsに結び目に証明論.

List of Accepted Papers出てました. 楕円曲線関係が多いなぁ. 暗号関係で, 以下をメモ. R. Granger, D. Page, and N.P. Smart High Security Pairing-Based Cryptography Revisited Damien Stehlé On the Randomness of Bits Produced by Sufficiently Regu…

公開鍵のサイズは, 元々. で, Micciancio (CaLC 2001) がHermite Normal Formにすることでサイズをに下げている. その後, Paeng, Jung and Ha (PKC 2003) がにしてたけど, あれは安全性が証明されていない. >

ECCC TR06-046 Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev "A Complete Public-Key Cryptosystem " さっき見て軽く読んだ. Completeねぇ? 一応出来てるっぽいけど. 10pと短いので, またあとで詳しく読むことにする. Danny Harnik, Moni Naorの…

Lyubashevsky and Micciancioのアレ. 後々の拡張という面から見ると, Peikert and Rosen (TCC '06)よりも筋が良いかも. で, この前検索してたら, 東北大の方々がRegular Lattice上のCVPについて話しているのを見つけたのだが, 何だろうね?

初めてMathematicaを弄った. そういえば評価版のCD-ROMどっかにあったような気もする. ヘルプ読もうとしてヘルプの項目ダブルクリックで落ちたことには驚いた. なぜそれで落ちるよ. 無駄にクリックしちゃ駄目なのか. リストに対するMapやらMapThreadやらがあ…

23日から学校で寝ていた. 24日には論文投稿. 帰宅したものの眠い. 22日に洗濯物を干していて取り込んでいなかったので, 雨に濡れる. 次のネタ用に何となくグラフを作ったのでアップ. これをx軸方向で切ったときの面積をf(x)として解析したいんだけど, という…

Prattのアレ. 証拠を判定するアルゴリズム on xyzzy lisp. (Prime? w11)->t (x1 x2 x3)というリストがあって (xi \in \{t,nil\}), (and x1 x2 x3)を計算したかったのに外した. (apply #'and list)は駄目だった. マクロをちゃんと理解しないと駄目だなぁ. 追…

今週頭に提出. 通るかどうかは分からん. こういう計算は無駄だが, 倍率6倍. acceptだろうがrejectだろうが, その結果を発表することになったので, 何とか本文を6ページに収めた. 後は, abstractを1ページ分作る作業. これは来週末までに完成させれば良い. 別…

出勤じゃないな. 一日グラフを書く勢いで. wgnuplot偉い. ↓射影 こんなグラフを色々と書こうかな, と.

それを使えばよかったのか! これで大丈夫. 前に同じようなことをやっていた人が, 言葉を濁していたところを, 別のところから持ってきた結果ですっきりと説明が出来る訳だ. その先行者の後に出た結果だからしょうがないのかな.

最後でも無いのかな. とりあえずここさえ終われば楽になると信じて頑張る. 今やってる解析が片付けば, 後は文章の問題になってしまう筈.

昨日のうちに証明を綺麗に直して送信. そこまで本質では無いので定数倍して調整して数字が分かりやすくなるように. 別に必要ないんだが, まぁいいか. 後は1.の詳しい解析と別方向の改善案. 1.の方は前から拾い読みしていたが, 本腰を入れて取り掛かることに…

1,2,3,4とあって、2と3の改良は片が付いて、昨日辺りから4をやっていたら4の改良の目処が付いた。1を理解するにはまだ時間が掛かるなぁ。 学会に通ると良いなぁという感じ。誰もやってなかったので、多少の意味はあると個人的には思っている。同内容の論文が…