Zero-knowledge accumulators and set algebra. (English) Zbl 1407.94110
Cheon, Jung Hee (ed.) et al., Advances in cryptology – ASIACRYPT 2016. 22nd international conference on the theory and application of cryptology and information security, Hanoi, Vietnam, December 4-8, 2016. Proceedings. Part II. Berlin: Springer. Lect. Notes Comput. Sci. 10032, 67-100 (2016).
Summary: Cryptographic accumulators allow to succinctly represent a set by an accumulation value with respect to which short (non-)membership proofs about the set can be efficiently constructed and verified. Traditionally, their security captures soundness but offers no privacy: convincing proofs reliably encode set membership, but they may well leak information about the accumulated set.{
}In this paper we put forward a strong privacy-preserving enhancement by introducing and devising zero-knowledge accumulators that additionally provide hiding guarantees: accumulation values and proofs leak nothing about a dynamic set that evolves via element insertions/deletions. We formalize the new property using the standard real-ideal paradigm, namely demanding that an adaptive adversary with access to query/update oracles, cannot tell whether he interacts with honest protocol executions or a simulator fully ignorant of the set (even of the type of updates on it). We rigorously compare the new primitive to existing ones for privacy-preserving verification of set membership (or other relations) and derive interesting implications among related security definitions, showing that zero-knowledge accumulators offer stronger privacy than recent related works by M. Naor and A. Ziv [TCC 2015, Lect. Notes Comput. Sci. 9015, 199–228 (2015; Zbl 1379.94046)] and D. Derler et al. [CT-RSA 2015, Lect. Notes Comput. Sci. 9048, 127-144 (2015; Zbl 1382.94088)]. We construct the first dynamic universal zero-knowledge accumulator that we show to be perfect zero-knowledge and secure under the \(q\)-strong bilinear Diffie-Hellman assumption.{
}Finally, we extend our new privacy notion and our new construction to provide privacy-preserving proofs also for an authenticated dynamic set collection – a primitive for efficiently verifying more elaborate set operations, beyond set-membership. We introduce a primitive that supports a zero-knowledge verifiable set algebra: succinct proofs for union, intersection and set difference queries over a dynamically evolving collection of sets can be efficiently constructed and optimally verified, while – for the first time – they leak nothing about the collection beyond the query result.
For the entire collection see [Zbl 1349.94006].
For the entire collection see [Zbl 1349.94006].
MSC:
| 94A60 | Cryptography |
Keywords:
zero-knowledge dynamic and universal accumulators; zero-knowledge updates; zero-knowledge set algebra; outsourced computation; integrity; privacy; bilinear accumulators; cloud privacyReferences:
| [1] | Ateniese, G.; Camenisch, J.; Joye, M.; Tsudik, G.; Bellare, M., A practical and provably secure coalition-resistant group signature scheme, Advances in Cryptology — CRYPTO 2000, 255-270, 2000, Heidelberg: Springer, Heidelberg · Zbl 0995.94544 · doi:10.1007/3-540-44598-6_16 |
| [2] | Au, MH; Tsang, PP; Susilo, W.; Mu, Y.; Fischlin, M., Dynamic universal accumulators for DDH groups and their application to attribute-based anonymous credential systems, Topics in Cryptology - CT-RSA 2009, 295-308, 2009, Heidelberg: Springer, Heidelberg · Zbl 1237.94048 · doi:10.1007/978-3-642-00862-7_20 |
| [3] | Barić, N.; Pfitzmann, B.; Fumy, W., Collision-free accumulators and fail-stop signature schemes without trees, Advances in Cryptology — EUROCRYPT ’97, 480-494, 1997, Heidelberg: Springer, Heidelberg · doi:10.1007/3-540-69053-0_33 |
| [4] | Benaloh, J.; de Mare, M.; Helleseth, T., One-way accumulators: a decentralized alternative to digital signatures, Advances in Cryptology — EUROCRYPT ’93, 274-285, 1994, Heidelberg: Springer, Heidelberg · Zbl 0951.94532 · doi:10.1007/3-540-48285-7_24 |
| [5] | Blanton, M., Aguiar, E.: Private and oblivious set and multiset operations. In: ASIACCS (2012) |
| [6] | Boneh, D.; Boyen, X.; Cachin, C.; Camenisch, JL, Short signatures without random oracles, Advances in Cryptology - EUROCRYPT 2004, 56-73, 2004, Heidelberg: Springer, Heidelberg · Zbl 1122.94354 · doi:10.1007/978-3-540-24676-3_4 |
| [7] | Buldas, A., Laud, P., Lipmaa, H.: Accountable certificate management using undeniable attestations. In: CCS (2000) |
| [8] | Camacho, P.; Hevia, A.; Abdalla, M.; Barreto, PSLM, On the impossibility of batch update for cryptographic accumulators, Progress in Cryptology - LATINCRYPT 2010, 178-188, 2010, Heidelberg: Springer, Heidelberg · Zbl 1286.94090 · doi:10.1007/978-3-642-14712-8_11 |
| [9] | Camacho, P., Hevia, A., Kiwi, M., Opazo, R.: Strong accumulators from collision-resistant hashing. In: Information Security (2008) |
| [10] | Camenisch, J.; Kohlweiss, M.; Soriente, C.; Jarecki, S.; Tsudik, G., An accumulator based on bilinear maps and efficient revocation for anonymous credentials, Public Key Cryptography - PKC 2009, 481-500, 2009, Heidelberg: Springer, Heidelberg · Zbl 1227.94074 · doi:10.1007/978-3-642-00468-1_27 |
| [11] | Camenisch, J.; Lysyanskaya, A.; Yung, M., Dynamic accumulators and application to efficient revocation of anonymous credentials, Advances in Cryptology — CRYPTO 2002, 61-76, 2002, Heidelberg: Springer, Heidelberg · Zbl 1026.94545 · doi:10.1007/3-540-45708-9_5 |
| [12] | Canetti, R.; Paneth, O.; Papadopoulos, D.; Triandopoulos, N.; Krawczyk, H., Verifiable set operations over outsourced databases, Public-Key Cryptography - PKC 2014, 113-130, 2014, Heidelberg: Springer, Heidelberg · Zbl 1296.94097 · doi:10.1007/978-3-642-54631-0_7 |
| [13] | Catalano, D.; Fiore, D.; Kurosawa, K.; Hanaoka, G., Vector commitments and their applications, Public-Key Cryptography - PKC 2013, 55-72, 2013, Heidelberg: Springer, Heidelberg · Zbl 1314.94059 · doi:10.1007/978-3-642-36362-7_5 |
| [14] | Catalano, D.; Fiore, D.; Messina, M.; Smart, N., Zero-knowledge sets with short proofs, Advances in Cryptology - EUROCRYPT 2008, 433-450, 2008, Heidelberg: Springer, Heidelberg · Zbl 1149.94308 · doi:10.1007/978-3-540-78967-3_25 |
| [15] | Chase, M.; Healy, A.; Lysyanskaya, A.; Malkin, T.; Reyzin, L.; Cramer, R., Mercurial commitments with applications to zero-knowledge sets, Advances in Cryptology - EUROCRYPT 2005, 422-439, 2005, Heidelberg: Springer, Heidelberg · Zbl 1137.94369 · doi:10.1007/11426639_25 |
| [16] | Chatterjee, S.; Menezes, A., On cryptographic protocols employing asymmetric pairings - the role of \(\uppsi\) revisited, Discrete Appl. Math., 159, 13, 1311-1322, 2011 · Zbl 1250.94031 · doi:10.1016/j.dam.2011.04.021 |
| [17] | Cristofaro, E.; Tsudik, G.; Sion, R., Practical private set intersection protocols with linear complexity, Financial Cryptography and Data Security, 143-159, 2010, Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-14577-3_13 |
| [18] | Dachman-Soled, D.; Malkin, T.; Raykova, M.; Yung, M.; Abdalla, M.; Pointcheval, D.; Fouque, P-A; Vergnaud, D., Efficient robust private set intersection, Applied Cryptography and Network Security, 125-142, 2009, Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-01957-9_8 |
| [19] | Damgård, I., Triandopoulos, N.: Supporting non-membership proofs with bilinear-map accumulators. Cryptology ePrint Archive, Report 2008/538 (2008) |
| [20] | de Meer, H., Liedel, M., Pöhls, H.C., Posegga, J.: Indistinguishability of one-way accumulators. In Technical Report MIP-1210, Faculty of Computer Science and Mathematics (FIM), University of Passau (2012) |
| [21] | de Meer, H., Pöhls, H.C., Posegga, J., Samelin, K.: Redactable signature schemes for trees with signer-controlled non-leaf-redactions. In: E-Business and Telecommunications (2014) |
| [22] | Santis, A.; Crescenzo, G.; Ostrovsky, R.; Persiano, G.; Sahai, A.; Kilian, J., Robust non-interactive zero knowledge, Advances in Cryptology — CRYPTO 2001, 566-598, 2001, Heidelberg: Springer, Heidelberg · Zbl 1003.94526 · doi:10.1007/3-540-44647-8_33 |
| [23] | Derler, D.; Hanser, C.; Slamanig, D.; Nyberg, K., Revisiting cryptographic accumulators, additional properties and relations to other primitives, Topics in Cryptology — CT-RSA 2015, 127-144, 2015, Heidelberg: Springer, Heidelberg · Zbl 1382.94088 |
| [24] | Dong, C., Chen, L., Wen, Z.: When private set intersection meets big data: an efficient and scalable protocol. In: ACM CCS (2013) |
| [25] | Fauzi, P.; Lipmaa, H.; Zhang, B.; Christin, N.; Safavi-Naini, R., Efficient non-interactive zero knowledge arguments for set operations, Financial Cryptography and Data Security, 216-233, 2014, Heidelberg: Springer, Heidelberg |
| [26] | Fazio, N., Nicolosi, A.: Cryptographic accumulators: Definitions, constructions and applications. In Technical report. Courant Institute of Mathematical Sciences, New York University (2002) |
| [27] | Freedman, MJ; Nissim, K.; Pinkas, B.; Cachin, C.; Camenisch, JL, Efficient private matching and set intersection, Advances in Cryptology - EUROCRYPT 2004, 1-19, 2004, Heidelberg: Springer, Heidelberg · Zbl 1122.94416 · doi:10.1007/978-3-540-24676-3_1 |
| [28] | Garay, JA; MacKenzie, P.; Yang, K.; Biham, E., Strengthening zero-knowledge protocols using signatures, Advances in Cryptology — EUROCRYPT 2003, 177-194, 2003, Heidelberg: Springer, Heidelberg · Zbl 1037.68741 · doi:10.1007/3-540-39200-9_11 |
| [29] | Ghosh, E.; Goodrich, MT; Ohrimenko, O.; Tamassia, R.; Zikas, V.; Prisco, R., Verifiable zero-knowledge order queries and updates for fully dynamic lists and trees, Security and Cryptography for Networks, 216-236, 2016, Heidelberg: Springer, Heidelberg · Zbl 1416.94051 · doi:10.1007/978-3-319-44618-9_12 |
| [30] | Ghosh, E., Ohrimenko, O., Papadopoulos, D., Tamassia, R., Triandopoulos, N.: Zero-knowledge accumulators and set operations. ePrint, 2015/404 (2015) |
| [31] | Ghosh, Esha; Ohrimenko, Olga; Tamassia, Roberto, Efficient Verifiable Range and Closest Point Queries in Zero-Knowledge, Proceedings on Privacy Enhancing Technologies, 2016, 4, 373-388, 2016 |
| [32] | Ghosh, E.; Ohrimenko, O.; Tamassia, R.; Malkin, T.; Kolesnikov, V.; Lewko, AB; Polychronakis, M., Zero-knowledge authenticated order queries and order statistics on a list, Applied Cryptography and Network Security, 149-171, 2015, Heidelberg: Springer, Heidelberg · Zbl 1459.68043 · doi:10.1007/978-3-319-28166-7_8 |
| [33] | Goldberg, S., Naor, M., Papadopoulos, D., Reyzin, L., Vasant, S., Ziv, A.: NSEC5: Provably preventing DNSSEC zone enumeration. Cryptology ePrint Archive, Report 2014/582 (2014) |
| [34] | Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems (extended abstract). In: STOC (1985) |
| [35] | Hanser, C.; Slamanig, D.; Sarkar, P.; Iwata, T., Structure-preserving signatures on equivalence classes and their application to anonymous credentials, Advances in Cryptology - ASIACRYPT 2014, 491-511, 2014, Heidelberg: Springer, Heidelberg · Zbl 1306.94060 |
| [36] | Hazay, C.; Nissim, K., Efficient set operations in the presence of malicious adversaries, J. Cryptology, 25, 3, 383-433, 2012 · Zbl 1272.94034 · doi:10.1007/s00145-011-9098-x |
| [37] | Huang, Y., Evans, D., Katz, J.: Private set intersection: are garbled circuits better than custom protocols? In: NDSS (2012) |
| [38] | Jarecki, S.; Liu, X.; Reingold, O., Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection, Theory of Cryptography, 577-594, 2009, Heidelberg: Springer, Heidelberg · Zbl 1213.94113 · doi:10.1007/978-3-642-00457-5_34 |
| [39] | Kissner, L.; Song, D.; Shoup, V., Privacy-preserving set operations, Advances in Cryptology - CRYPTO 2005, 241-257, 2005, Heidelberg: Springer, Heidelberg · Zbl 1145.94471 · doi:10.1007/11535218_15 |
| [40] | Kosba, A.E., Papadopoulos, D., Papamanthou, C., Sayed, M.F., Shi, E., Triandopoulos, N.: TRUESET: faster verifiable set computations. In: USENIX (2014) |
| [41] | Li, J.; Li, N.; Xue, R.; Katz, J.; Yung, M., Universal accumulators with efficient nonmembership proofs, Applied Cryptography and Network Security, 253-269, 2007, Heidelberg: Springer, Heidelberg · Zbl 1214.94049 · doi:10.1007/978-3-540-72738-5_17 |
| [42] | Libert, B., Ramanna, S.C., Yung, M.: Functional commitment schemes: from polynomial commitments to pairing-based accumulators from simple assumptions. In: ICALP (2016) |
| [43] | Libert, B.; Yung, M.; Micciancio, D., Concise mercurial vector commitments and independent zero-knowledge sets with short proofs, Theory of Cryptography, 499-517, 2010, Heidelberg: Springer, Heidelberg · Zbl 1274.94093 · doi:10.1007/978-3-642-11799-2_30 |
| [44] | Lipmaa, H.; Bao, F.; Samarati, P.; Zhou, J., Secure accumulators from euclidean rings without trusted setup, Applied Cryptography and Network Security, 224-240, 2012, Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-31284-7_14 |
| [45] | Liskov, M.; Roy, B., Updatable zero-knowledge databases, Advances in Cryptology - ASIACRYPT 2005, 174-198, 2005, Heidelberg: Springer, Heidelberg · Zbl 1154.94468 · doi:10.1007/11593447_10 |
| [46] | MacKenzie, P.; Yang, K.; Cachin, C.; Camenisch, JL, On simulation-sound trapdoor commitments, Advances in Cryptology - EUROCRYPT 2004, 382-400, 2004, Heidelberg: Springer, Heidelberg · Zbl 1122.94386 · doi:10.1007/978-3-540-24676-3_23 |
| [47] | Merkle, R.C.: Protocols for public key cryptosystems. In: IEEE Symposium on Security and Privacy (1980) |
| [48] | Micali, S., Rabin, M.O., Kilian, J.: Zero-knowledge sets. In: FOCS (2003) |
| [49] | Miers, I., Garman, C., Green, M., Rubin, A.D.: Zerocoin: anonymous distributed e-cash from bitcoin. In: IEEE Symposium on Security and Privacy (2013) |
| [50] | Morselli, R., Bhattacharjee, S., Katz, J., Keleher, P.J.: Trust-preserving set operations. In: IEEE INFOCOM (2004) |
| [51] | Naor, M.; Nissim, K., Certificate revocation and certificate update, IEEE J. Sel. Areas Commun., 18, 4, 561-570, 2000 · doi:10.1109/49.839932 |
| [52] | Naor, M.; Ziv, A.; Dodis, Y.; Nielsen, JB, Primary-secondary-resolver membership proof systems, Theory of Cryptography, 199-228, 2015, Heidelberg: Springer, Heidelberg · Zbl 1379.94046 · doi:10.1007/978-3-662-46497-7_8 |
| [53] | Nguyen, L.; Menezes, A., Accumulators from bilinear pairings and applications, Topics in Cryptology - CT-RSA 2005, 275-292, 2005, Heidelberg: Springer, Heidelberg · Zbl 1079.94568 · doi:10.1007/978-3-540-30574-3_19 |
| [54] | Nyberg, K.: Commutativity in cryptography. In: 1st International Trier Conference in Functional Analysis (1996) |
| [55] | Nyberg, K.; Gollmann, D., Fast accumulated hashing, Fast Software Encryption, 83-87, 1996, Heidelberg: Springer, Heidelberg · Zbl 1373.94926 · doi:10.1007/3-540-60865-6_45 |
| [56] | Papamanthou, C.; Tamassia, R.; Triandopoulos, N.; Rogaway, P., Optimal verification of operations on dynamic sets, Advances in Cryptology - CRYPTO 2011, 91-110, 2011, Heidelberg: Springer, Heidelberg · Zbl 1287.94094 · doi:10.1007/978-3-642-22792-9_6 |
| [57] | Papamanthou, C., Tamassia, R., Triandopoulos, N.: Authenticated hash tables based on cryptographic accumulators. Algorithmica (2015) |
| [58] | Prabhakaran, M.; Xue, R.; Fischlin, M., Statistically hiding sets, Topics in Cryptology - CT-RSA 2009, 100-116, 2009, Heidelberg: Springer, Heidelberg · Zbl 1237.94088 · doi:10.1007/978-3-642-00862-7_7 |
| [59] | Preparata, F., Sarwate, D., I. U. A. U.-C. C. S. LAB: Computational Complexity of Fourier Transforms Over Finite Fields. DTIC, 1976 |
| [60] | Reyzin, L.; Yakoubov, S.; Zikas, V.; Prisco, R., Efficient asynchronous accumulators for distributed PKI, Security and Cryptography for Networks, 292-309, 2016, Heidelberg: Springer, Heidelberg · Zbl 1416.94056 · doi:10.1007/978-3-319-44618-9_16 |
| [61] | Samelin, K.; Pöhls, HC; Bilzhause, A.; Posegga, J.; Meer, H.; Ryan, MD; Smyth, B.; Wang, G., Redactable signatures for independent removal of structure and content, Information Security Practice and Experience, 17-33, 2012, Heidelberg: Springer, Heidelberg · Zbl 1294.68077 · doi:10.1007/978-3-642-29101-2_2 |
| [62] | Sander, T.: Efficient accumulators without trapdoor. In: ICICS (1999) |
| [63] | Tamassia, R.; Battista, G.; Zwick, U., Authenticated data structures, Algorithms - ESA 2003, 2-5, 2003, Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-540-39658-1_2 |
| [64] | Zheng, Q., Xu, S.: Verifiable delegated set intersection operations on outsourced encrypted data. IACR Cryptology ePrint Archive (2014) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
