# [Resource Topic] 2014/670: DoubleMod and SingleMod: Simple Randomized Secret-Key Encryption with Bounded Homomorphicity

Welcome to the resource topic for 2014/670

Title:
DoubleMod and SingleMod: Simple Randomized Secret-Key Encryption with Bounded Homomorphicity

Authors: Dhananjay S. Phatak, Qiang Tang, Alan T. Sherman, Warren D. Smith, Peter Ryan, Kostas Kalpakis

Abstract:

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.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.