Verifiable Capacity-Bound Functions: A New Primitive from Kolmogorov Complexity (Revisiting Space-Based Security in the Adaptive Setting)

Giuseppe Ateniese; Long Chen; Danilo Francati; Dimitrios Papadopoulos; Qiang Tang

doi:10.1007/978-3-031-31371-4_3

Verifiable Capacity-Bound Functions: A New Primitive from Kolmogorov Complexity (Revisiting Space-Based Security in the Adaptive Setting)

Giuseppe Ateniese, Long Chen, Danilo Francati, Dimitrios Papadopoulos, Qiang Tang

Department of Information Security

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

Original language	English
Title of host publication	Public-Key Cryptography – PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
Editors	Alexandra Boldyreva, Vladimir Kolesnikov
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	63-93
Number of pages	31
ISBN (Print)	9783031313707
DOIs	https://doi.org/10.1007/978-3-031-31371-4_3
Publication status	Published - 2 May 2023
Event	26th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2023 - Atlanta, United States Duration: 7 May 2023 → 10 May 2023

Publication series

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

Conference

Conference	26th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2023
Country/Territory	United States
City	Atlanta
Period	7/05/23 → 10/05/23

Keywords

Adaptive security
Kolmogorov complexity
Polynomial evaluation
Verifiable computation
Verifiable delay function

Access to Document

10.1007/978-3-031-31371-4_3

Cite this

Ateniese, G., Chen, L., Francati, D., Papadopoulos, D., & Tang, Q. (2023). Verifiable Capacity-Bound Functions: A New Primitive from Kolmogorov Complexity (Revisiting Space-Based Security in the Adaptive Setting). In A. Boldyreva, & V. Kolesnikov (Eds.), Public-Key Cryptography – PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings (pp. 63-93). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13941 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-31371-4_3

Ateniese, Giuseppe ; Chen, Long ; Francati, Danilo et al. / Verifiable Capacity-Bound Functions : A New Primitive from Kolmogorov Complexity (Revisiting Space-Based Security in the Adaptive Setting). Public-Key Cryptography – PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. editor / Alexandra Boldyreva ; Vladimir Kolesnikov. Springer Science and Business Media Deutschland GmbH, 2023. pp. 63-93 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d52a3af2b78343d9bc3b40e219730aae,

title = "Verifiable Capacity-Bound Functions: A New Primitive from Kolmogorov Complexity (Revisiting Space-Based Security in the Adaptive Setting)",

keywords = "Adaptive security, Kolmogorov complexity, Polynomial evaluation, Verifiable computation, Verifiable delay function",

author = "Giuseppe Ateniese and Long Chen and Danilo Francati and Dimitrios Papadopoulos and Qiang Tang",

note = "Publisher Copyright: {\textcopyright} 2023, International Association for Cryptologic Research.; 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2023 ; Conference date: 07-05-2023 Through 10-05-2023",

year = "2023",

month = may,

day = "2",

doi = "10.1007/978-3-031-31371-4\_3",

language = "English",

isbn = "9783031313707",

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

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "63--93",

editor = "Alexandra Boldyreva and Vladimir Kolesnikov",

booktitle = "Public-Key Cryptography – PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings",

address = "Germany",

}

Ateniese, G, Chen, L, Francati, D, Papadopoulos, D & Tang, Q 2023, Verifiable Capacity-Bound Functions: A New Primitive from Kolmogorov Complexity (Revisiting Space-Based Security in the Adaptive Setting). in A Boldyreva & V Kolesnikov (eds), Public-Key Cryptography – PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13941 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 63-93, 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2023, Atlanta, United States, 7/05/23. https://doi.org/10.1007/978-3-031-31371-4_3

Verifiable Capacity-Bound Functions: A New Primitive from Kolmogorov Complexity (Revisiting Space-Based Security in the Adaptive Setting). / Ateniese, Giuseppe; Chen, Long; Francati, Danilo et al.
Public-Key Cryptography – PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. ed. / Alexandra Boldyreva; Vladimir Kolesnikov. Springer Science and Business Media Deutschland GmbH, 2023. p. 63-93 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13941 LNCS).

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

TY - GEN

T1 - Verifiable Capacity-Bound Functions

T2 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2023

AU - Ateniese, Giuseppe

AU - Chen, Long

AU - Francati, Danilo

AU - Papadopoulos, Dimitrios

AU - Tang, Qiang

PY - 2023/5/2

Y1 - 2023/5/2

KW - Adaptive security

KW - Kolmogorov complexity

KW - Polynomial evaluation

KW - Verifiable computation

KW - Verifiable delay function

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

U2 - 10.1007/978-3-031-31371-4_3

DO - 10.1007/978-3-031-31371-4_3

M3 - Conference contribution

AN - SCOPUS:85161623395

SN - 9783031313707

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

SP - 63

EP - 93

BT - Public-Key Cryptography – PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings

A2 - Boldyreva, Alexandra

A2 - Kolesnikov, Vladimir

PB - Springer Science and Business Media Deutschland GmbH

Y2 - 7 May 2023 through 10 May 2023

ER -

Ateniese G, Chen L, Francati D, Papadopoulos D, Tang Q. Verifiable Capacity-Bound Functions: A New Primitive from Kolmogorov Complexity (Revisiting Space-Based Security in the Adaptive Setting). In Boldyreva A, Kolesnikov V, editors, Public-Key Cryptography – PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 63-93. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-31371-4_3

Verifiable Capacity-Bound Functions: A New Primitive from Kolmogorov Complexity (Revisiting Space-Based Security in the Adaptive Setting)

Publication series

Conference

Keywords

Access to Document

Other files and links

Kolmogorov Complexity and Cryptography: New Connections and Applications to Space-Demanding Functions