The Okamoto–Uchiyama cryptosystem was discovered in 1998 by T. Okamoto and S. Uchiyama. The system works in the group , where n is of the form p^{2}q and p and q are large primes.
Scheme definition[]
Like many public key cryptosystems, this scheme works in the group . A fundamental difference of this cryptosystem is that here n is a of the form p^{2}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 two bits primes p and q and set .
 Choose such that and .
 Let h = g^{n} mod n.
The public key is then (n, g, h, k) and the private key is the factors (p, q).
Message encryption[]
To encrypt a message m, where m is taken to be an integer and
 Select at random. Set
Message decryption[]
If we define , then decryption becomes
How the system works[]
The group
 .
The group has a unique subgroup of order p, call it H. By the uniqueness of H, we must have
 .
For any element x in , we have x^{p−1} mod p^{2} 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 , 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
So to recover m we just need to take the logarithm with base g^{p−1}, which is accomplished by
Security[]
The security of the entire message can be shown to be equivalent to factoring n. The semantic security rests on the psubgroup assumption, which assumes that it is difficult to determine whether an element x in is in the subgroup of order p. This is very similar to the quadratic residuosity problem and the higher residuosity problem.
References[]
External links[]
