Fully Homomorphic SIMD Operations¶
Year: 2011
type: technique collection: schemes status: auto
Links: ePrint 2011/133
Summary¶
Auto-extracted summary (unreviewed)
Smart and Vercauteren show how to choose parameters for the Smart-Vercauteren / Gentry-Halevi variant of Gentry's FHE so that a single ciphertext packs many plaintext slots (SIMD) over finite fields of characteristic two while keeping the efficient FFT-based key generation of Gentry-Halevi. The SIMD slots are then used to run the recrypt (bootstrapping) procedure in parallel, which gives a substantial speed-up over recrypting each element separately. Two use cases, homomorphic AES and encrypted database lookup, illustrate the approach; experiments compare four packing options at toy security levels (N around 2048-2560).
Abstract¶
At PKC 2010 Smart and Vercauteren presented a variant of Gentry’s fully homomorphic public key encryption scheme and mentioned that the scheme could support SIMD style operations. The slow key generation process of the Smart–Vercauteren system was then addressed in a paper by Gentry and Halevi, but their key generation method appears to exclude the SIMD style operation alluded to by Smart and Vercauteren. In this paper, we show how to select parameters to enable such SIMD operations, whilst still maintaining practicality of the key generation technique of Gentry and Halevi. As such, we obtain a somewhat homomorphic scheme supporting both SIMD operations and operations on large finite fields of characteristic two. This somewhat homomorphic scheme can be made fully homomorphic in a naive way by recrypting all data elements seperately. However, we show that the SIMD operations can be used to perform the recrypt procedure in parallel, resulting in a substantial speed-up. Finally, we demonstrate how such SIMD operations can be used to perform various tasks by studying two use cases: implementing AES homomorphically and encrypted database lookup.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | parameter selection that enables SIMD slot operations while keeping Gentry-Halevi key generation practical | llm | 0.75 |
| contribution | somewhat homomorphic scheme over large finite fields of characteristic two | llm | 0.75 |
| contribution | parallel recryption (bootstrapping) using SIMD slots | llm | 0.75 |
| contribution | use cases: homomorphic AES evaluation and encrypted database lookup | llm | 0.75 |
| contribution | cost/space comparison of four packing options with a prototype implementation | llm | 0.75 |
| schemes | Smart-Vercauteren FHE | llm | 0.75 |
| schemes | Gentry-Halevi FHE | llm | 0.75 |
| schemes | SIMD batching | llm | 0.75 |
| tasks | homomorphic AES evaluation | llm | 0.75 |
| tasks | encrypted database lookup | llm | 0.75 |
| security level | toy / low security levels only (N approx. 2048-2560, explicitly not claimed secure) | llm | 0.75 |
| threat model | outsourced computation on an untrusted server | llm | 0.75 |
| interaction | non-interactive FHE | llm | 0.75 |
| limitations | experiments only at toy security levels, chosen for comparison with Gentry-Halevi | llm | 0.75 |
| limitations | SIMD overhead depends on the specific finite field / cyclotomic field combination and has no clean asymptotic meaning | llm | 0.75 |
| limitations | cost estimates ignore additions and data management | llm | 0.75 |
| llm relevance | low | llm | 0.75 |
| key result | ciphertext space for 16 elements of F_2^8: 2560t bits (Option 3, full SIMD) vs 262144t bits (Option 1, bitwise) (N=2560 vs N=2048, n'=8, l'=16) | llm | 0.75 |
| key result | parameter t needed for full recryption: t=600 for Options 1-2, t=800 for Options 3-4 ((N,n,l) = (2048,1,1), (2560,8,1), (2560,8,16), (2560,1,16)) | llm | 0.75 |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: Leveled / somewhat HE 18 [p.1], PIR 5 [p.17], MPC 2 [p.15]
- hardware: Intel Xeon 1 [p.14]
- technique: SIMD packing 67 [p.1], Bootstrapping 5 [p.1], Bitslicing 3 [p.2]
- assumption: Lattice-based 8 [p.1], RLWE 4 [p.3], LWE 4 [p.3]
- task: Language modeling / generation 3 [p.9]
- topic: Homomorphic encryption 38 [p.1]
Related papers¶
- this paper follow up of Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes — follow-up listed for scheme "Smart–Vercauteren (SIMD FHE)"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s30-1_eprint-2011-133.pdf |
schemes | 19 | 409.1 KB | d963475e486c |
Database key: fully-homomorphic-simd-operations · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set fully-homomorphic-simd-operations COLUMN VALUE