search

Inversed-Tech / eyelid

Private iris matching
Apache License 2.0
0 stars 0 forks source link

Extended GCD and Inverses #48

Closed emmorais closed 3 months ago

emmorais commented 3 months ago

This PR adds the Extended GCD for cyclotomic polynomials. Inverses can be computed using this primitive. For our parameters choices we have high probability of finding an invertible element for relatively small randomly sampled polynomials. Therefore we don't expect to sample multiple times before finding an invertible element. This is compatible with experiments carried out in the C++ repo.

This is efficient enough to be used for key generation of the YASHE construction.

Closes #10

teor2345 commented 3 months ago

Cyclotomic inverse: polynomial/1 relatively small random poly of degree N

I already added "inv" to the important benchmarks list in PR #57, so this is appearing as expected.

teor2345 commented 3 months ago

Benchmark

Benchmark suite Current: 2915b72 Previous: 9c62aec Ratio Full iris match: plaintext/Random bits 965615 ns/iter (± 8218) 980280 ns/iter (± 9526) 0.99 Cyclotomic multiplication: polynomial/2 random polys of degree N 70567255 ns/iter (± 43963) 66003408 ns/iter (± 181589) 1.07 Recursive Karatsuba multiplication: polynomial/2 random polys of degree N 9946048 ns/iter (± 20919)
Flat Karatsuba multiplication: polynomial/2 random polys of degree N 36023771 ns/iter (± 69736) 33642000 ns/iter (± 82031) 1.07 Cyclotomic inverse: polynomial/1 relatively small random poly of degree N 191523868 ns/iter (± 220543)
This comment was automatically generated by workflow using github-action-benchmark.

Looks like these changes saved about 5ms / 196ms.

teor2345 commented 3 months ago

I fixed the tests for tiny polynomials, because they fail occasionally: https://github.com/Inversed-Tech/eyelid/actions/runs/8779228223/job/24086917262?pr=48