証明は確認してもらった。証明の細かいところを書き直して記法を統一することになったのでそこを詰める。

予定が立ったので証明を引き続き行うことに。Average/Averageで帰着するので大丈夫だろうという読み。論文に纏め上げて投稿して来年へ続く。間に合うかどうかが心配。

もう一個Bもあらかた片付いた。分散を見れば確かにそうだ。 あと二つC, Dとあるが、これはAとBの結果を組み合わせれば大体説明できるので、山は越えた筈。 あー、証明書くの面倒臭い。

とりあえず峠は越えた。もう一つ拡張することになったのでそちらを解析中。来年どっかに投稿出来るといいなぁ。

もう一息で書いていた「最後の帰着」の前の帰着の方が駄目っぽかったのだけれども、師匠の機転で生き残った。アイデアが出たのが金曜日で、気づいたのが先生と師匠とディスカッションしていた今日というのは、自分でもどうかと思う。 纏められそうな雰囲気は…

素直にインスタンスを変換するのは無理っぽい。さて、どうしたものか。 やっているのが落穂拾いってのもアレだなぁ。あと昨日・今日の件でb:id:pulp_literature, b:id:wonder_wonderと2件見つけて、ブックマークのお気に入りに登録した。喜ばしいことだ。

最後の帰着が出来るかどうか不安。先生に相談しよう、そうしよう。

とりあえず2bitには出来る。後はn:security parameterに対してbit数kをに出来るかどうか。多分、出来ると思うんだが。 問題は、「何故誰もやってなかったのか」だなぁ。

Trolinのcycleの話をしていたら、ぐるりと回ってAD-Cryptosystemに帰ってきた。まぁ頑張りますか。

Ajtaiの証明はn/c cyclesの格子がhardcoreであることの証拠になるとTrolinが言っている意味がやっと分かった。そりゃそうだ。けれどもこの場合はcは定数だけど具体的に決まってないので駄目というかcycleの文脈からでは使いづらいということか。

CaLC(Cryptography and Lattice)(LNCS2146)の目次だけ眺めてみる。何でEditorがJoseph H. Silvermanなんだろう。NTRUでConvolution Modular Latticesだから?

SNFって何? ということになったので調べ物。 H.Cohenの『Course in Computational Algebraic Number Theory (GTM138)』の該当部分を調べて、Z自由加群に行って、そういや代数の最初の方で見たなということになって、代数関係を漁ることに。触ってないから忘…

後回しにしていたところが重要である点を突っ込まれしどろもどろ。 確かに『Complexity of Lattice Problems』に載ってました。ぎゃぁ。

昨日の続き。検討し直すと証明が上手くいったので一安心。一言で片付けられている部分も詳細に見直してみた。で、流して読んだProp. 1が残っているので、もうちょっと。明日、これで話をしなきゃいけないんだ。

は全部正の整数。少なくとも1組は同じ数がある。 とkを定義する。 としたときにが互いに素ということを示したいのだけれども、うまくいかなくて困る。あっさり「互いに素」とか書いてあるんだよなぁ。 やった反例出来たよーヽ( ・∀・)ノ で互いに素でなくな…

最近は格子の変形についての勉強をしている。計算用紙に行列書いて掛け算したり余因子行列取ったり。院試の際に復習しておいて本当に良かった。対角化、HNF、SNF。 調べてみると、ISSAC(International Symposium on Symbolic and Algebraic Computation)周り…

二つ意味がある罠。 cyclic_1 がcycle structureを持つとは、かつであること、と定義する。で、長さが1でないcycleをnon-trivialと言い、1個だけのnon-trivialなcycleをもつのがcyclic。 この定義から、cyclicな格子Lはあるベクトルvと正の整数dを使って、 …

V. Shoupの"Sequences of Games: A Tool for Taming Complexity in Security Proofs"を地味に日本語訳していたり、格子+暗号周りの論文を読んでいたり。Regevの2004の論文読んでて量子版の帰着のところだけ流したり。 ECCCのサーベイ訳して公開しておくと便…

学校のPCに入れたiTunesで論文を管理しようと思い片っ端から突っ込んだ。コメント欄にアブストをコピペしておくと楽かも。本当はbibtexと連携したソフトがあるのでそっち使った方が良いんだが。表計算ソフトでも十分だろうな。 研究室全員でそういうのを共有…

大雑把に纏めるとこんな感じ。 名前 格子の種類 安全性 One-way function? 応用 NTRU NTRU-Lattice 証明なし NTRUCrypt(暗号) NTRUSign(署名) Ajtai-Dwork unique-Lattice (SVP) w/a A-D Cryptosystem PRG GGH Lattice (CVP) なし GGH-Cryptosystem 覚えてい…

MicroSoft IMEは内積と外積を最初から登録しておいて欲しいと思います。 それはさておき、内積をどうにかしてゼロ知識証明に載せられないものかと悩み中。秘密情報（補助入力）の長さが分かってしまっているので、対象のベクトルと内積の値を教えた段階で次…

http://www.hatena.ne.jp/1122534879 懸賞付暗号問題。オロナミンCが頭から離れないのは何故だろう。こっちの方向であってる気はするんだがな。

検索で来ていたのでとりあえずメモ。 Google 暗号 解読 27・46・7・124・108・109・56・61・79・26% Excite 暗号 27・46・7・124・108・109・56・61・79・26・7・46・138・46・30・31・84・140・149・57・56・133・125・69・76・68・60・41・133 Google 46・…

倍すれば良いのか? 正しく作ってないと、証明者が困るようにならないかしら。4月頃にもらった冊子にWeb上で日記・ブログ等を書くのは宜しいが、詳しい研究内容を書くと後で困りますよ的なことが書かれていたなぁ、と今更思い出した。普通に読んでも訳が分か…

戦略的無条件降伏（Rallyは終わり） 2005/07/13 暗号問題。はてなポイント付き。を見て俺もやりたくなったので。制限時間は今週末。暇つぶしにどうぞ。古典的な手ばっかり使っているので割合簡単に解ける筈。暗号文の指示に従ってコメント欄に書き込みを。 …

やったー、署名できたよヽ( ´ー｀)ノ 問題は証明。

割と良いアイデアなのだが情報が、悪意ある検証者に対しては情報がだだ漏れ。さて、どないしたものか。 ということでO. Goldreichのゼロ知識証明に関するチュートリアルを読んでいたり。

太田先生の資料3頁に登場する暗黒時代って。ROモデルは今後どうなるのかしらん。姑息に見えて好きじゃないんですけど、あれ。

ここをこうすると上手くいくんじゃないかと思って、定義をじっと眺める。 Pの方は上手くいくが、\hat{P}はどうだろうなぁ。universal_2だろ? 面倒なことになる。

多項式環の直積上の関係を強引に格子論の言葉で言い換えたという感がする。だから格子の次元は2nになっている。公開鍵から秘密鍵を求める問題は、NTRU lattice上での近似CVPと同じになる。が、そのノルムの入れ方はどうなの。その近似CVPはどのクラスに入る…