MarriageTheoremのこと

_ 今日は科研費応募書類の内部提出〆切日、かつ職場の一般公開イベント初日である。「片方だけならスゲーよくわかる、だが両方同じ日に設定するってのはどういうことだこのド（中略）が」と私の頭の中のギアッチョ氏の怒りをなだめつつ職場へ向かう。

_ 折角arXivの新着チェックが最新版に追い付いていたのに、ここ最近の忙しさでまた引き離されてしまった。再度追い付かなければ。（メモ：arXiv:math 10月5日分まで、IACR ePrint 2012/562まで確認済み）

_ 今日は私の頭の中のギアッチョ氏が大活躍する一日だった。明日からはもっと静かに暮らしたいものである。

_ arXiv:math 10月5日分まで、IACR ePrint 2012/587まで確認済み

_ 気になった論文１：On the Power of Random Oracles, Iftach Haitner and Eran Omri and Hila Zarosim, http://eprint.iacr.org/2012/573

Abstract: In the random oracle model, the parties are given oracle access to a random member of a (typically huge) function family, and are assumed to have unbounded computational power (though they can only make a bounded number of oracle queries). This model provides powerful properties that allow proving the security of many protocols, even such that cannot be proved secure in the standard model (under any hardness assumption). The random oracle model is also used to show that a given cryptographic primitive cannot be used in a black-box way to construct another primitive; in their seminal work, Impagliazzo and Rudich [STOC ’89] showed that in the random function model – when the function family is the set of all functions – it is impossible to construct (secure) key-agreement protocols, yielding that key-agreement cannot be black-box reduced to one-way functions. Their work has a long line of followup works (Simon [EC ’98], Gertner et al. [STOC ’00] and Gennaro et al. [SICOMP ’05], to name a few), showing that given oracle access to a certain type of function family (e.g., the family that “implements” public-key encryption) is not sufficient for building a given cryptographic primitive (e.g., oblivious transfer). Yet, in the more general sense, the following fundamental question remained open:

What is the exact power of the random oracle model, and more specifically, of the random function model?

We make progress towards answering the above question, showing that any (no private input) semi-honest two-party functionality that can be securely implemented in the random function model, can be securely implemented information theoretically (where parties are assumed to be all powerful, and no oracle is given). We further generalize the above result to function families that provide some natural combinatorial property.

To exhibit the power of our result, we use the recent information theoretic impossibility result of McGregor et al. [FOCS ’10], to show the existence of functionalities (e.g., inner product) that cannot be computed both accurately and in a differentially private manner in the random function model; yielding that protocols for computing these functionalities cannot be black-box reduced to the existence of one-way functions.

_ 気になった論文２：Quantum algorithm for the discrete logarithm problem for matrices over finite group rings, A. D. Myasnikov and A. Ushakov, http://eprint.iacr.org/2012/574

We propose a polynomial time quantum algorithm for solving the discrete logarithm problem in matrices over finite group rings. The hardness of this problem was recently employed in the design of a key-exchange protocol proposed by D. Kahrobaei, C. Koupparis, and V. Shpilrain. Our result implies that the Kahrobaei et al. protocol does not belong to the realm of post-quantum cryptography.