Transcript Document

* Partially sponsored by IARPA SPAR
* Partially sponsored by DARPA PROCEED

We implemented [BGV’12], with optimizations
from [GHS’12]
◦
◦
◦
◦
Working over polynomials rings 𝑍 𝑋 Φ𝑚 𝑋
Security based on ring-LWE (+circular security)
Packed ciphertexts using polynomial CRT [SV’11]
Polynomials represented in “Double-CRT” format
 𝒂 𝑿 ∈ 𝒁𝒒 [𝑿]/𝝓𝒎 (𝑿) is 𝜶𝒊𝒋 = 𝒂 𝑿 𝒎𝒐𝒅 𝑭𝒊 𝑿 , 𝒑𝒋
 𝑝𝑗 are integer factors of q
 𝐹𝑖 𝑋 are polynomial factors of Φ𝑚 (𝑋) modulo q
◦ Assorted other optimizations
𝒊,𝒋
EncryptedArray/EncrytedArrayMod2r
Matrices for keyswitching
Ctxt
FHE
Ciphertext
operations
KeyGen/Enc/Dec
SingleCRT/DoubleCRT
parameters
KeySwitching
FHEcontext
Crypto
Routing plaintext slots
Math
polynomial arithmetic
CModulus
polynomials mod p
bluestein
FFT/IFFT
PAlgebraTwo/2r
plaintext-slot algebra
PAlgebra
Structure of Zm*
IndexSet/IndexMap
Indexing utilities
NumbTh
miscellaneous
utilities
timing

A ciphertext encrypts an array of values
◦ Either bits, elements of GF(2n), or integers mod 2r

Array size determined by other parameters
◦ Intended depth of circuits & security parameter
◦ E.g., 378, 600, 682, 720, 1285, …

Homomorphic operations include:
◦
◦
◦
◦
Element-wise addition/subtraction, multiplication
Addition/subtraction, multiplication by constants
Cyclic/non-cyclic shifts
Also SELECT(A1,A2, pattern)
= patternA1 + (1-pattern)A2

Security parameter=80, circuit width=4 arrays
(*)
Circuit “depth”
Array size
Time (hrs:min:sec)
7
224
0:00:38
14
480
0:02:49
35
512
0:19:05
70
720
3:01:51
84
2048
5:24:47
(*) maybe similar work to homomorphic AES
◦ If true, ~12x speedup on our previous implementation
[CRYPTO 2012]

Various optimizations and design choices
1.
2.
3.
4.
5.
6.
7.

Representing plaintext algebra (§2.4, §2.5)
Double-CRT representation of polynomials(§2.8)
Ciphertexts as “generic” vectors (§3.1.1-§3.1.3)
Dynamic noise estimate (§3.1.4)
Key-switching optimizations (§3.1.6)
Which key-switching matrices to generate (§3.3)
Implementation of rotation/shifts (§4.1)
Here I will only talk about 3 & 4
§ The section numbers correspond to
the design & implementation document

The library handles several cipehrtext “types”
◦ A “canonical” ciphertext is a pair (c0,c1)
 Decryption is c0 + c1 𝑠 𝑞 𝑚𝑜𝑑 2, with s the secret key
◦ After multiplication we have a triple (c0,c1,c2)
 Decryption is c0 + c1 𝑠 + 𝑐2 𝑠 2
𝑞
𝑚𝑜𝑑 2
◦ After “automorphism” 𝑋 ↦ 𝑋 𝑘 we have (c0,c1)
 Decryption is c0 + c1 𝑠′


𝑞
𝑚𝑜𝑑 2, 𝑠 ′ 𝑋 = 𝑠(𝑋 𝑘 )
Also, we may have more than one secret key 𝑠𝑖
Need a unified interface to handle them all

A ciphertext in the library is a vector of parts
◦ A part consists of polynomial & “handle”

Handle points to the secret key that should
multiply this part on decryption
◦ Handle consists of three integers H=(𝑟, 𝑡, 𝑖)
 I.e., this polynomial is to be multiplied by 𝑠𝑖 𝑋 𝑡
◦ H points to the constant 𝑠 𝑋 ≡ 1 iff 𝑟 = 0
◦ H points to a “base secret key” iff 𝑟 = 𝑡 = 1
𝑟

Using handles makes for a flexible design
◦ Easy to manipulate ciphertexts, just by handling
one part at a time

In principle, a ciphertext can have arbitrary
many parts with arbitrary distinct handles
◦ But we scarcely support handles with both 𝑟, 𝑡 > 1
◦ or handles that name different secret keys 𝑠𝑖 , 𝑠𝑗

By convention, the 1st part in any ciphertext
always points to the constant 1

Multiplying 𝑝, 𝐻 = 𝑟, 𝑡, 𝑖
× {𝑝′ , 𝐻 ′ = 𝑟′, 𝑡′, 𝑖′ }
◦ We first “multiply the handles”, H × 𝐻 ′ = 𝐻 ′′ where:
 If 𝑟 = 0 then 𝐻′′ = 𝐻′, if 𝑟′ = 0 then 𝐻′′ = 𝐻
 If both 𝑟, 𝑟 ′ > 0, and 𝑖 = 𝑖 ′ and 𝑡 = 𝑡 ′ then 𝐻′′ = (𝑟 + 𝑟 ′ , 𝑡, 𝑖)
 Else abort
◦ Then we output {𝑝 × 𝑝′, 𝐻′′}

Adding a part {𝑝, 𝐻} to a ciphertext 𝑐
◦ If 𝑐 contains a part {𝑝′, 𝐻} with the same handle,
then replace it by {𝑝 + 𝑝′, 𝐻}
◦ Else just append the part {𝑝, 𝐻} to 𝑐

Applying 𝑋 ↦ 𝑋 𝑘 to {𝑝, 𝑟, 𝑡, 𝑖 }
◦ Output {𝑝(𝑋 𝑘 ), 𝑟, 𝑘 ⋅ 𝑡, 𝑖 }

Multiplication 𝑐 × = 𝑐1 × 𝑐2 via tensoring
◦ Output

𝑝,𝐻 ∈𝑐1 , 𝑝′,𝐻′ ∈𝑐2
𝑝, 𝐻 × {𝑝′ , 𝐻 ′ }
Addition 𝑐 + = 𝑐1 + 𝑐2
◦ Add all the parts of 𝑐2 to 𝑐1

Applying 𝑋 ↦ 𝑋 𝑘 to 𝑐
◦ Apply 𝑋 ↦ 𝑋 𝑘 to all the parts of 𝑐

Key-switching, modulus-switching also applied
to each part separately
◦ Key-switching transforms {𝑝, 𝑟, 𝑡, 𝑖 } with 𝑟 > 1 or 𝑡 > 1
into a canonical pair 𝑝0 , 0,∗,∗ , 𝑝1 , 1,1, 𝑖

The “noise” in a ciphertext 𝑐 = (𝑐0, 𝑐1, … , 𝑐𝑡) is
the polynomial 𝑎 = 𝑘 𝑐𝑘 𝑠′𝑘 𝑞
◦ Computed during decryption before reduction mod 2

The “magnitude” of 𝑎 is the norm of the vector
𝑗
∗
𝑎 𝜁𝑚 : 𝑗 ∈ 𝑍𝑚
◦ 𝜁𝑚 is the principle complex m’th root of unity, 𝑒 2𝜋𝑖/𝑚
◦ This vector is the canonical embedding of 𝑎

Each ciphertext carries a “noise estimate”


Thinking of 𝑐𝑘 , 𝑠′𝑘 as random variables, estimate
heuristically the expected value 𝐸𝑋𝑃 𝑎 𝜁𝑚 2
Each ciphertext can be written as 𝑐 = 𝑑 + 𝑒
◦ Where


𝑘 𝑑𝑘 𝑠′𝑘 𝑞
𝑞
= 0 and the 𝑒𝑘 ’s are small
So 𝑎 = 𝑘 𝑒𝑘 𝑠′𝑘 (without reduction modulo q),
and 𝑎(𝐸𝑋𝑃 𝑎 𝜁𝑚 2
If the 𝑒𝑘 and 𝑠′𝑘 are independent, we have
𝐸𝑋𝑃 𝑎 𝜁𝑚 2 = 𝑘 𝐸𝑋𝑃 𝑒𝑘 𝜁𝑚 2 ⋅ 𝐸𝑋𝑃 𝑠′𝑘 𝜁𝑚
◦ We estimate 𝐸𝑋𝑃 𝑒𝑘 𝜁𝑚
2
, 𝐸𝑋𝑃 𝑠′𝑘 𝜁𝑚
2
2
separately

𝑒(𝑋) is usually a “rounding error” polynomial
◦ Coefficients are heuristically uniform in [-1,+1]
◦ So 𝐸𝑋𝑃 𝑒 𝜁𝑚 = 0, hence 𝐸𝑋𝑃 𝑒 𝜁𝑚 2 = 𝑉𝐴𝑅 𝑒 𝜁𝑚

𝑒 𝜁𝑚 =
𝜙 𝑚 −1
𝑖
𝑒
𝜁
𝑖 𝑚,
𝑖=0
and for every 𝑖:
𝑖 is a magnitude-one complex constant
◦ 𝜁𝑚
◦ 𝑒𝑖 is a 0-mean random-variable with variance 1/3

Hence 𝐸𝑋𝑃 𝑒 𝜁𝑚
2
= 𝑉𝐴𝑅 𝑒 𝜁𝑚
= 𝝓 𝒎 /𝟑

Recall that 𝒔′ (𝑋) = 𝑠𝑖 𝑋 𝑡
𝑟
for some r,t,i
◦ 𝑋 ↦ 𝑋 𝑡 does not change the noise magnitude
◦ 𝑠𝑖 is chosen at random with coefficients − 1 0 1
and a fixed Hamming weight 𝑤 (e.g. 𝑤 = 64)

So we need to estimate 𝐸𝑋𝑃 𝒔 𝜁𝑚 𝑟 2 for a
random Hamming-weight-𝑤 polynomial 𝑠
◦ For 𝑟 = 1, each to see that 𝐸𝑋𝑃 𝒔 𝜁𝑚
◦ For 𝑟 > 1, we get 𝑬𝑿𝑷 𝒔 𝜻𝒎
𝒓 𝟐
2
≈ 𝒓! ⋅ 𝑯𝒓
 Proof is nontrivial
 Assuming that 𝑟 ≪ min(log 𝑚 , 𝑤)
 We mainly use r=2,3
=𝑤




A freshly-encrypted ciphertext comes with
some noise estimate
The estimate evolves during computation
We use it to decide when to do modulusswitching
Also the application can use it to know if it
should expect a decryption error



We have the basic BGV implementation more
or less done
Evaluate nontrivial circuits in a few minutes,
and even complex circuits in just a few hours
Amenable to massive parallelism