Authenticated Hash Tables Based on Cryptographic Accumulators

详细信息    查看全文

• 作者：Charalampos Papamanthou ; Roberto Tamassia ; Nikos Triandopoulos
• 关键词：Authenticated data structures ; Cryptographic accumulators ; Cloud computing security
• 刊名：Algorithmica
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：74
• 期：2
• 页码：664-712
• 全文大小：798 KB
• 参考文献：1.Ateniese, G., Burns, R.C., Curtmola, R., Herring, J., Khan, O., Kissner, L., Peterson, Z.N.J., Song, D.: Remote data checking using provable data possession. ACM Trans. Inf. Syst. Secur. 14(1), 12 (2011)CrossRef
  2.Baric, N., Pfitzmann, B.: Collision-free accumulators and fail-stop signature schemes without trees. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), vol. 1233 of LNCS, pp. 480–494 (1997)
  3.Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of Conference on Computer and Communications Security (CCS), ACM, pp. 62–73 (1993)
  4.Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: SNARKs for C: verifying program executions succinctly and in zero knowledge. In: Proceedings of International Cryptology Conference (CRYPTO), vol. 8043 of LNCS, pp. 90–108 (2013)
  5.Benaloh, J., de Mare, M.: One-way accumulators: a decentralized alternative to digital signatures. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), vol. 765 of LNCS, pp. 274–285 (1993)
  6.Blum, M., Evans, W.S., Gemmell, P., Kannan, S., Naor, M.: Checking the correctness of memories. Algorithmica 12(2/3), 225–244 (1994)CrossRef MathSciNet
  7.Boneh, D., Boyen, X.: Short signatures without random oracles and the SDH assumption in bilinear groups. J. Cryptol. 21(2), 149–177 (2008)CrossRef MathSciNet MATH
  8.Braun, B., Feldman, A.J., Ren, Z., Setty, S.T.V., Blumberg, A.J., Walfish, M.: Verifying computations with state. In: Proceedings of Symposium on Operating Systems Principles (SOSP), ACM, pp. 341–357 (2013)
  9.Buldas, A., Laud, P., Lipmaa, H.: Accountable certificate management using undeniable attestations. In: Proceedings of Conference on Computer and Communications Security (CCS), ACM, pp. 9–18 (2000)
  10.Camenisch, J., Kohlweiss, M., Soriente, C.: An accumulator based on bilinear maps and efficient revocation for anonymous credentials. In: Proceedings of Public Key Cryptography (PKC), vol. 5443 of LNCS, pp. 481–500 (2009)
  11.Camenisch, J., Kohlweiss, M., Soriente, C.: An accumulator based on bilinear maps and efficient revocation for anonymous credentials. In: Proceedings of Public Key Cryptography (PKC), vol. 5443 of LNCS, pp. 481–500 (2009)
  12.Camenisch, J., Lysyanskaya, A.: A signature scheme with efficient protocols. In: Proceedings of Security in Communication Networks (SCN), vol. 2576 of LNCS, pp. 268–289 (2002)
  13.Canetti, R., Paneth, O., Papadopoulos, D., Triandopoulos, N.: Verifiable set operations over outsourced databases. In: Proceedings of Public Key Cryptography (PKC), vol. 8383 of LNCS, pp. 113–130 (2014)
  14.Carter, I.L., Wegman, M.N.: Universal classes of hash functions. In: Proceedings of Symposium on Theory of Computing (STOC), ACM, pp. 106–112 (1977)
  15.Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)MATH
  16.Damgård, I., Triandopoulos, N.: Supporting non-membership proofs with bilinear-map accumulators. http://​eprint.​iacr.​org/​ , Cryptology ePrint Archive, Report 2008/538 (2008)
  17.Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., Tarjan, R.E.: Dynamic perfect hashing: upper and lower bounds. SIAM J. Comput. 23, 738–761 (1994)CrossRef MathSciNet MATH
  18.Dwork, C., Naor, M., Rothblum, G.N., Vaikuntanathan, V.: How efficient can memory checking be? In: Proceedings of Theoretical Cryptography Conference (TCC), vol. 5444 of LNCS, pp. 503–520 (2009)
  19.Erway, C., Küpçü, A., Papamanthou, C., Tamassia, R.: Dynamic provable data possession. In: Proceedings of Conference on Computer and Communications Security (CCS), ACM, pp. 213–222 (2009)
  20.Gennaro, R., Halevi, S., Rabin, T.: Secure hash-and-sign signatures without the random oracle. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), vol. 1592 of LNCS, pp. 123–139 (1999)
  21.Goodrich, M.T., Papamanthou, C., Tamassia, R.: On the cost of persistence and authentication in skip lists. In: Proceedings of Workshop on Experimental Algorithms (WEA), vol. 4525 of LNCS, pp. 94–107 (2007)
  22.Goodrich, M.T., Tamassia, R., Hasic, J.: An efficient dynamic and distributed cryptographic accumulator. In: Proceedings of Information Security Conference (ISC), vol. 2433 of LNCS, pp. 372–388 (2002)
  23.Goodrich, M.T., Tamassia, R., Schwerin, A.: Implementation of an authenticated dictionary with skip lists and commutative hashing. In: Proceedings of DARPA Information Survivability Conference and Exposition II (DISCEX II), pp. 68–82 (2001)
  24.Goodrich, M.T., Tamassia, R., Triandopoulos, N.: Super-efficient verification of dynamic outsourced databases. In: Proceedings of RSA Conference, Cryptographers’ Track (CT-RSA), vol. 4964 of LNCS, pp. 407–424 (2008)
  25.Goodrich, M.T., Tamassia, R., Triandopoulos, N.: Efficient authenticated data structures for graph connectivity and geometric search problems. Algorithmica 60(3), 505–552 (2011)CrossRef MathSciNet MATH
  26.Hutflesz, A., Six, H.-W., Widmayer, P.: Globally order preserving multidimensional linear hashing. In: Proceedings of International Conference on Data Engineering (ICDE), IEEE, pp. 572–579 (1988)
  27.Kenyon, C.M., Vitter, J.S.: Maximum queue size and hashing with lazy deletion. Algorithmica 6, 597–619 (1991)CrossRef MathSciNet MATH
  28.Kosba, A.E., Papadopoulos, D., Papamanthou, C., Sayed, M.F., Shi, E., Triandopoulos, N.: TrueSet : nearly practical verifiable set computations. In: Usenix Security Symposium (USENIX SECURITY) (2014)
  29.Li, J., Li, N., Xue, R.: Universal accumulators with efficient nonmembership proofs. In: Proceedings of Applied Cryptography and Network Security (ACNS), vol. 4521 of LNCS, pp. 253–269 (2007)
  30.Linial, N., Sasson, O.: Non-expansive hashing. In: Proceedings of Symposium on Theory of Computing (STOC), ACM, pp. 509–517 (1996)
  31.Lynn, B.: On the implementation of pairing-based cryptosystems. Ph.D. thesis, Stanford University, Stanford, California (2008)
  32.Martel, C., Nuckolls, G., Devanbu, P., Gertz, M., Kwong, A., Stubblebine, S.G.: A general model for authenticated data structures. Algorithmica 39(1), 21–41 (2004)CrossRef MathSciNet MATH
  33.Merkle, R.C.: A certified digital signature. In: Proceedings of International Cryptology Conference (CRYPTO), vol. 435 of LNCS, pp. 218–238 (1989)
  34.Mullin, J.K.: Spiral storage: efficient dynamic hashing with constant-performance. Comput. J. 28, 330–334 (1985)CrossRef MathSciNet
  35.NTL: A library for doing number theory. http://​www.​shoup.​net/​ntl/​
  36.Naor, M., Nissim, K.: Certificate revocation and certificate update. In: Usenix Security Symposium (USENIX SECURITY), pp. 217–228 (1998)
  37.Nguyen, L.: Accumulators from bilinear pairings and applications. In: Proceedings of RSA Conference, Cryptographers’ Track (CT-RSA), vol. 3376 of LNCS, pp. 275–292 (2005)
  38.Nuckolls, G.: Verified query results from hybrid authentication trees. In: Proceedings of Working Conference on Data and Applications Security (DBSEC), vol. 3654 of LNCS, pp. 84–98 (2005)
  39.Overmars, M.H.: The Design of Dynamic Data Structures, vol. 156 of LNCS, Springer, London (1983)
  40.Papamanthou, C.: Cryptography for efficiency: new directions in authenticated data structures. Ph.D. thesis, Brown University, Providence, Rhode Island (2011)
  41.PBC: The pairing-based cryptography library. http://​crypto.​stanford.​edu/​pbc/​
  42.Papamanthou, C., Shi, E., Tamassia, R., Yi, K.: Streaming authenticated data structures. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), vol. 7881 of LNCS, pp. 353–370 (2013)
  43.Papamanthou, C., Tamassia, R.: Time and space efficient algorithms for two-party authenticated data structures. In: Proceedings of International Conference on Information and Communications Security (ICICS), vol. 4861 of LNCS, pp. 1–15 (2007)
  44.Papamanthou, C., Tamassia, R., Triandopoulos, N.: Authenticated hash tables. In: Proceedings of Conference on Computer and Communications Security (CCS), ACM, pp. 437–448 (2008)
  45.Papamanthou, C., Tamassia, R., Triandopoulos, N.: Optimal verification of operations on dynamic sets. In: Proceedings of International Cryptology Conference (CRYPTO), vol. 6841 of LNCS, pp. 91–110 (2011)
  46.Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: Nearly practical verifiable computation. In: Proceedings of Symposium on Security and Privacy (SSP), IEEE, pp. 238–252 (2013)
  47.Preparata, F.P., Sarwate, D.V.: Computational complexity of Fourier transforms over finite fields. Math. Comput. 31(139), 740–751 (1977)CrossRef MathSciNet MATH
  48.Sander, T.: Efficient accumulators without trapdoor (extended abstract). In: Proceedings of International Conference on Information and Communications Security (ICICS), vol. 1726 of LNCS, pp. 252–262 (1999)
  49.Sander, T., Ta-Shma, A., Yung, M.: Blind, auditable membership proofs. In: Proceedings of Financial Cryptography (FC), vol. 1962 of LNCS, pp. 53–71 (2001)
  50.Shoup, V.: A Computational Introduction to Number Theory and Algebra. Cambridge University Press, New York (2005)CrossRef MATH
  51.Tamassia, R.: Authenticated data structures. In: Proceedings of European Symposium on Algorithms (ESA), vol. 2832 of LNCS, pp. 2–5 (2003)
  52.Tamassia, R., Triandopoulos, N.: Computational bounds on hierarchical data processing with applications to information security. In: Proceedings of International Colloquium on Automata, Languages and Programming (ICALP), vol. 3580 of LNCS, pp. 153–165 (2005)
  53.Tamassia, R., Triandopoulos, N.: Efficient content authentication in peer-to-peer networks. In: Proceedings of Applied Cryptography and Network Security (ACNS), vol. 4521 of LNCS, pp. 354–372 (2007)
  54.Tamassia, R., Triandopoulos, N.: Certification and authentication of data structures. In: Proceedings of Alberto Mendelzon Workshop on Foundations of Data Management (2010)
  55.Wang, P., Wang, H., Pieprzyk, J.: A new dynamic accumulator for batch updates. In: Proceedings of International Conference on Information and Communications Security (ICICS), vol. 4861 of LNCS, pp. 98–112 (2007)
  
• 作者单位：Charalampos Papamanthou (1)
  Roberto Tamassia (2)
  Nikos Triandopoulos (3)
  
  1. Department of Electrical and Computer Engineering and Institute of Advanced Computer Studies (UMIACS), University of Maryland, College Park, MD, USA
  2. Department of Computer Science, Brown University, Providence, RI, USA
  3. RSA Laboratories and Department of Computer Science, Boston University, Boston, MA, USA
  
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity
  Theory of Computation
  Mathematics of Computing
  Algorithms
  Computer Systems Organization and Communication Networks
  Data Structures, Cryptology and Information Theory
  
• 出版者：Springer New York
• ISSN：1432-0541

文摘

Suppose a client stores \(n\) elements in a hash table that is outsourced to an untrusted server. We address the problem of authenticating the hash table operations, where the goal is to design protocols capable of verifying the correctness of queries and updates performed by the server, thus ensuring the integrity of the remotely stored data across its entire update history. Solutions to this authentication problem allow the client to gain trust in the operations performed by a faulty or even malicious server that lies outside the administrative control of the client. We present two novel schemes that implement an authenticated hash table. An authenticated hash table exports the basic hash-table functionality for maintaining a dynamic set of elements, coupled with the ability to provide short cryptographic proofs that a given element is a member or not of the current set. By employing efficient algorithmic constructs and cryptographic accumulators as the core security primitive, our schemes provide constant proof size, constant verification time and sublinear query or update time, strictly improving upon previous approaches. Specifically, in our first scheme which is based on the RSA accumulator, the server is able to construct a (non-)membership proof in constant time and perform updates in \(O\left( n^{\epsilon }\log n\right) \) time for any fixed constant \(0<\epsilon <1\). A variation of this scheme achieves a different trade-off, offering constant update time and \(O(n^{\epsilon })\) query time. Our second scheme uses an accumulator based on bilinear pairings to achieve \(O(n^{\epsilon })\) update time at the server while keeping all other complexities constant. A variation of this scheme achieves \(O(n^{\epsilon }\log n)\) time for queries and constant update time. An experimental evaluation of both solutions shows their practicality. Keywords Authenticated data structures Cryptographic accumulators Cloud computing security