Okamoto-Uchiyama cryptosystem

From Wikipedia, the free encyclopedia

The Okamoto-Uchiyama Cryptosystem was discovered in 1998 by T. Okamoto and S. Uchiyama. The system works in the group $(\mathbb{Z}/n\mathbb{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.

1 Scheme Definition
2 How The System Works
3 Security
4 References

[edit] Scheme Definition

Like many public key cryptosystems, this scheme works in the group $(\mathbb{Z}/n\mathbb{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.

[edit] 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}/n\mathbb{Z})^*$ such that g has order (p-1)p in the subgroup $(\mathbb{Z}/p^2\mathbb{Z})^*$ .
Let h=gⁿ mod n.

The public key is then (n,g,h) and the private key is the factors (p,q).

[edit] Message Encryption

To encrypt a message m, where m is taken to be an element in $\mathbb{Z}/p\mathbb{Z}$

Select $r \in \mathbb{Z}/n\mathbb{Z}$ at random.

Set

$C = g^m h^r \mod n$

[edit] Message Decryption

If we define $L(x) = \frac{x-1}{p}$ , then decryption becomes

$m = \frac{L\left(C^{p-1} \mod p^2\right)}{L\left(g^{p-1} \mod p^2 \right)} \mod p$

[edit] How The System Works

The group

$(\Z/n\Z)^* \simeq (\mathbb{Z}/p^2\mathbb{Z})^* \times (\mathbb{Z}/q\mathbb{Z})^*$ .

The group $(\mathbb{Z}/p^2\mathbb{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^2\mathbb{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}/p\mathbb{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 \right) }{L(g^{p-1})} = m \mod p$ .

[edit] Security

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