RSA: The First Homomorphic Encryption Scheme in Cryptography

The RSA algorithm was proposed in 1978 and is named after its inventors: Rivest, Shamir, and Adleman.

RSA: A Cornerstone of Cryptography

In 1976, the first asymmetric key encryption algorithm, Diffie-Hellman, was proposed. However, this algorithm left open the problem of realizing a one-way function — a function that is hard to invert.

The three cryptographers — Ron Rivest, Adi Shamir, and Leonard Adleman — solved the aforementioned problem.

RSA algorithm

This algorithm is divided into three phases, namely, key generation, encryption, and decryption. 

A. Key Generation: 

        1. Select two large prime numbers (say p, and q).

        2. Calculate n = pq.

        3. Calculate Euler totient function Φ(n) = (p-1)(q-1)

        4. Choose value of e (where 1 < e < Φ(n), and gcd(Φ(n),e)=1).

        5. Calculate d such that ed = 1 mod Φ(n).

Public key = {e,n}

Private key = {d, n}

B. Encryption:

Consider plaintext m (where m<n). Ciphertext can be obtained as follows. 

                            Ct = me mod n

C. Decryption:

                            m = Ctd mod n


RSA from a Homomorphic Encryption Perspective


RSA was the first homomorphic encryption algorithm. It is homomorphic with respect to multiplication. Unfortunately, addition cannot be applied to RSA-encrypted data. In other words, it supports only a single type of operation, making it an example of partial homomorphic encryption.

                                Enc(m1)*Enc(m2) = Enc(m1*m2)

Proof: Enc(m1) = m1e mod n, Enc(m2) = m2e mod n

Enc(m1)*Enc(m2) = m1e * m2emod n = m1*m2e mod n = Enc(m1*m2).


The 1978 discovery raised a fundamental question: is it possible to perform multiple operations on encrypted data within a single encryption scheme?



We thanks to..


1. R Rivest, L Adleman, and ML Dertouzos. "On data banks and privacy homomorphisms." Foundations of secure computation 4.11 (1978): 169-180.

2. R Rivest, A Shamir, and L Adleman. "A method for obtaining digital signatures and public-key  cryptosystems." Communications of the ACM 21.2 (1978): 120-126.


Comments

Post a Comment

Popular posts from this blog

Homomorphic Encryption: A Basic Idea

Image
Homomorphic encryption has the same aim as other encryption-decryption mechanisms: maintaining confidentiality, security, privacy, etc.  In this blog, we will see homomorphic encryption and its type.  Homomorphic Encryption (HE):  It is an encryption that computes operations over encrypted data without decrypting it (or without the need for a secret key).  Mathematically speaking in a client-server architecture: client has message 'm' and function f. The task of client is to compute f(m). Due to computational expensiveness (maybe one of the reason) client sends encryption of message (say Enc(m)) and 'f' to the server. Server will compute function over encrypted message, that is, f(Enc(m)), and return the result to the client, that is, Enc(f(m)). Client will decrypt it Dec(Enc(f(m)), that is, f(m). Hence, client achieves f(m).  Let's understand HE with our daily life (Tea making process): Figure 1. Here m is message, Enc is encryption, f is function, and Eval in...
Read more

Elliptic Curve Cryptography (ECC) and ECDSA

Image
Elliptic Curve Cryptography (ECC) Elliptic curve (EC) was first introduced by Neal Kobiltz and Victor Miller in 1985. Elliptic curve is a non-singular curve that is operated on a finite field Zq (where q is the order of elliptic curve). EC consists of set of points that satisfies the following equation as follows.                                                                   Y 2 = X 3 + aX + b Where {X,Y,a,b} ∈ Zq, and 4a 3 + 27b 2 ≠ 0. Next, we discuss the encryption and decryption mechanism between two parties (Say α and γ ). Remark 1: Elements selected from party α is represented by capital letters whereas elements selected from party γ is represented by small letters. i) Key Generation: 1. Secret key: Each party α and γ selects secret keys S ∈ Zq and s ∈ Zq. 2. Public key: P ...
Read more

Fast Base Conversion and Its Application

Image
Fast Base Conversion (FBC) is a technique used to convert a number from one modulus space to another. For example, if we have 14 m o d     77 14 \mod 77  and want to convert it to x m o d     390 x \mod 390 , FBC is widely used. Mathematically, it can be represented as follows: Here, the above equation represents an integer x x  in modulus q q , and FBC converts this integer into the modulus space t t . The modulus q q  is the product of small coprime moduli (i.e., q = q 1 q 2 … q k q = q_1 q_2 \dots q_k ​ ), and x x  is an integer such that x ∈ [ 0 , q ) x \in [0, q) . We also note that q q  and t t  are coprime numbers. Here, we remark that it is not necessary for the above equation to produce the exact result for x x . Instead of x m o d     t x \mod t , it will provide x ′ m o d     t x' \mod t . Thus, the output of the above equation is as follows: FBC ( x , q , t )  =  x  +  A q  mod  t , where A ∈ [ 0 , k − 1 ] A \in [0,...
Read more