docs(tfhe): add boolean sha256 tutorial by JoseSK999 · Pull Request #283 · zama-ai/tfhe-rs

JoseSK999 · 2023-05-09T18:36:48Z

This is the updated PR with the squashed commits.

IceTDrinker · 2023-05-10T06:11:14Z

Hey @JoseSK999 no need to open new PRs for the changes we request, force pushing to the PR branch is fine by us (and makes less noise with additional PRs)

IceTDrinker · 2023-05-10T06:11:49Z

Let's keep this one for the other reviews

IceTDrinker

Hello @JoseSK999 thanks a lot for this work, it is very good indeed.

Several suggestions/questions that you could fix, for the last few modifications (like location of the tutorial in the docs) we'll probably do it ourselves.

In any case this contribution is very much appreciated.

Thanks!

IceTDrinker · 2023-05-11T14:20:11Z

+    carry
+}
+
+// 2 (homomorphic) bitwise ops


what does this mean ?

I quantify the cost of each function using homomorphic bitwise operations as unit (kinda)

IceTDrinker · 2023-05-11T14:22:35Z

+    let result: Vec<Ciphertext> = (0..32)
+        .into_par_iter()
+        .map(|i| sk.xor(&a[i], &b[i]))
+        .collect();


how about something like

let mut result = a.clone(); result.par_iter_mut().zip(a.par_iter().zip(b.par_iter())).map(|(dst, (lhs, rhs))| *dst = sk.xor(lhs, rhs)); result

?

same thing for similar funcs, not sure if it has an impact on perfs

It seems a bit more efficient, thanks! We have to use for_each to consume the iterator

oh yeah my code snippet was slightly wrong

IceTDrinker · 2023-05-11T14:27:05Z

+    for (i, elem) in result.into_iter().enumerate() {
+        array[i] = elem;
+    }


if the above is not relevant, something like the following avoids indexing which has range checks for each indexing op :)

array.as_mut().copy.from_slice(&result);

to be applied where relevant in your code

IceTDrinker · 2023-05-11T14:29:34Z

+    array
+}
+
+fn and(a: &[Ciphertext; 32], b: &[Ciphertext; 32], sk: &ServerKey) -> [Ciphertext; 32] {


IceTDrinker · 2023-05-11T14:29:47Z

+    array
+}
+
+fn mux(condition: &[Ciphertext; 32], then: &[Ciphertext; 32], otherwise: &[Ciphertext; 32], sk: &ServerKey) -> [Ciphertext; 32] {


IceTDrinker · 2023-05-11T14:34:12Z

+        trivial_bools(&hex_to_bools(0x5be0cd19), &sk),
+    ];
+
+    let chunks = padded_input.chunks(512);


use chunks_exact as we know the length is a multiple of 512 :)

IceTDrinker · 2023-05-11T14:39:31Z

+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::sha256::bools_to_hex;


looks like this use statement does not resolve properly and prevents tests from running

test command used:

RUSTFLAGS="-C target-cpu=native" cargo +stable test --example sha256_bool --profile release --features=x86_64-unix,boolean -p tfhe

Fixed. I forgot to add "_function" in the test

IceTDrinker · 2023-05-11T14:46:38Z

+We see a function called ``trivial_bools`` that we use along our implementation to initialize an array of 32 Ciphertexts. This is because we cannot copy the same Ciphertext for each position of the array as we do with simple bools, so we create 32 different trivial encryptions. We will also use this function in order to trivially encrypt constant values to operate homomorphically with them.
+


not sure I understand here, you could clone x to be the mutable result and the call rotate/shift ops from rust right ?

https://doc.rust-lang.org/std/primitive.slice.html#method.rotate_right for the shift may need to do some manual management at the end

I guess the code could be updated as well then :)

That's a good point. About the highlighted text, I meant that we cannot initialize arrays of ciphertexts like this:
let a = [sk.trivial_encrypt(false); 32];

IceTDrinker · 2023-05-11T14:49:00Z

+```rust
+fn xor(a: &[Ciphertext; 32], b: &[Ciphertext; 32], sk: &ServerKey) -> [Ciphertext; 32] {
+    let result: Vec<Ciphertext> = (0..32)
+        .into_par_iter()
+        .map(|i| sk.xor(&a[i], &b[i]))
+        .collect();


to be updated depending on how the code gets updated with the suggestions made

IceTDrinker · 2023-05-11T14:53:08Z

+
+Our implementation uses Brent-Kung by default, but Ladner-Fischer can be enabled when needed by using the ```--ladner-fischer``` command line argument.
+
+For more information about parallel prefix adders you can read [this paper](https://www.iosrjournals.org/iosr-jece/papers/Vol6-Issue1/A0610106.pdf) or [this other](https://www.ijert.org/research/design-and-implementation-of-parallel-prefix-adder-for-improving-the-performance-of-carry-lookahead-adder-IJERTV4IS120608.pdf).


this other -> this other paper

JoseSK999 · 2023-05-11T21:53:06Z

I have updated everything, thanks for the feedback and the nice words!

JoseSK999 · 2023-05-19T10:49:54Z

Btw @IceTDrinker I just found out that perhaps it's better to implement trivial_bools and initialize_w in this way:

fn trivial_bools(bools: &[bool; 32], sk: &ServerKey) -> [Ciphertext; 32] {
    let array = array::from_fn(|i| sk.trivial_encrypt(bools[i]));
    array
}

fn initialize_w(sk: &ServerKey) -> [[Ciphertext; 32]; 64] {
    let array = array::from_fn(|_| trivial_bools(&[false; 32], sk));
    array
}

tmontaigu · 2023-05-22T17:00:47Z

Btw @IceTDrinker I just found out that perhaps it's better to implement trivial_bools and initialize_w in this way:

fn trivial_bools(bools: &[bool; 32], sk: &ServerKey) -> [Ciphertext; 32] {
    let array = array::from_fn(|i| sk.trivial_encrypt(bools[i]));
    array
}

fn initialize_w(sk: &ServerKey) -> [[Ciphertext; 32]; 64] {
    let array = array::from_fn(|_| trivial_bools(&[false; 32], sk));
    array
}

It looks better/shorter than the current code, you should be able to drop the temporary to make it even shorter

fn trivial_bools(bools: &[bool; 32], sk: &ServerKey) -> [Ciphertext; 32] {
    array::from_fn(|i| sk.trivial_encrypt(bools[i]))
}

aquint-zama · 2023-05-23T14:58:29Z

relates zama-ai/bounty-program#39

Clap dev dependency added

cla-bot bot added the cla-signed label May 9, 2023

IceTDrinker requested review from IceTDrinker and tmontaigu May 10, 2023 06:10

IceTDrinker reviewed May 10, 2023

View reviewed changes

Comment thread tfhe/Cargo.toml Outdated

JoseSK999 force-pushed the sha256 branch 2 times, most recently from b07f729 to 054b385 Compare May 10, 2023 21:42

tmontaigu mentioned this pull request May 11, 2023

FHE Regex Pattern Matching Engine #278

Merged

IceTDrinker reviewed May 11, 2023

View reviewed changes

JoseSK999 force-pushed the sha256 branch from 054b385 to cb0a1b0 Compare May 11, 2023 21:37

aquint-zama added the bounty label May 15, 2023

JoseSK999 force-pushed the sha256 branch from cb0a1b0 to 6ab5381 Compare May 23, 2023 09:42

soonum force-pushed the sha256 branch 2 times, most recently from a899ef1 to 6c7a936 Compare May 24, 2023 16:31

JoseSK999 and others added 3 commits May 24, 2023 23:30

docs(tfhe): add boolean sha256 tutorial

ab166ef

Clap dev dependency added

docs(tfhe): format sha256_bool and add make recipes to run it

2e13b14

chore(sha256_example): use array_fn

590b0fa

tmontaigu force-pushed the sha256 branch from 6c7a936 to 590b0fa Compare May 24, 2023 21:31

tmontaigu approved these changes May 24, 2023

View reviewed changes

tmontaigu merged commit 63247fa into zama-ai:main May 24, 2023

zaccherinij mentioned this pull request Feb 12, 2024

Create a SHA256 tutorial zama-ai/bounty-program#39

Closed

		We see a function called ``trivial_bools`` that we use along our implementation to initialize an array of 32 Ciphertexts. This is because we cannot copy the same Ciphertext for each position of the array as we do with simple bools, so we create 32 different trivial encryptions. We will also use this function in order to trivially encrypt constant values to operate homomorphically with them.


		Our implementation uses Brent-Kung by default, but Ladner-Fischer can be enabled when needed by using the ```--ladner-fischer``` command line argument.

		For more information about parallel prefix adders you can read [this paper](https://www.iosrjournals.org/iosr-jece/papers/Vol6-Issue1/A0610106.pdf) or [this other](https://www.ijert.org/research/design-and-implementation-of-parallel-prefix-adder-for-improving-the-performance-of-carry-lookahead-adder-IJERTV4IS120608.pdf).

Conversation

JoseSK999 commented May 9, 2023

Uh oh!

IceTDrinker commented May 10, 2023

Uh oh!

IceTDrinker commented May 10, 2023

Uh oh!

Uh oh!

IceTDrinker left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

JoseSK999 commented May 11, 2023

Uh oh!

JoseSK999 commented May 19, 2023

Uh oh!

tmontaigu commented May 22, 2023

Uh oh!

aquint-zama commented May 23, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants