MarriageTheoremのこと

_ （6/2記：打ち合わせのため出張。宿泊したホテルの部屋にポットが備え付けられていないという驚きの展開。貸出備品扱いらしい。）

_ 昼過ぎまで打ち合わせに参加した後に帰路に就いた。今回は週末を使って出張したので、どこで代休を取るかが思案のしどころである。

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

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

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

_ 気になった論文：Security Analysis of Pseudo-Random Number Generators with Input: /dev/random is not Robust, Yevgeniy Dodis and David Pointcheval and Sylvain Ruhault and Damien Vergnaud and Daniel Wichs, http://eprint.iacr.org/2013/338

A pseudo-random number generator (PRNG) is a deterministic algorithm that produces numbers whose distribution is indistinguishable from uniform. A formal security model for PRNGs with input was proposed in 2005 by Barak and Halevi (BH). This model involves an internal state that is refreshed with a (potentially biased) external random source, and a cryptographic function that outputs random numbers from the continually internal state. In this work we extend the BH model to also include a new security property capturing how it should accumulate the entropy of the input data into the internal state after state compromise. This property states that a good PRNG should be able to eventually recover from compromise even if the entropy is injected into the system at a very slow pace, and expresses the real-life expected behavior of existing PRNG designs.

Unfortunately, we show that neither the model nor the specific PRNG construction proposed by Barak and Halevi meet this new property, despite meeting a weaker robustness notion introduced by BH. From a practical side, we also give a precise assessment of the security of the two Linux PRNGs, /dev/random and /dev/urandom. In particular, we show several attacks proving that these PRNGs are not robust according to our definition, and do not accumulate entropy properly. These attacks are due to the vulnerabilities of the entropy estimator and the internal mixing function of the Linux PRNGs. These attacks against the Linux PRNG show that it does not satisfy the "robustness" notion of security, but it remains unclear if these attacks lead to actual exploitable vulnerabilities in practice. Finally, we propose a simple and very efficient PRNG construction that is provably robust in our new and stronger adversarial model. We therefore recommend to use this construction whenever a PRNG with input is used for cryptography.

_ （6/7記：職場のミーティング。珍しくよく喋ってしまった。）

_ （6/7記：先日の出張分の代休をとった。）

_ （6/8記：某C大ミーティング。他の人が論文誌に近々投稿しようとしている原稿の重箱の隅をつついたり、共同研究のネタについて証明の戦略を議論したりしていた。）

_ 週末。

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

_ 週末。CRYPTO 2013の論文リストが公開になっていた。

_ arXivの更新全チェックは諦めて、Electronic Colloquium on Computational Complexityの論文に目を通してみることにした。ひとまず1994年分を確認。

_ IACR ePrint 2013/347まで確認済み、ECCC 1996年分まで確認済み

_ 気になった論文：Limits of provable security for homomorphic encryption, Andrej Bogdanov and Chin Ho Lee, http://eprint.iacr.org/2013/344

We show that public-key bit encryption schemes which support weak (i.e., compact) homomorphic evaluation of any sufficiently "sensitive" collection of functions cannot be proved message indistinguishable beyond AM intersect coAM via general (adaptive) reductions, and beyond statistical zero-knowledge via reductions of constant query complexity. Examples of sensitive collections include parities, majorities, and the class consisting of all AND and OR functions.

Our techniques also give a method for converting a strong (i.e., distribution-preserving) homomorphic evaluator for essentially any boolean function (except the trivial ones, the NOT function, and the AND and OR functions) into a rerandomization algorithm: This is a procedure that converts a ciphertext into another ciphertext which is statistically close to being independent and identically distributed with the original one. Our transformation preserves negligible statistical error.

_ IACR ePrint 2013/368まで確認済み、ECCC 1996年分まで確認済み

_ （6/13記：某氏の歓迎会を行ったものの、歓迎される本人が急ぎの仕事で急遽欠席するという悲しい事案が発生した。）

_ IACR ePrint 2013/380まで確認済み、ECCC 1996年分まで確認済み

_ （6/15記：某C大ミーティングの最中にみんなでよってたかって某氏のスライドを改良していた。）

_ （6/16記：週末。蒸し暑くなってきた。）

_ 週末。

_ IACR ePrint 2013/380まで確認済み、ECCC 1997年分まで確認済み

_ IACR ePrint 2013/380まで確認済み、ECCC 1998年分まで確認済み

_ IACR ePrint 2013/389まで確認済み、ECCC 1999年分まで確認済み

_ IACR ePrint 2013/399まで確認済み、ECCC 1999年分まで確認済み

_ （6/21記：某所で打ち合わせ。分野違いの人たちと一緒に論文を書くのは難しいなぁと改めて実感した。）

_ IACR ePrint 2013/406まで確認済み、ECCC 1999年分まで確認済み

_ （6/25記：週末。外出して、楽しかったがへろへろになった。）

_ （6/25記：週末。

_ 都議会議員選挙のことが話題になっていた。そうした選挙報道に触れる度に思うのだが、確実でも何でもない（例えばこの事例とか）のに「当選確実」と称するあの用語はどうにかならないのだろうか。「当選見込」あたりがより適切な用語であろうと思う。報道関係者には出来る限り正確な報道を心がけていただきたいものである。）

_ （6/25記：久々に大学図書館へ調べ物をしに行ってきた。今考えている暗号方式のために解かないといけない数学の問題があって、一から考えるのは骨が折れるし、自然な問題設定だから誰か研究してないかなぁと期待していたところ、やはりかなり豊かな既存研究が存在しているらしい。というわけで、既存研究の山と格闘するという別種の骨折りが発生してしまった。）

_ 月初めの休日出勤の代休が残っていたので自宅で作業している。

_ IACR ePrint 2013/418まで確認済み、ECCC 2000年分まで確認済み

_ 今日はPKC 2013についてがっつり勉強してきた。世話人の方々と発表者の方々（特に、無茶ぶりに負けず立派に発表されていた院生の皆さん）にこの場を借りて御礼申し上げます。

_ ところで、今日の勉強会（他にも最近の暗号関係の勉強会など）に某エヌ氏が参加されていたり、某大先生が暗号のことを生まれた時から理解勉強されているっぽかったり、数学ガチ勢と暗号分野の距離が少しずつ縮まっているように感じられて嬉しい限りである。「関東つどい」での発表も期待以上に楽しんでもらえたみたいだし、もっと両者の距離が縮まって混沌とした状況になるといいなぁと思う。

_ 最近考えている研究ネタの紹介をしたらえらく評判がよかった。うまく孵化してくれるといいなあ。

_ （7/3記：週末。以前某氏から譲っていただいた「ちはやふる」の単行本を読み耽るなどしていた。ああいう話を読んで「自分もやってみたい」とつい思ってしまうのは良いことなのかどうか。）

_ （7/3記：週末。書きたいことがあるのだが事情により後で追記する（かも）。）