TU Darmstadt / ULB / TUbiblio

Functional Encryption for Turing Machines with Dynamic Bounded Collusion from LWE

Agrawal, Shweta ; Maitra, Monosij ; Vempati, Narasimha Sai ; Yamada, Shota
Hrsg.: Malkin, Tal ; Peikert, Chris (2021)
Functional Encryption for Turing Machines with Dynamic Bounded Collusion from LWE.
41st Annual International Cryptology Conference (CRYPTO 2021). virtual Conference (16.-20.08.2021)
doi: 10.1007/978-3-030-84259-8_9
Konferenzveröffentlichung, Bibliographie

Kurzbeschreibung (Abstract)

The classic work of Gorbunov, Vaikuntanathan and Wee (CRYPTO 2012) and follow-ups provided constructions of bounded collusion Functional Encryption (FE) for circuits from mild assumptions. In this work, we improve the state of affairs for bounded collusion FE in several ways: 1.New Security Notion. We introduce the notion of dynamic bounded collusion FE, where the declaration of collusion bound is delayed to the time of encryption. This enables the encryptor to dynamically choose the collusion bound for different ciphertexts depending on their individual level of sensitivity. Hence, the ciphertext size grows linearly with its own collusion bound and the public key size is independent of collusion bound. In contrast, all prior constructions have public key and ciphertext size that grow at least linearly with a fixed bound Q.2.CPFE for circuits with Dynamic Bounded Collusion. We provide the first CPFE schemes for circuits enjoying dynamic bounded collusion security. By assuming identity based encryption (IBE), we construct CPFE for circuits of unbounded size satisfying non-adaptive simulation based security. By strengthening the underlying assumption to IBE with receiver selective opening security, we obtain CPFE for circuits of bounded size enjoying adaptive simulation based security. Moreover, we show that IBE is a necessary assumption for these primitives. Furthermore, by relying on the Learning With Errors (LWE) assumption, we obtain the first succinct CPFE for circuits, i.e. supporting circuits with unbounded size, but fixed output length and depth. This scheme achieves adaptive simulation based security.3.KPFE for circuits with dynamic bounded collusion. We provide the first KPFE for circuits of unbounded size, but bounded depth and output length satisfying dynamic bounded collusion security from LWE. Our construction achieves adaptive simulation security improving security of 20.4.KP and CP FE for TM/NL with dynamic bounded collusion. We provide the first KPFE and CPFE constructions of bounded collusion functional encryption for Turing machines in the public key setting from LWE. Our constructions achieve non-adaptive simulation based security. Both the input and the machine in our construction can be of unbounded polynomial length.We provide a variant of the above scheme that satisfies adaptive security, but at the cost of supporting a smaller class of computation, namely Nondeterministic Logarithmic-space (NL). Since NL contains Nondeterministic Finite Automata (NFA), this result subsumes all prior work of bounded collusion FE for uniform models from standard assumptions 7, 9.

Typ des Eintrags: Konferenzveröffentlichung
Erschienen: 2021
Herausgeber: Malkin, Tal ; Peikert, Chris
Autor(en): Agrawal, Shweta ; Maitra, Monosij ; Vempati, Narasimha Sai ; Yamada, Shota
Art des Eintrags: Bibliographie
Titel: Functional Encryption for Turing Machines with Dynamic Bounded Collusion from LWE
Sprache: Englisch
Publikationsjahr: 11 August 2021
Verlag: Springer
Buchtitel: Advances in Cryptology - CRYPTO 2021
Reihe: Lecture Notes in Computer Science
Band einer Reihe: 12828
Veranstaltungstitel: 41st Annual International Cryptology Conference (CRYPTO 2021)
Veranstaltungsort: virtual Conference
Veranstaltungsdatum: 16.-20.08.2021
DOI: 10.1007/978-3-030-84259-8_9
Kurzbeschreibung (Abstract):

The classic work of Gorbunov, Vaikuntanathan and Wee (CRYPTO 2012) and follow-ups provided constructions of bounded collusion Functional Encryption (FE) for circuits from mild assumptions. In this work, we improve the state of affairs for bounded collusion FE in several ways: 1.New Security Notion. We introduce the notion of dynamic bounded collusion FE, where the declaration of collusion bound is delayed to the time of encryption. This enables the encryptor to dynamically choose the collusion bound for different ciphertexts depending on their individual level of sensitivity. Hence, the ciphertext size grows linearly with its own collusion bound and the public key size is independent of collusion bound. In contrast, all prior constructions have public key and ciphertext size that grow at least linearly with a fixed bound Q.2.CPFE for circuits with Dynamic Bounded Collusion. We provide the first CPFE schemes for circuits enjoying dynamic bounded collusion security. By assuming identity based encryption (IBE), we construct CPFE for circuits of unbounded size satisfying non-adaptive simulation based security. By strengthening the underlying assumption to IBE with receiver selective opening security, we obtain CPFE for circuits of bounded size enjoying adaptive simulation based security. Moreover, we show that IBE is a necessary assumption for these primitives. Furthermore, by relying on the Learning With Errors (LWE) assumption, we obtain the first succinct CPFE for circuits, i.e. supporting circuits with unbounded size, but fixed output length and depth. This scheme achieves adaptive simulation based security.3.KPFE for circuits with dynamic bounded collusion. We provide the first KPFE for circuits of unbounded size, but bounded depth and output length satisfying dynamic bounded collusion security from LWE. Our construction achieves adaptive simulation security improving security of 20.4.KP and CP FE for TM/NL with dynamic bounded collusion. We provide the first KPFE and CPFE constructions of bounded collusion functional encryption for Turing machines in the public key setting from LWE. Our constructions achieve non-adaptive simulation based security. Both the input and the machine in our construction can be of unbounded polynomial length.We provide a variant of the above scheme that satisfies adaptive security, but at the cost of supporting a smaller class of computation, namely Nondeterministic Logarithmic-space (NL). Since NL contains Nondeterministic Finite Automata (NFA), this result subsumes all prior work of bounded collusion FE for uniform models from standard assumptions 7, 9.

Zusätzliche Informationen:

Proceedings, Part IV

Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
20 Fachbereich Informatik > Angewandte Kryptographie
Hinterlegungsdatum: 16 Aug 2021 07:15
Letzte Änderung: 16 Aug 2021 07:15
PPN:
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen