How Does Bob The Taxgather Find Out Total Profits, Without Revealing Any of Them?

How Does Bob The Taxgather Find Out Total Profits, Without Revealing Any of Them?

The tax authority (Bob) wants to determine the total profit made by all the companies in its region (AliceCo, CharleyCo, DaveInc, EveCom, and FaithCo), but none of the companies wants to release their figures as it will give a commercial advantage to others. So how could we do this?

Well, initially Bob the tax gather generates a key pair: a public key and a private key, and sends Trent the tax agent the public key. In order to both be quantum robust, and preserve the privacy of the companies, Bob — a very forward-thinking tax gather— decides to use lattice cryptography and which give us homomorphic encryption, and where we can mathematically operate on encrypted values.

And so AliceCo, CharleyCo, DaveInc, EveCom, and FaithCo., all take their profit values and encrypt them with the public key, and send these to Alice. Alice cannot, at this stage, reveal any of their profits. Alice then performs homomorphic addition encryption on them and returns the result to Bob. Bob then uses his private key, on the result, and reveals the total profit made by AliceCo, CharleyCo, DaveInc, EveCom, and FaithCo.

Some sample code in Go which adds two numbers together is [here]:

package main

import (
    "github.com/dedis/lago/bigint"
    "github.com/dedis/lago/crypto"
    "github.com/dedis/lago/encoding"
    "fmt"
    "strconv"
    "os"
)

func main() {

    a:=1
    b:=3
    argCount := len(os.Args[1:])

        if (argCount>0) {a,_= strconv.Atoi(os.Args[1])}

        if (argCount>1) {b,_= strconv.Atoi(os.Args[2])}



    msg1 := bigint.NewInt(int64(a))
    msg2 := bigint.NewInt(int64(b))



    N := uint32(32)  // polynomial degree
    T := bigint.NewInt(10)  // plaintext moduli
    Q := bigint.NewInt(8380417)  // ciphertext moduli
    BigQ := bigint.NewIntFromString("4611686018326724609")  

    // create FV context and generate keys

    fv := crypto.NewFVContext(N, *T, *Q, *BigQ)
    key := crypto.GenerateKey(fv)

    // encode messages

    encoder := encoding.NewEncoder(fv)
    plaintext1 := crypto.NewPlaintext(N, *Q, fv.NttParams)
    plaintext2 := crypto.NewPlaintext(N, *Q, fv.NttParams)

    encoder.Encode(msg1, plaintext1)
    encoder.Encode(msg2, plaintext2)


    // encrypt plainetexts
    encryptor := crypto.NewEncryptor(fv, &key.PubKey)
    ciphertext1 := encryptor.Encrypt(plaintext1)
    ciphertext2 := encryptor.Encrypt(plaintext2)

    // evaluate ciphertexts
    evaluator := crypto.NewEvaluator(fv, &key.EvaKey, key.EvaSize)

    add_cipher := evaluator.Add(ciphertext1, ciphertext2)
    mul_cipher := evaluator.Multiply(ciphertext1, ciphertext2)
    sub_cipher := evaluator.Sub(ciphertext1, ciphertext2)


    // decrypt ciphertexts
    decryptor := crypto.NewDecryptor(fv, &key.SecKey)
    new_plaintext1 := decryptor.Decrypt(ciphertext1)
    new_plaintext2 := decryptor.Decrypt(ciphertext2)

    add_plaintext := decryptor.Decrypt(add_cipher)
    mul_plaintext := decryptor.Decrypt(mul_cipher)
    sub_plaintext := decryptor.Decrypt(sub_cipher)


    // decode messages
    new_msg1 := new(bigint.Int)
    new_msg2 := new(bigint.Int)
    add_msg := new(bigint.Int)
    mul_msg := new(bigint.Int)
    sub_msg := new(bigint.Int)


    encoder.Decode(new_msg1, new_plaintext1)
    encoder.Decode(new_msg2, new_plaintext2)
    encoder.Decode(add_msg, add_plaintext)
    encoder.Decode(mul_msg, mul_plaintext)
    encoder.Decode(sub_msg, sub_plaintext)


    fmt.Printf("N=%d, Q=%s\n", fv.N,fv.Q)

    fmt.Printf("a=%d, b=%d\n", a,b)
    fmt.Printf("Cipher (a)=%d, Cipher (b)=%d\n", ciphertext1,ciphertext2)
//  fmt.Printf("Public key=%s\n Private key=%s\n\n", key.PubKey,key.SecKey)

    fmt.Printf("%v + %v = %v\n", msg1.Int64(), msg2.Int64(), add_msg.Int64())
    fmt.Printf("%v * %v = %v\n", msg1.Int64(), msg2.Int64(), mul_msg.Int64())
    fmt.Printf("%v - %v = %v\n", msg1.Int64(), msg2.Int64(),sub_msg.Int64())


}

A sample run is:

N=32, Q={{%!s(bool=false) [%!s(big.Word=8380417)]}}
a=9, b=11
Cipher (a)=&{[824633830016 824633830064]}, Cipher (b)=&{[824633830256 824633830304]}
9 + 11 = 20
9 * 11 = 99

We can also use batch methods on our numbers — such as in spreadsheets. The following uses a newly released Go Lattigo library [here]:

and which gives a sample run of [here]:

Parameters : N=8, T=786433, Qi = 2x60, sigma = 3.190000 
Numbers: N1=[38 43 57 10 11]
Numbers: N2=[91 99 32 25 56]
38+91=129
38-91=-53

43+99=142
43-99=-56

57+32=89
57-32=25

10+25=35
10-25=-15

11+56=67
11-56=-45

Conclusions

Our models of computation often date back to the 1970s, and where security was just making sure that your coffee cup was placed at a safe distance from your keyboard. We now need to respect the rights of privacy for our citizens, and homomorphic encryption gives us a way to process data, without revealing its original contents.

Want to learn more about the magic of lattices? Try here:

and here: