More Web Proxy on the site http://driver.im/

Article

Super-efficient aggregating history-independent persistent authenticated dictionaries

Authors:

Scott A. Crosby,

Dan S. WallachAuthors Info & Claims

ESORICS'09: Proceedings of the 14th European conference on Research in computer security

Pages 671 - 688

Published: 21 September 2009 Publication History

Abstract

Authenticated dictionaries allow users to send lookup requests to an untrusted server and get authenticated answers. Persistent authenticated dictionaries (PADs) add queries against historical versions. We consider a variety of different trust models for PADs and we present several extensions, including support for aggregation and a rich query language, as well as hiding information about the order in which PADs were constructed. We consider variations on treelike data structures as well as a design that improves efficiency by speculative future predictions. We improve on prior constructions and feature two designs that can authenticate historical queries with constant storage per update and several designs that can return constant-sized authentication results.

References

[1]

Anagnostopoulos, A., Goodrich, M.T., Tamassia, R.: Persistent authenticated dictionaries and their applications. In: International Conference on Information Security (ISC), Seoul, Korea, December 2001, pp. 379-393 (2001).

Digital Library

[2]

Anderson, A., Ottmann, T.: Faster uniquely represented dictionaries. In: Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (SFCS), San Juan, Puerto Rico, October 1991, pp. 642-649 (1991).

Digital Library

[3]

Aragon, C.R., Seidel, R.G.: Randomized search trees. In: Proceedings of the 30th Annual Symposiumon Foundations of Computer Science (SFCS), October 1989, pp. 540-545 (1989).

Digital Library

[4]

Bagwell, P.: Fast functional lists, hash-lists, deques and variable length arrays. In: Implementation of Functional Languages, 14th InternationalWorkshop, Madrid, Spain, September 2002, p. 34 (2002).

Digital Library

[5]

Benaloh, J.C., deMare, M.: One-way accumulators: A decentralized alternative to digital signatures. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 274-285. Springer, Heidelberg (1994).

Digital Library

[6]

Blelloch, G.E., Reid-Miller, M.: Fast set operations using treaps. In: Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), Puerto Vallarta, Mexico, June 1998, pp. 16-26 (1998).

Digital Library

[7]

Blum, M., Evans, W., Gemmell, P., Kannan, S., Naor, M.: Checking the correctness of memories. In: Proceedings of the 32nd annual symposium on Foundations of computer science (SFCS), San Juan, Puerto Rico, October 1991, pp. 90-99 (1991).

Digital Library

[8]

Brodal, G.S.: Partially persistent data structures of bounded degree with constant update time. Nordic Journal of Computing 3(3), 238-255 (1996).

Digital Library

[9]

Buldas, A., Lipmaa, H., Schoenmakers, B.: Optimally efficient accountable time-stamping. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 293-305. Springer, Heidelberg (2000).

Digital Library

[10]

Camenisch, J., Lysyanskaya, A.: Dynamic accumulators and application to efficient revocation of anonymous credentials. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 61-76. Springer, Heidelberg (2002).

Digital Library

[11]

Crosby, S.A., Wallach, D.S.: Efficient data structures for tamper-evident logging. In: Proceedings of the 18th USENIX Security Symposium, Montreal, Canada (August 2009), http://www.cs.rice.edu/~scrosby/pubs/preprints/paper-treehist.pdf

Digital Library

[12]

Davis, D., Monrose, F., Reiter, M.K.: Time-scoped searching of encrypted audit logs. In: Information and Communications Security Conference, Malaga, Spain, October 2004, pp. 532-545 (2004).

[13]

Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. In: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (STOC), Berkeley, CA, May 1986, pp. 109-121 (1986).

Digital Library

[14]

Dwork, C., Naor, M., Rothblum, G.N., Vaikuntanathan, V.: How efficient can memory checking be?. In: Proceedings of the Theory of Cryptography Conference (TCC), San Francisco, CA, March 2009, pp. 503-520 (2009).

Digital Library

[15]

Fiat, A., Kaplan, H.: Making data structures confluently persistent. Journal of Algorithms 48(1), 16-58 (2003).

Digital Library

[16]

Fu, K., Kaashoek, M.F., Mazières, D.: Fast and secure distributed read-only file system. ACM Transactions on Compututer Systems 20(1), 1-24 (2002).

Digital Library

[17]

Gassend, B., Suh, G., Clarke, D., Dijk, M., Devadas, S.: Caches and hash trees for efficient memory integrity verification. In: The 9th International Symposium on High Performance Computer Architecture (HPCA), Anaheim, CA (February 2003).

Digital Library

[18]

Goodrich, M.T., Tamassia, R., Hasic, J.: An efficient dynamic and distributed cryptographic accumulator. In: Proceedings of the 5th International Conference on Information Security (ISC), Sao Paulo, Brazil, September 2002, pp. 372-388 (2002).

Digital Library

[19]

Goodrich, M.T., Tamassia, R., Triandopoulos, N., Cohen, R.F.: Authenticated data structures for graph and geometric searching. In: Topics in Cryptology, The Cryptographers' Track at the RSA Conference (CT-RSA), San Francisco, CA, April 2003, pp. 295-313 (2003).

Digital Library

[20]

Guibas, L.J., Sedgewick, R.: A dichromatic framework for balanced trees. In: Proceedings of the 19th Annual Symposium on Foundations of Computer Science (SFCS), October 1978, pp. 8-21 (1978).

Digital Library

[21]

Haber, S., Stornetta, W.S.: How to time-stamp a digital document. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 437-455. Springer, Heidelberg (1998).

Digital Library

[22]

Kaplan, H.: Persistent data structures. In: Mehta, D., Sahni, S. (eds.) Handbook on Data Structures and Applications. CRC Press, Boca Raton (2001).

[23]

Kocher, P.C.: On certificate revocation and validation. In: Hirschfeld, R. (ed.) FC 1998. LNCS, vol. 1465, pp. 172-177. Springer, Heidelberg (1998).

Digital Library

[24]

Li, J., Krohn, M., Mazières, D., Shasha, D.: Secure untrusted data repository (SUNDR). In: Operating Systems Design & Implementation (OSDI), San Francisco, CA (December 2004).

Digital Library

[25]

Li, J., Li, N., Xue, R.: Universal accumulators with efficient nonmembership proofs. In: Proceedings of the 5th International Conference on Applied Cryptography and Network Security (ACNS), Zhuhai, China, June 2007, pp. 253-269 (2007).

Digital Library

[26]

Merkle, R.C.: A digital signature based on a conventional encryption function. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 369-378. Springer, Heidelberg (1990).

Digital Library

[27]

Micali, S.: Efficient certificate revocation. Tech. Rep. TM-542b, Massachusetts Institute of Technology, Cambridge, MA (1996), http://www.ncstrl.org:8900/ncstrl/servlet/search?formname=detail&id=oai

Digital Library

[28]

Micciancio, D.: Oblivious data structures: Applications to cryptography. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), El Paso, Texas, May 1997, pp. 456-464 (1997).

Digital Library

[29]

Muthitacharoen, A., Morris, R., Gil, T., Chen, B.: Ivy: A read/write peer-to-peer file system. In: USENIX Symposium on Operating Systems Design and Implementation (OSDI 2002), Boston, MA (December 2002).

Digital Library

[30]

Naccache, D., M'Raïhi, D., Vaudenay, S., Raphaeli, D.: Can DSA be improved? In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 77-85. Springer, Heidelberg (1995).

[31]

Naor, M., Nissim, K.: Certificate revocation and certificate update. In: USENIX Security Symposium, San Antonio, TX (January 1998).

Digital Library

[32]

Naor, M., Teague, V.: Anti-presistence: history independent data structures. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (STOC), Heraklion, Crete, Greece, July 2001, pp. 492-501 (2001).

Digital Library

[33]

Okasaki, C.: Purely Functional Data Structures. Cambridge University Press, Cambridge (1999)

Digital Library

[34]

Papamanthou, C., Tamassia, R., Triandopoulos, N.: Authenticated hash tables. In: ACM Conference on Computer and Communications Security (CCS 2008), Alexandria, VA, October 2008, pp. 437-448 (2008).

Digital Library

[35]

Peterson, Z.N.J., Burns, R., Ateniese, G., Bono, S.: Design and implementation of verifiable audit trails for a versioning file system. In: USENIX Conference on File and Storage Technologies, San Jose, CA (February 2007).

Digital Library

[36]

Sarnak, N., Tarjan, R.E.: Planar point location using persistent search trees. Communications of the ACM 29(7), 669-679 (1986).

Digital Library

[37]

Schneier, B., Kelsey, J.: Secure audit logs to support computer forensics. ACM Transactions on Information and System Security 1(3) (1999).

Digital Library

[38]

Shapiro, J.S., Vanderburgh, J.: Access and integrity control in a public-access, high-assurance configuration management system. In: USENIX Security Symposium, San Francisco, CA, August 2002, pp. 109-120 (2002).

Digital Library

[39]

Wang, P., Wang, H., Pieprzyk, J.: A new dynamic accumulator for batch updates. In: Qing, S., Imai, H., Wang, G. (eds.) ICICS 2007. LNCS, vol. 4861, pp. 98-112. Springer, Heidelberg (2007).

Digital Library

[40]

Wang, P., Wang, H., Pieprzyk, J.: Improvement of a dynamic accumulator at ICICS 2007 and its application in multi-user keyword-based retrieval on encrypted data. In: Qing, S., Imai, H., Wang, G. (eds.) ICICS 2007. LNCS, vol. 4861, pp. 1381-1386. Springer, Heidelberg (2007).

Digital Library

[41]

Williams, P., Sion, R., Shasha, D.: The blind stone tablet: Outsourcing durability. In: Sixteenth Annual Network and Distributed Systems Security Symposium (NDSS), San Diego, CA (February 2009).

Cited By

Gao BChen BJia SXia LGalbraith SRussello GSusilo WGollmann DKirda ELiang Z(2019)eHIFSProceedings of the 2019 ACM Asia Conference on Computer and Communications Security10.1145/3321705.3329839(573-585)Online publication date: 2-Jul-2019
https://dl.acm.org/doi/10.1145/3321705.3329839
Tang YWang TLiu LHu XJang JPayne CHahn AButler KSherr M(2014)Lightweight authentication of freshness in outsourced key-value storesProceedings of the 30th Annual Computer Security Applications Conference10.1145/2664243.2664244(176-185)Online publication date: 8-Dec-2014
https://dl.acm.org/doi/10.1145/2664243.2664244
Bajaj SSion RSadeghi AGligor VYung M(2013)HIFSProceedings of the 2013 ACM SIGSAC conference on Computer & communications security10.1145/2508859.2516724(1285-1296)Online publication date: 4-Nov-2013
https://dl.acm.org/doi/10.1145/2508859.2516724
Show More Cited By

Super-efficient aggregating history-independent persistent authenticated dictionaries
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Authenticated Dictionaries: Real-World Costs and Trade-Offs

Authenticated dictionaries are a widely discussed paradigm to enable verifiable integrity for data storage on untrusted servers, such as today’s widely used “cloud computing” resources, allowing a server to provide a “proof,” typically in the form of a ...
Convertible multi-authenticated encryption scheme

A convertible authenticated encryption (CAE) scheme allows the signer to generate a valid authenticated ciphertext on his chosen message such that only the designated recipient can retrieve the message. Further, the recipient has the ability to convert ...
Practical convertible authenticated encryption schemes using self-certified public keys

A convertible authenticated encryption scheme allows a designated receiver to recover and verify a message simultaneously, during which the recipient can prove the dishonesty of the sender to any third party if the sender repudiates her signature later. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ESORICS'09: Proceedings of the 14th European conference on Research in computer security

September 2009

706 pages

ISBN:3642044433

Editors:
Michael Backes
Saarland University, Computer Science Department and MPI-SWS, Saarbrücken, Germany
,
Peng Ning
North Carolina State University, Department of Computer Science, Raleigh, NC

Sponsors

DCSSI
Alcatel-Lucent
EADS
Fondation Métivier
INRIA: Institut Natl de Recherche en Info et en Automatique

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 21 September 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gao BChen BJia SXia LGalbraith SRussello GSusilo WGollmann DKirda ELiang Z(2019)eHIFSProceedings of the 2019 ACM Asia Conference on Computer and Communications Security10.1145/3321705.3329839(573-585)Online publication date: 2-Jul-2019
https://dl.acm.org/doi/10.1145/3321705.3329839
Tang YWang TLiu LHu XJang JPayne CHahn AButler KSherr M(2014)Lightweight authentication of freshness in outsourced key-value storesProceedings of the 30th Annual Computer Security Applications Conference10.1145/2664243.2664244(176-185)Online publication date: 8-Dec-2014
https://dl.acm.org/doi/10.1145/2664243.2664244
Bajaj SSion RSadeghi AGligor VYung M(2013)HIFSProceedings of the 2013 ACM SIGSAC conference on Computer & communications security10.1145/2508859.2516724(1285-1296)Online publication date: 4-Nov-2013
https://dl.acm.org/doi/10.1145/2508859.2516724
Crosby SWallach D(2011)Authenticated DictionariesACM Transactions on Information and System Security10.1145/2019599.201960214:2(1-30)Online publication date: 1-Sep-2011
https://dl.acm.org/doi/10.1145/2019599.2019602

View Options

View options

Media

Figures

Other

Tables

View Table of Contents