{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T10:00:19Z","timestamp":1767175219247,"version":"build-2238731810"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Hum. Cent. Comput. Inf. Sci."],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Background<\/jats:title>\n                    <jats:p>Our work is focused on fuzzy keyword search over encrypted data in Cloud Computing.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Methods<\/jats:title>\n                    <jats:p>\n                      We adapt results on private identification schemes by Bringer\n                      <jats:italic>et al<\/jats:italic>\n                      . to this new context. We here exploit a classical embedding of the edit distance into the Hamming distance.\n                    <\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>Our way of doing enables some flexibility on the tolerated edit distance when looking for close keywords while preserving the confidentiality of the queries.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusion<\/jats:title>\n                    <jats:p>Our proposal is proved secure in a security model taking into account privacy.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/2192-1962-2-2","type":"journal-article","created":{"date-parts":[[2019,12,10]],"date-time":"2019-12-10T21:55:02Z","timestamp":1576014902000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Embedding edit distance to enable private keyword search"],"prefix":"10.1186","volume":"2","author":[{"given":"Julien","family":"Bringer","sequence":"first","affiliation":[]},{"given":"Herv\u00e9","family":"Chabanne","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,2,23]]},"reference":[{"key":"8_CR1","first-page":"50","volume-title":"CRYPTO, Volume 4622 of Lecture Notes in Computer Science","author":"D Boneh","year":"2007","unstructured":"Boneh D, Kushilevitz E, Ostrovsky R, Skeith WE III: Public Key Encryption That Allows PIR Queries. In CRYPTO, Volume 4622 of Lecture Notes in Computer Science. Edited by: Menezes A. Springer; 2007:50\u201367."},{"key":"8_CR2","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1145\/1180405.1180417","volume-title":"CCS'06: Proceedings of the 13th ACM conference on Computer and communications security","author":"R Curtmola","year":"2006","unstructured":"Curtmola R, Garay JA, Kamara S, Ostrovsky R: Searchable symmetric encryption: improved definitions and efficient constructions. In CCS'06: Proceedings of the 13th ACM conference on Computer and communications security. ACM; 2006:79\u201388."},{"key":"8_CR3","first-page":"16","volume-title":"Cryptology ePrint Archive, Report 2009\/593","author":"J Li","year":"2009","unstructured":"Li J, Wang Q, Wang C, Cao N, Ren K, Lou W: Enabling Efficient Fuzzy Keyword Search over Encrypted Data in Cloud Computing. Cryptology ePrint Archive, Report 2009\/593 2009, 16."},{"issue":"2","key":"8_CR4","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0031-3203(02)00030-4","volume":"36","author":"J Daugman","year":"2003","unstructured":"Daugman J: The importance of being random: statistical principles of iris recognition. Pattern Recognit 2003,36(2):279\u2013291. 10.1016\/S0031-3203(02)00030-4","journal-title":"Pattern Recognit"},{"key":"8_CR5","volume-title":"Biometrics: Theory, Applications, and Systems, 2010. BTAS'10. IEEE 4th International Conference on","author":"J Bringer","year":"2010","unstructured":"Bringer J, Despiegel V: Binary feature vector fingerprint representation from minutiae vicinities. Biometrics: Theory, Applications, and Systems, 2010. BTAS'10. IEEE 4th International Conference on 2010."},{"key":"8_CR6","volume-title":"SPIE Defense, Security, Sensing","author":"J Bringer","year":"2011","unstructured":"Bringer J, Despiegel V, Favre M: Adding localization information in a fingerprint binary feature vector representation. SPIE Defense, Security, Sensing 2011."},{"key":"8_CR7","volume-title":"IEEE ICC 2009 CISS","author":"J Bringer","year":"2009","unstructured":"Bringer J, Chabanne H, Kindarji B: Error-tolerant searchable encryption. IEEE ICC 2009 CISS 2009."},{"issue":"5","key":"8_CR8","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1002\/sec.206","volume":"4","author":"J Bringer","year":"2011","unstructured":"Bringer J, Chabanne H, Kindarji B: Identification with encrypted biometric data. Security Comm Networks 2011,4(5):548\u2013562. 10.1002\/sec.206","journal-title":"Security Comm Networks"},{"key":"8_CR9","first-page":"86","volume-title":"ICISS, Volume 5905 of Lecture Notes in Computer Science","author":"M Adjedj","year":"2009","unstructured":"Adjedj M, Bringer J, Chabanne H, Kindarji B: Biometric Identification over Encrypted Data Made Feasible. In ICISS, Volume 5905 of Lecture Notes in Computer Science. Edited by: Prakash A, Gupta I. Springer; 2009:86\u2013100."},{"key":"8_CR10","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1145\/1060590.1060623","volume-title":"STOC","author":"R Ostrovsky","year":"2005","unstructured":"Ostrovsky R, Rabani Y: Low distortion embeddings for edit distance. In STOC. Edited by: Gabow HN, Fagin R. ACM; 2005:218\u2013224."},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Ostrovsky R, Rabani Y: Low distortion embeddings for edit distance. J ACM 2007.,54(5):","DOI":"10.1145\/1284320.1284322"},{"issue":"6","key":"8_CR12","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/293347.293350","volume":"45","author":"B Chor","year":"1998","unstructured":"Chor B, Kushilevitz E, Goldreich O, Sudan M: Private Information Retrieval. J ACM 1998,45(6):965\u2013981. 10.1145\/293347.293350","journal-title":"J ACM"},{"key":"8_CR13","first-page":"151","volume-title":"STOC","author":"Y Gertner","year":"1998","unstructured":"Gertner Y, Ishai Y, Kushilevitz E, Malkin T: Protecting data privacy in private information retrieval schemes. STOC 1998, 151\u2013160."},{"key":"8_CR14","first-page":"803","volume-title":"ICALP, Volume 3580 of Lecture Notes in Computer Science","author":"C Gentry","year":"2005","unstructured":"Gentry C, Ramzan Z: Single-database private information retrieval with constant communication rate. In ICALP, Volume 3580 of Lecture Notes in Computer Science. Edited by: Caires L, Italiano GF, Monteiro L, Palamidessi C, Yung M. Springer; 2005:803\u2013815."},{"key":"8_CR15","first-page":"314","volume-title":"ISC, Volume 3650 of Lecture Notes in Computer Science","author":"H Lipmaa","year":"2005","unstructured":"Lipmaa H: An oblivious transfer protocol with log-squared communication. In ISC, Volume 3650 of Lecture Notes in Computer Science. Edited by: Zhou J, Lopez J, Deng RH, Bao F. Springer; 2005:314\u2013328."},{"key":"8_CR16","unstructured":"Gasarch WI: A Survey on Private Information Retrieval. [http:\/\/www.cs.umd.edu\/~gasarch\/pir\/pir.html]"},{"key":"8_CR17","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1145\/258533.258606","volume-title":"STOC","author":"R Ostrovsky","year":"1997","unstructured":"Ostrovsky R, Shoup V: Private information storage (extended abstract). STOC 1997, 294\u2013303."},{"key":"8_CR18","volume-title":"Cryptology ePrint Archive, Report 2007\/064","author":"R Ostrovsky","year":"2007","unstructured":"Ostrovsky R, Skeith WE III: Algebraic Lower Bounds for Computing on Encrypted Data. Cryptology ePrint Archive, Report 2007\/064 2007."},{"key":"8_CR19","volume-title":"Handbook of Discrete and Computational Geometry, Chapter 39","author":"I Piotr","year":"2004","unstructured":"Piotr I: Nearest neighbors in high-dimensional spaces. In Handbook of Discrete and Computational Geometry, Chapter 39. 2nd edition. Edited by: Goodman JE, O'Rourke J. CRC Press; 2004.","edition":"2"},{"key":"8_CR20","first-page":"614","volume-title":"Symposium on the Theory Of Computing","author":"E Kushilevitz","year":"1998","unstructured":"Kushilevitz E, Ostrovsky R, Rabani Y: Efficient Search for approximate nearest neighbor in high dimensional spaces. Symposium on the Theory Of Computing 1998, 614\u2013623."},{"key":"8_CR21","volume-title":"Algorithm Engineering & Experiments","author":"A Kirsch","year":"2006","unstructured":"Kirsch A, Mitzenmacher M: Distance-sensitive bloom filters. Algorithm Engineering & Experiments 2006."},{"key":"8_CR22","first-page":"604","volume-title":"Symposium on the Theory Of Computing","author":"I Piotr","year":"1998","unstructured":"Piotr I, Rajeev M: Approximate nearest neighbors: towards removing the curse of dimensionality. Symposium on the Theory Of Computing 1998, 604\u2013613."},{"key":"8_CR23","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1145\/1327452.1327494","volume":"51","author":"A Andoni","year":"2008","unstructured":"Andoni A, Piotr I: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun ACM 2008, 51: 117\u2013122.","journal-title":"Commun ACM"},{"issue":"2","key":"8_CR24","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1109\/TIFS.2008.920726","volume":"3","author":"F Hao","year":"2008","unstructured":"Hao F, Daugman J, Zielinski P: A Fast Search Algorithm for a Large Fuzzy Database. Inf Forensics Security, IEEE Trans 2008,3(2):203\u2013212.","journal-title":"Inf Forensics Security, IEEE Trans"},{"key":"8_CR25","first-page":"506","volume-title":"EUROCRYPT, Volume 3027 of LCNS","author":"D Boneh","year":"2004","unstructured":"Boneh D, Di Crescenzo G, Ostrovsky R, Persiano G: Public Key Encryption with Keyword Search. In EUROCRYPT, Volume 3027 of LCNS. Edited by: Cachin C, Camenisch J. Springer; 2004:506\u2013522."},{"key":"8_CR26","volume-title":"Cryptology ePrint Archive, Report 2003\/216","author":"EJ Goh","year":"2003","unstructured":"Goh EJ: Secure indexes. Cryptology ePrint Archive, Report 2003\/216 2003."},{"key":"8_CR27","first-page":"132","volume-title":"IEEE Symposium on Security and Privacy","author":"J Bethencourt","year":"2006","unstructured":"Bethencourt J, Song DX, Waters B: New constructions and practical applications for private stream searching (extended abstract). In IEEE Symposium on Security and Privacy. IEEE Computer Society; 2006:132\u2013139."},{"issue":"7","key":"8_CR28","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"BH Bloom","year":"1970","unstructured":"Bloom BH: Space\/time trade-offs in hash coding with allowable errors. Commun ACM 1970,13(7):422\u2013426. 10.1145\/362686.362692","journal-title":"Commun ACM"},{"issue":"2","key":"8_CR29","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S Goldwasser","year":"1984","unstructured":"Goldwasser S, Micali S: Probabilistic Encryption. J Comput Syst Sci 1984,28(2):270\u2013299. 10.1016\/0022-0000(84)90070-9","journal-title":"J Comput Syst Sci"}],"container-title":["Human-centric Computing and Information Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/2192-1962-2-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T17:15:42Z","timestamp":1695489342000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1186\/2192-1962-2-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,23]]},"references-count":29,"aliases":["10.1186\/preaccept-1253053215890607"],"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["8"],"URL":"https:\/\/doi.org\/10.1186\/2192-1962-2-2","relation":{},"ISSN":["2192-1962"],"issn-type":[{"value":"2192-1962","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,23]]},"assertion":[{"value":"24 August 2011","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2012","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2012","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"2"}}