Contents

Okamoto–Uchiyama cryptosystem

Let ${\displaystyle p}$ be an odd prime. Define ${\displaystyle \Gamma =\{x\in (\mathbb {Z} /p^{2}\mathbb {Z} )^{*}|x\equiv 1{\bmod {p}}\}}$. ${\displaystyle \Gamma }$ is a subgroup of ${\displaystyle (\mathbb {Z} /p^{2}\mathbb {Z} )^{*}}$ with ${\displaystyle |\Gamma |=p}$ (the elements of ${\displaystyle \Gamma }$ are ${\displaystyle 1,1+p,1+2p\dots 1+(p-1)p}$).

Define ${\displaystyle L:\Gamma \to \mathbb {Z} /p\mathbb {Z} }$by${\displaystyle L($x)={\frac {x-1}{p}}}

${\displaystyle L}$ is a homomorphism between ${\displaystyle \Gamma }$ and the additive group ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$: that is, ${\displaystyle L($ab)=L(a)+L(b){\bmod {p}}} . Since ${\displaystyle L}$ is bijective, it is an isomorphism.

One can now show the following as a corollary:

Let ${\displaystyle x\in \Gamma }$ such that ${\displaystyle L($x)\neq 0{\bmod {p}}} and ${\displaystyle y=x^{m}{\bmod {p}}^{2}}$ for ${\displaystyle 0\leq m<p}$. Then

${\displaystyle m={\frac {L($y)}{L(x)}}={\frac {y-1}{x-1}}{\bmod {p}}}

The corollary is a direct consequence of ${\displaystyle L(x^{m})=m\cdot L($x)} .

Operation[edit]

Like many public key cryptosystems, this scheme works in the group ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$. This scheme is homomorphic and hence malleable.

Key generation[edit]

A public/private key pair is generated as follows:

1. Generate two large primes ${\displaystyle p}$ and ${\displaystyle q}$.
2. Compute ${\displaystyle n=p^{2}q}$.
3. Choose a random integer ${\displaystyle g\in \{2\dots n-1\}}$ such that ${\displaystyle g^{p-1}\not \equiv 1\mod p^{2}}$.
4. Compute ${\displaystyle h=g^{n}{\bmod {n}}}$.

The public key is then ${\displaystyle (n,g,h)}$ and the private key is ${\displaystyle (p,q)}$.

Encryption[edit]

A message ${\displaystyle m<p}$ can be encrypted with the public key ${\displaystyle (n,g,h)}$ as follows.

1. Choose a random integer ${\displaystyle r\in \{1\dots n-1\}}$.
2. Compute ${\displaystyle c=g^{m}h^{r}{\bmod {n}}}$.

The value ${\displaystyle c}$ is the encryption of ${\displaystyle m}$.

Decryption[edit]

An encrypted message ${\displaystyle c}$ can be decrypted with the private key ${\displaystyle (p,q)}$ as follows.

1. Compute ${\displaystyle a=L(c^{p-1}{\bmod {p^{2}}})}$.
2. Compute ${\displaystyle b=L(g^{p-1}{\bmod {p^{2}}})}$. ${\displaystyle a}$ and ${\displaystyle b}$ will be integers.
3. Using the Extended Euclidean Algorithm, compute the inverse of ${\displaystyle b}$ modulo ${\displaystyle p}$:

   ${\displaystyle b'=b^{-1}{\bmod {p}}}$.

4. Compute ${\displaystyle m=ab'{\bmod {p}}}$.

The value ${\displaystyle m}$ is the decryption of ${\displaystyle c}$.

Example[edit]

Let ${\displaystyle p=3}$ and ${\displaystyle q=5}$. Then ${\displaystyle n=3^{2}\cdot 5=45}$. Select ${\displaystyle g=22}$. Then ${\displaystyle h=22^{45}{\bmod {4}}5=37}$.

Now to encrypt a message ${\displaystyle m=2}$, we pick a random ${\displaystyle r=13}$ and compute ${\displaystyle c=g^{m}h^{r}{\bmod {n}}=22^{2}37^{13}{\bmod {4}}5=43}$.

To decrypt the message 43, we compute

${\displaystyle a={\frac {(43^{2}{\bmod {3}}^{2})-1}{3}}=1}$.

${\displaystyle b={\frac {(22^{2}{\bmod {3}}^{2})-1}{3}}=2}$.

${\displaystyle b'=2^{-1}{\bmod {3}}=2}$.

And finally ${\displaystyle m=ab'=2}$.

Proof of correctness[edit]

We wish to prove that the value computed in the last decryption step, ${\displaystyle ab'{\bmod {p}}}$, is equal to the original message ${\displaystyle m}$. We have

${\displaystyle (g^{m}h^{r})^{p-1}\equiv (g^{m}g^{nr})^{p-1}\equiv (g^{p-1})^{m}g^{p(p-1)rpq}\equiv (g^{p-1})^{m}\mod p^{2}}$

So to recover ${\displaystyle m}$ we need to take the discrete logarithm with base ${\displaystyle g^{p-1}}$. This can be done by applying ${\displaystyle L}$, as follows.

ByFermat's little theorem, ${\displaystyle g^{p-1}\equiv 1{\bmod {p}}}$. Since ${\displaystyle g^{p-1}\not \equiv 1{\bmod {p}}^{2}}$ one can write ${\displaystyle g^{p-1}=1+pr}$ with ${\displaystyle 0<r<p}$. Then ${\displaystyle L(g^{p-1})\not \equiv 0{\bmod {p}}}$ and the corollary from earlier applies: ${\displaystyle m={\frac {L((g^{p-1})^{m})}{L(g^{p-1})}}{\bmod {p}}}$.

Security[edit]

Inverting the encryption function can be shown to be as hard as factoring n, meaning that if an adversary could recover the entire message from the encryption of the message they would be able to factor n. The semantic security (meaning adversaries cannot recover any information about the message from the encryption) rests on the p-subgroup assumption, which assumes that it is difficult to determine whether an element xin${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ is in the subgroup of order p. This is very similar to the quadratic residuosity problem and the higher residuosity problem.

References[edit]

• Okamoto, Tatsuaki; Uchiyama, Shigenori (1998). "A new public-key cryptosystem as secure as factoring". Advances in Cryptology – EUROCRYPT'98. Lecture Notes in Computer Science. Vol. 1403. Springer. pp. 308–318. doi:10.1007/BFb0054135. ISBN 978-3-540-64518-4.