Skip to content

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]

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