World Library  
Flag as Inappropriate
Email this Article

Okamoto–Uchiyama cryptosystem

Article Id: WHEBN0007503084
Reproduction Date:

Title: Okamoto–Uchiyama cryptosystem  
Author: World Heritage Encyclopedia
Language: English
Subject: Paillier cryptosystem, Computational hardness assumption, Cryptography public-key, Homomorphic encryption, Benaloh cryptosystem
Publisher: World Heritage Encyclopedia

Okamoto–Uchiyama cryptosystem

The Okamoto–Uchiyama cryptosystem was discovered in 1998 by Tatsuaki Okamoto and Shigenori Uchiyama. The system works in the multiplicative group of integers modulo n, (\mathbb{Z}/n\mathbb{Z})^*, where n is of the form p2q and p and q are large primes.


  • Scheme definition 1
    • Key generation 1.1
    • Message encryption 1.2
    • Message decryption 1.3
  • How the system works 2
  • Security 3
  • References 4

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 p2q, 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}/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 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

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

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^p \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.


  • Okamoto, Tatsuaki; Uchiyama, Shigenori (1998). "A new public-key cryptosystem as secure as factoring". Advances in Cryptology — EUROCRYPT'98.  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.