Approximate Homomorphic Encryption

Approximate Homomorphic Encryption- Construction & Bootstrapping- Construction & Bootstrapping

Yongsoo Song,

Yongsoo Song,

Seoul National Univ

ECC 2018, Osaka

Seoul National Univ
UC San Diego

ECC 2018, Osaka

Table of Contents! Background

Approximate Homomorphic Encryption- Construction & Bootstrapping
Yongsoo Song,

Seoul National Univ
UC San Diego
Microsoft Research, Redmond! Construction! [CKKS, AC17] Homomorphic Encryption for Arithmetic of Approximate Numbers! Bootstrapping! [CHKKS, EC18] Bootstrapping for Approximate Homomorphic Encryption

ECC 2018, Osaka! Related Works

Advanced Cryptography

Advanced Cryptography! Protecting Computation, not just data

! Protecting Computation, not just data

! Differential Privacy! Zero-knowledge Proof! Multiparty Computation! Attribute Based Encryption! …

Advanced Cryptography

Homomorphic Encryption! Protecting Computation, not just data

DB-1
! Differential Privacy! Zero-knowledge Proof

DB-2! Multiparty Computation! Attribute Based Encryption! Homomorphic Encryption (2009~)

()#

sk

'$%&

%

! …

!"#

()#

!"#

DB-k

!"#$%&' !"# %

Homomorphic Encryption

Homomorphic Encryption

DB-1

DB-1
Enc(DB-i; pk)

Enc(DB-i; pk)

DB-2

DB-2

sk

sk

DB-k

res = F(DB-i)

DB-kMulti-Party Computation

Comparison: HE vs MPC
Homomorphic Encryption

Multi-Party Computation

One-time encryption

Single-use encryption

No further interaction

Interaction between parties each time

Semi-honest Cloud

Semi-honest parties+ Trusted SK Owner

without collusion

Slow in computation

Slow in communication(but can speed-up using SIMD)(due to large circuit to be exchanged)

DB-1
Re-usability

DB-2

DB-k

res = F(DB-i)- Security Model- Communication Costs |F|, k

Model

Speed

Summary of Progresses! 2009-10: Plausibility! [GH11] A single bit operation takes 30 minutes! 2011-12: Large Circuits! [GHS12b] 120 blocks of AES-128 (30K gates) in 36 hours

Summary of Progresses! 2009-10: Plausibility! [GH11] A single bit operation takes 30 minutes! 2011-12: Large Circuits! [GHS12b] 120 blocks of AES-128 (30K gates) in 36 hours! 2013-15: Efficiency! [HS14] IBM's open-source library HElib! Implementation of Brakerski-Gentry-Vaikuntanathan (BGV) scheme! The same 30K-gate circuit in 4 minutes

Summary of Progresses! 2009-10: Plausibility! [GH11] A single bit operation takes 30 minutes! 2011-12: Large Circuits! [GHS12b] 120 blocks of AES-128 (30K gates) in 36 hours! 2013-15: Efficiency! [HS14] IBM's open-source library HElib! Implementation of Brakerski-Gentry-Vaikuntanathan (BGV) scheme! The same 30K-gate circuit in 4 minutes! 2015-today: Usability! Various schemes with different advantages! Simpler and faster implementations! Real-world tasks: Big data analysis, Machine learning! Standardization meetings (2017~)! iDASH competitions (2014~)

Best Performing HE Schemes
Type

Classical HE

Fast Bootstrapping

Approximate Encryption

Scheme[BGV12] BGV[Bra12, FV12] B/FV

[DM15] FHEW[CGGI16] TFHE[CKKS17] HEAAN

Plaintext

Operation

Library

Best Performing HE Schemes

Best Performing HE Schemes

Type

Classical HE

Fast Bootstrapping

Approximate Encryption

Type

Classical HE

Fast Bootstrapping

Approximate Encryption

Scheme[BGV12] BGV[Bra12, FV12] B/FV

[DM15] FHEW[CGGI16] TFHE[CKKS17] HEAAN

Scheme[BGV12] BGV[Bra12, FV12] B/FV

[DM15] FHEW[CGGI16] TFHE[CKKS17] HEAAN

Plaintext

Finite Field
Packing

Plaintext

Finite Field
Packing

Binary string

Operation

Addition, Multiplication

Operation

Addition, Multiplication

Look-up table & bootstrapping

Library

HElib (IBM)
SEAL (Microsoft Research)
Palisade (Duality inc.)

Library

HElib (IBM)
SEAL (Microsoft Research)
Palisade (Duality inc.)

TFHE(inpher, gemalto, etc.)

Best Performing HE Schemes

iDASH Security & Privacy Workshop! An interdisciplinary challenge on genomic
privacy research

TypeClassical HE

Fast Bootstrapping

Approximate Encryption

Scheme[BGV12] BGV[Bra12, FV12] B/FV

[DM15] FHEW[CGGI16] TFHE[CKKS17] HEAAN

Plaintext

Finite Field
Packing

Binary string

Real/Complex numbers
Packing! Participation of privacy technology experts(academia and industry)

Operation

Addition, Multiplication

Look-up table & bootstrapping

Fixed-point Arithmetic! Developed practical yet rigorous solutions forprivacy preserving genomic data sharing andanalysis

Library

HElib (IBM)
SEAL (Microsoft Research)
Palisade (Duality inc.)

TFHE(inpher, gemalto, etc.)

HEAAN (SNU)! Motivated by real world biomedical applications! Reported in the media (e.g., Nature News,
GenomeWeb)
http://www.nature.com/news/extreme-cryptography-paves-way-to-personalized-medicine-1.17174

iDASH 2017 – Logistic Regression Model Training

iDASH 2017 – Logistic Regression Model Training! A machine learning model to predict the disease! 1500 records + 18 features for training! A machine learning model to predict the disease! 1500 records + 18 features for training

DiseaseTeams

HealthyAUC
0.7136

Secure learning
Time (mins)

Memory (MB)DiseaseOverall time(mins)

SNU

0.693410.2502775.333

10.360

CEA LIST

0.69302206.057

238.255

2207.363

KU Leuven

0.6722155.695

7266.727

160.912EPFL

0.658415.0891498.513

16.739MSR

0.6574385.02126299.344

396.390

Waseda*0.71542.077

7635.600

5.332

48.35629752.527

57.344

Saarland**N/A* Interactive mechanism, no complete guarantee on 80-bit security at “analyst” side

HealthyiDASH 2018 – Semi-Parallel GWASiDASH 2018 – Semi-Parallel GWAS

! !"#$%&'()'*"#'(+,-'(.//"0,1&,"*(2&%-,'/(3)+.24! !"#$%&'()'*"#'(+,-'(.//"0,1&,"*(2&%-,'/(3)+.24! 5(!"6718,1*&/(91:';(<',:<&;(=',:<&>(?(@A;BA@(2CD2

X

~

Z

Y

! 5(!"6718,1*&/(91:';(<',:<&;(=',:<&>(?(@A;BA@(2CD2Team

Co-variants

Response

SNP data

A*FHE 1A*FHE

A*FHE 2ChimeraDelft Blue
UCSD

X

Zi

~

Y

Repeat logistic regression n times

Table of Contents! BackgroundIBM

Version 1

Schemes
HEAAN

Time(mins)

Memory
(MB)
3,777

0.999

1,632.97

4,093

0.905

201.73

10,3750.993

215.95

15,1660.35

1,844.82

10,814

0.969

TFHE+HEAAN(Chimera)

Delft Blue

HEAAN

Log Reg

HEAAN
pkg: RNS HEAAN

1.66

14,901

0.993

0.42

3,387

0.989

HEAAN
pkg: PALISADE

3.80

10,230

0.993

0.09

1,512

0.983

52.49

15,204

0.984

52.37

15,177

0.988

23.35

8,651

0.911

52.65

15,6130.526

Log Reg
Chi2 test
SNU 1
SNU 2
IBM-Complex
IBM- Real

HEAAN
HEAAN
pkg: HElIb

Z

Co-variants

SNP data

X

Approximate Computation! Numerical Representation! [CKKS, AC17] Homomorphic Encryption for Arithmetic of Approximate Numbers! Bootstrapping! [CHKKS, EC18] Bootstrapping for Approximate Homomorphic Encryption! Related Works- . /0/- * - 1 /23

Zi~

ResponseY

Repeat logistic regression n times

Encode % into an integer % * +, for a scaling factor +! Construction

Y

Accuracy

922.48

Version 2

Lin Reg

Duality Inc
SNU

Submission~

XApproximate Computation

Approximate Computation! Numerical Representation! Numerical Representation

Encode % into an integer % * +, for a scaling factor +Encode % into an integer % * +, for a scaling factor +- . /0/- * - 1 /23- . /0/- * - 1 /23! Fixed-Point Multiplication
Compute % 4 %5 %6 and extract! Fixed-Point Multiplication
Compute % 4 %5 %6 and extract its significant digits %7 * +85 1 %its significant digits %7 * +85 1 %/9-:0;<;=9>?@ 4 /-:0 1 /283 ;<; =>?@ 1 /2 83 4 ?22>>=- 1 /28A . ?22? 1 /2 83 4 ?922?

/9-:0;<;=9>?@ 4 /-:0 1 /283 ;<; =>?@ 1 /2 83 4 ?22>>=- 1 /28A . ?22? 1 /2 83 4 ?922?
! Previous (LWE-based) HE
H
I#B 4 !"#CD % ,#BE FG 4 % J K;$LMN;O&

Modulo P plaintext vs Rounding operation

HEAAN

OQP

P

HEAAN

! A New Message Encoding#B 4 !"#CD % ,K%

R5 4 +%5 J K5

#B 4 !"#CD % ,#BE FG 4 +% J K;;$LMN;O&

Consider K as part of approximation error! A New Message EncodingO

R5 4 +%5 J K5

#BE FG 4 +% J K;;$LMN;O&

Consider K as part of approximation error! Homomorphic Operations
Input:

R5 * +%5 E R6 * +%6

Addition:

R5 J R6 * + 1 $%5 J %6 &O
R6 4 +%6 J K6

HEAANHEAAN! A New Message Encoding#B 4 !"#CD % ,R5 4 +%5 J K5

#B 4 !"#CD % ,#BE FG 4 +% J K;;$LMN;O&

Consider K as part of approximation error

R5 * +%5 E R6 * +%6

Addition:

R5 J R6 * + 1 $%5 J %6 &Multiplication:

R 4 R5 R6 * +6 1 %5 %6

R5 4 +%5 J K5

#BE FG 4 +% J K;;$LMN;O&

Consider K as part of approximation errorO
R6 4 +%6 J K6

! Homomorphic Operations
Input:! A New Message Encoding

R 4 +6 %5 %6 J KO
R6 4 +%6 J K6

! Homomorphic Operations
Input:

R5 * +%5 E R6 * +%6

Addition:

R5 J R6 * + 1 $%5 J %6 &Multiplication:

R 4 R5 R6 * +6 1 %5 %6Rounding:

R 7 * + 85 1 R * + 1 %5%6

R 4 +6 %5 %6 J K

R7 4 + 1 %5 %6 J KS

OQ+

HEAAN

Packed Ciphertext! A New Message Encoding#B 4 !"#CD % ,R5 4 +%5 J K5

#BE FG 4 +% J K;;$LMN;O&

Consider K as part of approximation errorO
R6 4 +%6 J K6

! Homomorphic Operations
Input:

R5 * +%5 E R6 * +%6

Addition:

R5 J R6 * + 1 $%5 J %6 &R 4 +6 %5 %6 J K

Multiplication: R 4 R5 R6 * +6 1 %5 %6Rounding:

R 7 * + 85 1 R * + 1 %5%6

! Support for the (approximate) fixed-point arithmetic !
! Leveled HE : O 4 +T

R7 4 + 1 %5 %6 J KS

OQ+

! Construction over the ring U 4 V W Y WX J / and UH 4 U;$LMN;O&Packed Ciphertext

Packed Ciphertext! Construction over the ring U 4 V W Y WX J / and UH 4 U;$LMN;O&! Construction over the ring U 4 V W Y WX J / and UH 4 U;$LMN;O&! Packing Technique:! Packing Technique:! A single ciphertext can encrypt a vector of plaintext values Z 4 $Z5E Z6 E [ E Z\ &! Parallel computation in a SIMD manner Z ] ^ 4 $Z5 ^5 E Z6 ^6 E [ E Z\ ^\ &! A single ciphertext can encrypt a vector of plaintext values Z 4 $Z5E Z6 E [ E Z\ &! Parallel computation in a SIMD manner Z ] ^ 4 $Z5 ^5 E Z6 ^6 E [ E Z\ ^\ &! RLWE-based HEAAN! A ciphertext can encrypt a polynomial % W _ U
85! Observation: WX J / 4 W ` a5 W ` a585 W ` a6 $W ` a685 & [ $W ` aX Y6 &$W ` aX Y6 &Packed Ciphertext

Packed Ciphertext! Construction over the ring U 4 V W Y WX J / and UH 4 U;$LMN;O&! Construction over the ring U 4 V W Y WX J / and UH 4 U;$LMN;O&! Packing Technique:! Packing Technique:! A single ciphertext can encrypt a vector of plaintext values Z 4 $Z5E Z6 E [ E Z\ &! Parallel computation in a SIMD manner Z ] ^ 4 $Z5 ^5 E Z6 ^6 E [ E Z\ ^\ &! RLWE-based HEAAN! A single ciphertext can encrypt a vector of plaintext values Z 4 $Z5E Z6 E [ E Z\ &! Parallel computation in a SIMD manner Z ] ^ 4 $Z5 ^5 E Z6 ^6 E [ E Z\ ^\ &! RLWE-based HEAAN! A ciphertext can encrypt a polynomial % W _ U! A ciphertext can encrypt a polynomial % W _ U! Observation: WX J / 4 W ` a5 W ` a585 W ` a6 $W ` a685 & [ $W ` aX Y6 &$W ` aX85
Y6 &! Observation: WX J / 4 W ` a5 W ` a585 W ` a6 $W ` a685 & [ $W ` aX Y6 &$W ` aX85
Y6 &! Decoding/Encoding function! Decoding/Encoding function

U 4 V W Y WX J / b c W Y WX J / ;; d ;; eXQ6

U 4 V W Y WX J / b c W Y WX J / ;; d ;; eXQ6

R W ; . ;Z 4 Z5E[ E ZXf6 E Zg 4 R$ag &R W ; . ;Z 4 Z5E[ E ZXf6 E Zg 4 R$ag &! Permutation of plaintext slots

Rotate: !"# Z5E Z6E [ E ZXf6 . !"#$Z6E [ E ZXY6 EZ5&

Table of Contents

Bootstrapping of HEAAN! Bootstrapping! Background! Ciphertexts of a leveled HE have a limited lifespan! Refresh a ciphertext #B 4 !"#CD % by evaluating the decryption circuit homomorphically()#CD #B 4 %; h i FG 4 % where i j 4 ()#j #B! Construction! [CKKS, AC17] Homomorphic Encryption for Arithmetic of Approximate Numbers! Bootstrapping! [CHKKS, EC18] Bootstrapping for Approximate Homomorphic Encryption! Related Works

Bootstrapping of HEAAN

Bootstrapping of HEAAN! Bootstrapping! Bootstrapping! Ciphertexts of a leveled HE have a limited lifespan! Refresh a ciphertext #B 4 !"#CD % by evaluating the decryption circuit homomorphically! Ciphertexts of a leveled HE have a limited lifespan! Refresh a ciphertext #B 4 !"#CD % by evaluating the decryption circuit homomorphically()#CD #B 4 %; h i FG 4 % where i j 4 ()#j #B! Bootstrapping key kl 4 !"#CD $FG&

i kl 4 i !"#CD FG()#CD #B 4 %; h i FG 4 % where i j 4 ()#j #B! Bootstrapping key kl 4 !"#CD $FG&

4 !"#CD i FG

4 !"#CD $%&i kl 4 i !"#CD FG

4 !"#CD i FG

4 !"#CD $%&! HEAAN! Homomorphic operations introduce errors

i kl 4 i !"#CD FG

4 !"#CD i FG J K 4 !"#CD $% J K&

! It is ok to have an additional error! How to evaluate the decryption circuit efficiently?

()#CD #B 4 #BE FG ;;;$LMN;O&Approximate Decryption

Approximate Decryption()#CD #B ; . ;P 4 #BE FG ; . ; P H 4 R,()#CD #B ; . ;P 4 #BE FG ; . ; P H 4 R,

P 4 Op J R for some p q n! Naïve solution: polynomial interpolation on m`nOE nOo

P 4 Op J R for some p q n! Idea 1: Restriction of domain R r O! Huge depth, complexity & inaccurate result

Approximate Decryption

Sine Evaluation()#CD #B ; . ;P 4 #BE FG ; . ; P H 4 R,
P 4 Op J R for some p q n! Idea 1: Restriction of domain R r O! Idea 2: Sine approximation R *H;Ft";u for
6s

u4

6s
;P
H

Sine Evaluation

Sine Evaluation! Direct Taylor approximation! Direct Taylor approximation! huge depth & complexity, low precision! huge depth & complexity, low precision! Idea 1: Low-degree approximation ofsmooth functions
vw u

85 y
4 x}z~w
6z {u Y-| 6z * #MF u Y-| ,85 y•w u 4 x}z~w 6z€5 { u Y-| 6z€5 * Ft"$u Y-| &.

Sine Evaluation

Sine Evaluation! Direct Taylor approximation! Direct Taylor approximation! huge depth & complexity, low precision! Idea 1: Low-degree approximation of! huge depth & complexity, low precision! Idea 1: Low-degree approximation ofsmooth functions

smooth functions

vw u 4 x}z~w

85 y

u Y-| 6z * #MF u Y-| ,vw u 4 x}z~w

85 y•w u 4 x}z~w

85 y
u Y-| 6z€5 * Ft"$u Y-| &.
6z€5 {•w u 4 x}z~w

85 y
u Y-| 6z€5 * Ft"$u Y-| &.
6z€5 {

6z {! Idea 2: Use double-angle formulavz€5 u4 vz6 u` •z6 u , •z€5; u

4 -•z u 1 vz u .

6z {u Y-| 6z * #MF u Y-| ,! Idea 2: Use double-angle formulavz€5 u 4 vz6 u ` •z6 u , •z€5; u 4 -•z u 1 vz u .

Sine Evaluation

Sine Evaluation! Direct Taylor approximation! Direct Taylor approximation! huge depth & complexity, low precision! Idea 1: Low-degree approximation of! huge depth & complexity, low precision! Idea 1: Low-degree approximation ofsmooth functions
vw u

85 y
4 x}z~w
6z {u Y-| 6z * #MF u Y-| ,85 y•w u 4 x}z~w 6z€5 { u Y-| 6z€5 * Ft"$u Y-| &.

smooth functions
vw u

85 y
4 x}z~w
6z {u Y-| 6z * #MF u Y-| ,85 y•w u 4 x}z~w 6z€5 { u Y-| 6z€5 * Ft"$u Y-| &.

! Idea 2: Use double-angle formula! Idea 2: Use double-angle formulavz€5 u 4 vz6 u ` •z6 u , •z€5; u 4 -•z u 1 vz u .

vz€5 u 4 vz6 u ` •z6 u , •z€5; u 4 -•z u 1 vz u .

Sine Evaluation

Sine Evaluation! Direct Taylor approximation! Direct Taylor approximation! huge depth & complexity, low precision! Idea 1: Low-degree approximation of! huge depth & complexity, low precision! Idea 1: Low-degree approximation ofsmooth functions

smooth functions

vw u 4 x}z~w

85 y

u Y-| 6z * #MF u Y-| ,vw u 4 x}z~w

85 y•w u 4 x}z~w

85 y
u Y-| 6z€5 * Ft"$u Y-| &.
6z€5 {•w u 4 x}z~w

85 y
u Y-| 6z€5 * Ft"$u Y-| &.
6z€5 {

6z {! Idea 2: Use double-angle formulavz€5 u4 vz6 u` •z6 u , •z€5; u

4 -•z u 1 vz u .

6z {u Y-| 6z * #MF u Y-| ,! Idea 2: Use double-angle formulavz€5 u 4 vz6 u ` •z6 u , •z€5; u 4 -•z u 1 vz u .

Sine Evaluation

Sine Evaluation! Direct Taylor approximation! Direct Taylor approximation! huge depth & complexity, low precision! huge depth & complexity, low precision! Idea 1: Low-degree approximation of! Idea 1: Low-degree approximation ofsmooth functions
vw u

85 y
4 x}z~w
6z {smooth functions

u Y-| 6z * #MF u Y-| ,

vw u

85 y

85 y
4 x}z~w
6z {u Y-| 6z * #MF u Y-| ,85 y•w u 4 x}z~w 6z€5 { u Y-| 6z€5 * Ft"$u Y-| &.

•w u 4 x}z~w 6z€5 { u Y-| 6z€5 * Ft"$u Y-| &.
! Idea 2: Use double-angle formula! Idea 2: Use double-angle formulavz€5 u 4 vz6 u ` •z6 u , •z€5; u 4 -•z u 1 vz u .

vz€5 u 4 vz6 u ` •z6 u , •z€5; u 4 -•z u 1 vz u .

Sine Evaluation

Slot-Coefficient Switching! Ring-based HEAAN! Direct Taylor approximation! Homomorphic operations on plaintext slots, not on coefficients! We need to perform the modulo reduction on coefficients! huge depth & complexity, low precision! Idea 1: Low-degree approximation ofsmooth functions
85 y

vw u 4 x}z~w 6z { u Y-| 6z * #MF u Y-| ,•w u 4 x}z~w

85 y
u Y-| 6z€5 * Ft"$u Y-| &.
6z€5 {! Idea 2: Use double-angle formulavz€5 u 4 vz6 u ` •z6 u , •z€5; u 4 -•z u 1 vz u .
! Numerically stable & Linear complexity•| u * Ft";u•| u * Ft";uSlot-Coefficient Switching

Slot-Coefficient Switching! Ring-based HEAAN! Ring-based HEAAN! Homomorphic operations on plaintext slots, not on coefficients! We need to perform the modulo reduction on coefficients! Homomorphic operations on plaintext slots, not on coefficients! We need to perform the modulo reduction on coefficients! Pre/post computation before/after sine evaluation
Coefficientc W Y WX J /! Pre/post computation before/after sine evaluation
Plaintext SlotseX Y6

P W 4 O 1 p W J R$W&
1. coeff to slot
3. slot to coeff! Performance of Bootstrapping! Depth consumption : Sine evaluation! Complexity: Slot-Coefficient switchings (# of slots)$Rw ER5 E [ E RX85 &! Experimental Results! 127 + 12 = 139 s / 128 slots X 12 bits
! 456 + 68 = 524 s / 128 slots X 24 bits

! Background! Construction! [CKKS, AC17] Homomorphic Encryption for Arithmetic of Approximate Numbers

c W Y WX J /eX Y6
2. sine eval

1. coeff to slot

$Pw EP5 E [ PX85 &3. slot to coeff$Rw ER5 E [ E RX85 &R W 4 Rw J • J RX85 WX85

R W 4 Rw J • J RX85 WX85

Table of Contents

Plaintext Slots

P W 4 O 1 p W J R$W&

2. sine eval
$Pw EP5 E [ PX85 &Coefficient

Followed Work! Improved Bootstrapping for Approximate Homomorphic Encryption! Joint work with Hao Chen and Ilaria Chillotti (submission to EC19)! FFT-like algorithms to optimize Slot-Coefficient switchings! Better evaluation of sine function based on Chebyshev approximation! [JKLS, CCS18] Secure Outsourced Matrix Computation and Application to Neural Networks! Evaluation of an encrypted CNN model on the encrypted MNIST data

! Bootstrapping! [CHKKS, EC18] Bootstrapping for Approximate Homomorphic Encryption! [CHKKS, SAC18] A Full RNS Variant of Approximate Homomorphic Encryption! Better performance without any high-precision arithmetic library! iDASH 2018

! Related Works! [KS, ICISC18] Approximate Homomorphic Encryption over the Real Numbers