Article provided by Wikipedia

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, ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$, where n is of the form p2q and p and q are large "primes.

## Scheme definition

Like many "public key cryptosystems, this scheme works in the group ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$. A fundamental difference of this cryptosystem is that here n is an integer of the form p2q, 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 ${\displaystyle n=p^{2}q}$.
• Choose ${\displaystyle g\in (\mathbb {Z} /n\mathbb {Z} )^{*}}$ such that ${\displaystyle g^{p-1}\neq 1\mod p^{2}}$.
• Let h = gn mod n.

The public key is then (ngh) and the private key is the factors (pq).

### Message encryption

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

• Select ${\displaystyle r\in \mathbb {Z} /n\mathbb {Z} }$ at random. Set
${\displaystyle C=g^{m}h^{r}\mod n}$

### Message decryption

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

${\displaystyle 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

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

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

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

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

The map L should be thought of as a logarithm from the cyclic group H to the additive group ${\displaystyle \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

${\displaystyle (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 gp−1, which is accomplished by

${\displaystyle {\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 ${\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

) ) WikipediaAudio is not affiliated with Wikipedia or the WikiMedia Foundation.