Abstract Storage Devices | SpringerLink
Skip to main content
Springer Nature Link
Log in

Abstract Storage Devices

  • Conference paper
SOFSEM 2009: Theory and Practice of Computer Science (SOFSEM 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5404))

  • 679 Accesses

Abstract

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 combinatorial problems related to ASD’s, including reducibility among ASD’s, which is proved to be \(\mathcal{NP}\)-complete, and the factorization of ASD’s. In particular, we prove that the factorization into binary-output ASD’s (if it exists) is unique.

This research was partially supported by the Swiss National Science Foundation (SNF), project no. 200020-113700/1.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Boppana, R.B., Håstad, J., Zachos, S.: Does co-NP have short interactive proofs? Inf. Process. Lett. 25(2), 127–132 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  2. Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. In: STOC 1986, pp. 59–68 (1986)

    Google Scholar 

  3. Grätzer, G.: General Lattice Theory. Birkhäuser, Basel (1998)

    MATH  Google Scholar 

  4. Imrich, W., Klavžar, S.: Product Graphs: Structure and Recognition. Wiley, Chichester (2000)

    MATH  Google Scholar 

  5. Jónsson, B.: The unique factorization problem for finite relational structures. Colloq. Math. 14, 1–32 (1966)

    MathSciNet  MATH  Google Scholar 

  6. König, R., Maurer, U., Renner, R.: On the power of quantum memory. IEEE Transactions on Information Theory 51(7), 2391–2401 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  7. König, R., Maurer, U., Tessaro, S.: Abstract storage devices (June 2007), http://www.arxiv.org/abs/0706.2746

  8. Köpf, B., Basin, D.: An information-theoretic model for adaptive side-channel attacks. In: ACM CCS 2007, pp. 286–296 (2007)

    Google Scholar 

  9. Rabin, M.O.: How to exchange secrets with oblivious transfer. Technical Memo TR-81, Aiken Computation Laboratory, Harvard University (1981)

    Google Scholar 

  10. Shannon, C.E.: The zero-error capacity of a noisy channel. IEEE Transactions on Information Theory 2, 8–19 (1956)

    Article  MathSciNet  Google Scholar 

  11. Tessaro, S.: An abstract model for storage devices, Master Thesis, ETH Zurich (September 2005)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. California Institute of Technology, Pasadena, CA 91125, USA

    Robert König

  2. Department of Computer Science, ETH Zurich, 8092, Zurich, Switzerland

    Ueli Maurer & Stefano Tessaro

Authors
  1. Robert König
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ueli Maurer
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Stefano Tessaro
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Aarhus Graduate School of Science, University of Aarhus, Ny Munkegade Bldg 1521-110, DK-8000, Aarhus C, Denmark

    Mogens Nielsen

  2. Faculty of Informatics, Masaryk University, Botanická 68a, 60200, Brno, Czech Republic

    Antonín Kučera

  3. Department of Computer Science, University of Aarhus, IT-parken, Aabogade 34, DK-8200, Aarhus N., Denmark

    Peter Bro Miltersen

  4. Ecole Polytechnique, Rue de Saclay, 91128, Palaiseau Cedex, France

    Catuscia Palamidessi  & Frank Valencia  & 

  5. Faculty of Mathematics and Physics, Charles University, Malostranské námestí 25, 118 00, Prague 1, Malá Strana, Czech Republic

    Petr Tůma

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

König, R., Maurer, U., Tessaro, S. (2009). Abstract Storage Devices. In: Nielsen, M., Kučera, A., Miltersen, P.B., Palamidessi, C., Tůma, P., Valencia, F. (eds) SOFSEM 2009: Theory and Practice of Computer Science. SOFSEM 2009. Lecture Notes in Computer Science, vol 5404. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-95891-8_32

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-95891-8_32

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-95890-1

  • Online ISBN: 978-3-540-95891-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics