Okamoto–Uchiyama cryptosystem

566pages on
this wiki
Add New Page
Talk0 Share

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 p2q and p and q are large primes.

Scheme definitionEdit

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 p2q, where p and q are large primes. This scheme is homomorphic and hence malleable.

Key generationEdit

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^p \neq 1 \mod p^2.
  • Let h = gn mod n.

The public key is then (ngh) and the private key is the factors (pq).

Message encryptionEdit

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

  • Select r \in \mathbb{Z}/n\mathbb{Z} at random. Set
C = g^m h^r \mod n

Message decryptionEdit

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

How the system worksEdit

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 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}/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 gp−1, which is accomplished by

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


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.


External linksEdit

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.