IACR News item: 28 August 2014
Dhananjay S. Phatak, Qiang Tang, Alan T. Sherman, Warren D. Smith, Peter Ryan, Kostas Kalpakis
ePrint ReportWe 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.
Additional news items may be found on the IACR news page.