Reference : DoubleMod and SingleMod: Simple Randomized Secret-Key Encryption with Bounded Homomor...
Scientific journals : Article
Engineering, computing & technology : Computer science
DoubleMod and SingleMod: Simple Randomized Secret-Key Encryption with Bounded Homomorphicity
Ryan, Peter mailto [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 []
IACR Cryptology ePrint Archive
[en] Approximate GCD problem (AGCD) ; cryptanalysis ; cryptography ; cryptology ; DoubleMod ; homomorphic encryption ; lattice algorithms ; non-Euclidean algebraic number fields ; randomized encryption ; SingleMod
[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.

File(s) associated to this reference

Fulltext file(s):

Open access
DoubleMod and SingleMod.pdfPublisher postprint187.92 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.