Verifiable capacity-bound functions: a new primitive from Kolmogorov complexity. (Revisiting space-based security in the adaptive setting)

DOI10.1007/978-3-031-31371-4_3OpenAlexW3149545503MaRDI QIDQ6067351

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

Publication date: 16 November 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-31371-4_3

zbMATH Keywords

Kolmogorov complexitypolynomial evaluationadaptive securityverifiable computationverifiable delay function

Mathematics Subject Classification ID

Cryptography (94A60) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of small universal Turing machines: A survey
• Sustained space complexity
• Simple proofs of sequential work
• Verifiable delay functions
• Bandwidth hard functions for ASIC resistance
• Symmetrically and asymmetrically hard cryptography
• SPARKs: succinct parallelizable arguments of knowledge
• Simple proofs of space-time and rational proofs of storage
• Tight time-memory trade-offs for symmetric encryption
• Incremental proofs of sequential work
• Tight proofs of space and replication
• Memory-hard functions from cryptographic primitives
• Kolmogorov complexity and cryptography
• Secure communications over insecure channels
• Efficiently Computing Data-Independent Memory-Hard Functions
• Big-Key Symmetric Encryption: Resisting Key Exfiltration
• Proofs of Space: When Space Is of the Essence
• Cryptographic Schemes Based on the ASASA Structure: Black-Box, White-Box, and Public-Key (Extended Abstract)
• High Parallel Complexity Graphs and Memory-Hard Functions
• Towards Practical Whitebox Cryptography: Optimizing Efficiency and Space Hardness
• Efficient and Provable White-Box Primitives
• Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks
• Publicly verifiable proofs of sequential work
• Stronger Difficulty Notions for Client Puzzles and Denial-of-Service-Resistant Protocols
• Proof of Space from Stacked Expanders
• Proofs of Space
• Security Notions and Generic Constructions for Client Puzzles
• Signatures of Correct Computation
• Simple verifiable delay functions
• Scrypt Is Maximally Memory-Hard
• Advances in Cryptology - CRYPTO 2003
• Pebbling and Proofs of Work
• Theory of Cryptography
• An introduction to Kolmogorov complexity and its applications
• Four Small Universal Turing Machines
• Efficient verifiable delay functions