1. bookVolume 2016 (2016): Issue 4 (October 2016)
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

Efficient Verifiable Range and Closest Point Queries in Zero-Knowledge

Published Online: 14 Jul 2016
Page range: 373 - 388
Received: 29 Feb 2016
Accepted: 02 Jun 2016
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English

We present an efficient method for answering one-dimensional range and closest-point queries in a verifiable and privacy-preserving manner. We consider a model where a data owner outsources a dataset of key-value pairs to a server, who answers range and closest-point queries issued by a client and provides proofs of the answers. The client verifies the correctness of the answers while learning nothing about the dataset besides the answers to the current and previous queries. Our work yields for the first time a zero-knowledge privacy assurance to authenticated range and closest-point queries. Previous work leaked the size of the dataset and used an inefficient proof protocol. Our construction is based on hierarchical identity-based encryption. We prove its security and analyze its efficiency both theoretically and with experiments on synthetic and real data (Enron email and Boston taxi datasets).

Keywords

[1] Boston taxi dataset, https://data.cityofboston.gov/Transportation/Boston-Taxi-Data/ypqb-henq, accessed on 22 Feb 2016Search in Google Scholar

[2] Enron email dataset, https://www.cs.cmu.edu/~./enron/, accessed on 22 Feb 2016Search in Google Scholar

[3] GeoHash library, https://github.com/kungfoo/geohash-java, accessed on 22 Feb 2016Search in Google Scholar

[4] Synthetic datasets for range queries used in this paper, https://repository.library.brown.edu/studio/item/bdr:653992/Search in Google Scholar

[5] Ahn, J.H., Boneh, D., Camenisch, J., Hohenberger, S., Shelat, A., Waters, B.: Computing on authenticated data. In: Theory of Cryptography - Proc. TCC (2012)Search in Google Scholar

[6] Attrapadung, N., Libert, B., Peters, T.: Computing on authenticated data: New privacy definitions and constructions. In: Advances in Cryptology - Proc. ASIACRYPT (2012)Search in Google Scholar

[7] Boneh, D., Boyen, X., Goh, E.J.: Hierarchical identity based encryption with constant size ciphertext. In: Proc. Annual Int. Conf. on Theory and Applications of Cryptographic Techniques. pp. 440-456. EUROCRYPT (2005)Search in Google Scholar

[8] Brickell, E.F., Chaum, D., Damgaard, I.B., van de Graaf, J.: Gradual and verifiable release of a secret. In: Advances in Cryptology CRYPTO. LNCS, vol. 293 (1988)Search in Google Scholar

[9] Brzuska, C., Busch, H., Dagdelen, Ö., Fischlin, M., Franz, M., Katzenbeisser, S., Manulis, M., Onete, C., Peter, A., Poettering, B., Schröder, D.: Redactable signatures for treestructured data: Definitions and constructions. In: Proc. Applied Cryptography and Network Security ACNS (2010)Search in Google Scholar

[10] Catalano, D., Fiore, D., Messina, M.: Zero-knowledge sets with short proofs. In: Advances in Cryptology - Proc. EUROCRYPT (2008)Search in Google Scholar

[11] Chang, E.C., Lim, C.L., Xu, J.: Short redactable signatures using random trees. In: Topics in Cryptology - Proc. Cryptographer’s Track at the RSA Conference CT-RSA (2009)Search in Google Scholar

[12] Chase, M., Healy, A., Lysyanskaya, A., Malkin, T., Reyzin, L.: Mercurial commitments with applications to zeroknowledge sets. In: Advances in Cryptology - Proc. EUROCRYPT (2005)Search in Google Scholar

[13] Chen, F., Liu, A.X.: Privacy- and integrity-preserving range queries in sensor networks. IEEE/ACM Trans. Netw. 20(6), 1774-1787 (Dec 2012)Search in Google Scholar

[14] Devanbu, P.T., Gertz, M., Martel, C.U., Stubblebine, S.G.: Authentic third-party data publication. In: Conference on Data and Applications Security and Privacy DBSec. pp. 101-112 (2000)Search in Google Scholar

[15] Gaede, V., Günther, O.: Multidimensional access methods. ACM Comput. Surv. 30(2), 170-231 (Jun 1998)Search in Google Scholar

[16] Gentry, C., Silverberg, A.: Hierarchical ID-based cryptography. In: Advances in Cryptology - Proc. ASIACRYPT, vol. 2501, pp. 548-566 (2002)Search in Google Scholar

[17] Ghosh, E., Goodrich, M.T., Ohrimenko, O., Tamassia, R.: Fully-dynamic verifiable zero-knowledge order queries for network data. Cryptology ePrint Archive, Report 2015/283 (2015)Search in Google Scholar

[18] Ghosh, E., Ohrimenko, O., Papadopoulos, D., Tamassia, R., Triandopoulos, N.: Zero-knowledge accumulators and set operations. Cryptology ePrint Archive, Report 2015/404 (2015)Search in Google Scholar

[19] Ghosh, E., Ohrimenko, O., Tamassia, R.: Zero-knowledge authenticated order queries and order statistics on a list. In: Proc. Applied Cryptography and Network Security ACNS (2015)Search in Google Scholar

[20] Goldberg, S., Naor, M., Papadopoulos, D., Reyzin, L., Vasant, S., Ziv, A.: NSEC5: Provably preventing DNSSEC zone enumeration. In: The Network and Distributed System Security Symposium NDSS (2015)Search in Google Scholar

[21] Goodrich, M.T., Nguyen, D., Ohrimenko, O., Papamanthou, C., Tamassia, R., Triandopoulos, N., Lopes, C.V.: Efficient verification of web-content searching through authenticated web crawlers. Proceedings of Very Large Data Bases PVLDB 5(10), 920-931 (2012)Search in Google Scholar

[22] Hengartner, U., Steenkiste, P.: Exploiting hierarchical identity-based encryption for access control to pervasive computing information. In: Security and Privacy for Emerging Areas in Communications Networks, SecureComm. pp. 384-396 (2005)Search in Google Scholar

[23] Kamara, S.: Restructuring the NSA metadata program. In: Financial Cryptography and Data Security - FC Workshops. pp. 235-247 (2014)Search in Google Scholar

[24] Kerschbaum, F.: Oblivious outsourcing of garbled circuit generation. In: Proc. ACM Symp. on Applied Computing. pp. 2134-2140 (2015)Search in Google Scholar

[25] Kundu, A., Atallah, M.J., Bertino, E.: Leakage-free redactable signatures. In: .ACM conference on Data and application security and privacy CODASPY (2012)Search in Google Scholar

[26] Kundu, A., Bertino, E.: Structural signatures for tree data structures. Proceedings of Very Large Data Bases PVLDB 1(1) (2008)Search in Google Scholar

[27] Li, F., Hadjieleftheriou, M., Kollios, G., Reyzin, L.: Dynamic authenticated index structures for outsourced databases. In: Proc. of ACM SIGMOD International Conference on Management of Data. pp. 121-132 (2006)Search in Google Scholar

[28] Libert, B., Yung, M.: Concise mercurial vector commitments and independent zero-knowledge sets with short proofs. In: Theory of Cryptography - Proc. TCC (2010)Search in Google Scholar

[29] Merkle, R.C.: A certified digital signature. In: Advances in Cryptology CRYPTO. pp. 218-238 (1989)Search in Google Scholar

[30] Micali, S., Rabin, M.O., Kilian, J.: Zero-knowledge sets. In: Symposium on Foundations of Computer Science FOCS, Proceedings. pp. 80-91 (2003)Search in Google Scholar

[31] Naor, D., Naor, M., Lotspiech, J.: Revocation and tracing schemes for stateless receivers. Electronic Colloquium on Computational Complexity ECCC (043) (2002)Search in Google Scholar

[32] Naor, M., Ziv, A.: Primary-secondary-resolver membership proof systems. In: Theory of Cryptography - Proc. TCC, vol. 9015, pp. 199-228 (2015)Search in Google Scholar

[33] Ostrovsky, R., Rackoff, C., Smith, A.: Efficient consistency proofs for generalized queries on a committed database. In: Automata, Languages and Programming: International Colloquium, ICALP, Proceedings. pp. 1041-1053 (2004)Search in Google Scholar

[34] Papadopoulos, D., Papadopoulos, S., Triandopoulos, N.: Taking authenticated range queries to arbitrary dimensions. In: Proc.ACM Conf. on Computer and Communications Security. pp. 819-830. CCS (2014)Search in Google Scholar

[35] Papadopoulos, D., Papamanthou, C., Tamassia, R., Triandopoulos, N.: Practical authenticated pattern matching with optimal proof size. Proceedings of Very Large Data Bases PVLDB 8(7), 750-761 (2015)Search in Google Scholar

[36] Papamanthou, C., Shi, E., Tamassia, R., Yi, K.: Streaming authenticated data structures. In: Advances in Cryptology - Proc. EUROCRYPT. pp. 353-370 (2013)Search in Google Scholar

[37] Papamanthou, C., Tamassia, R., Triandopoulos, N.: Optimal verification of operations on dynamic sets. In: Advances in Cryptology - Proc. CRYPTO. pp. 91-110 (2011)Search in Google Scholar

[38] Papamanthou, C., Tamassia, R., Triandopoulos, N.: Authenticated hash tables based on cryptographic accumulators. Algorithmica 74(2), 664-712 (2016)Search in Google Scholar

[39] Samelin, K., Pöhls, H.C., Bilzhause, A., Posegga, J., de Meer, H.: On structural signatures for tree data structures. In: Proc. Applied Cryptography and Network Security ACNS (2012)Search in Google Scholar

[40] Sheng, B., Li, Q.: Verifiable privacy-preserving range query in two-tiered sensor networks. In: Proc. IEEE Int. Conf. on Computer Communications INFOCOM. pp. 46-50 (2008)Search in Google Scholar

[41] Shi, E., Bethencourt, J., Chan, T.H.H., Song, D., Perrig, A.: Multi-dimensional range query over encrypted data. In: Proc. IEEE Symp. on Security and Privacy. pp. 350-364 (2007)Search in Google Scholar

[42] Tamassia, R.: Authenticated data structures. In: Proc. European Symp. on Algorithms ESA. LNCS, vol. 2832, pp. 2-5 (2003)Search in Google Scholar

[43] Wang, Z.: Improvement on Ahn et al.’s RSA P-homomorphic signature scheme. In: Security and Privacy for Emerging Areas in Communications Networks, SecureComm (2012)Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo