Okamoto–Uchiyama cryptosystem

The Okamoto–Uchiyama cryptosystem was discovered in 1998 by Tatsuaki Okamoto and Shigenori Uchiyama. The system works in the multiplicative group of integers modulo n, $({\mathbb {Z}}/n{\mathbb {Z}})^{*}$, where n is of the form p²q and p and q are large primes.

Scheme definition

Like many public key cryptosystems, this scheme works in the group $({\mathbb {Z}}/n{\mathbb {Z}})^{*}$. A fundamental difference of this cryptosystem is that here n is a of the form p²q, where p and q are large primes. This scheme is homomorphic and hence malleable.

Key generation

A public/private key pair is generated as follows:

• Generate large primes p and q and set $n=p^{2}q$.
• Choose $g\in ({\mathbb {Z}}/n{\mathbb {Z}})^{*}$ such that ${\displaystyle g^{p-1}\neq 1\mod p^{2}}$.
• Let h = gⁿ mod n.

The public key is then (n, g, h) and the private key is the factors (p, q).

Message encryption

To encrypt a message m, where m is taken to be an element in $2^{k-1}$

• Select $r\in {\mathbb {Z}}/n{\mathbb {Z}}$ at random. Set

$C=g^{m}h^{r}\mod n$

Message decryption

If we define $L(x)={\frac {x-1}{p}}$, then decryption becomes

$m={\frac {L\left(C^{{p-1}}\mod p^{2}\right)}{L\left(g^{{p-1}}\mod p^{2}\right)}}\mod p$

How the system works

The group

$(\mathbb{Z } /n\mathbb{Z } )^{*}\simeq ({\mathbb {Z}}/p^{2}{\mathbb {Z}})^{*}\times ({\mathbb {Z}}/q{\mathbb {Z}})^{*}$.

The group $({\mathbb {Z}}/p^{2}{\mathbb {Z}})^{*}$ has a unique subgroup of order p, call it H. By the uniqueness of H, we must have

$H=\{x:x^{p}\equiv 1\mod p\}$.

For any element x in $({\mathbb {Z}}/p^{2}{\mathbb {Z}})^{*}$, we have x^p−1 mod p² is in H, since p divides x^p−1 − 1.

The map L should be thought of as a logarithm from the cyclic group H to the additive group ${\mathbb {Z}}/p{\mathbb {Z}}$, and it is easy to check that L(ab) = L(a) + L(b), and that the L is an isomorphism between these two groups. As is the case with the usual logarithm, L(x)/L(g) is, in a sense, the logarithm of x with base g.

We have

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

So to recover m we just need to take the logarithm with base g^p−1, which is accomplished by

${\frac {L\left((g^{{p-1}})^{m}\right)}{L(g^{{p-1}})}}=m\mod p.$

Security

The security of the entire message can be shown to be equivalent to factoring n. The semantic security rests on the p-subgroup assumption, which assumes that it is difficult to determine whether an element x in $({\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

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