Adaptively secure ABE for DFA from k-lin and more

Junqing Gong; Hoeteck Wee

doi:10.1007/978-3-030-45727-3_10

Adaptively secure ABE for DFA from k-lin and more

Junqing Gong^*
, Hoeteck Wee

^*Corresponding author for this work

Software Engineering Institute

CNRS

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

24 Scopus citations

Abstract

In this work, we present:the first adaptively secure ABE for DFA from the k-Lin assumption in prime-order bilinear groups; this resolves one of open problems posed by Waters [CRYPTO’12];the first ABE for NFA from the k-Lin assumption, provided the number of accepting paths is smaller than the order of the underlying group; the scheme achieves selective security;the first compact adaptively secure ABE (supporting unbounded multi-use of attributes) for branching programs from the k-Lin assumption, which generalizes and simplifies the recent result of Kowalczyk and Wee for boolean formula (NC1) [EUROCRYPT’19]. Our adaptively secure ABE for DFA relies on a new combinatorial mechanism avoiding the exponential security loss in the number of states when naively combining two recent techniques from CRYPTO’19 and EUROCRYPT’19. This requires us to design a selectively secure ABE for NFA; we give a construction which is sufficient for our purpose and of independent interest. Our ABE for branching programs leverages insights from our ABE for DFA.

Original language	English
Title of host publication	Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Editors	Anne Canteaut, Yuval Ishai
Publisher	Springer
Pages	278-308
Number of pages	31
ISBN (Print)	9783030457266
DOIs	https://doi.org/10.1007/978-3-030-45727-3_10
State	Published - 2020
Event	39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020 - Zagreb, Croatia Duration: 10 May 2020 → 14 May 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12107 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020
Country/Territory	Croatia
City	Zagreb
Period	10/05/20 → 14/05/20

Access to Document

10.1007/978-3-030-45727-3_10

Cite this

Gong, J., & Wee, H. (2020). Adaptively secure ABE for DFA from k-lin and more. In A. Canteaut, & Y. Ishai (Eds.), Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 278-308). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12107 LNCS). Springer. https://doi.org/10.1007/978-3-030-45727-3_10

Gong, Junqing ; Wee, Hoeteck. / Adaptively secure ABE for DFA from k-lin and more. Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. editor / Anne Canteaut ; Yuval Ishai. Springer, 2020. pp. 278-308 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3ad6eb916278440ca94eefc153a4cfc5,

title = "Adaptively secure ABE for DFA from k-lin and more",

abstract = "In this work, we present:the first adaptively secure ABE for DFA from the k-Lin assumption in prime-order bilinear groups; this resolves one of open problems posed by Waters [CRYPTO{\textquoteright}12];the first ABE for NFA from the k-Lin assumption, provided the number of accepting paths is smaller than the order of the underlying group; the scheme achieves selective security;the first compact adaptively secure ABE (supporting unbounded multi-use of attributes) for branching programs from the k-Lin assumption, which generalizes and simplifies the recent result of Kowalczyk and Wee for boolean formula (NC1) [EUROCRYPT{\textquoteright}19]. Our adaptively secure ABE for DFA relies on a new combinatorial mechanism avoiding the exponential security loss in the number of states when naively combining two recent techniques from CRYPTO{\textquoteright}19 and EUROCRYPT{\textquoteright}19. This requires us to design a selectively secure ABE for NFA; we give a construction which is sufficient for our purpose and of independent interest. Our ABE for branching programs leverages insights from our ABE for DFA.",

author = "Junqing Gong and Hoeteck Wee",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2020.; 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020 ; Conference date: 10-05-2020 Through 14-05-2020",

year = "2020",

doi = "10.1007/978-3-030-45727-3\_10",

language = "英语",

isbn = "9783030457266",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "278--308",

editor = "Anne Canteaut and Yuval Ishai",

booktitle = "Advances in Cryptology {\textendash} EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings",

address = "德国",

}

Gong, J & Wee, H 2020, Adaptively secure ABE for DFA from k-lin and more. in A Canteaut & Y Ishai (eds), Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12107 LNCS, Springer, pp. 278-308, 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020, Zagreb, Croatia, 10/05/20. https://doi.org/10.1007/978-3-030-45727-3_10

Adaptively secure ABE for DFA from k-lin and more. / Gong, Junqing; Wee, Hoeteck.
Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. ed. / Anne Canteaut; Yuval Ishai. Springer, 2020. p. 278-308 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12107 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Adaptively secure ABE for DFA from k-lin and more

AU - Gong, Junqing

AU - Wee, Hoeteck

N1 - Publisher Copyright: © International Association for Cryptologic Research 2020.

PY - 2020

Y1 - 2020

N2 - In this work, we present:the first adaptively secure ABE for DFA from the k-Lin assumption in prime-order bilinear groups; this resolves one of open problems posed by Waters [CRYPTO’12];the first ABE for NFA from the k-Lin assumption, provided the number of accepting paths is smaller than the order of the underlying group; the scheme achieves selective security;the first compact adaptively secure ABE (supporting unbounded multi-use of attributes) for branching programs from the k-Lin assumption, which generalizes and simplifies the recent result of Kowalczyk and Wee for boolean formula (NC1) [EUROCRYPT’19]. Our adaptively secure ABE for DFA relies on a new combinatorial mechanism avoiding the exponential security loss in the number of states when naively combining two recent techniques from CRYPTO’19 and EUROCRYPT’19. This requires us to design a selectively secure ABE for NFA; we give a construction which is sufficient for our purpose and of independent interest. Our ABE for branching programs leverages insights from our ABE for DFA.

AB - In this work, we present:the first adaptively secure ABE for DFA from the k-Lin assumption in prime-order bilinear groups; this resolves one of open problems posed by Waters [CRYPTO’12];the first ABE for NFA from the k-Lin assumption, provided the number of accepting paths is smaller than the order of the underlying group; the scheme achieves selective security;the first compact adaptively secure ABE (supporting unbounded multi-use of attributes) for branching programs from the k-Lin assumption, which generalizes and simplifies the recent result of Kowalczyk and Wee for boolean formula (NC1) [EUROCRYPT’19]. Our adaptively secure ABE for DFA relies on a new combinatorial mechanism avoiding the exponential security loss in the number of states when naively combining two recent techniques from CRYPTO’19 and EUROCRYPT’19. This requires us to design a selectively secure ABE for NFA; we give a construction which is sufficient for our purpose and of independent interest. Our ABE for branching programs leverages insights from our ABE for DFA.

UR - https://www.scopus.com/pages/publications/85090001021

U2 - 10.1007/978-3-030-45727-3_10

DO - 10.1007/978-3-030-45727-3_10

M3 - 会议稿件

AN - SCOPUS:85090001021

SN - 9783030457266

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 278

EP - 308

BT - Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings

A2 - Canteaut, Anne

A2 - Ishai, Yuval

PB - Springer

T2 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020

Y2 - 10 May 2020 through 14 May 2020

ER -

Gong J, Wee H. Adaptively secure ABE for DFA from k-lin and more. In Canteaut A, Ishai Y, editors, Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Springer. 2020. p. 278-308. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-45727-3_10

Adaptively secure ABE for DFA from k-lin and more

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this