Cryptanalysis of Brenner et al.'s Somewhat Homomorphic Encryption Scheme

Paulet, R. and Yi, X.

    Recently, Brenner et al. proposed a symmetric some-what homomorphic encryption scheme and applied it to solve some practical problems, such as the Millionaires' problem, which only need to evaluate circuits of limited depth. It is claimed that the security of their scheme is built on the hardness of integer factorization. In this paper, we use the Euclidean Greatest Common Divisor (GCD) algorithm to perform cryptanalysis on Brenner et al.'s scheme. We present several algorithms to find the secret key of their scheme. Our experiments have shown that our cryptanalysis is feasible and efficient.
Cite as: Paulet, R. and Yi, X. (2013). Cryptanalysis of Brenner et al.'s Somewhat Homomorphic Encryption Scheme. In Proc. Information Security 2013 (AISC 2013) Adelaide, Australia. CRPIT, 138. Thomborson, C. and Parampalli. U. Eds., ACS. 25-30
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS