Article (Scientific journals)
DoubleMod and SingleMod: Simple Randomized Secret-Key Encryption with Bounded Homomorphicity
Ryan, Peter; Phatak, Dhananjay S.; Tang, Qiang et al.
2014In IACR Cryptology ePrint Archive
Peer reviewed
 

Files


Full Text
DoubleMod and SingleMod.pdf
Publisher postprint (192.43 kB)
Download

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
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
Publication date :
2014
Journal title :
IACR Cryptology ePrint Archive
Peer reviewed :
Peer reviewed
Available on ORBilu :
since 10 March 2016

Statistics


Number of views
151 (7 by Unilu)
Number of downloads
103 (4 by Unilu)

Bibliography


Similar publications



Contact ORBilu