Square root of a number

Zama TFHE-rs
1

Since TFHE-rs operates only on integers, I’m curious if it’s possible to implement a function that produces a real number as output. For instance, can a square root function be implemented homomorphically?

If this is feasible, I assume it would require a lookup table (LUT) that approximates the square root function. Any insights would be greatly appreciated!

2

Hello @bhavinmoriya58

I guess you could check this proposal for a sqrt algorithm for Ethereum, it should be implementable with TFHE-rs primitives but is likely not the best implementation possible.

this should give “isqrt” which rounds down.

3

Thanks very much for the reference :slight_smile:

I was looking at the code. I need to perform if else to implement the code. The solution I see is using CMUX. However, it seem CMUX is only implemented for tfhe 0.1.3 (crates.io: Rust Package Registry). And it only works with booleans as in the following code,

use tfhe::boolean::prelude::*;

fn main() {
// We generate a set of client/server keys, using the default parameters:
    let (mut client_key, mut server_key) = gen_keys();

// We use the client secret key to encrypt two messages:
    let ct_1 = client_key.encrypt(true);
    let ct_2 = client_key.encrypt(false);

// We use the server public key to execute a boolean circuit:
// if ((NOT ct_2) NAND (ct_1 AND ct_2)) then (NOT ct_2) else (ct_1 AND ct_2)
    let ct_3 = server_key.not(&ct_2);
    let ct_4 = server_key.and(&ct_1, &ct_2);
    let ct_5 = server_key.nand(&ct_3, &ct_4);
    let ct_6 = server_key.mux(&ct_5, &ct_3, &ct_4);

// We use the client key to decrypt the output of the circuit:
    let output = client_key.decrypt(&ct_6);
    assert_eq!(output, true);
}

Hence I can not perform

if (xx >= 0x10000000000000000) { xx >>= 64; r <<= 32; }

Is there a better way to perform the operation?

Thanks again :slight_smile:

4

My code is as follows:

use tfhe::shortint::prelude::*;


fn main() {
    // We generate a set of client/server keys, using the default parameters:
    let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2);

    let msg1 = 2;
    let msg2 = 3;
    // let scalar = 4;

    // let modulus = client_key.parameters.message_modulus.0;

    // We use the client key to encrypt two messages:
    let mut ct_1 = client_key.encrypt(msg1);
    let mut ct_2 = client_key.encrypt(msg2);
    let ct_3 = server_key.smart_greater_or_equal(&mut ct_1, &mut ct_2);

    // server_key.smart_scalar_mul_assign(&mut ct_1, scalar);
    // server_key.smart_sub_assign(&mut ct_1, &mut ct_2);
    // server_key.smart_mul_lsb_assign(&mut ct_1, &mut ct_2);
    // We use the server public key to execute the NOT gate:
    let ct_xor = server_key.mux(&ct_3, &ct_1, &ct_3);

// We use the client key to decrypt the output of the circuit:
    // let output = client_key.decrypt(&ct_xor);
    let output = client_key.decrypt(&ct_3);

    // We use the client key to decrypt the output of the circuit:
    // let output = client_key.decrypt(&ct_1);
    println!("Output {}",output);
    // assert_eq!(output, ((msg1 * scalar as u64 - msg2) * msg2) % modulus as u64);
}

The output after runs is:

error[E0599]: no method named `mux` found for struct `tfhe::shortint::ServerKey` in the current scope
  --> src/main.rs:23:29
   |
23 |     let ct_xor = server_key.mux(&ct_3, &ct_1, &ct_3);
   |                             ^^^ method not found in `ServerKey`

For more information about this error, try `rustc --explain E0599`.
error: could not compile `opcmp` (bin "opcmp") due to 1 previous error

It seems that the serverkey arose while I generate key to encrypt integers are not capable of running cmux. Hence as per my understanding message has to be boolean in order to do cmux. Hence one can not perform above ifelse statements. I think I must be wrong with the logic here. I would really appreciate any leads.

5

So note that the proposed algorithms above is likely going to be very, very slow as it involves several divisions.

First of all, which API are you using ?

I see a boolean example and a shortint example, if you want to compute the square root on large integers (e.g. larger than 16 bits) you will need the integer API or the user friendly wrapping made in the high_level_api

So what is your use case @bhavinmoriya58 ?

6

Use case: Time comparison of tfhe-rs and other FHE schemes for performing squareroot operations.

I want to compute squareroot of 32 bit unsigned integer.

API: I have been using tfhe v0.11 so far and used integer API as well.

It worked fine for all other operations. However ifelse require cmux and hence I am stuck.

7

In the example you share you are using the shortint API and it does not have a cmux function, however the integer server key does

and the first argument needs to be a boolean block and the others integers, in your case you are trying to cmux ct_1 and ct_3 but I think it might be a typo?

1 Like