Comparison or Greater/Lesser Circuit in FHE

[mominbuet]

I have some background in Garbled Circuit and the way to do Less/Greater or Equality testing there with boolean circuit. I know there should be some kind of circuit involved in this kind of comparison in FHE as well. So how to do this? Will it need arithmetic circuit or boolean one?

#include "FHE.h"
#include "EncryptedArray.h"
#include <NTL/lzz_pXFactoring.h>
#include <fstream>
#include <sstream>
#include <sys/time.h>`

int main(int argc, char **argv) {
    long m = 0, p = 65539, r = 1; // Native plaintext space
    // Computations will be 'modulo p'
    long L = 16; // Levels
    long c = 3; // Columns in key switching matrix
    long w = 64; // Hamming weight of secret key
    long d = 0;
    long security = 128;
    ZZX G;
    m = FindM(security, L, c, p, d, 0, 0);
    FHEcontext context(m, p, r);

    buildModChain(context, L, c);
    G = context.alMod.getFactorsOverZZ()[0];

    //key generation
    FHESecKey secretKey(context);
    const FHEPubKey& publicKey = secretKey;
    secretKey.GenSecKey(w);
    EncryptedArray ea(context, G);
    cout << "input slots " << ea.size() << endl;
//    Ctxt ctx(publicKey);
    vector<long> v1;
//how to do this with NewPlaintextArray, like I want to encrypt only one value
    for (int i = 0; i < ea.size(); i++) {
        v1.push_back(10);
    }

    cout << "Plaintext " << v1[0] << endl;
    Ctxt ct1(publicKey);
    ea.encrypt(ct1, publicKey, v1);
    Ctxt ctProd = ct1;
    ctProd += ct1;
    Ctxt ctProd2 = ctProd;
    ctProd2 -= ct1;

    if(ctProd2.equalsTo(ct1))
        cout<<"same "<<endl;//doesn't print
    if(ctProd2==ct1)
        cout<<"same "<<endl;//doesn't print

    //cout << ct1 << endl;
    vector<long> res;
    ea.decrypt(ctProd2, secretKey, res);//10

    cout << "Decrypted " << res[0] << endl;

}

Is there any built-in circuit for these operations already? I know this might not be an appropriate place to ask this kind of question as this is not an issue but any help will be appreciated.

I am also new in this field so sorry in advance.

[fionser]

No, there is not out-of-the-shell comparison routine in HElib. You need to implement it by yourself. Since, addition and multiplication on GF(2) is equivalent to the OR and AND gate, so you can have a circuit to compare to encrypted integer (perhaps you need to encrypt the integer bit by bit.)

[ssmiler]

@mominbuet As fionser said you should implement binary comparison circuits by yourself. Circuits optimized for XOR-free garbled circuits are actually good for homomorphic encryption also, except that you should rewrite them such that the multiplicative depth is minimal. Look at https://eprint.iacr.org/2009/411.pdf for such circuits.

[mominbuet]

For equality, in GC I have: not(xor(inputA,intputB)) //both inputs are binary

So in FHE this would be the same? If yes then how do I get these binary values from EncryptedArray?

[ssmiler]

First of all choose a binary plaintext space (p=2) then perform the comparison circuit. As the plaintext slots are independent the comarison will be done on all slots in parallel.

[mominbuet]

Ok now I am getting some of the things. If I go to binary then I can use boolean circuit. So how to see the encrypted values in:

    Ctxt ct1(publicKey);
    ea.encrypt(ct1, publicKey, v1);

here v1 is the input vector. Also how can I do this without the vector, like encrypt only one number from PlaintextArray class? Hope I am not dragging this issue too far :(

[fionser]

@mominbuet If you just want to encrypt one integer, you can try

Ctxt ctxt(pk);
NTL::ZZX integer = NTL::to_ZZX(1);
ctxt.Encrypt(pk, integer);

Actually, here integer is a polynomial which just with one constant term.

[qdm12]

Hi there, I actually implemented various operations for my project such as comparison, addition, division etc. All are based on binary circuits (p=2) as I believe this is the only/feasible way. Start by implementing all the logic gates starting with XOR (addition) and AND (multiplication) then build up 1 bit circuits such as full adders. Finally you should implement some N bit circuits from these. Be warned, It is hard to find some of these circuits easily implementable and these become quickly very slow for 8 bit numbers for Example. So good luck! :)

[mominbuet]

Is this the project? @qdm12

Also how do I see the encrypted bits, suppose if I want to store/send them somewhere? @fionser

[shaih]

If you want to compare small numbers, then another option would be to work with plaintext space modulo 2^r for some small r. In this case you can just subtract one encrypted integer from another and test if the MSB of the result is set. Testing the MSB can be done using the extractDigits function (see Ctxt.h).

An obvious drawback of this approach is that the depth of extractDigits will be r, whereas you can make the depth as small as log r when working with binary representation (and encrypting the individual bits). But when r is small then this approach could still end up being better.

[qdm12]

Hi again, No that's not my project unfortunately, it's offline for now but I'll let you know once I uploaded it. In my implementation, numbers are represented with N ciphertexts with M slots, where N is also the number of bits of the number. The comparison is done simultaneously on all the slots thanks to the SIMD feature of HElib. It uses logic gates to form the comparison blocks. As shaih pointed me out in another issue, you can refer to Test_IO.cpp in the source folder to store ciphertexts. Hope that helps !

[mominbuet]

Test_IO.cpp has more on this I see.

One thing that I need is I have one bit (0/1), with p=2 how do I encrypt this? Or any1 can point to the part of he-library.pdf where these are discussed? The book seem to have quite some information.

[qdm12]

There is a way to encrypt a single value as fionser mentioned, but I'd encrypt N bits simultaneously packed in one ciphertext, where N is the number of slots of the ciphertext. So just set a vector of longs to 0s and 1s with a size of N, encrypt it and you will be able to perform operations in parallel on all the N bits. For example (N not realistic at all) You have N=4, and the vectors v1=(1, 0,0,1), v2=(0, 0,1,1). You encrypt them as ctxt1 and ctxt2 respectively. You do ctxt1.multiplyBy(ctxt2) Decrypt ctxt1 and you'll get the v1 AND v2 =(0, 0,0,1)

Hope that helps!

[mominbuet]

For the following code (p = 2, r = 1):

    vector<long> v1;
    for (int i = 0; i < ea.size() - 4; i++) {
        v1.push_back(0);
    }
    v1.push_back(1);
    v1.push_back(1);
    v1.push_back(1);
    v1.push_back(1);

    vector<long> v2;
    for (int i = 0; i < ea.size() - 4; i++) {
        v2.push_back(0);
    }
    v2.push_back(1);
    v2.push_back(1);
    v2.push_back(1);
    v2.push_back(1);

    Ctxt ct1(publicKey);
    ea.encrypt(ct1, publicKey, v1);
    Ctxt ct2(publicKey);
    ea.encrypt(ct2, publicKey, v2);

    Ctxt ctSum = ct1;
    ctSum.addCtxt(ct2, false);

    vector<long> res;
    ea.decrypt(ctSum, secretKey, res);
    for (int i = res.size() - 5; i < res.size(); i++) {
        cout << v1[i] << " + " << v2[i] << " ? " << res[i]  << endl;
    }

Does the addCtxtor +operatoradd with Carry bit with some other function? Also do I really need to fill up the total input slots ea.size()?

[qdm12]

You should read the documentation of HElib in HElib/doc/designDocument/he-library.pdf ; addCtxt only add two ciphertexts together in "SIMD" mode. Depending on your plaintext space, if p=2, r=1 then you are in binary so it will add following the rules of binary: 0+0=0, 0+1=1+0=1, 1+1=0. (which is a XOR gate actually) Anything more complex will have to be implemented on top of this so you'll need to: Implement logic gates -> Half adder circuit -> Full adder circuit -> Ripple carry adder circuit for example. And no you can leave the other slots to 0 by default (or anything) it will not change anything, but you should use the other slots for maximum throughput. Luckily for you, I just released an API for homomorphic binary operations here which use HElib and which should do pretty much everything you would like to start with; enjoy it! And if you want to contribute/continue the project, you're welcome to do so, just ask me :) !

[mominbuet]

Thanks a lot, that should wrap it up.