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

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.

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-1}\neq 1\mod p^{2}$ .
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 $2^{k-1}$

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

(\mathbb{Z } /n\mathbb{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 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^{m}h^{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.

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.

References

Okamoto, Tatsuaki; Uchiyama, Shigenori (1998). "A new public-key cryptosystem as secure as factoring". Advances in Cryptology — EUROCRYPT'98. Lecture Notes in Computer Science. 1403. Springer. pp. 308–318. doi:10.1007/BFb0054135.

Public-key cryptography

Algorithms

Integer Factorization	Benaloh Blum–Goldwasser Cayley–Purser Damgård–Jurik GMR Goldwasser–Micali Paillier Rabin RSA Okamoto–Uchiyama Schmidt–Samoa

Discrete logarithm	Cramer–Shoup DH DSA ECDH ECDSA EdDSA EKE ElGamal signature scheme MQV Schnorr SPEKE SRP STS

Others	AE CEILIDH EPOC HFE IES Lamport McEliece Merkle–Hellman Naccache–Stern Naccache–Stern knapsack cryptosystem NTRUEncrypt NTRUSign Three-pass protocol XTR

Theory

Standardization

Topics

Cryptography

History of cryptography Cryptanalysis Outline of cryptography

Symmetric-key algorithm Block cipher Stream cipher Public-key cryptography Cryptographic hash function Message authentication code Random numbers Steganography

Category Portal WikiProject

This article is issued from Wikipedia - version of the 5/2/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.