How Can We Determine If Bob Is Older Than Alice, Without Revealing Their Ages?

The millionaire’s problem has been known for decades, and when two millionaires meet and want to know who has the most money but don’t want to give away their wealth. One way to do this is to get Trent to look at their bank balance, and neither millionaire trusts Trent. So, how can we determine who has the most money? Well, we can use homomorphic encryption for this, so let’s do a simple example of determining if Bob is older than Alice and without revealing their ages.

With homomorphic encryption, we could perform this operation:

Enc(Bob-Alice) = Enc(Bob) - Enc(Alice)

And when we decrypt we will get:

Bob - Alice

But the problem with this, is that Bob will know how much money Alice has by the difference, and Alice will know how much money Bob has. An improved method is to evaluate using a Boolean circuit.

Using DM (FHEW)

This is a simple abstraction of homomorphic cipher for a decision if Bob is older than Alice. In this case, we will define Bob and Alice’s ages will be defined in two-bit binary values: 00 (0–10 years), 01 (10–20 years), 10 (20–30 years), and 11 (over 30 years). In this case, we will use the OpenFHE library and use DM (FHEW) [1]. This method uses a LWE (Learning With Error) method that provides fully homomorphic encryption (FHE). It is able to evaluate cipher data applied onto Boolean circuits and uses bootstrapping after each gate evaluation. This allows the evaluation to be conducted in less than 0.1 seconds. The gates implemented are AND, OR, NAND, NOR, and NOT.

Truth Table

In this example we will create a True Table for Bob (b1b0) and Alice (a1a0). In this case, we will return a 1 if Bob is older, and a 0 is he is not:

The logic is then:

For example, if a1 =0 and b1 = 1, we will get a 1 as an output, and where a 1 identifies that Bob is older than Alice.

Code

Overall, we use a symmetric key approach and where we use a private key (sk) to encrypt and decrypt the result:

auto cc = BinFHEContext();

    // We can use TOY, MEDIUM, STD192, and STD256.
cc.GenerateBinFHEContext(TOY);
auto sk = cc.KeyGen();
std::cout << "Creating bootstrapping keys..." << std::endl;
cc.BTKeyGen(sk);
std::cout << "Completed key generation." << std::endl;

auto a0 = cc.Encrypt(sk, a_0);
auto a1 = cc.Encrypt(sk, a_1);
auto b0 = cc.Encrypt(sk, b_0);
auto b1 = cc.Encrypt(sk, b_1);

The following is an outline [here]:

#include <openfhe.h>

using namespace lbcrypto;
using namespace std;
#include <iostream>
#include <sstream>
#include <cstdint>

int main(int argc, char *argv[]) {

int64_t a_0=0, a_1=0, b_0=0, b_1=0;

    if (argc>1) {
     std::istringstream iss(argv[1]);
     iss >> a_0;
 }
    if (argc>2) {
     std::istringstream iss(argv[2]);
     iss >>a_1;
 }
    if (argc>3) {
     std::istringstream iss(argv[3]);
     iss >>b_0;
 }
    if (argc>4) {
     std::istringstream iss(argv[4]);
     iss >>b_1;
 } 

    auto cc = BinFHEContext();
    // We can use TOY, MEDIUM, STD192, and STD256.
    cc.GenerateBinFHEContext(TOY);
    auto sk = cc.KeyGen();
    std::cout << "Creating bootstrapping keys..." << std::endl;
    cc.BTKeyGen(sk);
    std::cout << "Completed key generation." << std::endl;

    auto a0 = cc.Encrypt(sk, a_0);
    auto a1 = cc.Encrypt(sk, a_1);
    auto b0 = cc.Encrypt(sk, b_0);
    auto b1 = cc.Encrypt(sk, b_1);

// Z = NOT(a1). b1 + NOT(a1).NOT(a0).b0 + NOT(a0).b1.b0

    auto not_a1 = cc.EvalNOT(a1);
    auto not_a0 = cc.EvalNOT(a0);
    auto not_a1_b1 = cc.EvalBinGate(AND, not_a1, b1);
    auto not_a1_a0 = cc.EvalBinGate(AND, not_a1, not_a0);
    auto not_a1_a0_b0 = cc.EvalBinGate(AND, not_a1_a0, b0);
    auto not_a0_b1 = cc.EvalBinGate(AND, not_a0, b1);
    auto not_a0_b1_b0 = cc.EvalBinGate(AND, not_a0_b1, b0);
    auto not_a1_a0_b0_or_not_a0_b1_b0 = cc.EvalBinGate(OR,  not_a1_b1, not_a1_a0_b0);
    auto ctResult = cc.EvalBinGate(OR, not_a1_a0_b0_or_not_a0_b1_b0, not_a0_b1_b0);

    LWEPlaintext result;
    cc.Decrypt(sk, ctResult, &result);

    printf("(a0=%d a1=%d b0=%d b1=%d Result: %d\n",a_0,a_1,b_0,b_1,result);
    if (result==1) cout << "Bob is older than Alice" << endl;
    else cout << "Bob is not older than Alice" << endl;
    return 0;

}

A sample run is:

Creating bootstrapping keys...
Completed key generation.
(a0=0 a1=0 b0=1 b1=0 Result: 1
Bob is older than Alice

and:

Creating bootstrapping keys...
Completed key generation.
a0=0 a1=0 b0=0 b1=0 Result: 0
Bob is not older than Alice

Conclusions

Isn’t that magic? We can compare values and determine if one value is greater than another without revealing the values used. If you want to see more examples of OpenFHE and SEAL, try here:

Homomorphic Encryption (SEAL and OpenFHE)

References

[1] Ducas, L., & Micciancio, D. (2015, April). FHEW: bootstrapping homomorphic encryption in less than a second. In Annual international conference on the theory and applications of cryptographic techniques (pp. 617–640). Berlin, Heidelberg: Springer Berlin Heidelberg.

[2] Gama, N., Izabachène, M., Nguyen, P. Q., & Xie, X. (2016). Structural lattice reduction: generalized worst-case to average-case reductions and homomorphic cryptosystems. In Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8–12, 2016, Proceedings, Part II 35 (pp. 528–558). Springer Berlin Heidelberg.