Paper 2025/358
The Complexity of Memory Checking with Covert Security
Abstract
A memory checker is an algorithmic tool used to certify the integrity of a database maintained on a remote, unreliable, computationally bounded server. Concretely, it allows a user to issue instructions to the server and after every instruction, obtain either the correct value or a failure (but not an incorrect answer) with high probability. A recent result due to Boyle, Komargodski, and Vafa (BKV, STOC '24) showed a tradeoff between the size of the local storage and the number of queries the memory checker makes to the server upon every logical instruction. Specifically, they show that every non-trivial memory checker construction with inverse-polynomial soundness and local storage at most
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in EUROCRYPT 2025
- Keywords
- covert securitymemory checkinglower bound
- Contact author(s)
-
eboyle @ alum mit edu
ilank @ cs huji ac il
nvafa @ mit edu - History
- 2025-03-04: approved
- 2025-02-25: received
- See all versions
- Short URL
- https://ia.cr/2025/358
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/358, author = {Elette Boyle and Ilan Komargodski and Neekon Vafa}, title = {The Complexity of Memory Checking with Covert Security}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/358}, year = {2025}, url = {https://eprint.iacr.org/2025/358} }