Publicly verifiable proofs of sequential work

DOI10.1145/2422436.2422479zbMath1362.94041OpenAlexW2039317858MaRDI QIDQ2986887

Tal Moran, Mohammad Mahmoody, Salil P. Vadhan

Publication date: 16 May 2017

Published in: Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://nrs.harvard.edu/urn-3:HUL.InstRepos:34222828

zbMATH Keywords

timestampingtime-lock puzzlesproofs of workdepth-robust graphs

Mathematics Subject Classification ID

Related Items (17)

Proof of Space from Stacked Expanders ⋮ PoSAT: proof-of-work availability and unpredictability, without the work ⋮ An incremental PoSW for general weight distributions ⋮ Verifiable capacity-bound functions: a new primitive from Kolmogorov complexity. (Revisiting space-based security in the adaptive setting) ⋮ Practical statistically-sound proofs of exponentiation in any group ⋮ SNACKs: leveraging proofs of sequential work for blockchain light clients ⋮ Short-lived zero-knowledge proofs and signatures ⋮ Time-release cryptography from minimal circuit assumptions ⋮ Lattice-based timed cryptography ⋮ Environmentally friendly composable multi-party computation in the plain model from standard (timed) assumptions ⋮ How to build time-lock encryption ⋮ Continuous verifiable delay functions ⋮ Generic-group delay functions require hidden-order groups ⋮ Simple verifiable delay functions ⋮ Efficiently Computing Data-Independent Memory-Hard Functions ⋮ Generically speeding-up repeated squaring is equivalent to factoring: sharp thresholds for all generic-ring delay functions ⋮ Depth-Robust Graphs and Their Cumulative Memory Complexity

Cites Work

• Teachability in computational learning
• Measuring teachability using variants of the teaching dimension
• Teaching a smarter learner.
• Occam's razor
• Pseudorandom generators for space-bounded computation
• On the power of inductive inference from good examples
• A model of interactive teaching
• Learning from different teachers
• On the limits of efficient teachability
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• On the complexity of teaching
• On specifying Boolean functions by labelled examples
• Recent Developments in Algorithmic Teaching
• A theory of the learnable
• Teaching Randomized Learners
• Algorithmic Learning Theory
• A theory of goal-oriented communication
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Publicly verifiable proofs of sequential work