Okamoto Uchiyama cryptosystem

The Okamoto-Uchiyama cryptosystem is a semantically secure , asymmetric encryption algorithm . It was first presented in 1998 by Tatsuaki Okamoto and Shigenori Uchiyama at Eurocrypt , one of the largest annual cryptography conferences . The method is additive-homomorphic, which means that the plain texts are added by multiplying two key texts. It is therefore not necessary to decrypt the key texts in order to be able to operate on the plain texts.

Procedure

Like many asymmetric encryption methods, the Okamoto-Uchiyama cryptosystem works in a group . However, in contrast to other methods, e.g. B. RSA , of the form where are large prime numbers . The method is homomorphic and therefore suffers from the problems it entails. ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ ${\displaystyle n}$ ${\displaystyle n=p^{2}q}$ ${\displaystyle p,q}$

Generation of the public and private key

The key pair is generated as follows:

• You generate two prime numbers of the same bit length and set . In practice, it should have at least 1024, but better 1536 or 2048 binary digits . ${\displaystyle p,q}$ ${\displaystyle k}$ ${\displaystyle n=p^{2}q}$ ${\displaystyle n}$
• One randomly chooses in so that there is order . ${\displaystyle g}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ ${\displaystyle g_{p}=g^{p-1}{\bmod {p}}^{2}}$ ${\displaystyle p}$
• One defines ${\displaystyle h=g^{n}{\bmod {n}}}$

The public key consists of , the private key consists of . ${\displaystyle (n,g,h,k)}$ ${\displaystyle (p,q)}$

Encrypt messages

To encrypt a message with , proceed as follows: ${\displaystyle m}$ ${\displaystyle 0<m<2^{k-1}}$

• First you choose a random one . ${\displaystyle r\in \mathbb {Z} /n\mathbb {Z} }$
• The encrypted message is then given through . ${\displaystyle c=g^{m}h^{r}{\bmod {n}}}$

Decrypting messages (decoding)

To decrypt, you first define the function . Then the original message is obtained as follows: ${\displaystyle L(x)={\frac {x-1}{p}}}$

• One defines . ${\displaystyle c_{p}=c^{p-1}{\bmod {p}}^{2}}$
• One sets . ${\displaystyle m={\frac {L\left(c_{p}\right)}{L\left(g_{p}\right)}}{\bmod {p}}}$

In the last step it should be noted that the division must be carried out modulo , i. i.e., by multiplying by the multiplicative inverse . The division in the calculation of is carried out over the whole numbers. ${\displaystyle p}$ ${\displaystyle L()}$

Correctness of the Okamoto-Uchiyama cryptosystem

For an odd prime number , the p-group of is defined as ${\displaystyle p}$ ${\displaystyle (\mathbb {Z} /p^{2}\mathbb {Z} )^{*}}$

${\displaystyle \Gamma =\left\{x\in (\mathbb {Z} /p^{2}\mathbb {Z} )^{*}:x\equiv 1\mod p\right\}}$.

That is, contains exactly those elements of which yield 1 when divided by the remainder. ${\displaystyle \Gamma }$ ${\displaystyle (\mathbb {Z} /p^{2}\mathbb {Z} )^{*}}$ ${\displaystyle p}$

One then defines the logarithmic function on the elements of as ${\displaystyle L}$ ${\displaystyle \Gamma }$

${\displaystyle L(x)={\frac {x-1}{p}}}$.

This value is always an integer, since it applies to all that . ${\displaystyle x\in \Gamma }$ ${\displaystyle x-1\equiv 0\mod p}$

The task now is: . ${\displaystyle L(xy\mod p^{2})=L(x)+L(y)\mod p}$

Proof :

${\displaystyle {\begin{aligned}L(xy\mod p^{2})&={\frac {xy-1}{p}}\mod p\\&={\frac {(x-1)(y-1)+(x-1)+(y-1)}{p}}\mod p\\&={\frac {x-1}{p}}(y-1)+{\frac {x-1}{p}}+{\frac {y-1}{p}}\mod p\\&=L(x)(y-1)+L(x)+L(y)\mod p\\&=L(x)+L(y)\mod p\end{aligned}}}$

The first equation is true because of . The last equation holds because after the above observation holds. ${\displaystyle L(xy)={\frac {xy-1\mod p^{2}}{p}}={\frac {xy-1}{p}}\mod p}$ ${\displaystyle y-1=0\mod p}$

If it holds for one that , and furthermore is for one , one also obtains ${\displaystyle x}$ ${\displaystyle L(x)\neq 0\mod p}$ ${\displaystyle y=x^{m}\mod p^{2}}$ ${\displaystyle m\in (\mathbb {Z} /p\mathbb {Z} )^{*}}$

${\displaystyle m={\frac {L(y)}{L(x)}}\mod p}$.

This is the reason for the name logarithmic function , since the discrete logarithm of in basis is calculated. ${\displaystyle y}$ ${\displaystyle x}$

Proof : This follows trivially from the previous property, because and holds. ${\displaystyle L(y)=L(x^{m}\mod p^{2})=L(x)+\dots +L(x)=mL(x)\mod p}$ ${\displaystyle 0\leq m<p}$

The overall correctness of the procedure follows from this, that is

${\displaystyle m'={\frac {L\left(c_{p}\right)}{L\left(g_{p}\right)}}\mod p}$

actually matches the original message . ${\displaystyle m}$

Proof : We observe first that

${\displaystyle (g^{m}h^{r})^{p-1}=(g^{m}g^{nr})^{p-1}=(g^{p-1})^{m}g^{p(p-1)rq}=(g^{p-1})^{m}\mod p^{2}}$,

where Lagrange's theorem was used for the last equation . We then get:

${\displaystyle m'={\frac {L\left(c_{p}\right)}{L\left(g_{p}\right)}}={\frac {L\left(c^{p-1}\right)}{L\left(g^{p-1}\right)}}={\frac {L\left((g^{m}h^{r})^{p-1}\right)}{L\left(g^{p-1}\right)}}={\frac {L\left((g^{p-1})^{m}\right)}{L\left(g^{p-1}\right)}}=m\mod p}$.

It is important here that , and therefore also , was fulfilled, since the prerequisite was a number with a length of k bits. ${\displaystyle 0<m<2^{k-1}}$ ${\displaystyle m<p}$ ${\displaystyle p}$

safety

Under the p subgroup assumption, it can be shown that the method is semantically secure . Inverting the encryption has been proven to be just as complex as factoring the module . ${\displaystyle n}$

Homomorphism properties

As with all homomorphic encryption methods, an attacker can change a ciphertext in such a way that it is decrypted into a plaintext that is related to the original plaintext. For example, be the encryption of an unknown value . Then, by multiplying with the encrypted value, it can be changed very easily by any value : ${\displaystyle c}$ ${\displaystyle m}$ ${\displaystyle g^{\Delta m}}$ ${\displaystyle \Delta m}$

${\displaystyle c'=cg^{\Delta m}\mod n=g^{m}h^{r}g^{\Delta m}\mod n=g^{m+\Delta m}h^{r}\mod n}$.

In a similar way, you can also multiply the unknown plaintext by any factor by exponentiating the ciphertext: ${\displaystyle f}$

${\displaystyle c'=c^{f}\mod n=g^{fm}h^{fr}\mod n=g^{fm}h^{r'}\mod n}$.

However, in order to achieve a reasonable result here (e.g. a doubling of the plain text), it must be guaranteed that the following applies, or even so that the recipient cannot draw any conclusions about the manipulation from the decryption (all correctly encrypted plain texts are allowed according to the regulations it should be bits long at most). ${\displaystyle f\cdot m<p}$ ${\displaystyle f\cdot m<2^{k-1}}$ ${\displaystyle k-1}$

advantages

The homomorphic properties are u. a. exploited in connection with the following applications.

• E-voting : After each eligible voter has encrypted their vote (in the simplest case a 1 for yes , a 0 for no ) and transmitted it to the electoral authority, all key texts are multiplied and the resulting encryption contains the encryption of the total number of yes votes. The result of the election is obtained by decoding. It is important that the party performing the first step does not need to know the secret key, which means that no individual votes can be decrypted.
• eCash
• Zero-knowledge evidence in the Universal Composability Model

disadvantage

Due to the listed homomorphic properties, however, the method is not IND-CCA safe, i. H. not safe under selected ciphertext attacks . Every encryption system that has this security would have to be non-deformable , a property that contradicts homomorphism. In the literature one also finds transformations to transform the system into an IND-CCA safe variant. Whether these transformations are appropriate or not depends on the particular application.

Complete example

The steps outlined above are illustrated here using a small example.

Key generation

First, two secret prime numbers are chosen, for example and . Both have 10 bits in binary representation, i.e. h., it is . This also results in: ${\displaystyle p=1.019}$ ${\displaystyle q=883}$ ${\displaystyle k=10}$

• ${\displaystyle n=p^{2}\cdot q=916.872.763}$

The random, appropriate choice of supplies ${\displaystyle g}$

• ${\displaystyle g=332.706}$
• ${\displaystyle g_{p}=g^{p-1}\mod p^{2}=899.778}$, where and applies. ${\displaystyle g_{p}^{p}=1\mod n}$ ${\displaystyle g^{p}\neq 1\mod p^{2}}$
• ${\displaystyle h=g^{n}\mod n=344.141.213}$

The public key is given by: ${\displaystyle (n,g,h,k)=(916.872.763,332.706,344.141.213,10).}$

The secret key is . ${\displaystyle (p,q)=(1.019,883)}$

Preliminary work

In a first step, the text to be encrypted must be translated into numbers smaller than the number . To do this, we simply replace each letter with its position in the alphabet: ${\displaystyle 2^{k-1}=2^{9}=512}$

A=01 B=02 C=03 usw. (00 = Leerzeichen)

We now encrypt each character individually, since two consecutive letters u. U. could deliver too great a value.

Klartext:  O  U  K
Kodierung: 15 21 11

Encryption

We have three plaintexts to encrypt ( , and ), for each of which we need one. ${\displaystyle m_{1}=15}$ ${\displaystyle m_{2}=21}$ ${\displaystyle m_{3}=11}$ ${\displaystyle r_{i}}$

r1 = 523.423.432
r2 =  43.412.311
r3 = 633.186.663

The encryptions thus result in: ${\displaystyle c_{i}}$

ci = gmihri mod n
c1 = 33270615 344141213523423432 mod 916872763 = 289652071
c2 = 423840839
c3 = 684226192

Decryption

We can decipher the messages by:

mi = L(cip-1 mod p2) / L(gp) mod p

It is important here that the division is carried out. We therefore calculate the multiplicative inverse of modulo using the extended Euclidean algorithm and thus obtain . This results in the decryption to: ${\displaystyle \mod p}$ ${\displaystyle L(g_{p})}$ ${\displaystyle p}$ ${\displaystyle L(g_{p})^{-1}=502\mod p}$

m1 = L(2896520711018 mod 1038361) * 502 mod 1019 = 15
m2 = 21
m3 = 11

By inverting the substitution rule , these values ​​can now be translated back into letters.

swell

1. ↑ Tatsuako Okamoto and Shigenori Uchiyama: A new public-key cryptosystem as secure as factoring (English) . In: Eurocrypt 98 , Springer Verlag, 1998, pp. 308-318.  ( Page no longer available , search in web archives ) 
2. ↑ Eiichiro Fujisaki and Tatsuako Okamoto: How to Enhance the Security of Public-Key Encryption at Minimum Cost (English) . In: PKC 99 , Springer Verlag, 1999, pp. 53-68.  ( Page no longer available , search in web archives ) 
3. ↑ Pascal Paillier and David Pointcheval: Efficient Public-Key Cryptosystems provably Secure Against Active Adversaries (English) . In: ASIACRYPT 99 , Springer Verlag, 1999, pp. 165-179.  ( Page no longer available , search in web archives )