_ プレプリント確認状況：arXiv:math 2012年2月23日分まで、arXiv:quant-ph 2012年5月31日分まで、IACR ePrint：2012/242まで
_ 気になった論文：When Homomorphism Becomes a Liability
（Zvika Brakerski, IACR ePrint 2012/225）
We show that an encryption scheme cannot have a simple decryption circuit and be homomorphic at the same time. Specifically, if a scheme can homomorphically evaluate the majority function, then its decryption circuit cannot be a linear function of the secret key (or even a succinct polynomial), even if decryption error is allowed.
An immediate corollary is that known schemes that are based on the hardness of decoding in the presence of noise with low hamming weight cannot be fully homomorphic. This applies to known schemes such as LPN-based symmetric or public key encryption.
An additional corollary is that the recent candidate fully homomorphic encryption, suggested by Bogdanov and Lee (ePrint '11, henceforth BL), is insecure. In fact, we show two attacks on the BL scheme: One by applying the aforementioned general statement, and another by directly attacking one of the components of the scheme.
面白そうだからちゃんと読んでみた方がいいかもしれない。
_ 某キューネン本の演習問題、第２章の残り問題数が（先方でチェック中の物を除いて）あと１桁にまで辿り着いた。「その章の演習問題を全て片付けてから次へ進む」という制限プレイのため先の章を読めずにいたが、第３章以降を読めるようになる日も遠くないのかもしれない。
_ 某所に投稿していた論文の査読レポートが届いた。投稿から約２年（体感ではもっと経っているように思っていたけれどもそんなことはなかったらしい）。正確には査読レポートが投稿システム上に届いたというお知らせが届いただけで、まだレポートの中身は読んでいないのだが、とりあえず一発でrejectされなかったのは幸いである。
_ プレプリント確認状況：arXiv:math 2012年2月23日分まで、arXiv:quant-ph 2012年5月31日分まで、IACR ePrint：2012/250まで
_ 気になった論文その１："Cryptography from tensor problems"（Leonard J. Schulman, IACR ePrint 2012/244）
We describe a new proposal for a trap-door one-way function. The new proposal belongs to the ``multivariate quadratic'' family but the trap-door is different from existing methods, and is simpler.
Known quantum algorithms do not appear to help an adversary attack this trap-door. (Beyond the asymptotic square-root-speedup which applies to all oracle search problems.)
_ 気になった論文その２："A Secret Sharing Scheme Based on Group Presentations and the Word Problem"（Maggie Habeeb and Delaram Kahrobaei and Vladimir Shpilrain, IACR ePrint 2012/246）
A $(t,n)$-threshold secret sharing scheme is a method to distribute a secret among $n$ participants in such a way that any $t$ participants can recover the secret, but no $t-1$ participants can. In this paper, we propose two secret sharing schemes using non-abelian groups. One scheme is the special case where all the participants must get together to recover the secret. The other one is a $(t,n)$-threshold scheme that is a combination of Shamir's scheme and the group-theoretic scheme proposed in this paper.
_ 気になった論文その３："Binary and q-ary Tardos codes, revisited"（Boris Skoric and Jan-Jaap Oosterwijk, IACR ePrint 2012/249）
The Tardos code is a much studied collusion-resistant fingerprinting code, with the special property that it has asymptotically optimal length $m\propto c_0^2$, where $c_0$ is the number of colluders.
In this paper we simplify the security proofs for this code, making use of the Bernstein inequality and Bennett inequality instead of the typically used Markov inequality. This simplified proof technique also slightly improves the tightness of the bound on the false negative error probability. We present new results on code length optimization, for both small and asymptotically large coalition sizes.
_ （5/10記：連休最終日。職場の近くに竜巻が襲来していたらしく、１日ずれていたら自分も大変だったかもなぁ、と思った。被害に遭われた方々にお見舞い申し上げます。）
_ （5/10記：故有ってランダムオラクルモデルでの暗号方式の安全性証明というものを初めて真面目に読んだのだけど、やっぱり（使い勝手が良いのはわかるのだが）不思議なモデルだなぁと思った。）
_ （5/10記：研究で現れたとある量の計算過程をTeXのメモにまとめているのだが、途中の段階で既に6ページぐらいの分量になっている件。首尾よく結果を得て論文にまとめることになったときにどうやってページ数を常識的な範囲に圧縮しようか…と今から気が早い心配をしている。）
_ プレプリント確認状況：arXiv:math 2012年2月23日分まで、arXiv:quant-ph 2012年5月31日分まで、IACR ePrint：2012/261まで
_ 気になった論文その１："The Linux Psedorandom Number Generator Revisited"（Patrick Lacharme and Andrea Röck and Vincent Strubel and Marion Videau, IACR ePrint 2012/251）
The Linux pseudorandom number generator (PRNG) is a PRNG with entropy inputs which is widely used in many security related applications and protocols. This PRNG is written as an open source code which is subject to regular changes. It was last analyzed in the work of Gutterman et al. in 2006 [GPR06] but since then no new analysis has been made available, while in the meantime several changes have been applied to the code, among others, to counter the attacks presented [GPR06]. Our work describes the Linux PRNG of kernel versions 2.6.30.7 and upwards. We detail the PRNG architecture in the Linux system and provide its first accurate mathematical description and a precise analysis of the building blocks, including entropy estimation and extraction. Subsequently, we give a security analysis including the feasibility of cryptographic attacks and an empirical test of the entropy estimator.. Finally, we underline some important changes to the previous versions and their consequences.
_ 気になった論文その２："Fair Private Set Intersection with a Semi-trusted Arbiter"（Changyu Dong and Liqun Chen and Jan Camenisch and Giovanni Russello, IACR ePrint 2012/252）
A private set intersection (PSI) protocol allows two parties to compute the intersection of their input sets privately. Most of the previous PSI protocols only output the result to one party and the other party gets nothing from running the protocols. However, a mutual PSI protocol in which both parties can get the output is highly desirable in many applications. A major obstacle in designing a mutual PSI protocol is how to ensure fairness. In this paper we present the first fair mutual PSI protocol which is efficient and secure. Fairness of the protocol is obtained in an optimistic fashion, i.e. by using an offline third party arbiter. In contrast to many optimistic protocols which require a fully trusted arbiter, in our protocol the arbiter is only required to be semi-trusted, in the sense that we consider it to be a potential threat to both parties' privacy but believe it will follow the protocol and not collude with any of the two parties. The arbiter can resolve disputes blindly without knowing any private information belongs to the two parties. This feature is appealing for a PSI protocol in which privacy may be of ultimate importance.
_ 旅行二日目（最終日）。
_ プレプリント確認状況：arXiv:math 2012年2月23日分まで、arXiv:quant-ph 2012年5月31日分まで、IACR ePrint：2012/262まで
_ プレプリント確認状況：arXiv:math 2012年2月23日分まで、arXiv:quant-ph 2012年5月31日分まで、IACR ePrint：2012/264まで
_ 気になった論文："One-way Functions from Chebyshev Polynomials"（Kai-Yuen Cheong, IACR ePrint 2012/263）
In the past twenty years, the study of the conjunction of chaos and cryptography has attracted much interest but also met with many problems. Today the security of chaos-based encryptions is usually not considered comparable to those based on number theoretic functions. In this paper, instead of making an encryption system, we focus on the more fundamental notion of one-way function, which is a well-defined function that is easy to evaluate but hard to invert. We see that it is more natural to compare chaotic systems with one-way functions, and such a study could possibly give new insights for chaos-based cryptosystems. We propose a function based on Chebyshev polynomials, and we argue it is likely a one-way function.
_ プレプリント確認状況：arXiv:math 2012年2月23日分まで、arXiv:quant-ph 2012年5月31日分まで、IACR ePrint：2012/266まで
_ （5/24記：ここ数日、仕事の関係でとある量の上からの評価式を与える必要があって、とりあえず式は立ったものの実用的には悪すぎる評価であるため改善しようと奮闘していたのだが、今のところ良い方法が思いつかずにどうしたものかと思っている。）
_ プレプリント確認状況：arXiv:math 2012年2月23日分まで、arXiv:quant-ph 2012年5月31日分まで、IACR ePrint：2012/269まで
_ 気になった論文："On a CCA2-secure variant of McEliece in the standard model"（Edoardo Persichetti, IACR ePrint 2012/268）
We consider public-key encryption schemes based on error-correcting codes that are IND-CCA2 secure in the standard model. We analyze a system due to Dowsley, Muller-Quade and Nascimento. We then show how to instantiate the Rosen-Segev framework with the McEliece scheme.
_ 8月28日（火）から8月31日（金）まで、島根県松江市で「組合せ論サマースクール2012」という催しをやります。「サマースクール」と言いつつ入門講義のようなものは特になくて基本的には普通の合宿型研究集会なのですが、参加者が抱えている（もしくはその分野でお薦めの）未解決問題を持ち寄って議論の肴にする「未解決問題セッション」は他では中々見られない珍しい企画だと思いますし、宍道湖は本当に綺麗な湖ですので、是非多くの方に参加していただきたいと願っています。以上、宣伝でした。
_ プレプリント確認状況：arXiv:math 2012年2月23日分まで、arXiv:quant-ph 2012年5月31日分まで、IACR ePrint：2012/292まで
最近のツッコミ↓