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, , where n is of the form p^{2}q and p and q are large "primes.
Like many "public key cryptosystems, this scheme works in the group . A fundamental difference of this cryptosystem is that here n is an integer of the form p^{2}q, where p and q are large "primes. This scheme is "homomorphic and hence "malleable.
A public/private key pair is generated as follows:
The public key is then (n, g, h) and the private key is the factors (p, q).
To encrypt a message m, where m is taken to be an element in
If we define , then decryption becomes
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
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 is in the subgroup of order p. This is very similar to the "quadratic residuosity problem and the "higher residuosity problem.