MarriageTheoremのこと

_ IACR ePrint 2015/069まで確認済み、ECCC 2003年分まで確認済み

_ 気になった論文1：Cryptanalysis of a (Somewhat) Additively Homomorphic Encryption Scheme Used in PIR, Tancrède Lepoint and Mehdi Tibouchi, http://eprint.iacr.org/2015/012

Private Information Retrieval (PIR) protects users' privacy in outsourced storage applications and can be achieved using additively homomorphic encryption schemes. Several PIR schemes with a “real world” level of practicality, both in terms of computational and communication complexity, have been recently studied and implemented. One of the possible building block is a conceptually simple and computationally efficient protocol proposed by Trostle and Parrish at ISC 2010, that relies on an underlying secret-key (somewhat) additively homomorphic encryption scheme, and has been reused in numerous subsequent works in the PIR community (PETS 2012, FC 2013, NDSS 2014, etc.).

In this paper, we show that this encryption scheme is not one-way: we present an attack that decrypts arbitrary ciphertext without the secret key, and is quite efficient: it amounts to applying the LLL algorithm twice on small matrices. Used against existing practical instantiations of PIR protocols, it allows the server to recover the users' access pattern in a matter of seconds.

_ 気になった論文2：A LINEAR ATTACK ON A KEY EXCHANGE PROTOCOL USING EXTENSIONS OF MATRIX SEMIGROUPS, JINTAI DING, ALEXEI MIASNIKOV, AND ALEXANDER USHAKOV, http://eprint.iacr.org/2015/018

In this paper we analyze the Kahrobaei-Lam-Shpilrain (KLS) key exchange protocols that use extensions by endomorpisms of matrices over a Galois field proposed in \cite{Kahrobaei-Lam-Shpilrain:2014}. We show that both protocols are vulnerable to a simple linear algebra attack.

_ 気になった論文3：Group Signature with Deniability: How to Disavow a Signature, Ai Ishida, Keita Emura, Goichiro Hanaoka, Yusuke Sakai, and Keisuke Tanaka, http://eprint.iacr.org/2015/043

Group signature is a class of digital signatures with enhanced privacy. By using this type of signature, a user can prove membership of a specific group without revealing his identity, but in the case of a dispute, for a given signature, an authority can expose the identity of its signer. However, in some situations wherein it is necessary to only know whether a specified user is the signer of the given signature, the naive use of a group signature may be problematic since if the specified user is NOT the actual signer, then the identity of the actual signer will be exposed. In this paper, inspired by this problem, we propose the notion of a deniable group signature, where with respect to a signature and a user, the opener can issue a proof that the opening result of the signature is NOT the specified user without revealing the actual signer. We also describe a fairly practical construction by extending the Groth group signature scheme (ASIACRYPT 2007). In particular, a denial proof in our scheme consists of 96 group elements, which is about twice the size of a signature in the Groth scheme. The proposed scheme is provably secure under the same assumptions as those of the Groth scheme.

（ステマ）

_ 気になった論文4：Linearly Homomorphic Encryption from DDH, Guilhem Castagnos and Fabien Laguillaumie, http://eprint.iacr.org/2015/047

We design a linearly homomorphic encryption scheme whose security relies on the hardness of the decisional Diffie-Hellman problem. Our approach requires some special features of the underlying group. In particular, its order is unknown and it contains a subgroup in which the discrete logarithm problem is tractable. Therefore, our instantiation holds in the class group of a non maximal order of an imaginary quadratic field. Its algebraic structure makes it possible to obtain such a linearly homomorphic scheme whose message space is the whole set of integers modulo a prime p and which supports an unbounded number of additions modulo p from the ciphertexts. A notable difference with previous works is that, for the first time, the security does not depend on the hardness of the factorization of integers. As a consequence, under some conditions, the prime p can be scaled to fit the application needs.

CT-RSAの（なぜかウェブページからリンクされていない）accepted papers listで見かけて気になっていた論文、プレプリント版がアップされたのか。後で読もう。