<abstract xmlns="http://www.w3.org/1999/xhtml"><p>Cryptology is defined as the science of making communication incomprehensible to third parties who have no right to read and understand the data or messages. Cryptology consists of two parts, namely, cryptography and cryptanalysis. Cryptography analyzes methods of encrypting messages, and cryptanalysis analyzes methods of decrypting encrypted messages. Encryption is the process of translating plaintext data into something that appears to be random and meaningless. Decryption is the process of converting this random text into plaintext. Cloud computing is the legal transfer of computing services over the Internet. Cloud services let individuals and businesses to use software and hardware resources at remote locations. Widespread use of cloud computing raises the question of whether it is possible to delegate the processing of data without giving access to it. However, homomorphic encryption allows performing computations on encrypted data without decryption. In homomorphic encryption, only the encrypted version of the data is given to the untrusted computer to process. The computer will perform the computation on this encrypted data, without knowing anything on its real value. Finally, it will send back the result, and whoever has the proper deciphering key can decrypt the cryptogram correctly. The decrypted result will be equal to the intended computed value. In this paper, homomorphic encryption and their types are reviewed. Also, a simulation of somewhat homomorphic encryption is examined.</p></abstract>

Cryptology is defined as the science of making communication incomprehensible to third parties who have no right to read and understand the data or messages. Cryptology consists of two parts, namely, cryptography and cryptanalysis. Cryptography analyzes methods of encrypting messages, and cryptanalysis analyzes methods of decrypting encrypted messages. Encryption is the process of translating plaintext data into something that appears to be random and meaningless. Decryption is the process of converting this random text into plaintext. Cloud computing is the legal transfer of computing services over the Internet. Cloud services let individuals and businesses to use software and hardware resources at remote locations. Widespread use of cloud computing raises the question of whether it is possible to delegate the processing of data without giving access to it. However, homomorphic encryption allows performing computations on encrypted data without decryption. In homomorphic encryption, only the encrypted version of the data is given to the untrusted computer to process. The computer will perform the computation on this encrypted data, without knowing anything on its real value. Finally, it will send back the result, and whoever has the proper deciphering key can decrypt the cryptogram correctly. The decrypted result will be equal to the intended computed value. In this paper, homomorphic encryption and their types are reviewed. Also, a simulation of somewhat homomorphic encryption is examined.


<div xmlns="http://www.w3.org/1999/xhtml"><sec id="j_amns.2020.1.00046_s_001_w2aab3b7e2829b1b6b1ab1aAa"><label>1</label><div>Introduction</div><p>Cryptology is defined as the science of making communication incomprehensible to third parties who have no right to read and understand the data or messages. Cryptology is divided into cryptography, which is the science of securing data, and cryptanalysis, which is the science of analyzing and breaking secure communication. The main terms in cryptology are given in <a ref-type="table" href="#j_amns.2020.1.00046_tab_001_w2aab3b7e2829b1b6b1ab1ab3Aa">Table 1</a>.</p><table-wrap id="j_amns.2020.1.00046_tab_001_w2aab3b7e2829b1b6b1ab1ab3Aa" position="float"><label>Table 1</label><caption><p>Main terms in cryptology</p></caption><table rules="groups"><thead><tr><th align="left" valign="top"><bold>Keywords</bold></th><th align="left" valign="top"><bold>Explanation</bold></th></tr></thead><tbody><tr><td align="left" valign="top">Plaintext</td><td align="left" valign="top">Data that are wanted to be protected. Let us call it P</td></tr><tr><td align="left" valign="top">Ciphertext</td><td align="left" valign="top">Encrypted message</td></tr><tr><td align="left" valign="top">Encryption</td><td align="left" valign="top">Method of hiding message. If E refers to encryption function Ek (P) = C</td></tr><tr><td align="left" valign="top">Decryption</td><td align="left" valign="top">Recovering encrypted message. If D refers to decryption function Dk (C) = P</td></tr><tr><td align="left" valign="top">Key</td><td align="left" valign="top">A numeric value to cipher data to protect it</td></tr></tbody></table></table-wrap><sec id="j_amns.2020.1.00046_s_001_s_001_w2aab3b7e2829b1b6b1ab1ab4Aa"><label>1.1</label><div>Cryptography</div><p>Cryptography is the practice and study of hiding information. A cryptographic algorithm works in combination with a key—a word, number, or phrase—to encrypt the plaintext. The security of encrypted data is entirely dependent on two things: the strength of the cryptographic algorithm and the secrecy of the key. There are two types of cryptography: symmetric and asymmetric. If the same key is used for encryption and decryption, then the mechanism is called symmetric key cryptography or classical cryptography. This also implies to share a different key with everyone that is wanted to communicate with. Nevertheless, symmetric schemes present the advantage of being fast and should be used as often as possible.</p><p>However, if two different keys are used for encryption and decryption, then the mechanism is called asymmetric key cryptography or modern cryptography. The encryption key is public, as the decryption key remains private in this type. Asymmetric schemes are more functional than symmetric ones since there is no need for the sender and the receiver to agree on anything before the transaction. Asymmetric schemes, however, have a big drawback. They are often based on nontrivial mathematical computations and much slower than the symmetric ones. The two most prominent examples are RSA and ElGamal.</p><p>The right scheme is the one that fits your constraints in the best way. By constraints, we may understand constraints in terms of time, memory, security, and so forth.</p></sec><sec id="j_amns.2020.1.00046_s_001_s_002_w2aab3b7e2829b1b6b1ab1ab5Aa"><label>1.2</label><div>Cryptanalysis</div><p>It is the reverse process of cryptography. The objective of cryptanalyst is to decrypt the ciphertext.</p></sec></sec><sec id="j_amns.2020.1.00046_s_002_w2aab3b7e2829b1b6b1ab1b1Aa"><label>2</label><div>Homomorphic Encryption</div><p>The goal of encryption is to ensure confidentiality of data in communication and storage processes. Homomorphic encryption is a form of encryption that allows specific types of computations like addition or multiplication to be carried out on ciphertext. The encrypted result will be the same when decryption is done. Widespread use of cloud computing raises the question of whether it is possible to delegate the processing of data without giving access to it. Encrypting one’s data with a conventional encryption scheme to protect one’s privacy seems to undermine the benefits of cloud computing since it is impossible to process the data without the decryption key [<a ref-type="bibr" href="#j_amns.2020.1.00046_ref_001_w2aab3b7e2829b1b6b1ab2ab1Aa">1</a>]. However, in homomorphic encryption; only the encrypted version of the data is given to the untrusted computer to process. The computer will perform the computation on this encrypted data, without knowing anything on its real value. Finally, it will send back the result, and whoever has the proper deciphering key can decrypt the cryptogram correctly. For coherence, the decrypted result will be equal to the intended computed value.</p><p>Homomorphic encryption schemes are methods that allow the transformation of ciphertexts C(M) of message M, to ciphertexts C(f(M)) of a computation/function of message M, without disclosing the message. Generally, an encryption scheme contains a three-step algorithm. They are
<list list-type="order"><list-item><p>Key Generation—creates two keys, i.e. the secret key sk and the public key pk.</p></list-item><list-item><p>Encryption—encrypts the plaintext m with the public key pk to yield ciphertext c.</p></list-item><list-item><p>Decryption—decrypts the ciphertext c with the secret key sk to retrieve the plaintext m [<a ref-type="bibr" href="#j_amns.2020.1.00046_ref_002_w2aab3b7e2829b1b6b1ab2ab2Aa">2</a>].</p></list-item></list>
Homomorphic encryption schemes can be classified into three main categories namely: partially homomorphic encryption (PHE), somewhat homomorphic encryption (SWHE), and fully homomorphic encryption (FHE) [<a ref-type="bibr" href="#j_amns.2020.1.00046_ref_006_w2aab3b7e2829b1b6b1ab2ab6Aa">6</a>].</p><sec id="j_amns.2020.1.00046_s_002_s_001_w2aab3b7e2829b1b6b1ab1b1b4Aa"><label>2.1</label><div>PHE Scheme</div><p>The most popular PHE methods available are the RSA, ElGamal, and Paillier methods.
<list list-type="order"><list-item><p><italic>RSA method</italic>: RSA was the first homomorphic encryption scheme developed by Ronald Rivest, Leonard Adleman, and Michael Dertouzos in 1978. It is a public-key crypto technique and is multiplicative homomorphic.</p></list-item><list-item><p><italic>Paillier method</italic>: This is additive homomorphic and is developed by Pascal Paillier in 1999 [<a ref-type="bibr" href="#j_amns.2020.1.00046_ref_002_w2aab3b7e2829b1b6b1ab2ab2Aa">2</a>].</p></list-item></list></p></sec><sec id="j_amns.2020.1.00046_s_002_s_002_w2aab3b7e2829b1b6b1ab1b1b5Aa"><label>2.2</label><div>SWHE Scheme</div><p>The most popular SWHE method is Boneh-Goh-Nissim (BGN) method. This method allows any number of additions but only one multiplication to be performed on data.</p></sec><sec id="j_amns.2020.1.00046_s_002_s_003_w2aab3b7e2829b1b6b1ab1b1b6Aa"><label>2.3</label><div>FHE Scheme</div><p>The most popular FHE schemes are algebra homomorphic encryption scheme based on updated ElGamal proposed by Chen Liang and Gao Changmin in 2008 and enhanced homomorphic encryption scheme (EHES) proposed by Gorti VNKV and Subba Rao in 2013. In 2009, Gentry proposed the first not yet broken FHE scheme [<a ref-type="bibr" href="#j_amns.2020.1.00046_ref_003_w2aab3b7e2829b1b6b1ab2ab3Aa">3</a>]. FHE refers to cryptosystems that can process both additions and multiplications in the encrypted domain. Any polynomial function over encrypted data can be computed.</p></sec></sec><sec id="j_amns.2020.1.00046_s_003_w2aab3b7e2829b1b6b1ab1b2Aa"><label>3</label><div>Simulation of a Homomorphic System</div><p>In homomorphic encryption, the encryption of the product of two numbers is equal to the product of the encryptions of the numbers:
<disp-formula id="j_amns.2020.1.00046_ueq_001_w2aab3b7e2829b1b6b1ab1b2b2b1Aa"><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_amns.2020.1.00046_ueq_001.png"></graphic><math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="block"><mrow><mi>E</mi><mo stretchy="false">(</mo><mi>a</mi><mo>.</mo><mi>b</mi><mo stretchy="false">)</mo><mo>=</mo><mi>E</mi><mrow><mo>(</mo><mrow><mi>a</mi><mo stretchy="false">)</mo><mo>.</mo><mi>E</mi><mo stretchy="false">(</mo><mi>b</mi></mrow><mo>)</mo></mrow></mrow></math><tex-math>E(a.b) = E\left( {a).E(b} \right)</tex-math></alternatives></disp-formula><italic>E</italic> is an encryption algorithm or it is also known as a <italic>scheme.</italic> Schemes can be thought as <italic>Somewhat Homomorphic</italic> and <italic>Fully Homomorphic. Fully Homomorphic:</italic> Any kind of operations on ciphertexts can be done. This idea came from Rivest in 1978 but Craig Gentry was the first one whose scheme works on arbitrary functions. <italic>Somewhat Homomorphic:</italic> In this type, two ciphertexts can be added or a ciphertext and a plaintext can be multiplied [<a ref-type="bibr" href="#j_amns.2020.1.00046_ref_006_w2aab3b7e2829b1b6b1ab2ab6Aa">6</a>]
.</p><p>In this paper, SWHE is examined. The length of the plaintext and encryption time comparison has been made. To do that, Gentry’s encryption scheme is used [<a ref-type="bibr" href="#j_amns.2020.1.00046_ref_007_w2aab3b7e2829b1b6b1ab2ab7Aa">7</a>]
. The parameters will be
<disp-formula id="j_amns.2020.1.00046_ueq_002_w2aab3b7e2829b1b6b1ab1b2b3b3Aa"><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_amns.2020.1.00046_ueq_002.png"></graphic><math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="block"><mrow><mi>ρ</mi><mo>=</mo><mi>λ</mi><mo>,</mo><mo> </mo><mi>ρ</mi><mo>′</mo><mo>=</mo><mn>2</mn><mi>λ</mi><mo>,</mo><mo> </mo><mi>η</mi><mo>=</mo><mover accent="true"><mtext>O</mtext><mo>˜</mo></mover><mo stretchy="false">(</mo><msup><mrow><mi>λ</mi></mrow><mn>2</mn></msup><mo stretchy="false">)</mo><mo>,</mo><mo> </mo><mi>λ</mi><mo>=</mo><mover accent="true"><mtext>O</mtext><mo>˜</mo></mover><mo stretchy="false">(</mo><msup><mrow><mi>λ</mi></mrow><mn>5</mn></msup><mo stretchy="false">)</mo></mrow></math><tex-math>\rho = \lambda ,{\text{ }}\rho ' = 2\lambda ,{\text{ }}\eta = {\text{\tilde O}}({\lambda ^2}),{\text{ }}\lambda = {\text{\tilde O}}({\lambda ^5})</tex-math></alternatives></disp-formula><italic>λ</italic> is a safety parameter. Security parameters associated with the security of the scheme, usually take dozens to hundreds of bits.</p><p><italic>Key generation</italic>: We choose <italic>η</italic> bit odd prime numbers p and <italic>θ</italic> bits odd prime numbers q randomly and order N=pq. Then choose two random integers <italic>l</italic> ∈ [0,2<italic>γ</italic>/p] <italic>h</italic>∈ [−2p, 2p], and calculate x=<italic>pl</italic>+<italic>2h</italic>.</p><p>Set public key <italic>pk</italic>=<italic>(N,x)</italic>=, private key <italic>sk</italic>=<italic>p</italic>.</p><p><italic>Encryption (pk,m)</italic>: Given a plaintext <italic>m</italic>∈ {0,1}*; we choose two random integers <italic>r1</italic>∈ (−2p,2p) and <italic>r2</italic>∈ (−2p,2p). According to the public key <italic>pk</italic>=<italic>(N,x),</italic> we can calculate
<disp-formula id="j_amns.2020.1.00046_ueq_003_w2aab3b7e2829b1b6b1ab1b2b6c12Aa"><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_amns.2020.1.00046_ueq_003.png"></graphic><math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="block"><mrow><mi>c</mi><mo>=</mo><mi>m</mi><mo>+</mo><mn>2</mn><msub><mrow><mi>r</mi></mrow><mn>1</mn></msub><mo>+</mo><mo> </mo><msub><mrow><mi>r</mi></mrow><mn>2</mn></msub><mi>x</mi><mo> </mo><mtext>mod</mtext><mo> </mo><mi>N</mi><mo> </mo><mrow><mo>(</mo><mrow><mi>c</mi><mo> </mo><mtext>is</mtext><mo> </mo><mtext>the</mtext><mo> </mo><mtext>result</mtext><mo> </mo><mtext>of</mtext><mo> </mo><mtext>ciphertext</mtext><mo>.</mo></mrow><mo>)</mo></mrow></mrow></math><tex-math>c = m + 2{r_1} + {r_2}x\,\,\,\,\,\bmod \,\,\,\,N\,\,\,\left( {c\,\,\,{\text{is}}\,\,\,{\text{the}}\,\,\,{\text{result}}\,\,\,{\text{of}}\,\,\,{\text{ciphertext}}.} \right)\</tex-math></alternatives></disp-formula><italic>Decryption (sk,c):</italic> According to the given ciphertext, make use of private key <italic>sk</italic> to calculate:
<disp-formula id="j_amns.2020.1.00046_ueq_004_w2aab3b7e2829b1b6b1ab1b2b6c17Aa"><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_amns.2020.1.00046_ueq_004.png"></graphic><math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="block"><mrow><msup><mi>m</mi><mo>′</mo></msup><mo>=</mo><mo stretchy="false">(</mo><mi>c</mi><mo> </mo><mtext>mod</mtext><mo> </mo><mi>p</mi><mo stretchy="false">)</mo><mtext>mod</mtext><mn>2</mn></mrow></math><tex-math>m' = (c{\text{ mod }}p){\text{mod}}2</tex-math></alternatives></disp-formula><italic>Evaluate (pk, C, c1,c2,ct):</italic> Given a Boolean circuit <italic>C</italic> with <italic>t</italic> inputs and <italic>t</italic> ciphertexts <italic>ci</italic>. Let us put T ciphertext into extended circuits to perform all its operations, then verify the result of the circuit’s output in <a ref-type="disp-formula" href="#j_amns.2020.1.00046_eq_001_w2aab3b7e2829b1b6b1ab1b2b6c34Aa">(1)</a> to see if it conform <a ref-type="disp-formula" href="#j_amns.2020.1.00046_eq_002_w2aab3b7e2829b1b6b1ab1b2b6c35Aa">(2)</a> [<a ref-type="bibr" href="#j_amns.2020.1.00046_ref_007_w2aab3b7e2829b1b6b1ab2ab7Aa">7</a>].
<disp-formula id="j_amns.2020.1.00046_eq_001_w2aab3b7e2829b1b6b1ab1b2b6c34Aa"><label>(1)</label><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_amns.2020.1.00046_eq_001.png"></graphic><math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="block"><mrow><mi>c</mi><mo>*</mo><mo>=</mo><mtext>evaluate</mtext><mo stretchy="false">(</mo><mi mathvariant="italic">pk</mi><mo>,</mo><mi>C</mi><mo>,</mo><mi>c</mi><mo stretchy="false">)</mo></mrow></math><tex-math>c* = {\text{evaluate}}(pk,C,c)</tex-math></alternatives></disp-formula><disp-formula id="j_amns.2020.1.00046_eq_002_w2aab3b7e2829b1b6b1ab1b2b6c35Aa"><label>(2)</label><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_amns.2020.1.00046_eq_002.png"></graphic><math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="block"><mrow><mi mathvariant="italic">Dec</mi><mo stretchy="false">(</mo><mi mathvariant="italic">sk</mi><mo>,</mo><mi>c</mi><mo>*</mo><mo stretchy="false">)</mo><mo>=</mo><mi>C</mi><mo stretchy="false">(</mo><msub><mrow><mi>m</mi></mrow><mn>1</mn></msub><mo>,</mo><msub><mrow><mi>m</mi></mrow><mn>2</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mrow><mi>m</mi></mrow><mi>t</mi></msub><mo stretchy="false">)</mo></mrow></math><tex-math>Dec(sk,c*) = C({m_1},{m_2}, \ldots ,{m_t})</tex-math></alternatives></disp-formula></p><p>
In the experimental environment, safe parameter <italic>λ</italic> is set to the length of the 10 bits and the order of magnitude as 10<sup>5</sup>. So the order of magnitude for <italic>p</italic> = <italic>λ</italic> as 10<sup>5</sup>. <italic>p′</italic> = <italic>2λ</italic> as 10<sup>5</sup>, the order of magnitude for <italic>η</italic> = O(<italic>λ</italic><sup>2</sup>) as 10<sup>10</sup>, the order of magnitude for <italic>θ</italic> = O(<italic>λ</italic><sup>4</sup>) as 10<sup>20</sup>, and the order of magnitude for <italic>γ</italic>=~ O (<italic>λ</italic><sup>5</sup>) as 10<sup>25</sup>. Algorithm keygen of the data is determined by the above parameters. The relationship between the plaintext and ciphertext size is shown in <a ref-type="fig" href="#j_amns.2020.1.00046_fig_001_w2aab3b7e2829b1b6b1ab1b2b8Aa">Figure 1</a>. The simulation time is calculated in seconds. It is observed that when plaintext size is increased, the ciphertext size is also increased. But the growthe rate is not high. Still, it is gradually increased.</p><figure id="j_amns.2020.1.00046_fig_001_w2aab3b7e2829b1b6b1ab1b2b8Aa" position="float" fig-type="figure"><h2>Fig. 1</h2><figCaption><p>Relationship between the plaintext and ciphertext size.</p></figCaption><img xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_amns.2020.1.00046_fig_001.jpg" src="https://sciendo-parsed.s3.eu-central-1.amazonaws.com/64709f6071e4585e08aa191e/j_amns.2020.1.00046_fig_001.jpg?X-Amz-Algorithm=AWS4-HMAC-SHA256&amp;X-Amz-Date=20240608T180025Z&amp;X-Amz-SignedHeaders=host&amp;X-Amz-Expires=18000&amp;X-Amz-Credential=AKIA6AP2G7AKP25APDM2%2F20240608%2Feu-central-1%2Fs3%2Faws4_request&amp;X-Amz-Signature=4e81dd26347ee178d54c9b73939da0c9dc36f97f7741d9eb7a6a6e2adac87d58" class="mw-100"/></figure></sec><sec id="j_amns.2020.1.00046_s_004_w2aab3b7e2829b1b6b1ab1b3Aa"><label>4</label><div>Conclusion</div><p>Cryptography is a powerful tool to protect information. In recent years, cryptography and cryptanalysis had been improved. Widespread use of cloud computing raises the question of whether it is possible to delegate the processing of data without giving access to it. Homomorphic encryption is a new way to protect private data. Because it allows making computation without decrypting data. It is a new field and research is going on.</p></sec></div>

Simulation of a Homomorphic Encryption System

Department of Electrical and Electronics Engineering

Applied Mathematics and Nonlinear Sciences

This work is licensed under the Creative Commons Attribution 4.0 International License.

{"article-title":"Simulation of a Homomorphic Encryption System"}

Cryptology is defined as the science of making communication incomprehensible to third parties who have no right to read and understand the data or messages....

Simulation of a Homomorphic Encryption System

Publié en ligne: 10 avr. 2020

Pages: 479 - 484

Reçu: 15 juin 2019

Accepté: 02 mars 2020

DOI: https://doi.org/10.2478/amns.2020.1.00046

Mots clés
homomorphic encryption, cryptology, cloud computing

© 2019 Hanife Çağıl Bozduman et al., published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

Simulation of a Homomorphic Encryption System

Publié en ligne: 10 avr. 2020

Pages: 479 - 484

Reçu: 15 juin 2019

Accepté: 02 mars 2020

DOI: https://doi.org/10.2478/amns.2020.1.00046

Mots cléshomomorphic encryption, cryptology, cloud computing

© 2019 Hanife Çağıl Bozduman et al., published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

Mots clés
homomorphic encryption, cryptology, cloud computing