MarriageTheoremのこと

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

_ 気になった論文：Cryptanalysis of a New Additive Homomorphic Encryption based on the co-ACD Problem, Moon Sung Lee, http://eprint.iacr.org/2014/1024

In CCS'14, Cheon et al. proposed a new additive homomorphic encryption scheme which is claimed to be the most efficient among the additive homomorphic encryption schemes. The security is proved based on the hardness of a new problem, the (decisional) co-approximate common divisor problem. In this paper, we cryptanalyze the scheme and investigate the hardness of an aforementioned problem. Our first result shows that Cheon et al.'s scheme is insecure for the range of parameters considered in the original paper~\cite{CLSCCS14}. Experiments show that the message can be recovered in seconds for the proposed parameters. We also analyze the condition of the parameters to thwart the proposed attack. As a second result, we show that the co-approximate common divisor problem is easy for the similar range of parameters, in condition that the modulus is known and is a product of two primes. In our estimate, to thwart the proposed attack, the parameters should be enlarged many times. Apart from the scheme, the co-approximate common divisor problem itself is interestingly related to the well-known hard problem, an approximate common divisor problem. And further investigation on this relationship would be desirable.

_ 気になった論文2：On the Cryptographic Hardness of Finding a Nash Equilibrium, Nir Bitansky and Omer Paneth and Alon Rosen, http://eprint.iacr.org/2014/1029

We prove that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and injective one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in the complexity class PPAD, for which finding Nash equilibrium is known to be complete.

Previous proposals for basing PPAD-hardness on program obfuscation considered a strong “virtual black-box” notion that is subject to severe limitations and is unlikely to be realizable for the programs in question. In contrast, for indistinguishability obfuscation no such limitations are known, and recently, several candidate constructions of indistinguishability obfuscation were suggested based on different hardness assumptions on multilinear maps.

Our result provides further evidence of the intractability of finding a Nash equilibrium, one that is extrinsic to the evidence presented so far.