makischristou / fhestring Goto Github PK

View Code? Open in Web Editor NEW

1.0 1.0 0.0 1.85 MB

A FHE implementation of a String library for the Zama bounty program.

Rust 100.00%

bounty cli fhe rust string tfhe

fhestring's Introduction

FheString

A Fully Homomorphic String library written in Rust using Zama's tfhe-rs.

How it works

The binary given is not meant for production use but rather a proof of concept on how a FHE String library would work. The program takes as cli arguments the string, pattern, n, from and to and runs all supported algorithms and compares their results with the standard string library in Rust. It outputs the time it took as well as if the results match.

Supported String functions

The supported string functions are the following:

contains with clear / encrypted pattern
ends_with with clear pattern / encrypted pattern
eq_ignore_case
find with clear pattern / encrypted pattern
is_empty
len
repeat with clear / encrypted number of repetitions
replace with clear pattern / encrypted pattern
replacen with clear pattern / encrypted pattern
rfind with clear pattern / encrypted pattern
rsplit with clear pattern / encrypted pattern
rsplit_once with clear pattern / encrypted pattern
rsplitn with clear pattern / encrypted pattern
rsplit_terminator with clear pattern / encrypted pattern
split with clear pattern / encrypted pattern
split_ascii_whitespace
split_inclusive with clear pattern / encrypted pattern
split_terminator with clear pattern / encrypted pattern
splitn with clear pattern / encrypted pattern
starts_with with clear pattern / encrypted pattern
strip_prefix with clear pattern / encrypted pattern
strip_suffix with clear pattern / encrypted pattern
to_lowercase
to_uppercase
trim
trim_end
trim_start
+ (concatenation)
Comparisons between strings >=, <=, !=, ==

Buidling

cargo b --release

Example input

$ fhestring --string "hello" --pattern "ello" --n 1 --from "ello" --to "_llo"

Cli Arguments

$ fhestring --help
    Finished release [optimized] target(s) in 0.08s
     Running `target/release/fhestring --help`
A FHE string implementation using tfhe-rs

Usage: fhestring --string <STRING> --pattern <PATTERN> --n <N> --from <FROM> --to <TO>

Options:
  -s, --string <STRING>    The string to do the processing on
  -p, --pattern <PATTERN>  The pattern for the algoritmhs that need it
  -n, --n <N>              The number of times to make an operation for the algoritmhs that need it
  -f, --from <FROM>        What will be replaced (for replace algorithms)
  -t, --to <TO>            What will replace it (for replace algorithms)
  -h, --help               Print help
  -V, --version            Print version

fhestring's People

Contributors

Stargazers

Watchers

fhestring's Issues

Add consistent max string limit across all functions

Fix FheSplit to return if the delimiter is found as well (just line FheStrip)

Add padding in pattern for StripSuffixClear

Make API consistent across string functions

Fix EqIgnoreCase edge case

Running test: ./tfhe_strings --string   --pattern  --n 0 --from  --to 
Test Passed: OK, ToUpper 283.569185ms
Test Passed: OK, ToLower 298.561858ms
Test Passed: OK, Contains 5.408241ms
Test Passed: OK, ContainsClear 5.452949ms
Test Passed: OK, EndsWith 212.421µs
Test Passed: OK, EndsWithClear 203.422µs
Test Passed: OK, StripPrefix 221.311µs
Test Failed: Expected: 0, Got: 1, EqIgnoreCase 280.356794ms

Fix STRING_PADDING=1 issues

Running `target/release/examples/tfhe_strings --string hello --pattern '' --n 4 --from ' ' --to ''`
Test Passed: OK, ToUpper 21.179707469s
Test Passed: OK, ToLower 20.92299396s
Test Passed: OK, Contains 2.911510331s
Test Passed: OK, ContainsClear 2.964944386s
Test Passed: OK, EndsWith 1.909658411s
Test Passed: OK, EndsWithClear 1.841586934s
Test Passed: OK, StripPrefix 9.114443117s
Test Passed: OK, EqIgnoreCase 96.218539075s
Test Passed: OK, Find 8.971106757s
Test Passed: OK, FindClear 9.233282467s
Test Passed: OK, IsEmpty 4.270422098s
Test Passed: OK, Len 3.449544338s
Test Passed: OK, Repeat 339.8890711s
Test Passed: OK, RepeatClear 79.739965689s
Test Passed: OK, Replace 12.104162064s
Test Passed: OK, ReplaceClear 12.757276921s
Test Passed: OK, ReplaceN 11.841335527s
Test Passed: OK, ReplaceNClear 13.855013865s
Test Passed: OK, Rfind 10.439707471s
Test Passed: OK, RfindClear 10.535553913s
Test Passed: OK, Rsplit 117.291285946s
Test Passed: OK, RsplitClear 116.217540009s
Test Passed: OK, RsplitOnce 169.265606837s
Test Passed: OK, RsplitOnceClear 171.860394134s
Test Passed: OK, RsplitN 170.449393789s
Test Passed: OK, RsplitNClear 173.365654952s
Test Passed: OK, RsplitTerminator 145.048316542s
Test Passed: OK, RsplitTerminatorClear 145.22426622s
Test Passed: OK, Split 115.384516277s
Test Passed: OK, SplitClear 114.400620808s
Test Passed: OK, SplitAsciiWhitespace 613.871836173s
Test Passed: OK, SplitInclusive 78.257808854s
Test Passed: OK, SplitInclusiveClear 75.030111303s
Test Passed: OK, SplitTerminator 134.466177609s
Test Passed: OK, SplitTerminatorClear 133.10518647s
Test Failed: Expected: ["h", "e", "llo"], Got: ["h", "e", "l", "lo"], SplitN 156.64776823s
Test Failed: Expected: ["h", "e", "llo"], Got: ["h", "e", "l", "lo"], SplitNClear 161.865872362s
Test Passed: OK, StartsWith 2.02483933s
Test Passed: OK, StartsWithClear 2.017641023s
Test Passed: OK, StripPrefix 9.29820165s
Test Passed: OK, StripPrefixClear 9.092461733s
Test Passed: OK, StripSuffix 5.054438575s
Test Passed: OK, StripSuffixClear 4.988193751s
Test Passed: OK, ToLower 21.078457616s
Test Passed: OK, ToUpper 21.68225033s
Test Passed: OK, Trim 96.772222692s
Test Passed: OK, TrimEnd 47.042476931s
Test Passed: OK, TrimStart 52.881867203s
Test Passed: OK, Concatenate 9.379573004s
Test Passed: OK, Lt 7.041339365s
Test Passed: OK, Le 7.352336404s
Test Passed: OK, Gt 7.268666673s
Test Passed: OK, Ge 7.265533597s
Test Passed: OK, Eq 4.310878166s
Test Passed: OK, Ne 5.306369758s

See if bubble_zeroes_left can be paralleled or improved to O(n)

Maybe there is a time/memory trade-off we can make?

Fix ends_with edge case

Running test: ./target/release/examples/tfhe_strings --string abc --pattern b --n 1 --from a --to z
thread 'main' panicked at 'assertion failed: (left == right)
left: 1,
right: 0', tfhe/examples/tfhe_strings/main.rs:125:13
note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

Something is wrong with Repeat timings

Test Passed: OK, Repeat 122.663370111s
Test Passed: OK, RepeatClear 1.448250076s

Testcase: --string aBc --pattern B --n 1 --from B --to b

Add self contained doctests in docstrings

Fix SplitN Edge case

Running test: ./tfhe_strings --string hello --pattern  --n 2 --from a --to 
Test Passed: OK, ToUpper 1.707474455s
Test Passed: OK, ToLower 1.760863508s
Test Passed: OK, Contains 30.197492ms
Test Passed: OK, ContainsClear 32.980995ms
Test Passed: OK, EndsWith 798.476µs
Test Passed: OK, EndsWithClear 772.616µs
Test Passed: OK, StripPrefix 3.461998116s
Test Passed: OK, EqIgnoreCase 2.150112101s
Test Passed: OK, Find 62.109239ms
Test Passed: OK, FindClear 61.927838ms
Test Passed: OK, IsEmpty 307.335102ms
Test Passed: OK, Len 605.771865ms
Test Passed: OK, Repeat 261.379993217s
Test Passed: OK, RepeatClear 15.55182757s
Test Passed: OK, Replace 3.870809112s
Test Passed: OK, ReplaceClear 3.950059521s
Test Passed: OK, ReplaceN 4.87114673s
Test Passed: OK, ReplaceNClear 4.828838703s
Test Passed: OK, Rfind 507.650557ms
Test Passed: OK, RfindClear 423.753552ms
Test Passed: OK, Rsplit 22.508981687s
Test Passed: OK, RsplitClear 22.900883193s
Test Passed: OK, RsplitOnce 45.125263514s
Test Passed: OK, RsplitOnceClear 46.304763735s
Test Passed: OK, RsplitN 47.591896819s
Test Passed: OK, RsplitNClear 44.927082966s
Test Passed: OK, RsplitTerminator 26.727519181s
Test Passed: OK, RsplitTerminatorClear 26.65998095s
Test Passed: OK, Split 22.867822187s
Test Passed: OK, SplitClear 22.812230057s
Test Passed: OK, SplitAsciiWhitespace 52.014026785s
Test Passed: OK, SplitInclusive 22.517099459s
Test Passed: OK, SplitInclusiveClear 22.38348408s
Test Passed: OK, SplitTerminator 26.892758468s
Test Passed: OK, SplitTerminatorClear 26.905154938s
Test Failed: Expected: ["hello"], Got: ["h", "ello"], SplitN 47.365627782s
Test Failed: Expected: ["hello"], Got: ["h", "ello"], SplitNClear 45.019552556s

Return encrypted flag when no match is found

From this comment

Make strip_suffix work without client appending padding to the pattern

Optimization: Add early exit conditions

For example in pattern finding if pattern is larger than the string exit early, etc

Fix large pattern out of bounds issue

Running test: ./target/release/examples/tfhe_strings --string hello --pattern --n 1 --from a --to aaaa
thread 'main' panicked at 'index out of bounds: the len is 8 but the index is 8', tfhe/examples/tfhe_strings/server_key/mod.rs:336:69
note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

Refactor functionality out of FheString and into ServerKey

Have max repetitions be the n user provided but panic if n > 255

Don’t use the high level API like the config builder seems to imply??

Fix replace edge case: When ??? we get an out of bounds error

Test in question

target/release/examples/tfhe_strings --string '' --pattern '' --n 0 --from '' --to ' '

Refactor: Group function arguments into structs

Output the result next to timing and function name

Also do some pretty printing with colours maybe to show if it's invalid? Just brainstorming.

Fix repeat edge case

makis@shallot:~/Repositories/tfhe-rs-makis$ time ./tfhe_tests.sh > results.txt
thread 'main' panicked at 'index out of bounds: the len is 8 but the index is 8', tfhe/examples/tfhe_strings/server_key/mod.rs:167:23
note: run with RUST_BACKTRACE=1 environment variable to display a backtrace
thread 'main' panicked at 'assertion failed: (left == right)
left: "hellohellohellohello",
right: "hellohellohellohellohellohellohellohello"', tfhe/examples/tfhe_strings/main.rs:194:13
note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

Fix lt edge case

Running test: ./target/release/examples/tfhe_strings --string --pattern --n 1 --from --to
thread 'main' panicked at 'assertion failed: (left == right)
left: 0,
right: 255', tfhe/examples/tfhe_strings/main.rs:561:13
note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

Use templates for clear/encrypted pattern

Instead of duplicating all functions for both types FheString and String (encrypted or clear pattern), can we make template function that take FheString where T can be CipherText or char ? This will require in the main.rs to build both encrypted and clear FheString versions of the pattern string.

Fix n=0 Repeat algorithm errors

Running test: ./tfhe_strings --string  --pattern  --n 0 --from  --to 
Test Passed: OK, ToUpper 881.839723ms
Test Passed: OK, ToLower 862.996491ms
Test Passed: OK, Contains 16.463693ms
Test Passed: OK, ContainsClear 16.410522ms
Test Passed: OK, EndsWith 407.662µs
Test Passed: OK, EndsWithClear 384.643µs
Test Passed: OK, StripPrefix 756.79787ms
Test Passed: OK, EqIgnoreCase 2.149277093s
Test Passed: OK, Find 31.303914ms
Test Passed: OK, FindClear 31.764586ms
Test Passed: OK, IsEmpty 157.707037ms
Test Passed: OK, Len 315.702647ms
Test Passed: OK, Repeat 64.76781347s
./tfhe_tests.sh: line 4: 1182051 Killed                  ./target/release/examples/tfhe_strings "$@"

Test in question

run_test --string "" --pattern "" --n 0 --from "" --to " "

Fix no-padding algorithm errors

     Running `target/release/examples/tfhe_strings --string hello --pattern '' --n 4 --from ' ' --to ''`
Test Passed: OK, ToUpper 21.99995189s
Test Passed: OK, ToLower 22.139053569s
Test Passed: OK, Contains 3.693963019s
Test Passed: OK, ContainsClear 3.798254406s
Test Passed: OK, EndsWith 2.384946628s
Test Passed: OK, EndsWithClear 2.430659525s
Test Passed: OK, StripPrefix 8.645455426s
Test Passed: OK, EqIgnoreCase 107.355575114s
Test Passed: OK, Find 9.928827367s
Test Passed: OK, FindClear 9.861198777s
Test Passed: OK, IsEmpty 5.083041288s
Test Passed: OK, Len 4.176536228s
Test Passed: OK, Repeat 218.31372168s
Test Passed: OK, RepeatClear 52.648958795s
Test Passed: OK, Replace 11.32569492s
Test Passed: OK, ReplaceClear 12.565154446s
Test Passed: OK, ReplaceN 10.890658869s
Test Passed: OK, ReplaceNClear 13.022468968s
Test Passed: OK, Rfind 11.310225353s
Test Passed: OK, RfindClear 11.229673625s
Test Passed: OK, Rsplit 97.750492489s
Test Passed: OK, RsplitClear 97.381875965s
Test Failed: Expected: ["hello"], Got: ["o", "hell"], RsplitOnce 138.632498584s
Test Failed: Expected: ["hello"], Got: ["o", "hell"], RsplitOnceClear 139.73142365s
Test Failed: Expected: ["o", "l", "hel"], Got: ["o", "l", "l", "he"], RsplitN 138.098993996s
Test Failed: Expected: ["o", "l", "hel"], Got: ["o", "l", "l", "he"], RsplitNClear 138.798605514s
Test Passed: OK, RsplitTerminator 132.181546081s
Test Passed: OK, RsplitTerminatorClear 130.569729837s
Test Passed: OK, Split 98.12312713s
Test Passed: OK, SplitClear 102.66841263s
Test Passed: OK, SplitAsciiWhitespace 533.954217418s
Test Passed: OK, SplitInclusive 61.952361737s
Test Passed: OK, SplitInclusiveClear 61.832755733s
Test Passed: OK, SplitTerminator 128.791895937s
Test Passed: OK, SplitTerminatorClear 129.990722552s
Test Failed: Expected: ["h", "e", "llo"], Got: ["h", "e", "l", "lo"], SplitN 141.624100492s
Test Failed: Expected: ["h", "e", "llo"], Got: ["h", "e", "l", "lo"], SplitNClear 139.830190761s
Test Passed: OK, StartsWith 2.399171189s
Test Passed: OK, StartsWithClear 2.437822202s
Test Passed: OK, StripPrefix 8.788044653s
Test Passed: OK, StripPrefixClear 8.662153059s
Test Passed: OK, StripSuffix 6.27478939s
Test Passed: OK, StripSuffixClear 4.948165385s
Test Passed: OK, ToLower 22.818609474s
Test Passed: OK, ToUpper 23.102272906s
Test Passed: OK, Trim 103.921072923s
Test Passed: OK, TrimEnd 50.151216132s
Test Passed: OK, TrimStart 54.713549453s
Test Passed: OK, Concatenate 7.524414825s
Test Passed: OK, Lt 7.575066557s
Test Failed: Expected: 0, Got: 1, Le 7.692450802s
Test Failed: Expected: 1, Got: 0, Gt 7.465316925s
Test Passed: OK, Ge 7.298299222s
Test Failed: Expected: 0, Got: 1, Eq 4.901706809s
Test Failed: Expected: 1, Got: 0, Ne 6.501098764s

Explore different parameters

Also compare the speed of the high level API and see why in the add, sub, etc cases its faster than the integer API

Use scalar values in direct comparisons

For example this should be replaced with a new scalar function since it's used for comparison.

let digit_0 = FheAsciiChar::encrypt_trivial(0x30u8, server_key); // '0'
let digit_9 = FheAsciiChar::encrypt_trivial(0x39u8, server_key); // '9'

Implement missing clear functions

Specifically ReplaceNClear and SplitTerminatorClear

Add accessors instead of manually editing FheString::bytes

Fix the return type of the client decryption to truncate \0s

Make pattern also have padding

Change key generation with the following example

https://docs.zama.ai/tfhe-rs/fine-grained-apis/integer

Fix rsplit_once to return results in correct order

Remove public_parameters

Fix rfind edge case

Running test: ./target/release/examples/tfhe_strings --string hello --pattern --n 1 --from aaaa --to a
thread 'main' panicked at 'assertion failed: (left == right)
left: 7,
right: 5', tfhe/examples/tfhe_strings/main.rs:240:13
note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

FIx split and rsplit edge cases

e.g. when string is empty and pattern is not it panics with index out of bounds.

Make client/server keys work for u8 instead of u64

Fix n=0 Split/Rsplit Algorithm problems

Output Dump

makis@shallot:~/Repositories/tfhe-rs-makis$ time cargo r --release --example tfhe_strings -- --string "a" --pattern "" --n 0 --from "" --to ""
    Finished release [optimized] target(s) in 0.06s
     Running `target/release/examples/tfhe_strings --string a --pattern '' --n 0 --from '' --to ''`
Test Passed: OK, ToUpper 566.734368ms
Test Passed: OK, ToLower 558.353064ms
Test Passed: OK, Contains 10.256808ms
Test Passed: OK, ContainsClear 9.904776ms
Test Passed: OK, EndsWith 343.043µs
Test Passed: OK, EndsWithClear 325.192µs
Test Passed: OK, StripPrefix 212.220303ms
Test Passed: OK, EqIgnoreCase 1.013306222s
Test Passed: OK, Find 20.853211ms
Test Passed: OK, FindClear 21.044452ms
Test Passed: OK, IsEmpty 115.929551ms
Test Passed: OK, Len 203.288194ms
Test Passed: OK, Repeat 28.837379555s
Test Passed: OK, RepeatClear 353.693µs
Test Passed: OK, Replace 229.027793ms
Test Passed: OK, ReplaceClear 227.335218ms
Test Passed: OK, ReplaceN 398.514784ms
Test Passed: OK, ReplaceNClear 310.036014ms
Test Passed: OK, Rfind 136.229898ms
Test Passed: OK, RfindClear 138.544694ms
Test Passed: OK, Rsplit 690.738172ms
Test Passed: OK, RsplitClear 769.91949ms
Test Passed: OK, RsplitOnce 1.545450385s
Test Passed: OK, RsplitOnceClear 1.512752333s
Test Failed: Expected: [], Got: ["a"], RsplitN 2.127988644s
Test Failed: Expected: [], Got: ["a"], RsplitNClear 1.557199886s
Test Passed: OK, RsplitTerminator 1.377151689s
Test Passed: OK, RsplitTerminatorClear 1.447419021s
Test Passed: OK, Split 713.86172ms
Test Passed: OK, SplitClear 731.929388ms
Test Passed: OK, SplitAsciiWhitespace 4.530021416s
Test Passed: OK, SplitInclusive 706.21322ms
Test Passed: OK, SplitInclusiveClear 699.370698ms
Test Passed: OK, SplitTerminator 1.439337919s
Test Passed: OK, SplitTerminatorClear 1.510275494s
Test Failed: Expected: [], Got: ["a"], SplitN 1.987377652s
Test Failed: Expected: [], Got: ["a"], SplitNClear 1.556666381s
Test Passed: OK, StartsWith 351.293µs
Test Passed: OK, StartsWithClear 332.533µs
Test Passed: OK, StripPrefix 212.893105ms
Test Passed: OK, StripPrefixClear 223.193377ms
Test Passed: OK, StripSuffix 87.056829ms
Test Passed: OK, StripSuffixClear 88.171998ms
Test Passed: OK, ToLower 558.962549ms
Test Passed: OK, ToUpper 558.936329ms
Test Passed: OK, Trim 2.107493685s
Test Passed: OK, TrimEnd 929.828721ms
Test Passed: OK, TrimStart 1.184501619s
Test Passed: OK, Concatenate 682.79156ms
Test Passed: OK, Lt 254.596508ms
Test Passed: OK, Le 265.002459ms
Test Passed: OK, Gt 275.016935ms
Test Passed: OK, Ge 272.303013ms
Test Passed: OK, Eq 157.466601ms
Test Passed: OK, Ne 229.048031ms

Implement main.rs functionality

The code for a command line executable that will take an input string to be encrypted and a pattern for string functions which require it. This executable will encrypt the first string and run all the available APIs on the input string using the pattern when necessary. The results will be compared to the clear APIs provided by rust’s std::str, the ouptuts will be nicely formatted for the user to see that the results match (if there are errors then the bounty would not be considered valid) with timing information for the FHE version.

Add docstrings in functions

Each function should have a docstring describing what it does (those can be adapted from the rust std docs) with a doctest demonstrating the usage on simple hard coded cases.
We expect standard algorithms if it makes sense (with links to the papers describing them or publicly available content on the web like a Wikipedia page for example), if some tricks are used proper comments are expected to be provided in the code.

Fix starts_with edge case

Running target/release/examples/tfhe_strings --string '' --pattern ' ' --n 1 --from ' ' --to ' '
thread 'main' panicked at 'index out of bounds: the len is 3 but the index is 3', tfhe/examples/tfhe_strings/server_key/mod.rs:167:23
note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

Fix ends_with edge case

Running test: ./target/release/examples/tfhe_strings --string --pattern --n 1 --from --to
thread 'main' panicked at 'assertion failed: (left == right)
left: 0,
right: 1', tfhe/examples/tfhe_strings/main.rs:125:13
note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

Add accessors to FheString

Use pattern mask to stop overlapping matches

Test Failed: Expected: ["b"], Got: ["b", "a", "a"], Rsplit 31.57958765s
Test Passed: OK, RsplitOnce 56.755523609s
Test Passed: OK, RsplitN 62.535506159s
Test Failed: Expected: ["b"], Got: ["b", "a", "a"], RsplitTerminator 38.839361889s
Test Failed: Expected: ["b"], Got: ["a", "a", "b"], Split 32.567482437s
Test Passed: OK, SplitAsciiWhitespace 37.883388756s
Test Failed: Expected: ["aa", "aa", "b"], Got: ["aa", "a", "a", "b"], SplitInclusive 28.721244266s
Test Failed: Expected: ["b"], Got: ["a", "a", "b"], SplitTerminator 38.584312921s
Test Passed: OK, SplitN 61.203976058s

Optimise trim_start/trim_end

Remove the bitmask and use if_then_else

Add argument parsing in main with clap

Fix strip_suffix edge case

Running test: ./target/release/examples/tfhe_strings --string --pattern --n 1 --from --to -
thread 'main' panicked at 'assertion failed: (left == right)
left: 1,
right: 0', tfhe/examples/tfhe_strings/main.rs:493:21
note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

Fix ends_with and ends_with_clear to not require padding

Either the client can use a pattern with the correct padding if it knows it or ideally we should implement an algorithms that takes that into account

Compute correct max_possible_output_len

In handle_shorter_from when from.len() = 0 we get a panic since we attempt to divide by 0. We need to handle all 4 cases (from, to both > 0, from = 0, to > 0, etc)

Example test that causes the issue:

run_test --string "" --pattern " " --n 1 --from "" --to " "

function: replace