{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T22:08:35Z","timestamp":1761170915018,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030022235"},{"type":"electronic","value":"9783030022242"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-02224-2_18","type":"book-chapter","created":{"date-parts":[[2018,10,3]],"date-time":"2018-10-03T06:34:07Z","timestamp":1538548447000},"page":"226-240","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Privacy-Preserving String Edit Distance with Moves"],"prefix":"10.1007","author":[{"given":"Shunta","family":"Nakagawa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tokio","family":"Sakamoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoshimasa","family":"Takabatake","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomohiro","family":"I","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kilho","family":"Shin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroshi","family":"Sakamoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,10,4]]},"reference":[{"key":"18_CR1","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.jbi.2015.05.022","volume":"56","author":"M Akg\u00fcn","year":"2015","unstructured":"Akg\u00fcn, M., Bayrak, A.O., Ozer, B., Sa\u011firo\u011flu, M.S.: Privacy preserving processing of genomic data: a survey. J. Biomed. Inform. 56, 103\u2013111 (2015)","journal-title":"J. Biomed. Inform."},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Atallah, M.J., Kerschbaum, F., Du, W.: Secure and private sequence comparisons. In: WPES, pp. 39\u201344 (2003)","DOI":"10.1145\/1005140.1005147"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Aziz, M.M.A., Alhadidi, D., Mohammed, N.: Secure and efficient multiparty computation on genomic data. In: IDEAS, pp. 278\u2013283 (2016)","DOI":"10.1145\/2938503.2938507"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Beck, M., Kerschbaum, F.: Approximate two-party privacy-preserving string matching with linear complexity. In: BigData Congress, pp. 31\u201337 (2013)","DOI":"10.1109\/BigData.Congress.2013.14"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Zhang, Q.: Edit distance: sketching, streaming, and document exchange. In: FOCS, pp. 51\u201360 (2016)","DOI":"10.1109\/FOCS.2016.15"},{"key":"18_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/978-3-540-30539-2_36","volume-title":"Advances in Cryptology - ASIACRYPT 2004","author":"IF Blake","year":"2004","unstructured":"Blake, I.F., Kolesnikov, V.: Strong conditional oblivious transfer and computing on intervals. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 515\u2013529. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30539-2_36"},{"key":"18_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/978-3-540-30576-7_18","volume-title":"Theory of Cryptography","author":"D Boneh","year":"2005","unstructured":"Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325\u2013341. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/978-3-540-30576-7_18"},{"key":"18_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/978-3-319-44618-9_18","volume-title":"Security and Cryptography for Networks","author":"D Catalano","year":"2016","unstructured":"Catalano, D., Di Raimondo, M., Faro, S.: Verifiable pattern matching on outsourced texts. In: Zikas, V., De Prisco, R. (eds.) SCN 2016. LNCS, vol. 9841, pp. 333\u2013350. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-44618-9_18"},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"Cheon, J.H., Kim, M., Lauter, K.E.: Homomorphic computation of edit distance. In: FCW, pp. 194\u2013212 (2015)","DOI":"10.1007\/978-3-662-48051-9_15"},{"issue":"1","key":"18_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1186810.1186812","volume":"3","author":"Graham Cormode","year":"2007","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. ACM Trans. Algorithms 3(1) (2007). Article 2","journal-title":"ACM Transactions on Algorithms"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC, pp. 169\u2013178 (2009)","DOI":"10.1145\/1536414.1536440"},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: Reusable garbled circuits and succinct functional encryption. In: STOC, pp. 555\u2013564 (2013)","DOI":"10.1145\/2488608.2488678"},{"issue":"23","key":"18_CR13","doi-asserted-by":"publisher","first-page":"3051","DOI":"10.1093\/bioinformatics\/bts593","volume":"28","author":"F Hach","year":"2012","unstructured":"Hach, F., Numanagi\u0107, I., Alkan, C., Sahinalp, S.C.: Scalce: boosting sequence compression algorithms using locally consistent encoding. Bioinformatics 28(23), 3051\u20133057 (2012)","journal-title":"Bioinformatics"},{"issue":"3","key":"18_CR14","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1016\/j.datak.2007.03.015","volume":"63","author":"A Inan","year":"2007","unstructured":"Inan, A., Kaya, S., Saygin, Y., Savas, E., Hintoglu, A., Levi, A.: Privacy preserving clustering on horizontally partitioned data. Data Knowl. Eng. 63(3), 646\u2013666 (2007)","journal-title":"Data Knowl. Eng."},{"key":"18_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1007\/978-3-642-33090-2_56","volume-title":"Algorithms \u2013 ESA 2012","author":"H Jowhari","year":"2012","unstructured":"Jowhari, H.: Efficient communication protocols for deciding edit distance. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 648\u2013658. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33090-2_56"},{"issue":"12","key":"18_CR16","doi-asserted-by":"publisher","first-page":"3250","DOI":"10.1109\/TIT.2004.838101","volume":"50","author":"M Li","year":"2004","unstructured":"Li, M., Chen, X., Li, X., Ma, B., Vitanyi, P.M.B.: The similarity metric. IEEE Trans. Inform. Theory 50(12), 3250\u20133264 (2004)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"18_CR17","doi-asserted-by":"crossref","unstructured":"Maruyama, S., Tabei, Y.: Fully-online grammar compression in constant space. In: DCC, pp. 218\u2013229 (2014)","DOI":"10.1007\/978-3-319-02432-5_25"},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/3-540-48910-X_16","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 99","author":"P Paillier","year":"1999","unstructured":"Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223\u2013238. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48910-X_16"},{"key":"18_CR19","unstructured":"Patel, S., Persiano, G., Yeo, K.: Recursive orams with practical constructions. Cryptology ePrint Archive, Report 2017\/964 (2017)"},{"key":"18_CR20","doi-asserted-by":"crossref","unstructured":"Rane, S., Sun, W.: Privacy preserving string comparisons based on Levenshtein distance. In: WIFS, pp. 1\u20136 (2010)","DOI":"10.1109\/WIFS.2010.5711449"},{"key":"18_CR21","doi-asserted-by":"crossref","unstructured":"Rane, S., Sun, W., Vetro, A.: Privacy-preserving approximation of L1 distance for multimedia applications. In: ICME, pp. 492\u2013497 (2010)","DOI":"10.1109\/ICME.2010.5583030"},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"Samanthula, B.K.K., Chun, H., Jiang, W.: An efficient and probabilistic secure bit-decomposition. In: ACM SIGSAC Symposium on Information, Computer and Communications Security, pp. 541\u2013546 (2013)","DOI":"10.1145\/2484313.2484386"},{"issue":"2","key":"18_CR23","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1016\/j.jda.2005.01.010","volume":"5","author":"D Shapira","year":"2007","unstructured":"Shapira, D., Storer, J.A.: Edit distance with move operations. J. Discrete Algorithms 5(2), 380\u2013392 (2007)","journal-title":"J. Discrete Algorithms"},{"key":"18_CR24","unstructured":"Starikovskaya, T.: Communication and streaming complexity of approximate pattern matching. In: CPM, pp. 13:1\u201313:11 (2017)"},{"key":"18_CR25","doi-asserted-by":"crossref","unstructured":"Stefanov, E., et al.: Path oram: an extremely simple oblivious ram protocol. In: CCS, pp. 299\u2013310 (2013)","DOI":"10.1145\/2508859.2516660"},{"key":"18_CR26","unstructured":"Takabatake, Y., I, T., Sakamoto, H.: A space-optimal grammar compression. In: ESA, pp. 67:1\u201367:15 (2017)"},{"key":"18_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/978-3-642-00862-7_24","volume-title":"Topics in Cryptology \u2013 CT-RSA 2009","author":"T Toft","year":"2009","unstructured":"Toft, T.: Constant-rounds, almost-linear bit-decomposition of secret shared values. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473, pp. 357\u2013371. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-00862-7_24"},{"key":"18_CR28","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: How to generate and exchange secrets. In: FOCS, pp. 162\u2013167 (1986)","DOI":"10.1109\/SFCS.1986.25"},{"key":"18_CR29","unstructured":"Zhu, R., Huang, Y.: Efficient privacy-preserving edit distance and beyond. IACR Cryptology ePrint Archive 2017: 683 (2017)"}],"container-title":["Lecture Notes in Computer Science","Similarity Search and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-02224-2_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T03:28:17Z","timestamp":1761103697000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-02224-2_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030022235","9783030022242"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-02224-2_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"4 October 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SISAP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Similarity Search and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Lima","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Peru","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 October 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 October 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sisap2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.sisap.org\/2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}