Paper 2014/670
DoubleMod and SingleMod: Simple Randomized SecretKey Encryption with Bounded Homomorphicity
Dhananjay S. Phatak, Qiang Tang, Alan T. Sherman, Warren D. Smith, Peter Ryan, and Kostas Kalpakis
Abstract
An encryption relation $f \subseteq {\mathbb Z} \times {\mathbb Z}$ with decryption function $f^{1}$ is {\it ``grouphomomorphic''} 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 ``ringhomomorphic''} if furthermore $x_1 x_2 = f^{1} ( f(x_1) f(x_2) )$; it is {\it ``fieldhomomorphic''} 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 ringhomomorphic'' 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 prespecified bound on the operationcount 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 chosenciphertext 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 knownplaintext 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 nonEuclidean quadratic or higherorder 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 chosenciphertext attack works against SingleMod even in nonEuclidean fields.
Note: Contributions of this paper include: 1.A description and analysis of the Doublemod somewhat ringhomomorphic singlekey block encryption system, which generalizes an idea of Van Dijk et al. (Eurocrypt 2010). The simple and intuitive nature of Doublemod motivates its examination. 2.New attacks on Doublemod, which are of independent interest. 3.A preliminary discussion of an unsuccessful attempt to find a cryptographic system in nonEuclidean algebraic number fields, where computing GCD is hard. Specifically, we base our attempt on a system we call Singlemod. The fieldhomomorphic Singlemod encryption system is insecure in the integers because it can be easily broken with a GCD computation. Nevertheless, this quest is intriguing and potentially significant.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 Approximate GCD problem (AGCD)cryptanalysiscryptographycryptologyDoubleModhomomorphic encryptionlattice algorithmsnonEuclidean algebraic number fieldsquantum algorithmrandomized encryptionSingleMod
 Contact author(s)
 sherman @ umbc edu
 History
 20140828: received
 Short URL
 https://ia.cr/2014/670
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/670, author = {Dhananjay S. Phatak and Qiang Tang and Alan T. Sherman and Warren D. Smith and Peter Ryan and Kostas Kalpakis}, title = {DoubleMod and SingleMod: Simple Randomized SecretKey Encryption with Bounded Homomorphicity}, howpublished = {Cryptology ePrint Archive, Paper 2014/670}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/670}}, url = {https://eprint.iacr.org/2014/670} }