MarriageTheoremのこと

_ プレプリント確認状況：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.

面白そうだからちゃんと読んでみた方がいいかもしれない。