Derandomization Security of Homomorphic Encryption
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.
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)-24Full text of the paper in pdf (in Russian) Back to the contents of the volume