safe-calc

Inspiration

I don't want my private medical data leaked. So I built a calculator that works entirely in the dark.

What it does

Calculates 5*2^10.

(Specifically: It is a from-scratch, bare-metal C++ Fully Homomorphic Encryption engine that computes this on ciphertext. No external crypto libraries. No decrypting in memory.)

How we built it

Binder. Legal pad. C++. Coffee. I wrestled LLVM into submission using enough #pragma commands to make a post-doc cry.

Challenges we ran into

Implementing residual number system. Scale underflow. Making sure our gadget decomposition digits satisfied 128 bit post quantum lattice security assumptions. LLVM not vectorizing my instructions. NTT/iNTT implementations. Spent 6 hours staring at the extended P-basis key switching equation trying to figure out why our noise budgets were exploding: c_rel = ( c₀ + ⌊ P⁻¹ Σ(i=0..k) c₂⁽ⁱ⁾ · evk₀⁽ⁱ⁾ ⌉ (mod q), c₁ + ⌊ P⁻¹ Σ(i=0..k) c₂⁽ⁱ⁾ · evk₁⁽ⁱ⁾ ⌉ (mod q) )

Everything to do with relinearization really. I hate relinearization so much.

Accomplishments that we're proud of

I beat a trillion dollar corporation's flagship library (Microsoft SEAL) equivalent benchmark by 44% via hardware specific optimizations and unsafe compiler practices. I got my Number Theoretic Transform (NTT) butterfly computations down to 2 clock cycles.

What we learned

Compilers are merely suggestions if you are stubborn enough.

What's next for safe-calc

Writing a README that apologizes to the LLVM developers. Maybe.

Built With

• avx-512
• c++
• fhe
• gmp
• openmp
• rlwe
• rns-ckks