Checking the correctness of memories

DOI10.1007/BF01185212zbMath1323.68200OpenAlexW1994135885MaRDI QIDQ890427

N. E. Zubov

Publication date: 10 November 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01185212

Mathematics Subject Classification ID

Data structures (68P05) Information storage and retrieval of data (68P20) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Related Items

\textsf{Halo Infinite}: proof-carrying data from additive polynomial commitments, Checker for data structures which sort elements, Delegating RAM Computations, Performance improvement for the GGM-construction of pseudorandom functions, Gemini: elastic SNARKs for diverse environments, On the complexity of collision resistant hash functions: new and old black-box separations, Checking the correctness of memories, Scalable zero knowledge via cycles of elliptic curves, Hardness-preserving reductions via cuckoo hashing, Streaming graph computations with a helpful advisor, Proofs for inner pairing products and applications, \textsf{MacORAMa}: optimal oblivious RAM with integrity, Designing reliable algorithms in unreliable memories, Certifying algorithms, Resilient dynamic programming, Dynamic proofs of retrievability via oblivious RAM, Batch checking with applications to linear functions, Pipelined algorithms to detect cheating in long-term grid computations, Onion ORAM: A Constant Bandwidth Blowup Oblivious RAM, Super-Efficient Verification of Dynamic Outsourced Databases, Integrity and Consistency for Untrusted Services, Synthesizers and their application to the parallel construction of pseudo-random functions, Fast Interactive Coding against Adversarial Noise, Spartan: efficient and general-purpose zkSNARKs without trusted setup, Authenticated hash tables based on cryptographic accumulators

Cites Work

• Checking the correctness of memories
• Self-testing/correcting with applications to numerical problems
• On the power of multi-prover interactive protocols
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Relations Among Complexity Measures
• Finite state verifiers I
• Space-bounded probabilistic game automata
• Designing programs that check their work
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item