{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:50:23Z","timestamp":1740124223860,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T00:00:00Z","timestamp":1580256000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T00:00:00Z","timestamp":1580256000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["BO 2129\/13-1"],"award-info":[{"award-number":["BO 2129\/13-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib Parallel Databases"],"published-print":{"date-parts":[[2021,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Database outsourcing is a challenge concerning data secrecy. Even if an adversary, including the service provider, accesses the data, she should not be able to learn any information from the accessed data. In this paper, we address this problem for graph-structured data. First, we define a secrecy notion for graph-structured data based on the concepts of indistinguishability and searchable encryption. To address this problem, we propose an approach based on bucketization. Next to bucketization, it makes use of obfuscated indexes and encryption. We show that finding an optimal bucketization tailored to graph-structured data is NP-hard; therefore, we come up with a heuristic. We prove that the proposed bucketization approach fulfills our secrecy notion. In addition, we present a performance model for scale-free networks which consists of (1) a number-of-buckets model that estimates the number of buckets obtained after applying our bucketization approach and (2) a query-cost model. Finally, we demonstrate with a set of experiments the accuracy of our number-of-buckets model and the efficiency of our approach with respect to query processing.<\/jats:p>","DOI":"10.1007\/s10619-020-07284-0","type":"journal-article","created":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T12:04:00Z","timestamp":1580299440000},"page":"35-77","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Secrecy and performance models for query processing on outsourced graph data"],"prefix":"10.1007","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0298-5144","authenticated-orcid":false,"given":"Gabriela","family":"Suntaxi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aboubakr Achraf","family":"El Ghazi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klemens","family":"B\u00f6hm","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,29]]},"reference":[{"key":"7284_CR1","unstructured":"Aggarwal, G., Bawa, M., Ganesan, P., Garcia-Molina, H., Kenthapadi, K., Motwani, R., Srivastava, U., Thomas, D., Xu, Y.: Two can keep a secret: a distributed architecture for secure database services. CIDR (2005)"},{"issue":"5439","key":"7284_CR2","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"AL Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509\u2013512 (1999)","journal-title":"Science"},{"key":"7284_CR3","doi-asserted-by":"crossref","unstructured":"Bellare, M., Boldyreva, A., O\u2019Neill, A.: Deterministic and efficiently searchable encryption. In: Annual International Cryptology Conference, pp. 535\u2013552. Springer, New York (2007)","DOI":"10.1007\/978-3-540-74143-5_30"},{"key":"7284_CR4","doi-asserted-by":"crossref","unstructured":"Bhandari, A., Gupta, A., Das, D.: A framework for data security and storage in cloud computing. In: 2016 International Conference on Computational Techniques in Information and Communication Technologies (ICCTICT). IEEE, pp. 1\u20137 (2016)","DOI":"10.1109\/ICCTICT.2016.7514542"},{"key":"7284_CR5","unstructured":"Boneh, D., Shoup, V.: A graduate course in applied cryptography. (2008) https:\/\/crypto.stanford.edu\/~dabo\/cryptobook\/"},{"key":"7284_CR6","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/978-3-642-23556-6_8","volume":"6933","author":"C B\u00f6sch","year":"2011","unstructured":"B\u00f6sch, C., Brinkman, R., Hartel, P.H., Jonker, W.: Conjunctive wildcard search over encrypted data. Secur. Data Manag. 6933, 114\u2013127 (2011)","journal-title":"Secur. Data Manag."},{"key":"7284_CR7","doi-asserted-by":"crossref","unstructured":"Cao, J., Rao, F.Y., Kuzu, M., Bertino, E., Kantarcioglu, M.: Efficient tree pattern queries on encrypted xml documents. In: Proceedings of the Joint EDBT\/ICDT 2013 Workshops. ACM, pp. 111\u2013120 (2013)","DOI":"10.1145\/2457317.2457338"},{"key":"7284_CR8","doi-asserted-by":"crossref","unstructured":"Cao, N., Yang, Z., Wang, C., Ren, K., Lou, W.: Privacy-preserving query over encrypted graph-structured data in cloud computing. In: 2011 31st International Conference on Distributed Computing Systems (ICDCS). IEEE, pp. 393\u2013402 (2011)","DOI":"10.1109\/ICDCS.2011.84"},{"issue":"5","key":"7284_CR9","doi-asserted-by":"publisher","first-page":"895","DOI":"10.3233\/JCS-2011-0426","volume":"19","author":"R Curtmola","year":"2011","unstructured":"Curtmola, R., Garay, J., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. J. Comput. Secur. 19(5), 895\u2013934 (2011)","journal-title":"J. Comput. Secur."},{"issue":"8","key":"7284_CR10","doi-asserted-by":"publisher","first-page":"2275","DOI":"10.1109\/TKDE.2015.2399292","volume":"27","author":"Z Fan","year":"2015","unstructured":"Fan, Z., Choi, B., Chen, Q., Xu, J., Hu, H., Bhowmick, S.S.: Structure-preserving subgraph query services. IEEE Trans. Knowl. Data Eng. 27(8), 2275\u20132290 (2015)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"3","key":"7284_CR11","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"MR Garey","year":"1978","unstructured":"Garey, M.R., Johnson, D.S.: \u201cStrong\u201d np-completeness results: motivation, examples, and implications. J. ACM 25(3), 499\u2013508 (1978)","journal-title":"J. ACM"},{"key":"7284_CR12","first-page":"70","volume-title":"A Guide to the Theory of np-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: A Guide to the Theory of np-Completeness, p. 70. WH Freemann, New York (1979)"},{"key":"7284_CR13","doi-asserted-by":"crossref","unstructured":"Getoor, L., Taskar, B., Koller, D.: Selectivity estimation using probabilistic models. In: ACM SIGMOD Record. ACM, vol. 30, pp. 461\u2013472 (2001)","DOI":"10.1145\/376284.375727"},{"key":"7284_CR14","first-page":"216","volume":"2003","author":"EJ Goh","year":"2003","unstructured":"Goh, E.J., et al.: Secure indexes. IACR Cryptol. ePrint Arch. 2003, 216 (2003)","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"7284_CR15","doi-asserted-by":"crossref","unstructured":"Hacig\u00fcm\u00fc\u015f, H., Iyer, B., Li, C., Mehrotra, S.: Executing sql over encrypted data in the database-service-provider model. In: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data. ACM, pp. 216\u2013227 (2002)","DOI":"10.1145\/564691.564717"},{"key":"7284_CR16","doi-asserted-by":"crossref","unstructured":"Hac\u0131g\u00fcm\u00fc\u015f, H., Iyer, B., Mehrotra, S.: Query optimization in encrypted database systems. In: International Conference on Database Systems for Advanced Applications pp. 43\u201355. Springer, New York (2005)","DOI":"10.1007\/11408079_7"},{"key":"7284_CR17","doi-asserted-by":"crossref","unstructured":"He, X., Vaidya, J., Shafiq, B., Adam, N., Lin, X.: Reachability analysis in privacy-preserving perturbed graphs. In: 2010 IEEE\/WIC\/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT). IEEE, vol. 1, pp. 691\u2013694 (2010)","DOI":"10.1109\/WI-IAT.2010.216"},{"key":"7284_CR18","doi-asserted-by":"crossref","unstructured":"Hore, B., Mehrotra, S., Tsudik, G.: A privacy-preserving index for range queries. In: Proceedings of the Thirtieth International Conference on Very Large Data Bases, VLDB Endowment, vol. 30, pp. 720\u2013731 (2004)","DOI":"10.1016\/B978-012088469-8.50064-4"},{"key":"7284_CR19","unstructured":"Johnson, D.S.: Near-optimal bin packing algorithms. PhD thesis, Massachusetts Institute of Technology (1973)"},{"key":"7284_CR20","doi-asserted-by":"crossref","unstructured":"Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security. ACM, pp. 965\u2013976 (2012)","DOI":"10.1145\/2382196.2382298"},{"key":"7284_CR21","doi-asserted-by":"crossref","unstructured":"Katz, J., Lindell, Y.: Introduction to modern cryptography (2007)","DOI":"10.1201\/9781420010756"},{"key":"7284_CR22","doi-asserted-by":"crossref","unstructured":"Kellaris, G., Kollios, G., Nissim, K., O\u2019Neill, A.: Generic attacks on secure outsourced databases. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM, pp. 1329\u20131340 (2016)","DOI":"10.1145\/2976749.2978386"},{"key":"7284_CR23","doi-asserted-by":"crossref","unstructured":"Kunegis, J.: Konect: the koblenz network collection. In: Proceedings of the 22nd International Conference on World Wide Web. ACM, pp. 1343\u20131350 (2013)","DOI":"10.1145\/2487788.2488173"},{"key":"7284_CR24","doi-asserted-by":"crossref","unstructured":"LeFevre, K., DeWitt, D.J., Ramakrishnan, R.: Mondrian multidimensional k-anonymity. In: 22nd International Conference on Data Engineering (ICDE\u201906). IEEE, pp. 25\u201325 (2006)","DOI":"10.1109\/ICDE.2006.101"},{"key":"7284_CR25","unstructured":"Leskovec, J., Krevl, A.: Snap datasets: stanford large network dataset collection. http:\/\/snap.stanford.edu\/data\/cit-HepTh.html (2014)"},{"issue":"1","key":"7284_CR26","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1080\/15427951.2009.10129177","volume":"6","author":"J Leskovec","year":"2009","unstructured":"Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math. 6(1), 29\u2013123 (2009)","journal-title":"Internet Math."},{"key":"7284_CR27","doi-asserted-by":"crossref","unstructured":"Li, J., Wang, Q., Wang, C., Cao, N., Ren, K., Lou, W.: Fuzzy keyword search over encrypted data in cloud computing. In: 2010 Proceedings IEEE INFOCOM. IEEE, pp. 1\u20135 (2010)","DOI":"10.1109\/INFCOM.2010.5462196"},{"key":"7284_CR28","doi-asserted-by":"crossref","unstructured":"Maserrat, H., Pei, J.: Neighbor query friendly compression of social networks. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, pp. 533\u2013542 (2010)","DOI":"10.1145\/1835804.1835873"},{"key":"7284_CR29","doi-asserted-by":"crossref","unstructured":"Matias, Y., Vitter, J.S., Wang, M.: Wavelet-based histograms for selectivity estimation. In: ACM SIGMoD Record. ACM, vol. 27, pp. 448\u2013459 (1998)","DOI":"10.1145\/276305.276344"},{"key":"7284_CR30","doi-asserted-by":"crossref","unstructured":"Meng, X., Kamara, S., Nissim, K., Kollios, G.: Grecs: graph encryption for approximate shortest distance queries. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. ACM, pp. 504\u2013517 (2015)","DOI":"10.1145\/2810103.2813672"},{"key":"7284_CR31","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S., Poosala, V., Suel, T.: On rectangular partitionings in two dimensions: algorithms, complexity and applications. In: International Conference on Database Theory, pp. 236\u2013256. Springer, New York (1999)","DOI":"10.1007\/3-540-49257-7_16"},{"key":"7284_CR32","doi-asserted-by":"crossref","unstructured":"Naveed, M., Kamara, S., Wright, C.V.: Inference attacks on property-preserving encrypted databases. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. ACM, pp. 644\u2013655 (2015)","DOI":"10.1145\/2810103.2813651"},{"key":"7284_CR33","doi-asserted-by":"crossref","unstructured":"Orhanou, G., El\u00a0Hajji, S., Bentaleb, Y.: Eps aes-based confidentiality and integrity algorithms: complexity study. In: 2011 International Conference on Multimedia Computing and Systems (ICMCS). IEEE, pp. 1\u20134 (2011)","DOI":"10.1109\/ICMCS.2011.5945606"},{"key":"7284_CR34","doi-asserted-by":"crossref","unstructured":"Prakash, A.J., Uthariaraj, V.R.: Multicrypt: A provably secure encryption scheme for multicast communication. In: First International Conference on Networks and Communications, (NETCOM\u201909). IEEE, pp. 246\u2013253 (2009)","DOI":"10.1109\/NetCoM.2009.80"},{"key":"7284_CR35","unstructured":"Reddy, N., Haritsa, J.R.: Analyzing plan diagrams of database query optimizers. In: Proceedings of the 31st International Conference on Very Large Data Bases, VLDB Endowment, pp. 1228\u20131239 (2005)"},{"key":"7284_CR36","unstructured":"Schult, D.A., Swart, P.: Exploring network structure, dynamics, and function using networkx. In: Proceedings of the 7th Python in Science Conferences (SciPy 2008), vol. 2008, pp. 11\u201316 (2008)"},{"key":"7284_CR37","doi-asserted-by":"crossref","unstructured":"Syalim, A., Nishide, T., Sakurai, K.: Preserving integrity and confidentiality of a directed acyclic graph model of provenance. In: Data and Applications Security and Privacy, vol. XXIV, pp. 311\u2013318 (2010)","DOI":"10.1007\/978-3-642-13739-6_22"},{"key":"7284_CR38","doi-asserted-by":"crossref","unstructured":"Van\u00a0Liesdonk, P., Sedghi, S., Doumen, J., Hartel, P., Jonker, W.: Computationally efficient searchable symmetric encryption. In: Workshop on Secure Data Management, pp. 87\u2013100. Springer, New York (2010)","DOI":"10.1007\/978-3-642-15546-8_7"},{"key":"7284_CR39","unstructured":"Wang, H., Lakshmanan, L.V.: Efficient secure query evaluation over encrypted xml databases. In: Proceedings of the 32nd International Conference on Very Large Data Bases, VLDB Endowment, pp. 127\u2013138 (2006)"},{"key":"7284_CR40","doi-asserted-by":"crossref","unstructured":"Wang, J., Du, X.: A secure multi-dimensional partition based index in das. In: Asia-Pacific Web Conference, pp. 319\u2013330. Springer, New York (2008)","DOI":"10.1007\/978-3-540-78849-2_33"},{"key":"7284_CR41","doi-asserted-by":"crossref","unstructured":"Wang, Q., Ren, K., Du, M., Li, Q., Mohaisen, A.: Secgdb: Graph encryption for exact shortest distance queries with efficient updates. In: International Conference on Financial Cryptography and Data Security, pp. 79\u201397. Springer, New York (2017)","DOI":"10.1007\/978-3-319-70972-7_5"},{"key":"7284_CR42","doi-asserted-by":"crossref","unstructured":"Yi, P., Fan, Z., Yin, S.: Privacy-preserving reachability query services for sparse graphs. In: 2014 IEEE 30th International Conference on Data Engineering Workshops (ICDEW). IEEE, pp. 32\u201335 (2014)","DOI":"10.1109\/ICDEW.2014.6818298"},{"issue":"11","key":"7284_CR43","doi-asserted-by":"publisher","first-page":"1933","DOI":"10.1002\/sec.907","volume":"7","author":"Y Zhang","year":"2014","unstructured":"Zhang, Y., Su, S., Wang, Y., Chen, W., Yang, F.: Privacy-assured substructure similarity query over encrypted graph-structured data in cloud. Secur. Commun. Netw. 7(11), 1933\u20131944 (2014)","journal-title":"Secur. Commun. Netw."},{"key":"7284_CR44","doi-asserted-by":"crossref","unstructured":"Zhou, B., Pei, J.: Preserving privacy in social networks against neighborhood attacks. In: IEEE 24th International Conference on Data Engineering, (ICDE 2008). IEEE, pp. 506\u2013515 (2008)","DOI":"10.1109\/ICDE.2008.4497459"}],"container-title":["Distributed and Parallel Databases"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10619-020-07284-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10619-020-07284-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10619-020-07284-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,5]],"date-time":"2021-02-05T12:22:51Z","timestamp":1612527771000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10619-020-07284-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,29]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["7284"],"URL":"https:\/\/doi.org\/10.1007\/s10619-020-07284-0","relation":{},"ISSN":["0926-8782","1573-7578"],"issn-type":[{"type":"print","value":"0926-8782"},{"type":"electronic","value":"1573-7578"}],"subject":[],"published":{"date-parts":[[2020,1,29]]},"assertion":[{"value":"29 January 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}