Approximate GCD problem (AGCD); cryptanalysis; cryptography; cryptology; DoubleMod; homomorphic encryption; lattice algorithms; non-Euclidean algebraic number fields; randomized encryption; SingleMod
Abstract :
[en] An encryption relation f Z Z with decryption function f 1 is “group-homomorphic”
if, for any suitable plaintexts x1 and x2, x1+x2 = f 1( f (x1)+f (x2)). It is “ring-homomorphic”
if furthermore x1x2 = f 1( f (x1) f (x2)); it is “field-homomorphic” if furthermore 1=x1 =
f 1( f (1=x1)). Such relations would support oblivious processing of encrypted data.
We propose a simple randomized encryption relation f over the integers, called
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 2 ZR, 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 > R2 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 mod v) mod u.
DoubleMod generalizes an independent idea of van Dijk 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 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 Approximate
GCD (AGCD) problem. The complexity of AGCD is not known.
We also introduce the SingleMod field-homomorphic cryptosystems. The simplest
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 di cult, 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.
Disciplines :
Computer science
Author, co-author :
Ryan, Peter ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Phatak, Dhananjay S.
Tang, Qiang
Smith, Warren D.
Sherman, Alan T.
Kalpakis, Kostas
External co-authors :
yes
Language :
English
Title :
DoubleMod and SingleMod: Simple Randomized Secret-Key Encryption with Bounded Homomorphicity