Cryptosystem Okamoto - Utiyama

The Okamoto and Utiyama cryptosystem is a probabilistic cryptosystem proposed in 1998 by Tatsuaki Okamoto and Shinegori Utiyama. This cryptosystem is based on a logarithmic function $L$ ${\ displaystyle L}$ $L$ defined over the multiplicative group $\mathbb {(} {Z}/n\mathbb {Z} )^{*}$ ${\ displaystyle \ mathbb {(} {Z} / n \ mathbb {Z}) ^ {*}}$ ${\ displaystyle \ mathbb {(} {Z} / n \ mathbb {Z}) ^ {*}}$ where $n=p^{2}q$ ${\ displaystyle n = p ^ {2} q}$ ${\ displaystyle n = p ^ {2} q}$ , but $p$ ${\ displaystyle p}$ $p$ and $q$ ${\ displaystyle q}$ $q$ are large primes.

For example, if $p$ ${\ displaystyle p}$ $p$ - a large prime number and $\gamma _{p}\subset \mathbb {Z_{p^{2}}^{n}}$ ${\ displaystyle \ gamma _ {p} \ subset \ mathbb {Z_ {p ^ {2}} ^ {n}}}$ ${\ displaystyle \ gamma _ {p} \ subset \ mathbb {Z_ {p ^ {2}} ^ {n}}}$ such that { ${\displaystyle \gamma _{p}={x<semantics><mrow class=$ ${\ displaystyle \ gamma _ {p} = {x <p ^ {2} \ mid x = 1 {\ bmod {p}}}}$ ${\ displaystyle \ gamma _ {p} = {x <p ^ {2} \ mid x = 1 {\ bmod {p}}}}$ } then $\gamma _{p}$ ${\ displaystyle \ gamma _ {p}}$ ${\ displaystyle \ gamma _ {p}}$ has a group structure with respect to the multiplicative module $p^{2}$ ${\ displaystyle p ^ {2}}$ ${\ displaystyle p ^ {2}}$ . Function $\log(.):\gamma _{p}\longrightarrow Z_{p}$ ${\ displaystyle \ log (.): \ gamma _ {p} \ longrightarrow Z_ {p}}$ ${\ displaystyle \ log (.): \ gamma _ {p} \ longrightarrow Z_ {p}}$ connecting ${\frac {x-1}{p}}$ ${\ displaystyle {\ frac {x-1} {p}}}$ ${\ displaystyle {\ frac {x-1} {p}}}$ with $x$ ${\ displaystyle x}$ $x$ defined on $n=p^{2}q$ ${\ displaystyle n = p ^ {2} q}$ ${\ displaystyle n = p ^ {2} q}$ and has homomorphic properties, and in particular:

${\forall x,y\in \gamma _{p}}$ ${\ displaystyle {\ forall x, y \ in \ gamma _ {p}}}$ ${\ displaystyle {\ forall x, y \ in \ gamma _ {p}}}$ ${\log(xy{\bmod {p}}^{2})=\log(x)+\log(y){\bmod {p}}}$ ${\ displaystyle {\ log (xy {\ bmod {p}} ^ {2}) = \ log (x) + \ log (y) {\ bmod {p}}}}$ ${\ displaystyle {\ log (xy {\ bmod {p}} ^ {2}) = \ log (x) + \ log (y) {\ bmod {p}}}}$

Or, summarizing:

${\forall g\in \gamma _{p},m\in Z_{p}}$ ${\ displaystyle {\ forall g \ in \ gamma _ {p}, m \ in Z_ {p}}}$ ${\ displaystyle {\ forall g \ in \ gamma _ {p}, m \ in Z_ {p}}}$ ${\log(g^{m}{\bmod {p}}^{2})=m\log(g){\bmod {p}}}$ ${\ displaystyle {\ log (g ^ {m} {\ bmod {p}} ^ {2}) = m \ log (g) {\ bmod {p}}}}$ ${\ displaystyle {\ log (g ^ {m} {\ bmod {p}} ^ {2}) = m \ log (g) {\ bmod {p}}}}$

Algorithm Description

Key Generation

Two large different prime numbers are chosen. $p$ ${\ displaystyle p}$ $p$ and $q$ ${\ displaystyle q}$ $q$ and is calculated $n=p^{2}q$ ${\ displaystyle n = p ^ {2} q}$ $n=p^{2}q$ ;
Number is selected $g\in ({\mathbb {Z} }/n{\mathbb {Z} })^{*}$ ${\ displaystyle g \ in ({\ mathbb {Z}} / n {\ mathbb {Z}}) ^ {*}}$ $g\in ({\mathbb {Z} }/n{\mathbb {Z} })^{*}$ such that ${g^{p-1}\neq 1\mod p^{2}}$ ${\ displaystyle {g ^ {p-1} \ neq 1 \ mod p ^ {2}}}$ ${g^{p-1}\neq 1\mod p^{2}}$ ;
Calculated ${h=g^{n}{\bmod {n}}}$ ${\ displaystyle {h = g ^ {n} {\ bmod {n}}}}$ ${h=g^{n}{\bmod {n}}}$

In this way, $(n,g,h)$ ${\ displaystyle (n, g, h)}$ $(n,g,h)$ - public key , $(p,q)$ ${\ displaystyle (p, q)}$ $(p,q)$ - secret key .

Encryption

To encrypt a k-bit message $m$ ${\ displaystyle m}$ $m$ where ${0<m<2^{k-1}}$ ${\ displaystyle {0 <m <2 ^ {k-1}}}$ ${0<m<2^{k-1}}$ :

Random selected ${r\in {\mathbb {Z} }/n{\mathbb {Z} }}$ ${\ displaystyle {r \ in {\ mathbb {Z}} / n {\ mathbb {Z}}}}$ ${r\in {\mathbb {Z} }/n{\mathbb {Z} }}$ ;
The ciphertext is calculated: ${C=g^{m}h^{r}{\bmod {n}}}$ ${\ displaystyle {C = g ^ {m} h ^ {r} {\ bmod {n}}}}$ ${C=g^{m}h^{r}{\bmod {n}}}$

Decryption

We denote $L(x)={\frac {x-1}{p}}$ ${\ displaystyle L (x) = {\ frac {x-1} {p}}}$ $L(x)={\frac {x-1}{p}}$ . Thus decrypting the message $C$ ${\ displaystyle C}$ $C$ :

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

Cryptosystem Properties

Homomorphism

The cryptosystem is additively homomorphic , since when ${\displaystyle {m_{1}+m_{2}<semantics><mrow class=$ ${\ displaystyle {m_ {1} + m_ {2} <p}}$ performed:

${{\mathcal {E}}(m_{1})\cdot {\mathcal {E}}(m_{2})=(g^{m_{1}}r_{1}^{c})(g^{m_{2}}r_{2}^{c}){\bmod {n}}=g^{m_{1}+m_{2}}(r_{1}r_{2})^{c}{\bmod {=}}{\mathcal {E}}(m_{1}+m_{2})}$ ${\ displaystyle {{\ mathcal {E}} (m_ {1}) \ cdot {\ mathcal {E}} (m_ {2}) = (g ^ {m_ {1}} r_ {1} ^ {c} ) (g ^ {m_ {2}} r_ {2} ^ {c}) {\ bmod {n}} = g ^ {m_ {1} + m_ {2}} (r_ {1} r_ {2}) ^ {c} {\ bmod {=}} {\ mathcal {E}} (m_ {1} + m_ {2})}}$ where ${{\mathcal {E}}(m)}$ ${\ displaystyle {{\ mathcal {E}} (m)}}$ is a message encryption function $m$ ${\ displaystyle m}$ .

Persistence

The strength of the cryptosystem Okamoto and Utiyama is based on the problem of factoring the number $n$ ${\ displaystyle n}$ and asks $O(\log _{3}n)$ ${\ displaystyle O (\ log _ {3} n)}$ bit operations.

Decryption Reduction Method

To lower the complexity of the circuit to $O(\log _{2}n)$ ${\ displaystyle O (\ log _ {2} n)}$ , can choose $p$ ${\ displaystyle p}$ through a large (160-bit) coefficient $t$ ${\ displaystyle t}$ as follows ^[1] : ${p-1=tu}$ ${\ displaystyle {p-1 = tu}}$ and modify the circuit as follows:

Choose an arbitrary number $g<n$ ${\ displaystyle g <n}$ such that ${g_{p}=g^{(p-1)}{\bmod {p}}^{2}}$ ${\ displaystyle {g_ {p} = g ^ {(p-1)} {\ bmod {p}} ^ {2}}}$
Calculate ${G=g^{u}{\bmod {n}}}$ ${\ displaystyle {G = g ^ {u} {\ bmod {n}}}}$
Choose an arbitrary number $g^{\prime }<n$ ${\ displaystyle g ^ {\ prime} <n}$ and calculate ${H={g^{\prime }}^{nu}{\bmod {n}}}$ ${\ displaystyle {H = {g ^ {\ prime}} ^ {nu} {\ bmod {n}}}}$

Then the three values ${(n,G,H)}$ ${\ displaystyle {(n, G, H)}}$ forms a public key, and ${(p,q)}$ ${\ displaystyle {(p, q)}}$ - The secret key.

Encryption:

Randomly select a number $r<n$ ${\ displaystyle r <n}$
Decrypt ${(k-1)}$ ${\ displaystyle {(k-1)}}$ bit message $m$ ${\ displaystyle m}$ in the following way: ${c=G^{m}H^{r}{\bmod {n}}}$ ${\ displaystyle {c = G ^ {m} H ^ {r} {\ bmod {n}}}}$ .

Decryption:

${c^{\prime }=c^{t}{\bmod {p}}^{2}=g^{m(p-1)}g^{\prime nr(p-1)}=g_{p}^{m}{\bmod {p}}^{2}}$ ${\ displaystyle {c ^ {\ prime} = c ^ {t} {\ bmod {p}} ^ {2} = g ^ {m (p-1)} g ^ {\ prime nr (p-1)} = g_ {p} ^ {m} {\ bmod {p}} ^ {2}}}$ ;
${m=\log(c^{\prime })\log(g_{p})^{-1}{\bmod {p}}}$ ${\ displaystyle {m = \ log (c ^ {\ prime}) \ log (g_ {p}) ^ {- 1} {\ bmod {p}}}}$ .

Notes

↑ Accelerating Okamoto-Uchiyama's Public-Key Cryptosystem (Jean-S´ebastien Coron, David Naccache, Pascal Paillier)

Literature

Okamoto, Tatsuaki; Uchiyama, Shigenori (1998). "A new public-key cryptosystem as secure as factoring." Advances in Cryptology - EUROCRYPT'98.
Accelerating Okamoto-Uchiyama's Public-Key Cryptosystem (Jean-S´ebastien Coron, David Naccache, Pascal Paillier)

[1] Accelerating Okamoto-Uchiyama's Public-Key Cryptosystem (Jean-S´ebastien Coron, David Naccache, Pascal Paillier)