The Okamoto–Uchiyama cryptosystem is a public key cryptosystem proposed 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 p2q and p and q are large primes.
be an odd prime.
mod
and the additive group
mod
{\displaystyle L(ab)=L(a)+L(b){\bmod {p}}}
is bijective, it is an isomorphism.
One can now show the following as a corollary: Let
mod
Then The corollary is a direct consequence of
Like many public key cryptosystems, this scheme works in the group
This scheme is homomorphic and hence malleable.
A public/private key pair is generated as follows: The public key is then
and the private key is
can be encrypted with the public key
An encrypted message
can be decrypted with the private key
Now to encrypt a message
, we pick a random
To decrypt the message 43, we compute And finally
We wish to prove that the value computed in the last decryption step,
, is equal to the original message
we need to take the discrete logarithm with base
This can be done by applying
By Fermat's little theorem,
and the corollary from earlier applies:
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 x in
is in the subgroup of order p. This is very similar to the quadratic residuosity problem and the higher residuosity problem.