Building Applications with
Homomorphic Encryption
A Presentation from the Homomorphic Encryption
Standardization Consortium
HomomorphicEncryption.org

0.1 – Presenters
●
●
●
●
●
●
●

Roger A. Hallman (SPAWAR Systems Center Pacific; Thayer School of Engineering, DartmouthCollege, USA)
Kim Laine (Microsoft Research, USA)Wei Dai (Worcester Polytechnic Institute, USA)
Nicolas Gama (Inpher, Inc., Switzerland)Alex J. Malozemoff (Galois, Inc., USA)
Yuriy Polyakov (NJIT Cybersecurity Research Center, USA)
Sergiu Carpov (CEA, LIST, France)

0.2 – Agenda – Part 1
1.
2.
3.
4.
5.

Introduction to Homomorphic Encryption (Presenter: Roger Hallman)
HE Fundamentals (Presenter: Wei Dai)
How to Build HE Applications? (Presenter: Yuriy Polyakov)
Standardization and Open Problems (Presenter: Kim Laine)
Previewing Part 2 of this Tutorial (Presenter: Roger Hallman)

0.3 – Agenda – BreakAssistance will be provided during a 30-minute break for audience members who
are downloading and installing HE libraries.

0.4 – Agenda – Part 2
1.
2.
3.
4.
5.
6.
7.

A High-level View of Available HE Libraries (Presenter: Roger Hallman)
SEAL (Presenter: Kim Laine)
PALISADE (Presenter: Yuriy Polyakov)
TFHE (Presenter: Nicolas Gama)
cuFHE and Hardware Acceleration (Presenter: Wei Dai)
Compilers for HE (Presenters: Alex Malozemoff and Sergiu Carpov)
Concluding Remarks (Presenter: Roger Hallman)

1.0 – Introduction to Homomorphic Encryption
What is Homomorphic Encryption (HE)?
❏❏Allows for computation on encrypted data
Enables outsourcing of data storage/processing

History of HE:❏❏❏

Rivest, Adleman, Dertouzos (1978) -- “On Data Banks and Privacy
Homomorphisms”
Gentry (2009) -- “A Fully Homomorphic Encryption Scheme”
Multiple HE schemes developed after 2009

1.1 – How HE is related to symmetric and public key
encryption?
❏❏

HE schemes provide efficient instantiations of post-quantum public-key andsymmetric-key encryption schemes
Homomorphic encryption can be viewed as a generalization of public key
encryption

1.2 – FAQ❏

Data enter / stay in / leave untrusted networks encrypted.

❏

Do operations on ciphertext and plaintext reveal secret?
No, an operation on ciphertext and plaintext outputs ciphertext.

❏

Is decryption performed during computation?
No, computation is performed
without decryption.

1.3 – Applications
Business models and application domains:
DomainGenomics

HealthNational
Security

Education

SocialSecurity

Business
Analytics

Cloud

SampleTopicsGWAS

billing andreportingsmart gridschooldropouts

credithistory

prediction

storage,sharing

Data Owner

medicalinstitutions

clinics andhospitals

nodes andnetwork

schools,
welfaregovernment

businessownersclients

Why HE?

HIPAA

cyber
insurance

privacy

FERPA

cyber
crimesdata arevaluable

untrusted
serverWho pays?

healthinsurance

hospitalenergycompany

DoEgovernment

businessownersclients

1.3 – Example: Healthcare
Precision medicine requires intensive computation on highly identifiable data.
Challenges:
1.
2.
3.
4.

Therapy safety and efficacy must by determined.
Patients are concerned about privacy and agency (against breaches).
Agency, hospitals must ensure compliance with relevant laws (such as HIPAA).
Pharmaceutical companies are concerned about protecting their IP.

Currently, require unappealing trade-offs, sometimes with disastrous outcomes for both organizations andtheir patients.
HE provides a novel solution to some of these trade-offs at a cost that is minimal compared to suchoutcomes.

1.4 – Other Secure Computing Approaches
How HE is different from MPC and SGX
HE

MPC

Compute-boundNetwork-boundEncryption

Encryption /Non-collusion

Trusted Hardware

Non-interactive

✔

✘

✔

Cryptographic
security✔

✔

✘(known attacks)

Performance
Privacy●Hybrid approaches possible

SGX

2.0 – Understanding HE❏ “Homomorphic”: a (secret) mapping from plaintext space to ciphertext spacethat preserves arithmetic operations.
❏ Mathematical Hardness: (Ring) Learning with Errors Assumption; every image(ciphertext) of this mapping looks uniformly random in range (ciphertext space).
❏ “Security level”: the hardness of inverting this mapping without the secret key.
❏

Example: 128 bits → 2128 operations to break2.0 – Understanding HE❏ Plaintext: elements and operations of a polynomial ring (mod xn+1, mod p).
❏

Example: 3x5 + x4 + 2x3 + ...

❏ Ciphertext: elements and operations of a polynomial ring (mod xn+1, mod q).
❏

Example: 7862x5 + 5652x4 + ...

2.1 – A Fresh Encryption
Initial Noise(removable mod p)

Plaintext mod p
Mask mod q(removable with thesecret key)••

Horizontal: each coefficient in a polynomial or in a vector.
Vertical: size of coefficients.

Initial noise is small in terms of coefficients’ size.

Ciphertext

2.2 – Noise Growth in Computation
After some computation:
Result mod p
Mask mod q(removable with thesecret key)••

Current Noise(removable mod p)

Horizontal: each coefficient in a polynomial or in a vector.
Vertical: size of coefficients.

After each level, noise increases.

Ciphertext

2.3 – Bootstrapping
Homomorphic decryption with an encrypted secret key.
Initial Noise(removable mod p)

Plaintext mod p
Mask mod q(removable with thesecret key)••

Horizontal: each coefficient in a polynomial or in a vector.
Vertical: size of coefficients.

At some level, noise is too much to decrypt.

Ciphertext

2.4 – Noise Overflow
Too much computation:
Result mod p
Mask mod q(removable with thesecret key)••

Too Much Noise

Horizontal: each coefficient in a polynomial or in a vector.
Vertical: size of coefficients.

At some level, noise is too much to decrypt.

Ciphertext

2.5 – Encoding Techniques
Reduce ciphertext / plaintext size ratio.
1.
2.

Multi-precision integers / fractional
numbers (mod pn).
Batching a vector of integers /fractional numbers (mod p).

Encoding Failure
Data

Data

EncodePlaintext

Plaintext

Encrypt

Plaintext encoding should be correct
before ciphertext evaluation.
Example:5 × 7 mod 17 ≠ 35

Ciphertext
Noise Failure

DecodeEvaluate

Decrypt
Ciphertext

2.6 – Encoding Integers / Fractional Numbers
Correctness only depend on plaintext:
Initial Noise(removable mod p)

Plaintext mod p
Mask mod q(removable with thesecret key)••

Horizontal: each coefficient in a polynomial or in a vector.
Vertical: size of coefficients.

Initial noise is small in terms of coefficients’ size.
Message are encoded to lower-degree terms of a plaintext.

Ciphertext

2.7 – Computation on Integer / Fractional Numbers
Result mod p
Mask mod q(removable with thesecret key)••

Result Noise(removable mod p)

Horizontal: each coefficient in a polynomial or in a vector.
Vertical: size of coefficients.

After each level, noise increases, plaintext spreads to higher-degree terms.

Ciphertext

2.8 – Integer / Fractional Encoding Failure
Product mod p
Mask mod q(removable with thesecret key)••

Product Noise

Ciphertext

Horizontal: each coefficient in a polynomial or in a vector.
Vertical: size of coefficients.

At some level, plaintext reaches the highest-degree term before the noise grows too much.
Message will then be reduced mod pn.

3.0 – How to Build HE Applications?
❏
❏
❏
❏
❏
❏

How to design an HE compute model for your application?
How to select the most efficient scheme and its implementation?
How to encode the data prior to encryption?
How to select the security parameters?
How to guarantee the correctness of your implementation?
How to optimize your implementation?

3.1 – Models of Homomorphic Computation
It is important to choose the right approach for designing your HE computation:
1.

Boolean Circuits○○

2.

Modular (Exact) Arithmetic○○

3.

Plaintext data represented as bits
Computations expressed as Boolean circuits
Plaintext data represented as integers modulo a plaintext modulus “t” (or their vectors)
Computations expressed as integer arithmetic circuits mod t

Approximate Number Arithmetic○○

Plaintext data represented as real numbers (or complex numbers)
Compute model similar to floating-point arithmetic

3.2 – Boolean Circuits Approach
Features:❏❏❏

Fast number comparison
Supports arbitrary Boolean circuits
Fast bootstrapping (noise refreshing procedure)

Selected schemes:
1.
2.
3.

Gentry-Sahai-Waters (GSW) [GSW13] - foundation for other schemes
Fastest Homomorphic Encryption in the West (FHEW) [DM15]
Fast Fully Homomorphic Encryption over the Torus (TFHE)[CGGI16,CGGI17]

3.3 – Modular (Exact) Arithmetic Approach
Features:❏❏❏❏

Efficient SIMD computations over vectors of integers (using batching)
Fast high-precision integer arithmetic
Fast scalar multiplication
Leveled design (often used without bootstrapping)Selected schemes:
1.
2.
3.

Brakerski-Vaikuntanathan (BV) [BV11] - foundation for other schemes
Brakerski-Gentry-Vaikuntanathan (BGV) [BGV12, GHS12]
Brakerski/Fan-Vercauteren (BFV) [Brakerski12, FV12, BEHZ16, HPS18]

3.4 – Approximate Number Arithmetic Approach
Features:
❏
❏
❏
❏
❏

Fast polynomial approximation
Relatively fast multiplicative inverse and Discrete Fourier Transform
Deep approximate computations, such as logistic regression learning
Efficient SIMD computations over vectors of real numbers (using batching)
Leveled design (often used without bootstrapping)Selected schemes:
1.

Cheon-Kim-Kim-Song (CKKS) [CKKS17]

3.5 – Library Matrix
Library/Scheme

FHEW

BGV

BFV

✔
✔

FV-NFLlib

✔

HEAAN
HElib

✔

PALISADE✔

SEAL
TFHE(-Chimera)

CKKS

✔

cuFHE
FHEW

TFHE

✔

✔

(✔)
✔

(✔)

✔

✔

(✔)

(✔)

3.6 – Application Development Best Practices
Main guidelines:
1.
2.
3.
4.
5.
6.

Choose the right compute model
Choose the plaintext encoding/batching technique
Determine the correctness requirements for the computation
Consult the security tables
Write the code using standard API
Fine-tune the parameters to optimize the performance3.7 – Application Development: Compute Model
1.

Choose the compute model
○
○
○

2.

Boolean Circuits
Modular (Exact) Arithmetic
Approximate Number Arithmetic.

Determine how the data should be encoded, and whether multiple pieces ofdata can be packed in single ciphertexts.
○
○
○
○
○

One ciphertext per integer (high-precision arithmetic)
One ciphertext per vector of integers
One ciphertext per vector of real numbers
One ciphertext per matrix of real numbers
Etc.

3.8 – Application Development: Correctness
The functional parameters, such as “plaintext modulus” and “ciphertext modulus”,
should guarantee the correctness of decrypted result.
1.

Plaintext computation correctness○○

2.

If the modular (exact) arithmetic approach is selected, verify that the result is correct:■ 11*7 mod 50 ≠ 77
Always build a reference implementation in the clear. This helps a lot in debugging the
HE-enabled application code.

Encrypted computation correctness○

Each ciphertext operation increases the noise. Verify that the fresh ciphertext modulus ischosen to be large enough, or bootstrapping is applied before the noise can cause adecryption failure.

3.9 – Application Development: Security
The ring dimension (degree of polynomial) should be chosen according to thesecurity tables published at HomomorphicEncryption.org (some libraries canselect it automatically).

3.10 – Application Development: PerformanceFine-tune the parameters affecting the performance:
❏
❏
❏
❏
❏
❏
❏

Plaintext encoding settings
Choose smallest ring dimension and ciphertext modulus that meet thecorrectness and security requirements
Fine-tune scheme-specific parameters, such as relinearization window
Update the order of HE maintenance procedures, such as relinearization,
modulus switching/rescaling, and bootstrapping
Turn on multi-threading
Take advantage of library-specific performance optimization tools, such as
memory pools or RNS representation of large integers
Use specialized hardware, such as GPU, if supported by the library4.0 – Standardization
Applications of HE in regulated industries requires standardization❏❏❏❏

Finance
Health-care
Government
Military

Must guarantee HE to be at least as secure as AES, RSA!

4.1 – Standardization Workshops❏ In July 2017 at Microsoft❏ In March 2018 at MIT❏ October 20, 2018 at U Toronto
Outcomes:❏❏❏❏

HomomorphicEncryption.org community
White papers
Mailing list
Attended and endorsed by leading
experts in crypto and security

4.2 – White papers
Three white papers from the first workshop:❏❏❏

Security of Homomorphic Encryption
API for Homomorphic Encryption
Applications of Homomorphic Encryption

Guiding principles of the standardization effort:❏❏❏

Security is priority
API standardization needed for making HE developer-friendly
Motivated by practical use-cases

4.3 – Security
What is the security standard?
❏
❏
❏
❏
❏

Describes encryption schemes
Describes best known attacks
Describes tables of parameters in termsof standard security levels
Written by leading security experts
Available at HomomorphicEncryption.org

4.4 – Third Standardization Workshop
❏
❏
❏
❏
❏

On Saturday at University of Toronto
Significant progress towards API standardization
Automation and developer tools
Compiler for homomorphic encryption
If you still want to register, come talk to me5.0 – Challenges and Open Problems❏

HE is hard to use
❏
❏
❏
❏

❏

Standardized API
Languages and compilers for writing and optimizing HE programs easily
Higher-level automation to help developers design efficient HE-based solutions
Library interoperability

HE is not practical for all computations❏❏❏❏

Only small/low depth arithmetic and Boolean circuits are feasible
E.g. division, comparison can be costly (scheme-dependent)
E.g. data filtering is impossible in the traditional sense
Most computational workloads are not designed in an HE-friendly way

6.0 – What to Expect in Part II (After the Break)30-minute break: we will help you download and install HE libraries[SEAL] -- http://sealcrypto.org[PALISADE] -- https://git.njit.edu/palisade/PALISADE[TFHE] -- https://tfhe.github.io/tfhe[cuFHE] -- https://github.com/vernamlab/cuFHE (requires an NVIDIA GPU)

An Overview of HE Libraries●

At least 10 open source HE libraries available○●

4 libraries presented here

Libraries not included:
○
○
○
○
○
○

HeaAn - (https://github.com/kimandrik/HEAAN)
HElib - (https://github.com/shaih/HElib)Λ ○ λ (“LOL”) - (https://github.com/cpeikert/Lol)■
Used by the “ALCHEMY” compiler (Crockett, et al.)NFLlib - (https://github.com/quarkslab/NFLlib)
FHEW - (https://github.com/lducas/FHEW)
And more...

SEAL
Simple Encrypted Arithmetic Library

Kim Laine / kim.laine@microsoft.com
http://sealcrypto.org

Quick Background❏❏❏

Homomorphic Encryption library from Microsoft ResearchFirst version released in 2015; SEAL 3.0 just released
Developed in standard C++❏

Implements BFV and CKKS schemes
❏
❏

❏
❏

BFV for exact (e.g. integer) computations
CKKS for approximate fixed-point computations

Header-files extensively commented
Comes with detailed examples

Downloading SEAL❏❏❏

SEAL 3.0 source code can be downloaded as .tar.gz (Linux and OS X) or .zip
(Windows) packages from http://sealcrypto.org
SEAL is completely self-contained: no external dependencies
GitHub release coming soon

Building SEAL and Linking with Applications❏

On Visual Studio use accompanying solution and project files❏❏

On Linux/OS X use g++/clang++ and CMake❏❏❏

Requires Visual Studio 2017
Requires g++ >= 6 or clang++ >= 5

Uses some features from C++17 but can be compiled as C++14 if necessary
With CMake easy to configure and link with your application
cmake_minimum_required(VERSION 3.10)
project(CCSTutorial)
add_executable(example example.cpp)
find_package(SEAL 3.0.0 REQUIRED)
target_link_libraries(example SEAL::seal)

Learning to Use SEAL❏Best way to learn to use SEAL is going over SEALExamples/main.cpp❏

Doing something with SEAL is not so hard …

❏

But doing it well can be❏

Learning to use SEAL efficiently will require a lot of work❏

Recommendation: Learn BFV scheme first; CKKS after that❏In the future: Compilers and better developer tools will help❏

StackOverflow tag [seal]

Now let’s look at some code ...

SEAL
Simple Encrypted Arithmetic Library

http://sealcrypto.org

PALISADE
Yuriy Polyakov (NJIT)

CCS’18 Tutorial: “Building Applications with
Homomorphic Encryption”
October 19, 2018

PALISADE Lattice Cryptography Library (NJIT)❑❑

Project-based Development since 2014❑

Next generation of DARPA PROCEED SIPHER project❑

Cryptographic program obfuscation (DARPA Safeware)❑

Homomorphic Encryption for statistical analysis (Sloan, IARPA)❑

Proxy Re-Encryption for Pub/Sub systems (Simons, NSA)❑

HE backend for Secure Programming in Julia (IARPA)

Implementation Partners and Collaborators❑

Academia: MIT, UCSD, WPI, NUS, Sabanci U❑

Industry: Raytheon (BBN), IBM Research, Lucent, Vencore Labs, Galois, Two Six Labs❑

BSD 2-clause license❑

Cross-Platform Support

Modular DesignCapabilities❑❑

Public Key Encryption/Homomorphic Encryption❑

3 variants of BFV scheme

❑

BGV

❑

LTV, Stehle-Steinfeld

❑

Null

❑

Proxy Re-Encryption based on all of the above HE schemes

Capabilities that will be released within next few months (in v1.4 and v2.0)❑

CKKS HE scheme❑

Identity-based encryption, 2 variants of attribute-based encryption❑

GPV digital signature

Key Concepts/Classes❑❑

CryptoContext❑

A wrapper that encapsulates the scheme, crypto parameters, encoding parameters, and keys❑

Provides the same API for all HE schemes

Ciphertext❑❑

Stores the ciphertext polynomials

Plaintext❑

Stores the plaintext data (both raw and encoded)❑

Supports multiple encodings in a polymorphic manner, including PackedEncoding,IntegerEncodering, CoefPackedEncoding, etc.

Sample Program: Step 1 – Set CryptoContext//Set the main parameters
int plaintextModulus = 65537;
double sigma = 3.2;
SecurityLevel securityLevel = HEStd_128_classic;
uint32_t depth = 2;//Instantiate the crypto context
CryptoContext<DCRTPoly> cryptoContext =CryptoContextFactory<DCRTPoly>::genCryptoContextBFVrns(
plaintextModulus, securityLevel, sigma, 0, depth, 0, OPTIMIZED);//Enable features that you wish to use
cryptoContext->Enable(ENCRYPTION);
cryptoContext->Enable(SHE);

Sample Program: Step 2 – Key Generation// Initialize Public Key Containers
LPKeyPair<DCRTPoly> keyPair;// Generate a public/private key pairkeyPair = cryptoContext->KeyGen();// Generate the relinearization key
cryptoContext->EvalMultKeyGen(keyPair.secretKey);Sample Program: Step 3 – Encryption// First plaintext vector is encoded
std::vector<uint64_t> vectorOfInts1 = {1,2,3,4,5,6,7,8,9,10,11,12};Plaintext plaintext1 = cryptoContext->MakePackedPlaintext(vectorOfInts1);// Second plaintext vector is encoded
std::vector<uint64_t> vectorOfInts2 = {3,2,1,4,5,6,7,8,9,10,11,12};Plaintext plaintext2 = cryptoContext->MakePackedPlaintext(vectorOfInts2);// Third plaintext vector is encoded
std::vector<uint64_t> vectorOfInts3 = {1,2,5,2,5,6,7,8,9,10,11,12};Plaintext plaintext3 = cryptoContext->MakePackedPlaintext(vectorOfInts3);// The encoded vectors are encrypted
auto ciphertext1 = cryptoContext->Encrypt(keyPair.publicKey, plaintext1);
auto ciphertext2 = cryptoContext->Encrypt(keyPair.publicKey, plaintext2);
auto ciphertext3 = cryptoContext->Encrypt(keyPair.publicKey, plaintext3);

Sample Program: Step 4 – Evaluation// Homomorphic additions
auto ciphertextAdd12 = cryptoContext->EvalAdd(ciphertext1,ciphertext2);
auto ciphertextAddResult = cryptoContext->EvalAdd(ciphertextAdd12,ciphertext3);// Homomorphic multiplications
auto ciphertextMul12 = cryptoContext->EvalMult(ciphertext1,ciphertext2);
auto ciphertextMultResult = cryptoContext->EvalMult(ciphertextMul12,ciphertext3);

Sample Program: Step 5 – Decryption// Decrypt the result of additions
Plaintext plaintextAddResult;
cryptoContext->Decrypt(keyPair.secretKey, ciphertextAddResult, &plaintextAddResult);// Decrypt the result of multiplications
Plaintext plaintextMultResult;
cryptoContext->Decrypt(keyPair.secretKey, ciphertextMultResult,&plaintextMultResult);// Output resultscout << plaintextAddResult << endl;
cout << plaintextMultResult << endl;

Real Application Implemented in PALISADE❑

Secure Genome-Wide Association Study (GWAS)❑

245 individuals❑

3 phenotypic covariates❑

15K SNPs (genetic variations)❑

iDASH’18 Track 2❑

Goal: Identify which SNPs may be associated to a certain disease/condition❑

Result: A highly accurate solution with the following performance❑End-to-end runtime on a 4-core machine: under 4 minutes❑

RAM utilization: under 10 GB

Design Decisions
Guideline

Decision

Choose the right compute model

Approximate Number Arithmetic; CKKS

Choose the plaintext encoding/batching
technique

Packed encoding: two variants

Determine the correctness requirements for thecomputation

Ran computations in the clear to find theplaintext parameters providing adequate
accuracy

Consult the security tables

Chose N = 215 and log2 q = 850 based on the
security standard

Write the code using standard API

Implemented using the PALISADE
CryptoContext wrapper

Fine-tune the parameters to optimize theperformance

Used a full RNS variant of CKKS; Applied many
optimizations: encoding switching, lazy key
switching, etc.

More Information❑

Download the library❑❑

Download the manual❑❑https://git.njit.edu/palisade/PALISADE/blob/master/doc/palisade_manual.pdf

Contact by email if you have any questions❑❑

https://git.njit.edu/palisade/PALISADE

palisade@njit.edu

Q&A

TFHE
Fast Fully Homomorphic Encryption over the Torus

https://github.com/tfhe/tfhehttp://lab.algonics.net/slides/index-ccs.html#/

cuFHE
CUDA-enabled Fully Homomorphic Encryption
https://github.com/vernamlab/cuFHE
Wei Dai (WPI) / wdai@wpi.edu

Features●

Implementing the TFHE scheme: binary gates.
○

Single-bit encryption / decryption / evaluation.

●

Developed in C++, interfaces wrapped in Python.

●

Homomorphic binary gates on CUDA-enabled GPUs.

●

Performance
Library

Platform (Price)

Amortized
Gate Latency

Throughput

Speedup

TFHE

CPU (unknown)

13 ms

77 gates / sec

1×

cuFHE

Titan Xp ($1,200)

500 μs2,000 gates / sec

26×

cuFHE

Tesla V100 ($8,000)

137 μs7,300 gates / sec

95×

How to Use
Every circuit can be expressed with binary gates.
import lib.fhepy_gpu as fhepubkey, prikey = fhe.KeyGen()
m1 = random.randint(0,1)
m2 = random.randint(0,1)
c1 = fhe.Encrypt(m1, prikey)
c2 = fhe.Encrypt(m2, prikey)c = c1 & c2
c = c1 | c2
c = c1 ^ c2
fhe.NAND(c, c1, c2)
c = ~(c1 & c2)
result = c.Decrypt(prikey)

PriKey pri_key;
PubKey pub_key;
KeyGen(pub_key, pri_key);
Ptxt* pt = new Ptxt[2];pt[0].message_ = rand() % Ptxt::kPtxtSpace;pt[1].message_ = rand() % Ptxt::kPtxtSpace;Ctxt* ct = new Ctxt[2];Encrypt(ct[0], pt[0], pri_key);
Encrypt(ct[1], pt[1], pri_key);
Nand(ct[0], ct[0], ct[1]);And(ct[0], ct[0], ct[1]);Xor(ct[0], ct[0], ct[1]);Decrypt(pt[0], ct[0], pri_key);

Hardware Accelerationfor HE

Performance Bottlenecks of HE●●

Data Efficiency○

Ciphertexts○

Relinearization keys, bootstrapping keys○

Requires high memory bandwidth

Computational Efficiency○

Polynomial ring arithmetic○

Integer modular arithmetic○

Requires high computational power / cost ratio

Comparison of Platforms
CPU

GPU

FPGA

Computation / Price

Bad

Good

OK

Computation / Power

Bad

Good

Better

Memory Efficiency

BetterGood

Bad

Portability & Scalability

Good

Good

Bad

Programming Effort

Good

OK

Bad

Performance Growth

Limited

Good

LimitedPopularity

Good

OK

Bad

Previous Works using GPUs
More than 30× speedup over a single-threaded CPU
Comparing homomorphic multiplications of ciphertexts
GPU Works

SchemeSpeedup over CPU

cuHE

general

30×

cuFHE

TFHE

30× (100× on V100)

nuFHE

TFHE

100× on P100

SEAL Dev

full-RNS BFV

50×

ASTAR

full-RNS BFV

30× on P100

By default, the GPU used is Titan Xp, unless specified.

Previous Works using FPGAs
Better performance / power consumption vs. GPUs.
Worse performance / price vs. GPUs.
Comparing homomorphic multiplications of ciphertexts
FPGA Works

SchemeSpeedup over CPUÖztürk, Doröz, Sunar, Savaş

LTV variant

100×

SEAL Dev

full-RNS BFV

20× (~120×)

Performance varies greatly on different FPGA models.

Application-specific Integrated Circuit (ASIC)●

CPU, GPU and FPGA are general purpose.

●

Design driven by○

CPU: general○

GPU: AI, Machine Learning, Computer Graphics○

FPGA: DSP●

There has never been a hardware platform specific for HE.

●

Base cost starts at a few millions (USD).

●

Ideal in future, when there is a market.

Compilers for HE

Why have compilers?
1.

Writing HE code directly can be tediousDot product (in SEAL)

Parameter selection (in SEAL)

void
dot(SEALContext &context,
vector<Ciphertext> &vec1, vector<Ciphertext> &vec2,
Ciphertext &dotprod){
Evaluator evaluator(context);
evaluator.multiply(vec1[0], vec2[0], res);for (int i = 1; i < vec1.size(); ++i) {Ciphertext tmp;
evaluator.multiply(vec1[i], vec2[i], tmp);
evaluator.add(dotprod, tmp);
}
}

void
dot_parms(EncryptionParameters &parms, size_t size){
ChooserEncoder encoder(3);ChooserEncryptor encryptor;
ChooserEvaluator evaluator;
vector<ChooserPoly> vec1, vec2;
ChooserPoly dotprod;// ...
res = evaluator.multiply(vec1[0], vec2[0]);for (int i = 1; i < size; ++i) {ChooserPoly tmp;
tmp = evaluator.multiply(vec1[i], vec2[i]);res = evaluator.add(dotprod, tmp);}
evaluator.select_parameters({ dotprod },0,parms);}

Code very similar: easy to introduce bugs

Why have compilers?
1.
2.

Writing HE code directly can be tedious
Code not easy to analyze/optimize
void
multmany(SEALContext &context,
vector<Ciphertext> &vec,
Ciphertext &res){
Evaluator evaluator(context);
for (int i = 1; i < vec.size(); ++i) {evaluator.multiply(vec[i], res, res);}}

Goal: Compile as tree of mults to reduce depth
Requires full C++ code analysis

Why have compilers?
1.
2.
3.

Writing HE code directly can be tedious
Code not easy to analyze/optimize
Programs must have finite number of operations

int
gcd(int a, int b){
return b == 0 ? a : gcd(b, a % b);}

How do we compute the max depth of this computation?

Why have compilers?
1.
2.
3.

Writing HE code directly can be tedious
Code not easy to analyze/optimize
Programs must have finite number of operations

4.

Branching is hard:-

if / else / switch: need to execute all branches-

for / while: need computable loop boundHigh-level languages + compilers help address all of these concerns!

(Select) compiler approaches●●●●

RAMPARTS
HE-IR
Cingulata(Several other approaches in the literature)

RAMPARTS●

Compiles Julia → PALISADE: Programming language targeting scientific users (similar to MATLAB)

function sharpen(image::Array{Int,2})::Array{Int,2}weight = [[1 1 1]; [1 -8 1]; [1 1 1]]
image2 = deepcopy(image)dx,dy = size(image)for x = 2:dx-1, y = 2:dy-1
value = 0
for j = -1:1, i = -1:1
value += weight[i+2,j+2] * image[x+i,y+j]
end
image2[x,y] = image[x,y] - (value >> 1)
end
image2end

Uses symbolic simulation to convert
Julia program into arithmetic circuit

HE-IR●

How should we define an intermediate representation for HE?
○○●

IR should be:○○●“Frontend” compilers compile from <insert favorite language here> to IR“Backend” compilers compile from IR to <insert favorite HE library here>
Easy to analyze (for parameter selection / optimizations)
Accurately capture HE capabilities / limitations

Work in progress:○○○

Initially investigated “assembly language” approach■ Unconstrained branching (e.g., jumps and labels) makes analysis hard
Currently targeting SEAL only
Feedback/suggestions welcome!

HE-IR: Architecture
C++

Julia

R

...

TFHE

...

HE-IR

SEAL

PALISADE

HE-IR: Example
input vec1 : ct[<=20]
input vec2 : ct[<=20]
output dotprod : ct
if vec1.length() != vec2.length() {fail "both vectors must be the same length"}
if vec1.length() < 1 {fail "vector length must be greater than zero"}let! res : ct = vec1[0] * vec2[0]for i : int in [1 .. vec1.length() - 1] {res = res + (vec1[i] * vec2[i])}dotprod = res⇒

Parameter Selection Code
Executable Program

Cingulata●

Toolchain for compiling and running programs over FHE
○
○
○
○

●

Cingulata v2 to come...
○
○
○

●

C++ input, instrumented ints build boolean circuit
Efficient multiplicative depth minimization modules
Parallel runtime environment
Tools for generating keys, encryption, decryption and execution
Python input
Generic interface for HE libraries
On-the-fly optimized execution for bootstrapped schemes (TFHE)

Available here:
https://github.com/CEA-LIST/Cingulata

Cingulata - bubble sorting arrays●

Clear and Cingulata versions

template<typename integer>
void bsort(integer* const arr, const int n){for(int i=0;i<n-1;i++){for(int j=1;j<n-i;j++){integer swap = arr[j-1]>arr[j];if (swap) {integer t = arr[j-1];
arr[j-1] = arr[j];arr[j] = t;}}}}

template<typename integer>
void bsort(integer* const arr, const int n){for(int i=0;i<n-1;i++){for(int j=1;j<n-i;j++){integer swap = arr[j-1]>arr[j];integer t = select(swap,arr[j-1],arr[j]);arr[j-1] = select(swap,arr[j],arr[j-1]);
arr[j] = t;}}}// here select(c,a,b) ≡ c?a:b

Cingulata compilation and execution processC++sourcehello.cxx

Symbolic
executionHE
encryption

Keys

Input
ciphertext

Circuit HE//-execution

input/*.ct

fhe_key.sk
fhe_key.pk

Initialcircuithello.blif

Keysgeneration

Outputciphertext
output/*.ct

Optimize⨉ depthParamsfile

Optimized
circuithello_opt.blif

fhe_params.xml

HE params
generationHE
decryption

42

Cingulata compilation and execution processC++sourcehello.cxx

Symbolic
executionHE
encryption

Keys

Input
ciphertext

Circuit HE//-execution

input/*.ct

fhe_key.sk
fhe_key.pk

Initialcircuithello.blif

Keysgeneration

Outputciphertext
output/*.ct

Optimize⨉ depthParamsfile

Optimized
circuithello_opt.blif

fhe_params.xml

HE params
generationHE
decryption

42

Cingulata compilation and execution processC++sourcehello.cxx

Symbolic
executionHE
encryption

Keys

Input
ciphertext

Circuit HE//-execution

input/*.ct

fhe_key.sk
fhe_key.pk

Initialcircuithello.blif

Keysgeneration

Outputciphertext
output/*.ct

Optimize⨉ depthParamsfile

Optimized
circuithello_opt.blif

fhe_params.xml

HE params
generationHE
decryption

42

Cingulata compilation and execution processC++sourcehello.cxx

Symbolic
executionHE
encryption

Keys

Input
ciphertext

Circuit HE//-execution

input/*.ct

fhe_key.sk
fhe_key.pk

Initialcircuithello.blif

Keysgeneration

Outputciphertext
output/*.ct

Optimize⨉ depthParamsfile

Optimized
circuithello_opt.blif

fhe_params.xml

HE params
generationHE
decryption

42

Cingulata compilation and execution processC++sourcehello.cxx

Symbolic
executionHE
encryption

Keys

Input
ciphertext

Circuit HE//-execution

input/*.ct

fhe_key.sk
fhe_key.pk

Initialcircuithello.blif

Keysgeneration

Outputciphertext
output/*.ct

Optimize⨉ depthParamsfile

Optimized
circuithello_opt.blif

fhe_params.xml

HE params
generationHE
decryption

42

Cingulata compilation and execution processC++sourcehello.cxx

Symbolic
executionHE
encryption

Keys

Input
ciphertext

Circuit HE//-execution

input/*.ct

fhe_key.sk
fhe_key.pk

Initialcircuithello.blif

Keysgeneration

Outputciphertext
output/*.ct

Optimize⨉ depthParamsfile

Optimized
circuithello_opt.blif

fhe_params.xml

HE params
generationHE
decryption

42

Cingulata - conclusion
Compiling and running HE applications in Cingulata●

As simple as two lines

make hello
bash run.shhttps://github.com/CEA-LIST/Cingulata

Demo