- 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"2"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"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 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=gn" 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:/n)^* simeq (mathbb{Z}/p^2mathbb{Z})^* imes (mathbb{Z}/qmathbb{Z})^*.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 "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 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 "gp-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 thequadratic residuosity problem and thehigher residuosity problem .References
* [http://citeseer.ist.psu.edu/context/329970/0 Original Paper]
Wikimedia Foundation. 2010.