research-article

GSHADE: faster privacy-preserving distance computation and biometric identification

Authors:

Julien Bringer,

Herve Chabanne,

Thomas Schneider,

Michael ZohnerAuthors Info & Claims

IH&MMSec '14: Proceedings of the 2nd ACM workshop on Information hiding and multimedia security

Pages 187 - 198

https://doi.org/10.1145/2600918.2600922

Published: 11 June 2014 Publication History

Abstract

At WAHC'13, Bringer et al. introduced a protocol called SHADE for secure and efficient Hamming distance computation using oblivious transfer only. In this paper, we introduce a generalization of the SHADE protocol, called GSHADE, that enables privacy-preserving computation of several distance metrics, including (normalized) Hamming distance, Euclidean distance, Mahalanobis distance, and scalar product. GSHADE can be used to efficiently compute one-to-many biometric identification for several traits (iris, face, fingerprint) and benefits from recent optimizations of oblivious transfer extensions. GSHADE allows identification against a database of 1000 Eigenfaces in 1.28 seconds and against a database of 10000 IrisCodes in 17.2 seconds which is more than 10 times faster than previous works.

References

[1]

G. Asharov, Y. Lindell, T. Schneider, and M. Zohner. More efficient oblivious transfer and extensions for faster secure computation. In Computer and Communications Security (CCS), pages 535--548. ACM, 2013. Code available at http://encrypto.de/code/OTExtension.

Digital Library

[2]

AT&T Laboratories Cambridge. The database of faces. http://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html.

[3]

M. Barni, T. Bianchi, D. Catalano, M. Di Raimondo, R. Donida Labati, P. Failla, D. Fiore, R. Lazzeretti, V. Piuri, F. Scotti, and A. Piva. Privacy-preserving fingercode authentication. In ACM workshop on Multimedia and Security (MMSEC), pages 231--240. ACM, 2010.

Digital Library

[4]

P. N. Belhumeur, J. P. Hespanha, and D. J. Kriegman. Eigenfaces vs. Fisherfaces: Recognition using class specific linear projection. In European Conference on Computer Vision (ECCV), volume 1064 of LNCS, pages 43--58. Springer, 1996.

Digital Library

[5]

M. Blanton and P. Gasti. Secure and efficient protocols for iris and fingerprint identification. In European Symposium on Research in Computer Security (ESORICS), volume 6879 of LNCS, pages 190--209. Springer, 2011.

Digital Library

[6]

D. Bogdanov, R. Talviste, and J. Willemson. Deploying secure multi-party computation for financial data analysis. In Financial Cryptography (FC), volume 7397 of LNCS, pages 57--64. Springer, 2012.

[7]

P. Bogetoft, D. L. Christensen, I. Damgård, M. Geisler, T. P. Jakobsen, M. Króigaard, J. D. Nielsen, J. B. Nielsen, K. Nielsen, J. Pagter, M. I. Schwartzbach, and T. Toft. Secure multiparty computation goes live. In Financial Cryptography (FC), volume 5628 of LNCS, pages 325--343. Springer, 2009.

Digital Library

[8]

J. Bringer, H. Chabanne, and A. Patey. Privacy-preserving biometric identification using secure multiparty computation: An overview and recent trends. IEEE Signal Processing Magazine, 30(2):42--52, 2013.

[9]

J. Bringer, H. Chabanne, and A. Patey. SHADE: Secure HAmming DistancE computation from oblivious transfer. In Workshop on Applied Homomorphic Cryptography (WAHC), volume 7862 of LNCS, pages 164--176. Springer, 2013.

[10]

J. Bringer, M. Favre, H. Chabanne, and A. Patey. Faster secure computation for biometric identification using filtering. In IAPR International Conference on Biometrics (ICB), pages 257--264. IEEE, 2012.

[11]

Carnegie Mellon University. The CMU Multi-PIE face database. http://www.multipie.org.

[12]

S. G. Choi, K.-W. Hwang, J. Katz, T. Malkin, and D. Rubenstein. Secure multi-party computation of Boolean circuits with applications to privacy in on-line marketplaces. In Cryptographers' Track at the RSA Conference (CT-RSA), volume 7178 of LNCS, pages 416--432. Springer, 2012. Code available at http://www.ee.columbia.edu/~kwhwang/projects/gmw.html.

Digital Library

[13]

R. Cramer, I. Damgård, and J. B. Nielsen. Multiparty computation from threshold homomorphic encryption. In EUROCRYPT, volume 2045 of LNCS, pages 280--300. Springer, 2001.

Digital Library

[14]

E. D. Cristofaro and G. Tsudik. Practical private set intersection protocols with linear complexity. In Financial Cryptography (FC), volume 6052 of LNCS, pages 143--159. Springer, 2010.

Digital Library

[15]

I. Damgård, M. Geisler, and M. Krøigaard. Efficient and secure comparison for on-line auctions. In Australasian Conference on Information Security and Privacy (ACISP), volume 4586 of LNCS, pages 416--430. Springer, 2007.

Digital Library

[16]

J. Daugman. How iris recognition works. IEEE Transactions on Circuits and Systems for Video Technology, 14(1):21--30, 2004.

Digital Library

[17]

C. Dong, L. Chen, and Z. Wen. When private set intersection meets big data: An efficient and scalable protocol. In Computer and Communications Security (CCS), pages 789--800. ACM, 2013.

Digital Library

[18]

Z. Erkin, M. Franz, J. Guajardo, S. Katzenbeisser, I. Lagendijk, and T. Toft. Privacy-preserving face recognition. In Privacy Enhancing Technologies Symposium (PETS), volume 5672 of LNCS, pages 235--253. Springer, 2009.

Digital Library

[19]

S. Even, O. Goldreich, and A. Lempel. A randomized protocol for signing contracts. In CRYPTO, pages 205--210. Springer, 1982.

[20]

C. Gentry. Fully homomorphic encryption using ideal lattices. In Symposium on Theory of Computing (STOC), pages 169--178. ACM, 2009.

Digital Library

[21]

O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In Symposium on Theory of Computing (STOC), pages 218--229. ACM, 1987.

Digital Library

[22]

R. Gross, I. Matthews, J. F. Cohn, T. Kanade, and S. Baker. Multi-PIE. Image Vision and Computing, 28(5):807--813, 2010.

Digital Library

[23]

M. Günther, R. Wallace, and S. Marcel. An open source framework for standardized comparisons of face recognition algorithms. In Benchmarking Facial Image Analysis Technologies (BeFIT), volume 7585 of LNCS, pages 547--556. Springer, 2012.

Digital Library

[24]

C. Hazay and Y. Lindell. Efficient Secure Two-Party Protocols - Techniques and Constructions. Information Security and Cryptography. Springer, 2010.

Digital Library

[25]

W. Henecka, S. Kögl, A.-R. Sadeghi, T. Schneider, and I. Wehrenberg. TASTY: Tool for Automating Secure Two-partY computations. In Computer and Communications Security (CCS), pages 451--462, 2010.

Digital Library

[26]

Y. Huang, D. Evans, and J. Katz. Private set intersection: Are garbled circuits better than custom protocols? In Network and Distributed System Security Symposium (NDSS). The Internet Society, 2012.

[27]

Y. Huang, D. Evans, J. Katz, and L. Malka. Faster secure two-party computation using garbled circuits. In USENIX Security Symposium. USENIX Association, 2011.

Digital Library

[28]

Y. Huang, L. Malka, D. Evans, and J. Katz. Efficient privacy-preserving biometric identification. In Network and Distributed System Security Symposium (NDSS). The Internet Society, 2011.

[29]

Idiap Research Institute. Face recognition library. https://pypi.python.org/pypi/facereclib.

[30]

Y. Ishai, J. Kilian, K. Nissim, and E. Petrank. Extending oblivious transfers efficiently. In CRYPTO, volume 2729 of LNCS, pages 145--161. Springer, 2003.

[31]

A. K. Jain, S. Prabhakar, L. Hong, and S. Pankanti. FingerCode: A filterbank for fingerprint representation and matching. In Computer Vision and Pattern Recognition (CVPR), pages 187--193. IEEE, 1999.

[32]

V. Kolesnikov and R. Kumaresan. Improved OT extension for transferring short secrets. In CRYPTO, volume 8043 of LNCS, pages 54--70. Springer, 2013.

[33]

V. Kolesnikov and T. Schneider. Improved garbled circuit: Free XOR gates and applications. In International Colloquium on Automata, Languages and Programming (ICALP), volume 5126 of LNCS, pages 486--498. Springer, 2008.

Digital Library

[34]

S. Z. Li and A. K. Jain, editors. Encyclopedia of Biometrics. Springer, 2009.

Digital Library

[35]

Y. Luo, S.-C. S. Cheung, T. Pignata, R. Lazzeretti, and M. Barni. An efficient protocol for private iris-code matching by means of garbled circuits. In International Conference on Image Processing (ICIP), pages 2653--2656. IEEE, 2012.

[36]

M. Naor and B. Pinkas. Efficient oblivious transfer protocols. In Symposium On Discrete Algorithms (SODA), pages 448--457. ACM/SIAM, 2001.

Digital Library

[37]

M. Naor, B. Pinkas, and R. Sumner. Privacy preserving auctions and mechanism design. In Conference on Electronic Commerce (EC), pages 129--139. ACM, 1999.

Digital Library

[38]

M. Osadchy, B. Pinkas, A. Jarrous, and B. Moskovich. SCiFI - a system for secure face identification. In IEEE Symposium on Security and Privacy (S&P), pages 239--254. IEEE, 2010.

Digital Library

[39]

P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, volume 1592 of LNCS, pages 223--238. Springer, 1999.

Digital Library

[40]

M. O. Rabin. How to exchange secrets with oblivious transfer, TR-81 edition, 1981. Aiken Computation Lab, Harvard University.

[41]

A.-R. Sadeghi, T. Schneider, and I. Wehrenberg. Efficient privacy-preserving face recognition. In International Conference on Information Security and Cryptology (ICISC), volume 5984 of LNCS, pages 229--244. Springer, 2009.

Digital Library

[42]

T. Schneider and M. Zohner. GMW vs. Yao? Efficient secure two-party computation with low depth circuits. In Financial Cryptography (FC), volume 7859 of LNCS, pages 275--292. Springer, 2013.

[43]

S. F. Shahandashti, R. Safavi-Naini, and P. Ogunbona. Private fingerprint matching. In Australasian Conference on Information Security and Privacy (ACISP), volume 7372 of LNCS, pages 426--433. Springer, 2012.

Digital Library

[44]

M. Turk and A. Pentland. Eigenfaces for recognition. Journal of Cognitive Neuroscience, 3(1):71--86, 1991.

Digital Library

[45]

A. C.-C. Yao. How to generate and exchange secrets (extended abstract). In Foundations of Computer Science (FOCS), pages 162--167. IEEE, 1986.

Digital Library

Cited By

Gunasinghe HAtallah MBertino E(2024)PEBASI: A Privacy preserving, Efficient Biometric Authentication Scheme based on IrisesACM Transactions on Privacy and Security10.1145/3677017Online publication date: 11-Jul-2024
https://doi.org/10.1145/3677017
EdalatNejad KLueks WSukaitis JNarbel VMarelli MTroncoso C(2024)Janus: Safe Biometric Deduplication for Humanitarian Aid Distribution2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00116(655-672)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00116
Peng ZShi RDing RZhang F(2024)A novel quantum protocol for secure hamming distance computationQuantum Information Processing10.1007/s11128-024-04357-223:5Online publication date: 29-Apr-2024
https://doi.org/10.1007/s11128-024-04357-2
Show More Cited By

Index Terms

GSHADE: faster privacy-preserving distance computation and biometric identification
1. Security and privacy
  1. Cryptography
  2. Systems security
    1. Operating systems security

Recommendations

Boosting GSHADE Capabilities: New Applications and Security in Malicious Setting
SACMAT '16: Proceedings of the 21st ACM on Symposium on Access Control Models and Technologies

The secure two-party computation (S2PC) protocols SHADE and GSHADE have been introduced by Bringer et al. in the last two years. The protocol GSHADE permits to compute different distances (Hamming, Euclidean, Mahalanobis) quite efficiently and is one of ...
A privacy-preserving cancelable iris template generation scheme using decimal encoding and look-up table mapping

Biometric-based recognition systems have overcome passive issues of traditional human authentication systems. However, security theft and privacy invasion are two passive issues that still persist in the effective deployment of biometric-based ...
Blind authentication: a secure crypto-biometric verification protocol

Concerns on widespread use of biometric authentication systems are primarily centered around template security, revocability, and privacy. The use of cryptographic primitives to bolster the authentication process can alleviate some of these concerns as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

IH&MMSec '14: Proceedings of the 2nd ACM workshop on Information hiding and multimedia security

June 2014

212 pages

ISBN:9781450326476

DOI:10.1145/2600918

Conference Chair:
Andreas Unterweger
University of Salzburg, Austria
,
General Chair:
Andreas Uhl
University of Salzburg, Austria
,
Program Chairs:
Stefan Katzenbeisser
TU Darmstadt, Germany
,
Roland Kwitt
University of Salzburg, Austria
,
Alessandro Piva
University of Florence, Italy

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMM: ACM Special Interest Group on Multimedia

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Seventh Framework Programme

Conference

IH&MMSec '14

Sponsor:

SIGMM

IH&MMSec '14: ACM Information Hiding and Multimedia Security Workshop

June 11 - 13, 2014

Salzburg, Austria

Acceptance Rates

IH&MMSec '14 Paper Acceptance Rate 24 of 64 submissions, 38%;

Overall Acceptance Rate 128 of 318 submissions, 40%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
631
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)3

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gunasinghe HAtallah MBertino E(2024)PEBASI: A Privacy preserving, Efficient Biometric Authentication Scheme based on IrisesACM Transactions on Privacy and Security10.1145/3677017Online publication date: 11-Jul-2024
https://doi.org/10.1145/3677017
EdalatNejad KLueks WSukaitis JNarbel VMarelli MTroncoso C(2024)Janus: Safe Biometric Deduplication for Humanitarian Aid Distribution2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00116(655-672)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00116
Peng ZShi RDing RZhang F(2024)A novel quantum protocol for secure hamming distance computationQuantum Information Processing10.1007/s11128-024-04357-223:5Online publication date: 29-Apr-2024
https://doi.org/10.1007/s11128-024-04357-2
Wu DLiang BLu ZDing J(2024)Efficient Secure Multi-party Computation for Multi-dimensional Arithmetics and Its Application in Privacy-Preserving Biometric IdentificationCryptology and Network Security10.1007/978-981-97-8013-6_1(3-25)Online publication date: 2-Oct-2024
https://doi.org/10.1007/978-981-97-8013-6_1
Manvi PDesai ASrinathan KNamboodiri A(2023)S-BAN: Secure Biometric Authentication using NoiseProceedings of the Fourteenth Indian Conference on Computer Vision, Graphics and Image Processing10.1145/3627631.3627638(1-9)Online publication date: 15-Dec-2023
https://dl.acm.org/doi/10.1145/3627631.3627638
Polireddi NSuryadevara MVenkata SRangineni SKoduru SAgal S(2023)A Novel Study on Data Science for Data Security and Data Integrity with Enhanced Heuristic Scheduling in Cloud2023 2nd International Conference on Automation, Computing and Renewable Systems (ICACRS)10.1109/ICACRS58579.2023.10404262(1862-1868)Online publication date: 11-Dec-2023
https://doi.org/10.1109/ICACRS58579.2023.10404262
Verma GKanrar S(2022)A novel model to enhance the data security in cloud environmentMultiagent and Grid Systems10.3233/MGS-22036118:1(45-63)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.3233/MGS-220361
Hu MWu DWu RShi ZChen MZhou Y(2022) RAP : A Light-Weight Privacy-Preserving Framework for Recommender Systems IEEE Transactions on Services Computing10.1109/TSC.2021.306503515:5(2969-2981)Online publication date: 1-Sep-2022
https://doi.org/10.1109/TSC.2021.3065035
Zhao FLi ZWang H(2022)PPCNN: An efficient privacy‐preserving CNN training and inference frameworkInternational Journal of Intelligent Systems10.1002/int.2303037:12(10988-11018)Online publication date: 23-Aug-2022
https://doi.org/10.1002/int.23030
Xie HGuo YJia X(2021)A Privacy-Preserving Online Ride-Hailing System Without Involving a Third Trusted ServerIEEE Transactions on Information Forensics and Security10.1109/TIFS.2021.306583216(3068-3081)Online publication date: 2021
https://doi.org/10.1109/TIFS.2021.3065832
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents