MarriageTheoremのこと

_ （4/8記：年度初め。新しくうちのグループに加わった人や海外から帰ってきた人（正確には、こちらの人は先週から復帰していたのだが）などで居室が少し賑やかになった…のを視界の端に入れつつ論文書き。）

_ （4/8記：職場までの移動時間が勿体無いので有給休暇発動。）

_ （4/8記：この日は、というか正確には日本時間で翌朝９時が某国際会議の投稿締切だったので、徹夜の勢いで論文を書いていたのだが、途中で限界がきて少しだけ仮眠を取ることになった。時の流れを感じた。）

_ （4/8記：論文締切との闘いを終えて何とか職場に向かったものの、当然のように具合悪くなってすぐ帰宅する羽目になった。）

_ （4/8記：某C大ミーティング。この日も締切疲れの影響で家を出るのがだいぶ遅れてしまった。）

_ （4/8記：週末。休んだ。）

_ （4/8記：週末。久々に出掛けようかと思ったものの、台風を思わせる強風のため断念。）

_ 疲れが残っているのか、脳みそが研究するほどシャキッとしてくれないので、居室の机と本棚の大掃除をしていた。

_ つい最近まで論文投稿に追われていたから言うわけではないのだが、現在の論文査読システムにおいて、論文が採録されるまでに何度も不採録→再投稿を繰り返す部分はもうちょっと効率化できないものかと思う。勿論、内容に不備があって不採録になるのは仕方ないけれども、内容の不備ではなく投稿先のレベルと論文の価値の不整合が原因の場合は、エディターからその論文の価値に見合った論文誌や国際会議へ推薦する（内容は審査済みとして簡単な審査のみ）制度などがあると、再投稿の度に同じ論文が繰り返し査読される非効率さが少しは解消されないかなぁ、と思っている。研究者が昔より忙しくなっている現状、相対的に査読の負担が重くなっているわけで、省ける無駄は省いた方が業界全体のために良いのではないだろうか。

_ 先日、twitterにて「印象操作」の話題を見かけたので「印章操作」というネタを投入したところ、某氏からこちらの品の存在を知らされた。素晴らしいマジレスであった。

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

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

_ 気になった論文１：On Evaluating Circuits with Inputs Encrypted by Different Fully Homomorphic Encryption Schemes, Zhizhou Li and Ten H. Lai, http://eprint.iacr.org/2013/198

We consider the problem of evaluating circuits whose inputs are encrypted with possibly different encryption schemes. Let $\mathcal{C}$ be any circuit with input $x_1, \dots, x_t \in \{0,1\}$, and let $\mathcal{E}_i$, $1 \le i \le t$, be (possibly) different fully homomorphic encryption schemes, whose encryption algorithms are $\Enc_i$. Suppose $x_i$ is encrypted with $\mathcal{E}_i$ under a public key $pk_i$, say $c_i \leftarrow \Enc_i({pk_i}, x_i)$. Is there any algorithm $\Evaluate$ such that $\Evaluate(\mathcal{C}, \langle \mathcal{E}_1, pk_1, c_1\rangle, \dots, \langle \mathcal{E}_t, pk_t, c_t\rangle)$ returns a ciphertext $c$ that, once decrypted, equals $\mathcal{C}(x_1, \dots, x_t)$? We propose a solution to this seemingly impossible problem with the number of different schemes and/or keys limited to a small value. Our result also provides a partial solution to the open problem of converting any FHE scheme to a multikey FHE scheme.

_ 気になった論文２：Non-malleable Codes from Additive Combinatorics, Divesh Aggarwal and Yevgeniy Dodis and Shachar Lovett, http://eprint.iacr.org/2013/201

Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. Although such codes do not exist if the family of "tampering functions" \cF is completely unrestricted, they are known to exist for many broad tampering families \cF. One such natural family is the family of tampering functions in the so called {\em split-state} model. Here the message m is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with L and R {\em individually}. The split-state tampering arises in many realistic applications, such as the design of non-malleable secret sharing schemes, motivating the question of designing efficient non-malleable codes in this model.

Prior to this work, non-malleable codes in the split-state model received considerable attention in the literature, but were either (1) constructed in the random oracle model [DPW10], or (2) relied on advanced cryptographic assumptions (such as non-interactive zero-knowledge proofs and leakage-resilient encryption) [LL12], or (3) could only encode 1-bit messages [DKO13]. As our main result, we build the first efficient, multi-bit, information-theoretically-secure non-malleable code in the split-state model.

The heart of our construction uses the following new property of the inner-product function over the vector space F^n (for any finite field F and large enough dimension n): if L and R are uniformly random over F^n, and $f,g: F^n \rightarrow \F^n are two arbitrary functions on L and R, the joint distribution (,) is ``close'' to the convex combination of "affine distributions" {(U,c U+d)| c,d \in F}, where U is uniformly random in F. In turn, the proof of this surprising property of the inner product function critically relies on some results from additive combinatorics, including the so called {\em Quasi-polynomial Freiman-Ruzsa Theorem} (which was recently established by Sanders [San12] as a step towards resolving the Polynomial Freiman-Ruzsa conjecture [Gre05]).

_ ひょんなことからTwitterで某river_jpn氏に教わったところによると、オセロでプレイヤーが互いに協力した場合、最短９手で後手（白）を全滅させることができ、また最短１１手で双方の石が残っているのにどちらも打つ手がない状態にできるらしい。特に後者はたった１１手でそんなことが可能ということでたいそう驚いた。オセロは奥が深いですねぇ（←ちょっと意味が違う気が）。

ところで、後手ではなく先手（黒）を全滅させられる最短手数は何手なのだろう？

_ （4/15記：某C大ミーティング。思ったより体力を消耗していたらしい。）

_ （4/15記：週末。自宅の最寄り駅から15分ぐらいの某駅周辺が想像以上に充実していて驚いた。今まで気付いていなかったのは迂闊であった。また行こう。）

_ （4/15記：週末。出かけようと思っていたがあまりの風の強さに外出を断念。本当に今春は不安定な天気の日が多いなぁ。）

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

_ 詰将棋解答選手権の一般戦の問題を解いてみた。とりあえず全部解けたので一安心。チャンピオン戦を全問解くのはブランクとか関係なく私には無茶だから置いといて、一般戦を全問解けるくらいの解図力は一応維持しておきたいものである。ちなみに、作品としては２，３，５番あたりが好み。

_ （4/17記：職場の歓送迎会に出席した。）

_ 地元の書店が開いている時間帯と行き帰りの時間帯が合わず、まだ今月号の「数学セミナー」を買えていない。

_ （4/20記：３件打ち合わせが連続していた。）

_ （4/20記：某C大でYMDさんの論文紹介を聴いた。面白そうなアイデアが浮かんだけれども何かできるかなあ。）

_ 週末。このところ週末になると天気が悪くて困ったものである。

_ （4/22記：週末。久々に夕食を作った。豚汁を作っているつもりがξ具材の選択を誤ったらしく気付いたらただの味噌煮込み鍋が出来上がっていた。な、何を言っているのか（以下略））

_ 最近以下の商品を発見してしまい、何度か購入。

どう考えても販売元の策略にまんまと嵌っている。だがそれがいい。

_ （4/28記：この日が中間締切の書類があったため対応に追われるなど。）

_ （4/28記：勤務先と共同研究相手方の両方で用事があったため移動時間が多かった。）

_ （4/28記：某所で研究のお話。事務員さんが、私がコーヒーを飲めないことを憶えてくれていて初めからコーヒー以外の飲み物を出してくれるのはとてもありがたい。）

_ （4/28記：某C大ミーティング。事務書類やら論文やらの締切が近い案件が大量にあっててんてこ舞いであった。実るといいなぁ。）

_ （4/28記：連休初日。へばっていた。）

_ 連休二日目。たまっていた日記書きを進めるなど。

_ 連休三日目。久々の外食。

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

_ 気になった論文：Public key exchange using semidirect product of (semi)groups, Maggie Habeeb and Delaram Kahrobaei and Charalambos Koupparis and Vladimir Shpilrain, http://eprint.iacr.org/2013/226

In this paper, we describe a brand new key exchange protocol based on a semidirect product of (semi)groups (more specifically, on extension of a (semi)group by automorphisms), and then focus on practical instances of this general idea. Our protocol can be based on any group, in particular on any non-commutative group. One of its special cases is the standard Diffie-Hellman protocol, which is based on a cyclic group. However, when our protocol is used with a non-commutative (semi)group, it acquires several useful features that make it compare favorably to the Diffie-Hellman protocol. Here we also suggest a particular non-commutative semigroup (of matrices) as the platform and show that security of the relevant protocol is based on a quite different assumption compared to that of the standard Diffie-Hellman protocol.

（ACNS 2013にアクセプトされた論文と思われる）

_ （5/1記：連休明け。最近、Wordと格闘しすぎている。）