ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

Abstract Storage Devices

Robert Koenig and Ueli Maurer and Stefano Tessaro

The purpose of this paper is to initiate the study of a combinatorial abstraction, called abstract storage device (ASD), which models deterministic storage devices with the property that only partial information about the state can be read, but that there is a degree of freedom as to which partial information should be retrieved.

We study several combinatorial problems related to ASD's, including reducibility among ASD's, which we prove to be $\mathcal{NP}$-complete, and the factorization of ASD's. The factorization into binary-output devices is proved to be unique.