# Information Security and Cryptography Research Group

## Abstract Storage Devices

### Robert Koenig, Ueli Maurer, and Stefano Tessaro

Theory and Practice of Computer Science — SOFSEM 2009, Lecture Notes in Computer Science, Springer-Verlag, vol. 5404, pp. 341–352, Jan 2009.

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.

## BibTeX Citation

@inproceedings{KoMaTe09,
author       = {Robert Koenig and Ueli Maurer and Stefano Tessaro},
title        = {Abstract Storage Devices},
booktitle    = {Theory and Practice of Computer Science --- SOFSEM 2009},
pages        = 341--352,
series       = {Lecture Notes in Computer Science},
volume       = 5404,
year         = 2009,
month        = 1,
publisher    = {Springer-Verlag},
}