Proceedings of ISP RAS

Derandomization Security of Homomorphic Encryption

A. Trepacheva (SFU, Rostov-on-Don)


The  paper  considers  the  problems  of  developing  and  analysis  of  cloud  database  systems. We determine the minimal requirements for encryption to be usable in practical applications. A new notion – a non-derandomizable encryption – allows to do this and we explain the practical  value  of  this  notion  as  well  as  links  between  it  and  classical  notions  of  cryptosystem’s  security, practical security of whole cloud computing system.
The derandomizable encryption essentially is equivalent to a simple substitution cipher. In other words, encryption is derandomizable if an effective algorithm exists translating it into a simple substitution cipher.
There are some features of derandomizable encryption allowing to check their properties in a simple way . For this purpose, this paper proposes an alternative definition of derandomizable encryption in terms of systems of equations, drawn up by known plaintext cryptanalysis.
Then the paper proposes definitions of generalized derandomization and full derandomization.
Briefly, the generalized derandomizable encryption allows to reduce efficiently the number of variables in system of equations composed for known plaintext attack; the fully derandomizable encryption allows to compose uniquely solvable system of equations by known plaintext attack effectively.
We show the examples of simple   algebraically   homomorphic   cryptosystems   –both   derandomizable   and   not   non-derandomizable. The paper finally concludes about usability of considered cryptosystems for practical cloud systems.


information security, cloud computing, homomorphic encryption, secure computations, deran-domization


Proceedings of the Institute for System Programming, vol. 27, issue 6, 2015, pp. 381-394.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2015-27(6)-24

Full text of the paper in pdf (in Russian) Back to the contents of the volume