MarriageTheoremのこと

_ 調べ物のため母校の図書館に行ったところ、「パズルゲームで楽しむ写像類群入門」の著者サイン入り本が本棚に飾ってあったのを発見してニヤリとした。

_ IACR ePrint 2014/041まで確認済み、ECCC 2003年分まで確認済み

_ 気になった論文1：General Impossibility of Group Homomorphic Encryption in the Quantum World, Frederik Armknecht and Tommaso Gagliardoni and Stefan Katzenbeisser and Andreas Peter, http://eprint.iacr.org/2014/029

Group homomorphic encryption represents one of the most important building blocks in modern cryptography. It forms the basis of widely-used, more sophisticated primitives, such as CCA2-secure encryption or secure multiparty computation. Unfortunately, recent advances in quantum computation show that many of the existing schemes completely break down once quantum computers reach maturity (mainly due to Shor’s algorithm). This leads to the challenge of constructing quantum-resistant group homomorphic cryptosystems.

In this work, we prove the general impossibility of (abelian) group homomorphic encryption in the presence of quantum adversaries, when assuming the IND-CPA security notion as the minimal security requirement. To this end, we prove a new result on the probability of sampling generating sets of finite (sub-)groups if sampling is done with respect to an arbitrary, unknown distribution. Finally, we provide a sufficient condition on homomorphic encryption schemes for our quantum attack to work and discuss its satisfiability in non-group homomorphic cases. The impact of our results on recent fully homomorphic encryption schemes poses itself as an open question.

_ 気になった論文2：Practical polynomial time solutions of several major problems in noncommutative-algebraic cryptography, Boaz Tsaban, http://eprint.iacr.org/2014/041

We provide new provable polynomial time solutions of a number of problems in noncommutative-algebraic cryptography. In contrast to the linear centralizer method of \cite{LinCent}, the new method is very simple: In order to solve linear equations on matrices restricted to matrix groups, solve them over the generated algebras. We name this approach the \emph{algebraic span method}.

The resulting algorithms are have substantially better performance than those of \cite{LinCent}. These algorithms constitute cryptanalyses of the motivating protocols that cannot be foiled by changing the distributions used in the protocols, and are practical for most affordable parameter settings.