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.
ePrint: https://eprint.iacr.org/2014/670
See all topics related to this paper.
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.
For more information, see the rules for Resource Topics .