Homomorphic encryption in Clojure

{:deps {org.clojure/clojure {:mvn/version "1.10.1"}

        compliment/compliment {:mvn/version "0.3.9"}}}

Paillier cryptosystem

is a probabilistic asymmetric algorithm for public key cryptography. It was created by Pascal Paillier in 1999. It is an encryption scheme with additive and multiplicative homomorphic properties.

Homomorphic encryption is a form of encryption that permits users to perform computations on encrypted data without first decrypting it. Homomorphic encryption is handy when privacy-preserving is a priority, usually in some form of outsourced storage or computation. For sensitive data, such as health care information, homomorphic encryption can enable new services by removing privacy barriers inhibiting data sharing or increasing security to existing services. 

Unfortunately, fully homomorphic cryptography is still a research topic and unfeasible in practice. For some applications, partial homomorphic cryptosystems are still a possibility. However, it's still limited to one or two algebraic operations. An example of such a cryptosystem is Paillier cryptosystem. Pascal Paillier invented this cryptosystem in 1999. It provides homomorphic addition and multiplication.

Conceptually, Paillier cryptosystem provides the following utilities:

Encryption of plaintext x and decryption of a ciphertext E(x)

Addition of two ciphertexts x, y

Multiplication of a plaintext constant k and a ciphertext x

is a symbol to denote homomorphic addition of two ciphertexts

is a symbol to denote homomorphic multiplication of one plaintext and one ciphertext

Note that the above notation is just my attempt to demonstrate how the cryptosystem works for the user. For formal definition you have to look somewhere else.

(ns fun.clojure.paillier

  (:import [java.math BigInteger]

   [java.security SecureRandom]

   [java.nio.charset StandardCharsets]))

(defn- random-number!

  "Generate a random number from the interval <2, n>"

  [end]

  (let [start (BigInteger/valueOf 2)

        interval (.subtract end start)

        i (BigInteger. (.bitCount interval) (SecureRandom.))]

    (.add start i)))

(defn- L [a n]

  (-> a

    (.subtract BigInteger/ONE)

    (.divide n)))

(defn- lcm [a b]

  (-> a

    (.multiply b)

    (.divide (.gcd a b))))

(defn- square

  "Square of a number"

  [n]

  (.multiply n n))

(defn public-key

  "Define a public key"

  [n g]

  {:n n

   :g g})

(defn private-key

  "Define a private key"

  [lambda mu p q public-key]

  {:lambda lambda

   :mu mu

   :p p

   :q q

   :public-key public-key})

(defn- get-prime!

  "Generate a big prime number with a given amount bits and certainty"

  [bits certainty]

  (BigInteger. (/ bits 2) certainty (SecureRandom.)))

(defn- yield!

  "Helper function. Generate a component of the key pair with improved properties"

  [n]

  (let [nsqr (square n)

        alpha (random-number! n)

        beta (random-number! n)]

    (-> alpha

      (.multiply n)

      (.add BigInteger/ONE)

      (.multiply (.modPow beta n nsqr))

      (.mod nsqr))))

(defn key-pair!

  "Generate a cryptographic pair with a simplified g-parameter. Returns a map with the public and private keys"

  [bits certainty]

  (let [p (get-prime! bits certainty)

        q (get-prime! bits certainty)

        n (.multiply p q)

        g (.add n BigInteger/ONE)

        l1 (.subtract p BigInteger/ONE)

        l2 (.subtract q BigInteger/ONE)

        lambda (.multiply l1 l2)

        mu (.modInverse lambda n)

        pk (public-key n g)]

    {:public-key pk

     :private-key (private-key lambda mu p q pk)}))

(defn key-pair2!

  "Generate a cryptographic pair with a vastly better g-parameter. Return a map with public and private keys"

  [bits certainty]

  (let [p (get-prime! bits certainty)

        q (get-prime! bits certainty)

        n (.multiply p q)

        g (yield! n)

        lambda (lcm (.subtract p BigInteger/ONE) (.subtract q BigInteger/ONE))

        mu (.modInverse (L (.modPow g lambda (square n)) n) n)

        pk (public-key n g)]

    {:public-key pk

     :private-key (private-key lambda mu p q pk)}))

(defn encrypt!

  "Encrypt a given plaintext number"

  [public-key plaintext]

  (let [{:keys [n g]} public-key

        nsqr (square n)]

    (-> g

      (.modPow plaintext nsqr)

      (.multiply (.modPow (random-number! n) n nsqr))

      (.mod nsqr))))

(defn encrypt-number!

  "Encrypt a number with a given public-key"

  [public-key n]

  (encrypt! public-key (BigInteger/valueOf n)))

(defn encrypt-string!

  "Encrypt a string with a given public-key"

  [public-key str]

  (let [bytes (.getBytes str StandardCharsets/UTF_8)]

    (encrypt! public-key (BigInteger. bytes))))

(defn h+

  "Addition of two ciphertexts. Requires a public-key"

  [public-key ciphertext1 ciphertext2]

  (let [n (:n public-key)]

    (-> ciphertext1

      (.multiply ciphertext2)

      (.mod (square n)))))

(defn h*

  "Multiplication of ciphertext and a plaintext constant. Requires a public-key"

  [public-key ciphertext k]

  (let [n (:n public-key)]

    (-> ciphertext

      (.modPow (BigInteger/valueOf k) (square n)))))

(defn decrypt

  "Decrypt a ciphertext number using a given private-key" 

  [private-key ciphertext]

  (let [public-key (:public-key private-key)

        lambda (:lambda private-key)

        n (:n public-key)

        nsqr (square n)

        mu (:mu private-key)]

    (-> (L (.modPow ciphertext lambda nsqr) n)

      (.multiply mu)

      (.mod n))))

(defn decrypt-string

  "Decrypt a ciphertext string using a given private-key"

  [private-key ciphertext]

  (String. (.toByteArray (decrypt private-key ciphertext))

    StandardCharsets/UTF_8))

(println "Ready to encrypt something?")

Generate a key pair

(def a-pair (key-pair2! 1024 8))

a-pair

Public key

Is used for encryption and is freely sharable. Person who holds this key is not able to decrypt content encrypted with the key.

(:public-key a-pair)

Private key

Is used for decryption. Person who holds this key is able to decrypt message encrypted with a corresponding public-key.

(:private-key a-pair)

Encrypt a number

Let's encrypt some nice number: 100

(def m (encrypt-number! (:public-key a-pair) 100))

m

Let's encrypt another number: 200

(def n (encrypt-number! (:public-key a-pair) 200))

n

Additive homomorphic property

This means holder of a public-key is able to add two ciphertexts together without decrypting them.

(def o (h+ (:public-key a-pair) m n))

o

Now to show that addition actually works let's use the private key to decrypt the result.

(def p (decrypt (:private-key a-pair) o))

p

Multiplicative homomorphic property

There is also a multiplication of a ciphertext number and a plaintext number. Let's use "m" which has a nice value (pssst! It was 100, but not tell anyone!) and make it 1000 times bigger without decrypting it.

(def q (h* (:public-key a-pair) m 1000))

q

(decrypt (:private-key a-pair) q)

String encryption

In essence strings are numbers too. There are some hairy details which above code does not handle. But for the demostration purposes this should be enough.

(def msg (encrypt-string! (:public-key a-pair) "Hello world!"))

msg

String decryption

(decrypt-string (:private-key a-pair) msg)

Examples of application

Privacy protecting survey

Imagine you have to organize a survey where you're asking about employees' salaries in the organization. You want to know the average salary in the company. Also, you want to keep each responder's answer undisclosed to the other employees.

If you have additive homomorphic encryption at hand, you can structure this task accordingly:

Having a pair of public and private keys gives the public key to each employee to form a chain. In this chain, the first participant encrypts the answer and passes this ciphertext to the second. The second participant uses homomorphic addition and adds his response to the previous employee, handing it to the next employee. Apply this procedure to the rest of the respondents. In the end, pass the result to the collector, who can decrypt the final sum using his private key. The last step necessary is to divide it by the number of participants in the survey. And the average salary is born without exposing each employee's salary. Addition operation effectively erases intermediate results.

E-voting

Semantic security is not the only consideration. There are situations under which malleability may be desirable. Secure electronic voting systems can utilize the above homomorphic properties. Consider a simple binary ("for" or "against") vote. Let m voters cast a vote of either 1 (for) or 0 (against). Each voter encrypts their choice before casting their vote. The election official takes the product of the m encrypted votes and then decrypts the result and obtains the value n, which is the sum of all the votes. The election official then knows that n people voted for and m-n people voted against. The role of the random r ensures that two equivalent votes will encrypt to the same value only with negligible likelihood, hence ensuring voter privacy.

E-cash

Another feature named in the paper is the notion of self-blinding. This is the ability to change one ciphertext into another without changing the content of its decryption. This has application to the development of ecash, an effort originally spearheaded by David Chaum. Imagine paying for an item online without the vendor needing to know your credit card number, and hence your identity. The goal in electronic cash is to ensure the e-coin is valid, while at the same time not disclosing the identity of the person with whom it is currently associated.

Email and other PII protection

You may effectively implement storage that is write-and-forget to a group of participants. But it can only be read by another group of people. Let's take a look into our product: we need to store email alongside the booking in our production database. Still, only Customer Support should contact a person directly based on the encoded email record in the booking detail. In such a scenario, homomorphic properties of the Paillier cryptosystem are not helpful. There is still a valuable property of self-blinding. The email is completely anonymous in the database to all except those who have the private key and is the only one capable of decrypting the information. There is one more valuable property. Even if the same email is encrypted twice in a different context, thanks to the probabilistic nature, the ciphertext cannot be easily reversed using a Rainbow table attack.

Final words

I hope reader received a useful and demonstrative introduction to partial homomorphic encryption. While this topic can be exciting, practical use is still way behind and implementations are in my opinion not very convincing. As a research of fully homomorphic system progresses I'd expect this topic to get a huge attention, because we are all waiting for the Holy Grail of cryptography. Aren't we?