MarriageTheoremのこと

_ （3/2記：某国際会議最終日。荷物が重かった。）

_ （3/3記：休日。風がものすごかった。）

_ （3/4記：桃の節句。ちらし寿司の存在をすっかり忘れていた。）

_ 今日から某国際会議なんだけど、某大変な事務書類の〆切が大幅に短縮されたせいで作業を余儀なくされている。表には出にくいけど、参加費払って参加してる国際会議を事務仕事に邪魔されるってのもおカネの無駄遣いだよなぁ。

_ あと、上役が部下の仕事の邪魔をする事例を耳にして大いにげんなりしている。上役の「仕事」は何だと思っているのかと小一時間問い詰めたい。

_ 某国際会議ランプセッション。英語でジョークを言うのは難しいと痛感（正確には、英語でジョークを言って笑いをとるのは、だが）。

_ arXiv:math 1月9日分まで、IACR ePrint 2013/127まで確認済み

_ ウェブページに載せている某詰将棋作品の問題図の持駒に歩が足りていなかったことを指摘しているブログ記事を妻が発見して知らせてくれたので、慌ててウェブページを修正した。ページの最終更新が2005年1月となっていたので、8年以上もミスに気付かないまま放置してしまっていたことになる。いやはや、なんとも恥ずかしい限りである。

_ （3/8記：某所に打合せに行った後で、駅周辺で某書類の仕上げに追われていた。）

_ arXiv:math 1月9日分まで、IACR ePrint 2013/135まで確認済み

_ （3/10記：一週間の疲れが出たらしくてへばっていた。）

_ arXiv:math 1月9日分まで、IACR ePrint 2013/138まで確認済み

_ 気になった論文１：Multi-bit homomorphic encryption based on learning with errors over rings, Zhang Wei, Liu Shuguang, Yang Xiaoyuan, http://eprint.iacr.org/2013/138

Basing on Learning with errors over rings (RLWE) assumption, we provide a new multi-bit somewhat homomorphic encryption scheme. We introduce canonical embedding to transform a ring element into a vector, such that polynomial multiplication can be performed in O(nlog n) scalar operations, and ciphertext size is reduced at the same time. The CPA security of this scheme can be reduced into RLWE assumption.

_ 気になった論文２：New Lattice Based Signature Using The Jordan Normal Form, Hemlata Nagesh and Birendra Kumar Sharma, http://eprint.iacr.org/2013/133

In this paper it is shown that the use of Jordan normal form instead of Hermite normal form would improve substantially the efficiency and the security of the lattice based signature scheme. In this scheme we also use a new hash function in such a way that the efficiency improved is obtain without decreasing the security of the function.

_ （3/12記：ここ数日の気候変化にやられたのか体調が明らかにおかしかった。）

_ （3/13記：移動中に、Twitterで見た以下の問題に想いを巡らせていた：

実数集合Rの通常の位相で連結な部分集合全体をSとしたとき、Rの位相で「その位相について連結な部分集合全体がSと一致する」ものたちの中でRの通常の位相を何らかの形で特徴付けできるだろうか？

多分解けたのだけど、完全に細部まで精査したわけではないので一度きちんと証明を詰めてみたい。それにしても、位相空間論の考えやすい問題は上質なパズルのように頭を心地よく動かしてくれるものだなぁ、と再確認した次第。）

_ arXiv:math 1月9日分まで、IACR ePrint 2013/145まで確認済み

_ 気になった論文：Limitations of the Meta-Reduction Technique: The Case of Schnorr Signatures, Marc Fischlin and Nils Fleischhacker, http://eprint.iacr.org/2013/140

We revisit the security of Fiat-Shamir signatures in the non-programmable random oracle model. The well-known proof by Pointcheval and Stern for such signature schemes (Journal of Cryptology, 2000) relies on the ability to re-program the random oracle, and it has been unknown if this property is inherent. Pailler and Vergnaud (Asiacrypt 2005) gave some first evidence of the hardness by showing via meta-reduction techniques that algebraic reductions cannot succeed in reducing key-only attacks against unforgeability to the discrete-log assumptions. We also use meta-reductions to show that the security of Schnorr signatures cannot be proven equivalent to the discrete logarithm problem without programming the random oracle. Our result also holds under the one-more discrete logarithm assumption but applies to a large class of reductions, we call *single-instance* reductions, subsuming those used in previous proofs of security in the (programmable) random oracle model. In contrast to algebraic reductions, our class allows arbitrary operations, but can only invoke a single resettable adversary instance, making our class incomparable to algebraic reductions.

Our main result, however, is about meta-reductions and the question if this technique can be used to further strengthen the separations above. Our answer is negative. We present, to the best of our knowledge for the first time, limitations of the meta-reduction technique in the sense that finding a meta-reduction for general reductions is most likely infeasible. In fact, we prove that finding a meta-reduction against a potential reduction is equivalent to finding a ``meta-meta-reduction'' against the strong existential unforgeability of the signature scheme. This means that the existence of a meta-reduction implies that the scheme must be insecure (against a slightly stronger attack) in the first place.

_ arXiv:math 1月9日分まで、IACR ePrint 2013/146まで確認済み

_ arXiv:math 1月9日分まで、IACR ePrint 2013/155まで確認済み

_ 気になった論文：AES-like ciphers: are special S-boxes better then random ones? (Virtual isomorphisms again), Alexander Rostovtsev, http://eprint.iacr.org/2013/148

In [eprint.iacr.org/2012/663] method of virtual isomorphisms of ciphers was applied for differential/linear cryptanalysis of AES. It was shown that AES seems to be weak against those attacks. That result can be generalized to AES-like ciphers, which diffusion map is a block matrix, and its block size is the same as the S-box size. S-box is possibly weak if it is affine equivalent to a substitution that has the same cycling type as an affine substitution. Class of possibly weak S-boxes is very large; we do not know is there an S-box that is not possibly weak. Strength of AES-like cipher is defined by virtual isomorphism and not by differential/linear properties of the S-box. So we can assume that special S-boxes have little or no advantage comparatively to random nonlinear S-boxes. The conjecture is verified by experiments. If the conjecture is true, then search of the best S-boxes that maximizes the cipher strength against differential and linear attacks joined with virtual isomorphisms has no sense.

_ （3/19記：この日は「第３回関西すうがく徒のつどい」初日。私自身は、参加者募集期間中に「会いに行きたい方々もいるけど、時期的に忙しそうだしなぁ、どうしようかなぁ」とうだうだしている間に「人気歌手のコンサートチケットじゃないんだから」とあきれるほどの早さで参加申し込みが定員に達してしまった*1ので不参加だったのだが、こちらのまとめなどを読むとたいへん盛況だったようで喜ばしいことである。
なお、結局私は前日に急遽舞い込んだ書類書きの仕事でこの日と翌日はてんてこまいだったので（なぜ金曜夜に月曜始業時間前〆切の仕事が舞い込むのか、という点はとりあえず不問）、もし参加していたら「会場でPC立ち上げて実況の振りして書類書き」という駄目なオトナの姿を高校生や大学生の皆様に見せる羽目になっていた。そう考えると欠席でよかったのだろうなぁ、と自らに思いこませている。）

_ （3/19記：「第３回関西すうがく徒のつどい」二日目。まだまとめは読めていないのだが、TwitterのTLを眺めている限り盛況のうちに終了したらしい。よきかな。で、私はというと、書類書きはどうにか格好が付いたものの、夜になってひどい悪寒がするようになったので早めに床に就いた。きっと「つどい」不参加のショックが今頃になって出てきたのだろう（←誇張表現）。）

_ （3/19記：前夜の体調不良からはだいぶ快復したもののまだ体調が本調子ではなく、翌日のワークショップでの発表のことも考え、大事を取って休暇を取得して家で寝込んでいた…というか蒲団の中で発表準備に勤しんでいた。）

_ （3/20記：公開鍵暗号に関する某ワークショップで発表。これまでにも何回か各所で発表してその度に「主張が不思議すぎてよくわからない」的な定評を得ている曰くつき（？）の研究成果の紹介だったが、今回は「今までで一番理解できた」といった感想を複数の方からいただけたので発表者冥利に尽きた。）

_ （4/7記：論文〆切に追われて日記を放置していたら未記入の日がたまり過ぎて驚愕している。この日は祝日だったらしいのだが、さすがに何があったか覚えてないぞ…）

_ （4/8記：諸々の用事が一段落したので、４月頭締切の某国際会議投稿に向けて本格的に準備を開始した。）

_ （4/8記：某C大でのいつもの勉強会。）

_ （4/8記：週末。この日に何をしたかは覚えていないのだが、そろそろテレビアニメも番組改編期だなぁと考えた記憶が何となく残っている。）

_ （4/8記：週末。多分論文を書いていた。）

_ （4/8記：年度末なので事務作業が多い。この日はとある業者さんにとある物品を納品しに来ていただき、追加作業のためにその物品をそのまま持ち帰っていただくという何ともえげつない作業が発生した。）

_ （4/8記：手帳を見返すとこの日は有給休暇を取っていたらしいのだが理由が思い出せない。まぁ、論文の書き過ぎで体調不良になったか自宅で論文書きに集中したかったかの二択なのはまず間違いない。）

_ （4/8記：年度最後の会議だったのだが、論文書きでそれどころではなかった。）

_ （4/8記：年度末の最終営業日は翌日だがその日は某C大行きということで、年度末の事務処理締め作業（と論文書き）に追われていた。数ヶ月前の出張の旅費精算のために事務の方に渡したはずの書類が私の机の引き出しから発見されるなど凄惨な状況であった。）

_ （4/8記：某C大ミーティング。論文のタイトルについて相談したら大幅に改良された（と感じられる）新タイトルが返ってきた。ありがたい。）

_ （4/8記：週末だが必然的に論文書きに追われる。）

_ （4/8記：週末。論文書き。何故以前の投稿論文を手直しするだけでこんなに時間がかかるのかと自問したが、結果自体をだいぶ改良したからだという当たり前の結論を再確認しただけであった。）