Is the encryption more secure if we apply Pohlig-Hellman cipher twice with different keys but with the same modulus? To encrypt a message $M$, we compute $C=M^k \bmod p$
and to decrypt a Cipher-text we compute $M=C^{k^{−1} \bmod (p−1)} \bmod p$

But if we use Pohlig Hellman twice like $C_1=M^k \bmod p$, and then $C_2=C_1^k \bmod p$,
So is this more secure than doing it just once or not.

And what if we do it multiple times like a Cascade?
So is this more secure than doing it just once or not.


TL;DR; No, multiple encryptions are equal to single encryption and this is not better than single encryption

Pohlig-Hellman Cipher

In setting up of Pohlig-Hellman Cipher;


Select a large prime modulus, let say $p$,
then select a public modulus $e$ with $\gcd(e,\varphi(p))=1$ otherwise no unique decryption.
so, we have a public key as $(e,p)$.
Your private key is the tuple $(d,p)$ such that $e \cdot d \equiv 1 \bmod \varphi(p)$.


To encrypt a message Alice take a message $m &lt; p$, then encrypt you with $$c = m^e \pmod p$$

Once, you get the message you decrypt by $$ c^d = m^{e\cdot d} \equiv m \pmod p$$ with the help of the Little Fermat Theorem.

Example:


p = 3001
e = 37
d = 973

let $m = 57$ then $c = 57^{37} \equiv  2778 \pmod{3001}$

with $c = 2778$ then $ m = 2778^{973} = 57 \pmod{3001} $


Cascade Property: Double encryption is single encryption

To show the cascade property we will use the same modulus with different parameters. This will show that double encryption is equal to single encryption.

Let $p$ is the modulus, $(e_1,p)$ and $(d_1,p)$ be corresponding pairs and $(e_2,p)$ and $(d_2,p)$ be another pair. Let encrypt a message $m$ with the first public key then with the second.

$$c_1 = m^{e_1} \pmod p$$ then
  $$c_2 = c_1^{e_2} = (m^{e_1})^{e_2} = m^{e_1 \cdot e_2} \bmod p$$

Let call $e' = e_1 \cdot e_2 \pmod{\varphi(p)}$ and $d = e'^{-1} \pmod{\varphi(p)}$

Therefore $(e',d')$ will be the single key for the double encryption

Example:

Continue the previous example with $(31,3001)$ and $(871,3001)$ as second public and private keys.

$$2778^{31} \equiv 197 \pmod{3001}$$

$$e' = 31*37 \equiv 1147 \pmod{3000}$$

$$d' = 1483 \pmod{3000}$$

Now, decrypt with $d'$

$$ 197^{1483} \equiv 57 \pmod{3001}$$



Some notes on Pohlig-Hellman Cipher


It is vulnerable to KPA.
It is not IND-CPA secure
It is Multiplicative
No probabilistic Encryption.
Security relies on the discrete logarithm
The prime $p$ must be chosen properly, safe prime*, against Pohlig-Hellmans' algorithm for finding a discrete log.




*A safe prime is a prime number of the form 2p + 1, where p is also a prime