The Okamoto-Uchiyama cryptosystem is a semantically secure, asymmetric encryption algorithm. It was first introduced in 1998 by Tatsuaki Okamoto and Shigenori Uchiyama. The method is additive-homomorphic, which means that the plaintexts are added by multiplying two ciphertexts. It is therefore not necessary to decrypt the ciphertexts in order to be able to operate on the plaintexts.

While searching for implementations of this algorithm on github, I realized that there were only two rough implementations. One in python and one in Go and that they were only at the state of proof of concept. With this in mind (and also because I was looking for a project to get my hands on in Rust), I decided to write an implementation of this cryptosystem. Which you can find here.

Table of contents:

🔒 The cryptosystem

Generate a key pair

I describe the cryptosystem here in broad brush strokes, but for those who want a more formal definition, you can find the original publication presenting it here.

A public/private key pair is generated as follow:

  1. Generate two large primes $p$ and $q$.
  2. Compute $n=p^{2}q$.
  3. Choose a random integer $g\in {2\dots n-1}$ such that $g^{p-1}\not \equiv 1\mod p^{2}$.
  4. Compute $h=g^{n}{\bmod {n}}$.

The public key is then $(n,g,h)$ and the private key is $(p,q)$.

use num_bigint_dig::BigUint;
use okamoto_uchiyama::{OkamotoUchiyama, PrivateKey, PublicKey};
// Initialization
// In this exemple we use a 1024 bits key
let length = okamoto_uchiyama::key::KeySize::Bits1024;
let okamoto_uchiyama = OkamotoUchiyama::init(length);

// Generate the key pair
let private_key = okamoto_uchiyama.generate_private_key();
let public_key = private_key.public_key.clone();

It is possible to generate keys of 512, 1024, 2048 or 4096 bits using okamoto_uchiyama::key::KeySize::Bits512, okamoto_uchiyama::key::KeySize::Bits1024, okamoto_uchiyama::key::KeySize::Bits2048, okamoto_uchiyama::key::KeySize::Bits4096.

Load existing keys

You can load existing private and public keys

use num_bigint_dig::BigUint;
use okamoto_uchiyama::{OkamotoUchiyama, PrivateKey, PublicKey};

let public_key = PublicKey::new(
    
    &BigUint::from(9432233159u64),
    &BigUint::from(8083706871u64),
    &BigUint::from(7988052977u64),
);
let private_key = PrivateKey::new(
    &public_key,
    &BigUint::from(2003u64),
    &BigUint::from(2351u64),
);

🔑 Encrypt and Decrypt

Encryption

A message $m<p$ can be encrypted with the public key $(n,g,h)$ as follows.

  1. Choose a random integer $r\in {1\dots n-1}$.
  2. Compute $c=g^{m}h^{r}{\bmod {n}}$.

The value $c$ is the encryption of $m$.

Decryption

An encrypted message $c$ can be decrypted with the private key $(p,q)$ as follows.

  1. Compute $a={\frac {(c^{p-1}{\bmod {p^{2}}})-1}{p}}$.
  2. Compute $b={\frac {(g^{p-1}{\bmod {p^{2}}})-1}{p}}$. $a$ and $b$ will be integers.
  3. Using the Extended Euclidean Algorithm to compute the inverse of $b$ modulo $p$: $b'=b^{-1}{\bmod {p}}$.
  4. Compute $m=ab'{\bmod {p}}$.

The value $m$ is the decryption of $c$.

use  num_bigint_dig::BigUint;
use  okamoto_uchiyama::{OkamotoUchiyama,  PrivateKey,  PublicKey};

let  cleartext = BigUint::from(6u64);

// Initialization
let  length = okamoto_uchiyama::key::KeySize::Bits1024;
let  okamoto_uchiyama = OkamotoUchiyama::init(length);

// Generate the key pair
let  private_key = okamoto_uchiyama.generate_private_key();
let  public_key = private_key.public_key.clone();

// Encrypt and decrypt
let  c = OkamotoUchiyama::encrypt(&cleartext,  &public_key);
let  m = OkamotoUchiyama::decrypt(&cleartext,  &private_key);

🧐 Homomorphic ?

Homomorphic encryption is a form of encryption that allows computations to be performed on encrypted data without first having to decrypt it. The resulting computations are left in an encrypted form which, when decrypted, result in an output that is identical to that produced had the operations been performed on the unencrypted data.

A notable feature of the Okamoto-Uchiyama cryptosystem is its homomorphic properties.

However, the Okamoto-Uchiyama only allows Partially homomorphic encryption which means that you can perform additions on encrypted data but not multiplications.

Add two encrypted ciphertexts

Since this scheme makes possible Homomorphic addition of plaintexts, the product of two ciphertexts will decrypt to the sum of their corresponding plaintexts

-> $E(m1) \cdot E(m2) = E(m1 + m2)$

use  num_bigint_dig::BigUint;
use  okamoto_uchiyama::{OkamotoUchiyama,  PrivateKey,  PublicKey};

let  m1  =  BigUint::from(6u64);
let  m2  =  BigUint::from(7u64);

// Initialization
let  length  =  okamoto_uchiyama::key::KeySize::Bits1024;
let  okamoto_uchiyama  =  OkamotoUchiyama::init(length);

// Generate the key pair
let  private_key  =  okamoto_uchiyama.generate_private_key();
let  public_key  =  private_key.public_key.clone();

let  c1  =  OkamotoUchiyama::encrypt(&m1,  &public_key);
let  c2  =  OkamotoUchiyama::encrypt(&m2,  &public_key);

let  c1_c2  =  public_key.homomorphic_encrypt_two(&c1,  &c2).unwrap();
// Result is c1 + c2 = 6 + 7 = 13
let  decrypted_c1_c2  =  OkamotoUchiyama::decrypt(&c1_c2,  &private_key);

Add multiple encrypted ciphertexts

-> $E(m_1) \cdot E(m_2) \cdot … \cdot E(m_n) = E(m_1 + m_2 + … + m_n)$

use  num_bigint_dig::BigUint;
use  okamoto_uchiyama::{OkamotoUchiyama,  PrivateKey,  PublicKey};

let  m1  =  BigUint::from(6u64);
let  m2  =  BigUint::from(7u64);
let  m3  =  BigUint::from(8u64);

// Initialization
let  length  =  okamoto_uchiyama::key::KeySize::Bits1024;
let  okamoto_uchiyama  =  OkamotoUchiyama::init(length);

// Generate the key pair
let  private_key  =  okamoto_uchiyama.generate_private_key();
let  public_key  =  private_key.public_key.clone();

let  c1  =  OkamotoUchiyama::encrypt(&m1,  &public_key);
let  c2  =  OkamotoUchiyama::encrypt(&m2,  &public_key);
let  c3  =  OkamotoUchiyama::encrypt(&m3,  &public_key);

let  c1_c2_c3  =  public_key
	.homomorphic_encrypt_multiple(vec![&c1,  &c2,  &c3])
	.unwrap();
	
// Result is c1 + c2 + c2 = 6 + 7 + 8 = 21
let  decrypted_c1_c2_c3  =  OkamotoUchiyama::decrypt(&c1_c2_c3,  &private_key);

😎 Cool things I discovered while creating this project

Anyone who has implemented a cryptographic algorithm knows that we often work with very large numbers. Therefore I had started to work with the num-bigint library, which worked very well at first. But I discovered this pretty cool fork num-bigint-dig which implement a lot of functions useful in Cryptography such as the modular inverse which I used in my code.

I also came across this pretty cool paper which is a PoC of a voting system using Okamoto Uchiyama’s cryptosystem.