Multi-Identity and Multi-Key Leveled FHE from Learning with Errors¶
Year: 2014
type: technique collection: schemes status: auto
Links: ePrint 2014/798
Summary¶
Auto-extracted summary (unreviewed)
The paper extends the Gentry-Sahai-Waters identity-based leveled FHE from the single-identity to the multi-identity setting: an LWE-based IBE equipped with a 'masking system' (shown to exist for the GPV IBE) is compiled into a multi-identity IBFHE whose ciphertexts are expanded to dN x dN matrices over d distinct identities, selectively secure in the random oracle model under LWE. The same ideas give a multi-key leveled FHE secure under standard LWE in the standard model, the first multi-key FHE from a well-established assumption (Lopez-Alt, Tromer and Vaikuntanathan relied on the non-standard DSPR assumption); both schemes are 1-hop homomorphic.
Abstract¶
Gentry, Sahai and Waters recently presented the first (leveled) identity-based fully homomorphic (IBFHE) encryption scheme (CRYPTO 2013). Their scheme however only works in the single-identity setting; that is, homomorphic evaluation can only be performed on ciphertexts created with the same identity. In this work, we extend their results to the multi-identity setting and obtain a multi-identity IBFHE scheme that is selectively secure in the random oracle model under the hardness of Learning with Errors (LWE). We also obtain a multi-key fullyhomomorphic encryption (FHE) scheme that is secure under LWE in the standard model. This is the first multi-key FHE based on a wellestablished assumption such as standard LWE. The multi-key FHE of L´opez-Alt, Tromer and Vaikuntanathan (STOC 2012) relied on a nonstandard assumption, referred to as the Decisional Small Polynomial Ratio assumption.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | first multi-identity leveled IBFHE whose security rests on a well-established problem (LWE), without indistinguishability obfuscation | llm | 0.80 |
| contribution | compiler transforming an LWE-based IBE with a secure masking system into a multi-identity IBFHE | llm | 0.80 |
| contribution | concrete instantiation via the Gentry-Peikert-Vaikuntanathan IBE (random oracle model) | llm | 0.80 |
| contribution | first multi-key leveled FHE secure under standard LWE in the standard model | llm | 0.80 |
| schemes | GSW | llm | 0.80 |
| schemes | identity-based FHE | llm | 0.80 |
| schemes | multi-key FHE | llm | 0.80 |
| schemes | LWE | llm | 0.80 |
| threat model | selective-identity IND-CPA in the random oracle model (multi-identity IBFHE); IND-CPA under LWE in the standard model (multi-key FHE) | llm | 0.80 |
| interaction | non-interactive FHE | llm | 0.80 |
| limitations | schemes are only 1-hop homomorphic: no further evaluation after an evaluated ciphertext is produced | llm | 0.80 |
| limitations | multi-identity IBFHE is only selectively secure and relies on the random oracle model (GPV IBE) | llm | 0.80 |
| limitations | leveled: circuit depth L and maximum number of identities D are fixed at setup | llm | 0.80 |
| limitations | ciphertext size grows with the number of distinct identities | llm | 0.80 |
| llm relevance | low | llm | 0.80 |
| key result | ciphertext expansion: dN x dN matrix for d distinct identities (d at most D) (multi-identity evaluation of NAND circuits) | llm | 0.80 |
| key result | correctness condition: q > 8 w B (DN+1)^L (depth-L NAND circuits, up to D identities) | llm | 0.80 |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: GSW 15 [p.2], Multi-key HE 10 [p.1], Leveled / somewhat HE 4 [p.1], MPC 2 [p.2], Functional encryption 2 [p.19]
- library: Concrete (Zama) 1 [p.15]
- technique: Compiler 25 [p.2], Bootstrapping 2 [p.19], Lookup table 2 [p.15]
- assumption: LWE 39 [p.1], Lattice-based 23 [p.2], RLWE 6 [p.18]
- topic: Homomorphic encryption 26 [p.1]
Related papers¶
- this paper follow up of Multi-Key Homomorphic Encryption from TFHE — follow-up listed for scheme "Multi-key TFHE"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s38-2_eprint-2014-798.pdf |
schemes | 28 | 567.9 KB | 125e85811774 |
Database key: multi-identity-and-multi-key-leveled-fhe-from-learning-with-errors · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set multi-identity-and-multi-key-leveled-fhe-from-learning-with-errors COLUMN VALUE