*00:17*[Pub][ePrint] DoubleMod and SingleMod: Simple Randomized Secret-Key Encryption with Bounded Homomorphicity, by Dhananjay S. Phatak, Qiang Tang, Alan T. Sherman, Warren D. Smith, Peter Ryan, Kostas Kalpakis

An encryption relation $f \\subseteq {\\mathbb Z} \\times {\\mathbb Z}$ with decryption function $f^{-1}$ is {\\it ``group-homomorphic\'\'} if, for any suitable plaintexts $x_1$ and $x_2$, $\\, x_1+x_2 = f^{-1} ( f(x_1) + f(x_2) )$. It is {\\it ``ring-homomorphic\'\'} if furthermore $x_1 x_2 = f^{-1} ( f(x_1) f(x_2) )$; it is {\\it ``field-homomorphic\'\'} if furthermore $1/x_1 = f^{-1} ( f(1/x_1) )$. Such relations would support oblivious processing of encrypted data.

We propose a simple randomized encryption relation~$f$ over the integers, called\\linebreak {\\it \\mbox{DoubleMod}}, which is ``bounded ring-homomorphic\'\' or what some call \"somewhat homomorphic.\" Here, ``bounded\'\' means that the number of additions and multiplications that can be performed, while not allowing the encrypted values to go out of range, is limited~(any pre-specified bound on the operation-count can be accommodated). Let $R$ be any large integer. For any plaintext $x \\in {\\mathbb Z}_R$, DoubleMod encrypts $x$ as $f(x) = x + au + bv$, where $a$ and $b$ are randomly chosen integers in some appropriate interval, while $(u,v)$ is the secret key. Here $u>R^2$ is a large prime and the smallest prime factor of $v$ exceeds $u$. With knowledge of the key, but not of $a$ and $b$, the receiver decrypts the ciphertext by computing $f^{-1}(y) =(y \\bmod v) \\bmod u$.

DoubleMod generalizes an independent idea of van Dijk {\\it et al.} 2010. We present and refine a new CCA1 chosen-ciphertext attack that finds the secret key of both systems (ours and van Dijk {\\it et al.}\'s) in linear time in the bit length of the security parameter. Under a known-plaintext attack, breaking DoubleMod is at most as hard as solving the {\\it Approximate GCD (AGCD)} problem. The complexity of AGCD is not known.

We also introduce the \\mbox{{\\it SingleMod}} {field}-homomorphic cryptosystems. The simplest\\linebreak \\mbox{SingleMod} system based on the integers can be broken trivially. We had hoped, that if SingleMod is implemented inside non-Euclidean quadratic or higher-order fields with large discriminants, where GCD computations appear difficult, it may be feasible to achieve a desired level of security. We show, however, that a variation of our chosen-ciphertext attack works against SingleMod even in non-Euclidean fields.