Fully Homomorphic Encryption and cryptography

Fully Homomorphic Encryption and cryptography Introduction Transferring files between machines (and users) is a common daily occurrence although the confidentiality of the data is a basic condition. Now problem was how to secure them from inadvertent addressee from observing the data, which are supposed to confidential and likely on risk if prepared well-known to negligent parties. In each of these cases, its important to know what options are available to get your file from point A to point B and to comprehend whether the technique you choose provides sufficient security given the sensitivity of the data being transferred. Cryptography is ability of secret text, or more precisely of stock up resource (for a long or shorter period of time) in a shape which allows it to be revealed to those you wish to see it yet hides it from all others. A cryptosystem is a technique to accomplish this. Cryptanalysis is to put into practice to overcome such endeavors to hide information. Cryptology comprises of both cryptography and cryptanalysis. The unique information to be hidden is called plaintext. The concealed information is called ciphertext. Encryption or Decryption is any modus operandi to convert plaintext into ciphertext. A cryptosystem is designed so that decryption can be consummated only under certain conditions, which usually means simply by persons in control of both a decryption engine (these days, generally a computer program) and a meticulous piece in sequence, called the decryption key, which is supplied to the decryption engine in the course of decryption. Plaintext is transformed into ciphertext by process of an encryption engine (again, generally a computer program) whose operation is fixed and determinate (the encryption method) nevertheless which functions in practice in a way dependent on a piece of information (the encryption key) which has a major effect on the output of the encryption process. The main purpose was to make sure privacy while you transferring your private data from one place to another place do not matter electronically or via users. There were many scheme but very complicated to follow them and most important less security. So time by time many scientists discover different techniques but Gentrys technique â€Å"Fully Homomorphic Encryption† got a tremendous value against all technique. All others techniques were performing well but with restriction but Gentrys scheme user can perform unlimited action. Objective Cloud computing Literature review â€Å"Homomorphic encryption is a paradigm that refers to the ability, given encryptions of some messages, to generate an encryption of a value that is related to the original messages. Speciï ¬ cally, this ability means that from encryptions of k messages (m1,†¦,mk), it is possible to generate an encryption of m* = f(m1,†¦,mk) for some (efficiently computable) function f. Ideally, one may want the homomorphically generated encryption of m* to be distributed identically (or statistically close) to a standard encryption of m*. We call schemes that have this property strongly homomorphic. Indeed, some proposed encryption schemes are strongly homomorphic w. r. t some algebraic operations such as addition or multiplication.† (Rothblum R, 2010). â€Å"An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: 1. Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intended recipient. Only he can decipher the message, since only he knows the corresponding decryption key. 2. A message can be â€Å"signed† using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in â€Å"electronic mail† and â€Å"electronic funds transfer† systems.† (Rivest et al, 1978) â€Å"Homomorphic encryption enables â€Å"computing with encrypted data† and is hence a useful tool for secure protocols. Current homomorphic public key systems have limited homomorphic properties: given two ciphertexts Encrypt (PK, x) and Encrypt (PK, y), anyone can compute either the sum Encrypt (PK, x+y), or the product Encrypt (PK, xy), but not both.† (Boneh et al, 2006) ARMONK, N.Y 25 Jun 2009: â€Å"An IBMResearcher has solved a thorny mathematical problem that has confounded scientists since the invention of public-key encryption several decades ago. The breakthrough, called privacy homomorphism, or fully homomorphic encryption, makes possible the deep and unlimited analysis of encrypted information data that has been intentionally scrambled without sacrificing confidentiality.† (IBM, 2009) â€Å"We propose the first fully homomorphic encryption scheme, solving a central open problem in cryptography. Such a scheme allows one to compute arbitrary functions over encrypted data without the decryption key i.e., given encryptions E(m1) ,†¦,E(mt) of m1,†¦.,mtone can efficiently compute a compact ciphertext that encrypts f(m1,†¦.,mt) for any efficiently computable function Æ’. This problem was posed by Rivest et al. in 1978.† (Gentry C, 2009) â€Å"Searching databases is usually done in the clear. And even if the query is encrypted, it has to be decrypted (revealing its contents) before it can be used by a search engine. Whats worse is that databases themselves are stored as plaintext, available to anyone gaining access. The smarter way to handle sensitive information would be to encrypt the queries, encrypt the database and search it in its encrypted form. Impossible until now, IBMs T.J. Watson Research Center (Yorktown Heights, N.Y.) recently described a homomorphic encryption scheme that allows encrypted data to be searched, sorted and processed without decrypting it. Fully homomorphic encryption schemes theoretically allow ciphertext to be manipulated as easily as plaintext, making it perfect for modern cloud computing, where your data is located remotely.† (Johnson R C, 2009) Body History of Cryptography In earliest era communications or correspondence among recipient and correspondent were only possible through extremely safe and sound way like loyal pigeon, physically or any other source but must be trusted. That was a time when it was very tough to believe or trust on available sources. There was a little doubt and big risk for the sender was if transporter discloses the information then any one can harm them. Progressively a newly ideas came with world called Cryptography/Encryption† means this is a technique in which the sender encrypts the communication using proper key and its only possible for receiver to decrypt it if he possessed the key. Key based Encryption. In key based encryption keys are the most important part of creating new ciphertext. A sequence of small piece used generally in cryptography, letting people to encrypt/decrypt facts and the same key can be used to carry out additional mathematical business as well. Specified a secret message, a key established the connection with the sequence to the ciphertext. The key we use for a special cryptosystem has worth so whenever this key used to ciphertext, always lets the encrypted communication to be decrypted and always doing reverse like encrypt the plaintext. In ancient era because calculation was very hard so they prefer to use not lengthy keys in respect of bits but on the other hand its safe to use longer key. Communications also one can encrypt in n-bit blocks. It is true that the longer a key is, more difficult for one to break the encrypted message. Encryptions consist of two categories. Private Key or Symmetric Key Encryption Public Key or Asymmetric Key Encryption Private Key / Symmetric Key Encryption This was thousands of years ago when Julian Caesar used this scheme to send his communication to his military. He used very simple key based classic cryptographic algorithm in which he just shifted each letter with preplanned key number 4. In his algorithm key varies so thats why we cannot guess what number he will use next. Lets take said number 4 which means â€Å"A† will swap with â€Å"D† and â€Å"B† will swap with â€Å"G† and so on â€Å"X† will swap with â€Å"A† etc. ABCDEFGHIJKLMNOPQRSTUVWXYZ DEFGHIJKLMNOPQRSTUVWXYZABC The same letter changing technique was useful to small case correspondence and also covering around the letters as well. (S. Tewksbury). Cryptography history is very old so we can divide it in to two categories. Classic era Cryptography Computer era Cryptography In classic era there was no computer or any electronic machine to solve this problem so people were used pen and paper to unreveal the truth of letters. Julian Caesar technique is classic era practice. Until WWII all cryptography techniques are none as classic era cryptography. After WWII development of machine made cryptography life very complex and that time was very easy to break all classic time encryptions mostly called key based techniques. Key word was very important in these practices and because of the key it was very easy to break through encryption algorithm. ROT13 is the best practice of encryption algorithm which we know its famous name Caesar cipher and this is extension of Julian Caesar scheme. The most useful technique was ROT13 in which they used fix key 13 to encrypt the letters. This algorithm was very famous in the beginning of computer era and anyone wants to use ROT13 scheme, both side parties must use the same key to encrypt and decrypt the code. This key calle d secret key. The development of the machine set a stander in respect of key codes and then everyone prepared a code book to share as a key code book. For example in ROT13 simply they rotate the letters by 13 places. Application of this scheme is very easy like Julius Caesar technique where he swapped letters with fix key 4 and now in ROT13 with key 13 and wrapping around like â€Å"a† become â€Å"n† and â€Å"m† become â€Å"z† and wrapping continue if necessary but the problem was user can play only English alphabet. The beauty of this technique was it made its function its own inverse like for any text x we can write its function mathematically inverse of ROT13(x) or ROT13 (ROT13(x)) where x is belong to a character which one wants to encrypt. This characteristic furthermore called an involution in arithmetic and a give-and-take code in cryptography. This scheme work as below ABCDEFGHIJKLM ↔ abcdefghijklm NOPQRSTUVWXYZ ↔ nopqrstuvwxyz In this scheme problem was again if someone steel or rob your data then it is very easy to decode it. This is not reasonable cryptographic proposal even though its known as secret key cryptosystem. If we observe closely the ROT13 is partially homomorphic particularly with respect to the concatenation function because it has a reciprocal property. Lets write a function to prove its homomorphic property using secret key 13, in this function we encrypt the text using said algorithm and we will add the encrypted text to see its homomorphic property and then finally decrypt the result. Java ROT13 Code. import java.util.*; public class ROT13 { static int x,y,n,fx,l,m; public static void main(String[] args) { Scanner sc=new Scanner(System.in); System.out.println(Enter your text); String t = sc.nextLine(); int j=0; int key=13; for (int i=0; i { char ch3 = t.charAt(j); if (ch3 >= a ch3 else if (ch3 >= n ch3 else if (ch3 >= A ch3 else if (ch3 >= A ch3 System.out.print(ch3); j++; }}} OUTPUT Enter your text HelloWorld UryybJbeyq The above algorithm is very uncomplicated algorithm to illustrate how ROT13 scheme works and in above output â€Å"Uryyb Jbeyq† is encrypted cipher formed with above algorithm. To check its homomorphic property now anyone can break this cipher text and then apply a concatenation (addition operator) to this text. After getting a new text anyone can apply ROT13 algorithm to decode it to see if he/she is getting the original text. import java.util.*; public class ROT13 { static int x,y,n,fx,l,m; public static void main(String[] args) { Scanner sc=new Scanner(System.in); System.out.println(Enter yout text); String t = sc.nextLine(); int j=0; int key=13; for (int i=0; i { char ch3 = t.charAt(j); if (ch3 >= a ch3 else if (ch3 >= n ch3 else if (ch3 >= A ch3 else if (ch3 >= A ch3 System.out.print(ch3); j++; } System.out.println(); System.out.println(Enter yout 2nd text); String t1 = sc.nextLine(); int j1=0; int key1=13; for (int i1=0; i1 { char ch3 = t1.charAt(j1); if (ch3 >= a ch3 else if (ch3 >= n ch3 else if (ch3 >= A ch3 else if (ch3 >= A ch3 System.out.print(ch3); j1++; } System.out.println(); System.out.println(Enter the 1st encrypted result=); String a=sc.nextLine(); System.out.println(); System.out.println(Enter the 2st encrypted result=); String a1=sc.nextLine(); String con = a+a1; System.out.print(con); System.out.println(); int j2=0; int key2=13; for (int i2=0; i2 { char ch3 = con.charAt(j2); if (ch3 >= a ch3 else if (ch3 >= n ch3 else if (ch3 >= A ch3 else if (ch3 >= A ch3 System.out.print(ch3); j2++; }}} OUTPUT Enter the 1st encrypted result=Uryyb Enter the 2st encrypted result=Jbeyq UryybJbeyq HelloWorld Explanation of Output Text a = Encrypt (13, Hello); a = Uryyb Text b = Encrypt (13, World); b = Jbeyq Text c = Concat (a,b); c = UryybJbeyq Text d = Decrypt(13, c); d = HelloWorld As we can see clearly that we used an addition (concat) property to encrypt the text but after this we got the same result as we got without using concat. This property demonstrates that ROT13 is partially homomorphic scheme with respect of addition. The problem start with this technique when machine came in to being and it was easy to break secret code and even drawback of this scheme was numbers because user only were to able to encrypt alphabetic. Then gradually, ROT47 new scheme introduced and this scheme was derived from ROT13 as-well. Inside this scheme there was a big border for its users so now they were able to play with numbers and special characters. ROT47 exercise a larger alphabet, resulting from a regularcharacter programmingwell-known asAmerican Standard Code for Information Interchange (ASCII). The ASCII is a 7-bit code to correspond to English alphabet structure and these codes are in practice to symbolize data which includes numbers used in central processing unit, interactions technology and additional associated mechanism. The first publication of this standard code was in 1967 then afterward restructured and produced as â€Å"ANSI X3.4-1968†, at that time as â€Å"ANSI X3.4-1977† and at last as â€Å"ANSI X3.4-1986†. It is given that, it is a seven-bit code and it preserves the largest part symbolizing 128 characters. It presently characterize 95 printable characters together with 26 upper-case letters (A to Z), 26 lower-case letters (a to z), 10 numbers (0 to 9) and 33 special characters as well as arithmetic signs, punctuation marks and space character. . (Maini A K, 2007) However ROT13 introduced with new values of its alphabets separately both capital and smaller. Unlike ROT13, ROT47 was also not able to protect your text at all. This scheme is also having homomorphic property like addition. If closely observe the both scheme then we will be able to see that there is only little difference in both schemes. Both working pattern is same, both dealing with alphabets but ROT47 got advantage because this scheme deal with numbers and individual characters. In this method ASCII cipher connect to trade letters or numbers during encryption/decryption. Knowledge of ASCII codes to one lead to revel the facts. So here this scheme becomes the same like ROT13, so failure of this scheme once again involvement of the secret key. Is Symmetric Key Encryption Secure? ROT13 encryption scheme is not secured at all because the code of this scheme you can decode very easy. This was the disadvantage of this scheme. The reason we encrypt our transcript is to make it protected from illegitimate access however this scheme only consist of 26 characters which is very simple to decipher even from side to side a common person who have an access to the written text. For example: Anyone wishes to encrypt â€Å"atotaa†, after that the cipher we will achieve â€Å"ngbgnn† which is very effortless to work out through repetition of â€Å"a g†. ROT47 was novel encryption scheme derived from ROT13and also another example of symmetric key encryption but bit difficult. In ROT47 moving the basic letter swiftly like ROT13 with given substitute of ASCII. In this scheme one can take care of numbers and many other special characters as a substitute of the basic 26 letters however awareness of ASCII codes can show the way to one to search out the facts. Consequently, at this point this scheme turn into insecure category like ROT13, so failure of this scheme was once again its own typical contribution of the ASCII codes. Public Key or Asymmetric Key Encryption An important contribution in the peak field that time named â€Å"public-key cryptography† fulfilled by Whitfield Diffie, Martin Hellman and Ralph Merkle in 1976 when they introduce an elegant cryptosystem for a public-key. The major difference as compare to prior scheme was one extra key named as public key. The public key assume to be used for encryption and then private key will use to decryption. Cryptography has been a derivative security entirety once a secure channel exists along which keys can be transmitted, the security can be extended to other channels of higher bandwidth or smaller delay by encrypting the messages sent on them. The effect has been to limit the use of cryptography to communications among people who have made prior preparation for cryptographic security. (W Diffie and M Hellman, 1976) ABOVE NOT COMPLETE YET RSA respected the idea of Diffie et al and in 1978 they introduced first public key algorithm in public at MIT byRon Rivest,Adi Shamir, andLeonard Adleman. They illustrate what is predetermined by a trapdoor cipher, but how do you construct one? One usually used of the secret message of this type is called RSA encryption, wherever RSA are the initials of three initiators which are Rivest, Shamir, and Adleman. It is based on the idea below; it is simply multiply numbers together, particularly with the help of computers reason, factorization of this numbers could be difficult. To get them, one needs to factor N, which seems to be an extremely complex problem. But exactly how is N used to encode a message, and how are p and q used to decode it? Below is presented a complete example, although there will be used minute prime numbers so it is easy to follow the arithmetic. Actually in RSA encryption scheme they used very big prime numbers. As per them it makes scheme more secure because in their algorithm they need to factorize the number to get the result. If someone using small number then its easy to factorize the number but it is not the same with big number. Therefore, they in their algorithm they used key size 768-bit for ordinary use and they suggest 1024-bit key size for commercial use but for highly important information key size should be double (2048-bit) as compare to business key size just for mind satisfaction regarding security threat. RSA advised to one and all concerning their scheme that how scheme work to get own encryption and decryption key if any want using their method. First step decide two separate prime numbers like p, q. Later than multiply integers pq and make n = pq public. Exposing n in public will help one to hide original integers like q q and now it will be very difficult for illegitimate person to find original integers p q because factorization will be very hard for big prime numbers. This achievement will help to hide the value of multiplicative inverse d and the way derived from co-prime e. Choosing big integer d but d must comparatively prime with φ((p-1).(q-1)) and must fulfill the condition of greater common devisor gcd (d, (p-1)(q-1)). Finally one can compute the integer e â€Å"1 Mathematically Implementation of RSA algorithm RSA algorithm steps below Two prime integers p=61 and q=53 Multiply both prime integers n = pq = 61.53=3233. The value of n afterward used as modulus for public and private key. Calculate φ(n) = (p-1).(q-1) = 3120. Where φ is Eulers totient function. For the value of e = 17 select any integer from 1 One can conclude d = e-1 mod φ(n). The value of d = 2753 will be using in private key exponent so supervision of this key is essential. Extended Euclidean algorithm helps to determine the d. Thepublic keywill be (n= 3233,e= 17) and for text m the encryption function is m17 mod φ(n). Theprivate keyis (n= 3233,d= 2753) and for the encrypted text c decryption function will be cd mod φ(n). For example: Encryptm= 65, we compute c= 6517(mod 3233) = 2790. For decryptc= 2790, we calculate m= 27902753(mod 3233) = 65. Using the above boring however easy for a computer to calculate, One can decode others message and obtain the original message m = 65. Java Code for RSA Algorithm: public class RSACode { static long x,y,n,fx,l,m; static int p,q,e,tn; public static void main(String[] args) { Scanner sc=new Scanner(System.in); System.out.println(Please enter ist prime no P); p =sc.nextInt(); System.out.println(Please enter 2nd prime no q); q =sc.nextInt(); n=p*q; System.out.println(p*q = n +n); //Totient of n tn=(p-1)*(q-1); System.out.println(Totation of tn(pq) = +tn); int k=tn; for (int i=1; i { int fi= (int)(Math.pow(2, i)+1); l=fi; while (tn % fi !=0) { int r = (tn % fi); tn = fi; fi = r; } if (fi==1) System.out.println(GCD Of+[+k+,+l+] is+fi+Recommended for you); } System.out.println(So please use +l+ as e); System.out.println(Enter number to exponent e); e=sc.nextInt(); for (int d=1;d if ((e*d)%k==1) System.out.println(The value of e^-1 mod n= d ==+d); System.out.println(Enter the above valu of d); int d1=sc.nextInt(); System.out.println(Enter number to encrypt); m=sc.nextInt(); //encryption function is c = (m ^ e)/n; double encryption = (Math.pow(m, e)% n); System.out.println(encryption Key =+ encryption); System.out.println(The value of d= e^-1 mod n ==+d1); double decrypt = (Math.pow(encryption, d1) % n); System.out.println(encryption +to decryption is = + decrypt); OUT PUT Please enter ist prime no P 5 Please enter 2nd prime no q 7 p*q = n 35 Totation of tn(pq) = 24 GCD Of[24,5] is1Recommended for you GCD Of[24,9] is1Recommended for you So please use 9 as e Enter number to exponent e 5 The value of e-1 mod n= d ==5 Enter the above value of d 5 Enter number to encrypt 9 encryption Key =4.0 The value of d= e-1 mod n ==5 4.0to decryption is =9.0 The above java code works fine on small prime integers with small exponential power and small value of d (multiplicative inverse). OUT PUT Please enter ist prime no P 61 Please enter 2nd prime no q 53 p*q = n 3233 Totation of tn(pq) = 3120 GCD Of[3120,17] is1Recommended for you So please use 17 as e Enter number to exponent e 17 The value of e-1 mod n= d ==2753 Enter the above value of d 2753 Enter number to encrypt 65 encryption Key =887.0 The value of d= e-1 mod n ==2753 887.0to decryption is =NaN The same java code work perfect on big numbers but there you need different data types to adjust the output value the error NaN means data type mismatch. Practically Implementation An RSA operation whether encrypting, decrypting, signing, or verifying is fundamentally a modular exponentiation. This computation is executed with a sequence of modular multiplications. In practical uses, it is general to select a small public exponent for the public key. In reality, entire group of users preserve to use the matching public exponent, every one through a different modulus. However there are few boundaries on the prime factors of the modulus when the public exponent is set. For the reason of this it creates encryption more rapidly than decryption and verification quicker than signing. Through the typical modular power algorithms used to put into practice the RSA algorithm, public-key operations takeO(k2) steps, private-key operations take O(k3) steps, and key generation takesO(k4) steps, wherekis the number of bits in the modulus. (RSA 2010) Is RSA Work Secure? This scheme is not fully secure on the basses of following attacks Elementary attack Low private exponent attack Low private exponent attack Implementation attack Boneh et al Homomorphic Encryption (Boneh D, 1999) examined the RSA cryptosystem, was original exposed in the 1977-1978 topic of â€Å"Scientific American†. The cryptosystem is mainly generally in practice for offering confidentiality and certification validity of digital data. In those days RSA was positioned in many big business organizations. It is used by web servers and browsers to safe web transfer, it is used to make sure confidentiality and legitimacy of correspondence, it is used to safe remote login phase, and it is at the heart of electronic credit-card payment method. However, RSA is commonly take part in meanings anywhere safety of digital data is on risk. In view of the fact of first publication, the RSA scheme evaluates meant for weakness through a lot of examiners. However since 1977 to 1999, examiner have direct to a many interesting attacks but not any of them is critical. They typically demonstrate the risk of offensive use of RSA. Definitely, protected execution of RSA is a nontrivial job. Twenty years of research into inverting the RSA service created various perceptive attacks, other than no shocking attack has ever been discovered. The attacks exposed so far mostly demonstrate the drawbacks which one can avoid once applying RSA. Currently comes into view that correct applications can offer assurance to afford protection in the electronic globe. Openattacks on RSA scheme: Chosen chipper attack is very famous in cryptography in it attacker gathered information in pieces and then process it. This attack claimed against RSA in 1998 by Y. Desmedt and A. M. Odlyzko. According to RSA choose two prime numbers to calculate n then use φ(n) for modulus in encryption and decryption but if any enemy used brute force attack on their public key (N, e) to find the factorization and as well as their φ(n). On the other hand if we assume that only big prime number only allowed in RSA then it will affect the speed of the scheme because performance depend on n-bit key. While encrypting with not big encryption supporter e= 3 and small values of them like m Another attack was if sender send a plain clear message to e or more beneficiary after encrypted and the recipients distribute the similar exponente, except differentintegers p,q, andn, in that case it is simple to decode the plaintext using theChinese remainder theorem.Hà ¥stadJ become aware of that, this attack is achievable still if the plaintexts are not identical, however the attacker recognize a linear relation among them.Afterward Don Coppersmith enhanced this attack which was low exponent. RSA has the property that the multiplication of two encrypted text is the same to the encryption of the product of the individual plaintexts. That isâ€Å"† since of this multiplicative property achosen ciphertext attackis possible. For example an attacker, who needs to identify the decryption of a ciphertextc=me(modn)possibly will request the owner of the private key to decrypt an innocent appearing ciphertextc =re c (modn)for random rselected by the attacker. For the reason that of the multipli