Okamoto-Uchiyama cryptosystem

The Okamoto-Uchiyama Cryptosystem was discovered in 1998 by T. Okamoto and S. Uchiyama. The system works in the group $(mathbb\{Z\}/nmathbb\{Z\})^*$, where "n" is of the form "p"²"q". The Okamoto-Uchiyama cryptosystem is a precursor to the Paillier cryptosystem, but has mostly been replaced by Paillier's system.

cheme Definition

Like many public key cryptosystems, this scheme works in the group $(mathbb\{Z\}/nmathbb\{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\}/nmathbb\{Z\})^*$ such that "g" has order "(p-1)p" in the subgroup $(mathbb\{Z\}/p^2mathbb\{Z\})^*$.
*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 $mathbb\{Z\}/pmathbb\{Z\}$

*Select $r\; in\; mathbb\{Z\}/nmathbb\{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\{Lleft(C^\{p-1\}\; mod\; p^2\; ight)\}\{Lleft(g^\{p-1\}\; mod\; p^2\; ight)\}\; mod\; p$

How The System Works

The group:.The group $(mathbb\{Z\}/p^2mathbb\{Z\})^*$ has a unique subgroup of order "p", call it "H".By the uniqueness of "H", we must have:$H\; =\; \{\; x\; :\; x\; equiv\; 1\; mod\; p\; \}$.For any element "x" in $(mathbb\{Z\}/p^2mathbb\{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\}/pmathbb\{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^mh^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\; ight)\; \}\{L(g^\{p-1\})\}\; =\; m\; mod\; p$.

ecurity

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\}/nmathbb\{Z\})^*$ is in the subgroup of order "p". This is very similar to the quadratic residuosity problem and the higher residuosity problem.

References

* [http://citeseer.ist.psu.edu/context/329970/0 Original Paper]