Top

Published in:

2020 | OriginalPaper | Chapter

Faster Privacy-Preserving Computation of Edit Distance with Moves

Authors : Yohei Yoshimoto, Masaharu Kataoka, Yoshimasa Takabatake, Tomohiro I, Kilho Shin, Hiroshi Sakamoto

Published in: WALCOM: Algorithms and Computation

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider an efficient two-party protocol for securely computing the similarity of strings w.r.t. an extended edit distance measure. Here, two parties possessing strings x and y, respectively, want to jointly compute an approximate value for \(\mathrm {EDM}(x,y)\), the minimum number of edit operations including substring moves needed to transform x into y, without revealing any private information. Recently, the first secure two-party protocol for this was proposed, based on homomorphic encryption, but this approach is not suitable for long strings due to its high communication and round complexities. In this paper, we propose an improved algorithm that significantly reduces the round complexity without sacrificing its cryptographic strength. We examine the performance of our algorithm for DNA sequences compared to previous one.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Efficient Enumeration of Non-isomorphic Ptolemaic Graphs

next chapter Parameterized Algorithms for the Happy Set Problem

In Appendix A of [10], the authors point out that there is a subtle flaw in the ESP algorithm [8] that achieves this \(O(\lg ^*N\lg N )\) bound. However, this flaw can be remedied by an alternative algorithm called HSP [10].

\(\lg ^*N\) is the number of times the logarithm function \(\lg \) must be iteratively applied to N until the result is at most 1.

In general, the number of applicable operations over ciphertexts is bounded by the size of (pk, sk).

https://github.com/herumi/mcl.

http://pizzachili.dcc.uchile.cl.

https://www.7-zip.org/.

Akgün, M., Bayrak, A.O., Ozer, B., Sağiroğlu, M.S.: Privacy preserving processing of genomic data: a survey. J. Biomed. Inform. 56, 103–111 (2015)CrossRef

Attrapadung, N., Hanaoka, G., Mitsunari, S., Sakai, Y., Shimizu, K., Teruya, T.: Efficient two-level homomorphic encryption in prime-order bilinear groups and a fast implementation in webassembly. In: ASIACCS, pp. 685–697 (2018)

Blanton, M., Aguiar, E.: Private and oblivious set and multiset operations. In: ASIACCS, pp. 40–41 (2012)

Bloom, B.H.: Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422–426 (1970)CrossRef

Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30576-7_18CrossRef

Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: ITCS, pp. 309–325 (2012)

Catalano, D., Fiore, D.: Using linearly-homomorphic encryption to evaluate degree-2 functions on encrypted data. In: CCS, pp. 1518–1529 (2015)

Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. ACM Trans. Algor. 3(1), 1–19 (2007). Article 2 MathSciNetCrossRef

Davidson, A., Cid, C.: An efficient toolkit for computing private set operations. In: Pieprzyk, J., Suriadi, S. (eds.) ACISP 2017. LNCS, Part II, vol. 10343, pp. 261–278. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59870-3_15CrossRef

10.

Fischer, J., I, T., Köppl, D.: Deterministic sparse suffix sorting on rewritable texts. In: Kranakis, E., Navarro, G., Chávez, E. (eds.) LATIN 2016. LNCS, vol. 9644, pp. 483–496. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49529-2_36CrossRef

11.

Freeman, D.M.: Converting pairing-based cryptosystems from composite-order groups to prime-order groups. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 44–61. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_3CrossRef

12.

Ganczorz, M., Gawrychowski, P., Jez, A., Kociumaka, T.: Edit distance with block operations. In: ESA, pp. 33:1–33:14 (2018)

13.

Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC, pp. 169–178 (2009)

14.

Goldreich, O.: Foundations of Cryptography, vol. II. Cambridge University Press, New York (2004)CrossRef

15.

Herold, G., Hesse, J., Hofheinz, D., Ràfols, C., Rupp, A.: Polynomial spaces: a new framework for composite-to-prime-order transformations. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 261–279. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_15CrossRef

16.

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–666 (2007)CrossRef

17.

Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2), 249–260 (1987)MathSciNetCrossRef

18.

Kissner, L., Song, D.: Privacy-preserving set operations. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 241–257. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_15CrossRef

19.

Nakagawa, S., Sakamoto, T., Takabatake, Y., I, T., Shin, K., Sakamoto, H.: Privacy-preserving string edit distance with moves. In: Marchand-Maillet, S., Silva, Y.N., Chávez, E. (eds.) SISAP 2018. LNCS, vol. 11223, pp. 226–240. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-02224-2_18CrossRef

20.

Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_16CrossRef

21.

Rane, S., Sun, W.: Privacy preserving string comparisons based on Levenshtein distance. In: WIFS, pp. 1–6 (2010)

22.

Shapira, D., Storer, J.A.: Edit distance with move operations. J. Discrete Algorithms 5(2), 380–392 (2007)MathSciNetCrossRef

Title: Faster Privacy-Preserving Computation of Edit Distance with Moves
Authors: Yohei Yoshimoto
Masaharu Kataoka
Yoshimasa Takabatake
Tomohiro I
Kilho Shin
Hiroshi Sakamoto
Publisher: Springer International Publishing
Book: WALCOM: Algorithms and Computation
Print ISBN: 978-3-030-39880-4

Electronic ISBN: 978-3-030-39881-1

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-39881-1_26

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner