Homomorphic encryption schemes can be utilized to produce cryptographic tools, for example, zero-knowledge proofs, signatures, MACs and multiparty computation implementations.

## ZERO-KNOWLEDGE PROOFS

Gentry shows in his paper [7] that homomorphic encryption can be used in the development of non-interactive zero-knowledge (NIZK) proofs of small size. A user needs to prove knowledge of a satisfying assignment of bits π1, . . . , πt for a boolean circuit *C*. The NIZK proof consists of generating a public key, encrypting the πi’s and homomorphically evaluating *C* on these encryptions. A standard NIZK proof is connected to prove that every ciphertext encrypts either 0 or 1 and that the output of the evaluation encrypts 1.

## DELEGATION OF COMPUTATION

Outsourcing computation is the second huge pillar in cloud computing, other than outsourcing information. A user might need to delegate the computation of a function *f *to the server. However, the server may be malicious or just prone to malfunctions, meaning the user may not trust the result of the computation. The user wants to have a proof that the computation was done correctly and verifying this proof should also be significantly more efficient than the user doing the computation.

One example for the delegation of computation is *message authenticators*. A user who has outsourced computation on a data set might want to check that the return value is really the correct result. The tag should be independent of the size of the original data set, and only verifiable for the holder of the private key.

## SIGNATURES

The leveled fully homomorphic signature scheme can evaluate arbitrary circuits with maximal depth *d* over signed data and homomorphically produce a short signature which can be verified by anybody using the public verification key. The user transfers the signed data *x*, at that point the server runs some function *g* over the data which yields *y = g(x)*. Furthermore, the server publishes the signature *σ**g,y* to verify the computation.

This work additionally presents the notion of homomorphic trapdoor functions (HTDF), one of the building blocks for the signature construction. HTDF themselves are based on the small integer solution (SIS) problem.

## MULTIPARTY COMPUTATION

Multiparty computation requires interaction between participants. The players use the somewhat homomorphic scheme to develop offline multiplication in a preprocessing phase, yet come back to the significantly more efficient methods of multiparty computation in the computation phase.

**SYSTEMATIZATION**

All modern information systems are related to the use of databases and database management systems (DBMS). One of the current problems associated with the use of databases is the challenge of securing and safely storing and proper handling of confidential data in the remote database.

The adaptation of fully homomorphic cryptosystem will keep the ability to perform typical database operations on encrypted data without decrypting the data in an untrusted environment. However, such a cryptosystem must satisfy certain requirements for functional characteristics and computational complexity, which is important.

A cryptosystem is a fully homomorphic encryption scheme, if it is additive and multiplicative homomorphic cryptosystem. Systematization of fully homomorphic encryption schemes is shown in Figure below.

## NEED FOR SYSTEMATIZATION

Treatment of FHE can seem very confusing. Sometimes, two definitions seem to say the same thing – for example, at first glance, being able to evaluate an arbitrary circuit and being able to evaluate arbitrarily many circuits consecutively seems to be the same thing.

To help understand the distinction, consider the cloud computing example: FHE is normally sold as the solution. However, if only one circuit of arbitrary size can be evaluated, then intermediate results for further computations cannot be used later; everything has to be computed from scratch through the original ciphertexts. This satisfies the usual definition of FHE (i.e., A *fully homomorphic encryption *scheme is a *C*–evaluation scheme (Gen, Enc, Eval, Dec) that is compact, correct and where *C* is the set of all circuits.), but is unintuitive and is hardly an optimal solution. What is required in this situation is the ability to assess arbitrarily numerous circuits sequentially.

This highlights another problem in this field: in some cases, definitions do not express what one would intuitively assume. In other cases, one intuition has different definitions in different places. This, for instance, is the situation for an attribute called *compactness*, which intuitively says that the ciphertext size ought not to be growing through homomorphic operations.

Sometimes, attributes are not properly defined at all, and sometimes implications are used that have not been mentioned.

**HISTORY OF FHE**

In 2009, the first fully homomorphic encryption scheme was proposed by Craig Gentry, that allows to calculate any number of addition and multiplication and hence compute arbitrary functions of encrypted data. Gentry’s scheme based on somewhat homomorphic encryption scheme has two disadvantages: the length and noise of ciphertext are increasing when operations are performing on ciphertexts, so it becomes impossible to decrypt result correctly after computing some operations. To solve these problems Gentry suggested the use of bootstrapping which allowed re-encryption and get compact ciphertext.

Gentry’s scheme was impractical because the re-encryption required a large number of operations. That is why new advanced fully homomorphic encryption schemes were developed. First, optimized Gentry’s schemes were proposed, then fully homomorphic encryption schemes using new somewhat homomorphic encryption schemes based on other mathematical objects and methods of noise reduction were developed. Later fully homomorphic encryption schemes without the application of Gentry’s scheme construct principles were developed.