Skip to content

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]

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