More Web Proxy on the site http://driver.im/

research-article

PriSearch: Efficient Search on Private Data

Authors:

M. Sadegh Riazi,

Ebrahim M. Songhori,

Farinaz KoushanfarAuthors Info & Claims

DAC '17: Proceedings of the 54th Annual Design Automation Conference 2017

Article No.: 14, Pages 1 - 6

https://doi.org/10.1145/3061639.3062305

Published: 18 June 2017 Publication History

Abstract

We propose PriSearch, a provably secure methodology for two-party string search. The scenario involves two parties, Alice (holding a query string) and Bob (holding a text), who wish to perform a string search while keeping both the query and the text private without relying on any third party. Such privacy-preserving string search avoids any data leakage when handling sensitive information, e.g., genomic data. PriSearch provides an efficient solution where two parties only need to interact for a constant number of rounds independent of the query and text size. Our approach is based on the provably secure Yao's Garbled Circuit (GC) protocol that requires the string search algorithm to be described as a Boolean circuit. We leverage logic synthesis tools to generate an optimized Boolean circuit for PriSearch such that it incurs the minimum communication/computation cost. We achieve approximately 2x and 140x performance improvements compared to the best prior non-GC and GC-based solutions, respectively.

References

[1]

J. Baron, K. El Defrawy, K. Minkovich, R. Ostrovsky, and E. Tressler. 5pm: Secure pattern matching. In International Conference on Security and Cryptography for Networks. Springer, 2012.

Digital Library

[2]

M. Bellare, V. T. Hoang, S. Keelveedhi, and P. Rogaway. Efficient garbling from a fixed-key blockcipher. In S&P. IEEE, 2013.

Digital Library

[3]

E. De Cristofaro, S. Faber, and G. Tsudik. Secure genomic testing with size-and position-hiding private substring matching. In Proceedings of the 12th ACM workshop on Workshop on privacy in the electronic society. ACM, 2013.

Digital Library

[4]

K. B. Frikken. Practical private DNA string searching and matching through efficient oblivious automata evaluation. In IFIP Annual Conference on Data and Applications Security and Privacy. Springer, 2009.

Digital Library

[5]

J. R. Gibbs and A. Singleton. Application of genome-wide single nucleotide polymorphism typing: simple association and beyond. PLoS Genet, 2006.

[6]

M. Gymrek, A. L. McGuire, D. Golan, E. Halperin, and Y. Erlich. Identifying personal genomes by surname inference. Science, 339(6117), 2013.

[7]

C. Hazay and Y. Lindell. Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. In Theory of Cryptography Conference. Springer, 2008.

Digital Library

[8]

C. Hazay and T. Toft. Computationally secure pattern matching in the presence of malicious adversaries. In ASIACRYPT, 2010.

[9]

N. Homer, S. Szelinger, M. Redman, D. Duggan, W. Tembe, J. Muehling, J. V. Pearson, D. A. Stephan, S. F. Nelson, and D. W. Craig. Resolving individuals contributing trace amounts of DNA to highly complex mixtures using high-density snp genotyping microarrays. PLoS Genet, 4(8), 2008.

[10]

V. Kolesnikov and T. Schneider. Improved garbled circuit: Free XOR gates and applications. In Automata, Languages and Programming. Springer, 2008.

Digital Library

[11]

Y. Lindell and B. Pinkas. Secure two-party computation via cut-and-choose oblivious transfer. Journal of Cryptology, 25(4), 2012.

Digital Library

[12]

M. Naor, B. Pinkas, and R. Sumner. Privacy preserving auctions and mechanism design. In Proceedings of the 1st ACM conference on Electronic commerce. ACM, 1999.

Digital Library

[13]

M. O. Rabin. How to exchange secrets with oblivious transfer, 2005. Harvard University Technical Report 81 [email protected] 12955 received 21 Jun 2005.

[14]

M. S. Riazi, N. K. Dantu, L. V. Gattu, and F. Koushanfar. GenMatch: Secure DNA compatibility testing. In IEEE HOST, 2016.

[15]

M. S. Riazi, E. M. Songhori, A.-R. Sadeghi, T. Schneider, and F. Koushanfar. Toward practical secure stable matching. Proceedings on Privacy Enhancing Technologies, 2017(1):62--78, 2017.

[16]

R. Sedgewick and K. Wayne. Algorithms. Pearson Education, 2011.

Digital Library

[17]

E. M. Songhori, S. U. Hussain, A.-R. Sadeghi, T. Schneider, and F. Koushanfar. TinyGarble: Highly compressed and scalable sequential garbled circuits. In IEEE S & P, 2015.

Digital Library

[18]

J. R. Troncoso-Pastoriza, S. Katzenbeisser, and M. Celik. Privacy-preserving error resilient DNA searching through oblivious automata. In CCS. ACM, 2007.

Digital Library

[19]

D. Vergnaud. Efficient and secure generalized pattern matching via fast fourier transform. In International Conference on Cryptology in Africa. Springer, 2011.

Digital Library

[20]

X. Wang, H. Chan, and E. Shi. Circuit ORAM: On tightness of the Goldreich-Ostrovsky lower bound. In ACM CCS'15. ACM, 2015.

Digital Library

[21]

M. Yasuda, T. Shimoyama, J. Kogure, K. Yokoyama, and T. Koshiba. Secure pattern matching using somewhat homomorphic encryption. In Proceedings of the 2013 ACM workshop on Cloud computing security workshop. ACM, 2013.

Digital Library

[22]

S. Zahur, M. Rosulek, and D. Evans. Two halves make a whole. In EUROCRYPT. Springer, 2015.

Cited By

Hussain SRiazi MKoushanfar F(2021)The Fusion of Secure Function Evaluation and Logic SynthesisIEEE Security & Privacy10.1109/MSEC.2020.304906219:2(48-55)Online publication date: Mar-2021
https://doi.org/10.1109/MSEC.2020.3049062
Xu RJoshi J(2020)Revisiting Secure Computation Using Functional Encryption: Opportunities and Research Directions2020 Second IEEE International Conference on Trust, Privacy and Security in Intelligent Systems and Applications (TPS-ISA)10.1109/TPS-ISA50397.2020.00038(226-235)Online publication date: Oct-2020
https://doi.org/10.1109/TPS-ISA50397.2020.00038
Riazi MJavaheripi MHussain SKoushanfar F(2019)MPCircuits: Optimized Circuit Generation for Secure Multi-Party Computation2019 IEEE International Symposium on Hardware Oriented Security and Trust (HOST)10.1109/HST.2019.8740831(198-207)Online publication date: May-2019
https://doi.org/10.1109/HST.2019.8740831
Show More Cited By

Recommendations

Compacting privacy-preserving k-nearest neighbor search using logic synthesis
DAC '15: Proceedings of the 52nd Annual Design Automation Conference

This paper introduces the first efficient, scalable, and practical method for privacy-preserving k-nearest neighbors (k-NN) search. The approach enables performing the widely used k-NN search in sensitive scenarios where none of the parties reveal their ...
Two-Round MPC: Information-Theoretic and Black-Box
Theory of Cryptography
Abstract
We continue the study of protocols for secure multiparty computation (MPC) that require only two rounds of interaction. The recent works of Garg and Srinivasan (Eurocrypt 2018) and Benhamouda and Lin (Eurocrypt 2018) essentially settle the ...
Two-Round Adaptively Secure Multiparty Computation from Standard Assumptions
Theory of Cryptography
Abstract
We present the first two-round multiparty computation (MPC) protocols secure against malicious adaptive corruption in the common reference string (CRS) model, based on DDH, LWE, or QR. Prior two-round adaptively secure protocols were known only in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '17: Proceedings of the 54th Annual Design Automation Conference 2017

June 2017

533 pages

ISBN:9781450349277

DOI:10.1145/3061639

Copyright © 2017 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

EDAC: Electronic Design Automation Consortium
SIGDA: ACM Special Interest Group on Design Automation
IEEE-CEDA

In-Cooperation

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 June 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

NSF Trust Hub
UConn AFOSR MURI
NSF SRC

Conference

DAC '17

Sponsor:

EDAC
SIGDA

DAC '17: The 54th Annual Design Automation Conference 2017

June 18 - 22, 2017

TX, Austin, USA

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
152
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hussain SRiazi MKoushanfar F(2021)The Fusion of Secure Function Evaluation and Logic SynthesisIEEE Security & Privacy10.1109/MSEC.2020.304906219:2(48-55)Online publication date: Mar-2021
https://doi.org/10.1109/MSEC.2020.3049062
Xu RJoshi J(2020)Revisiting Secure Computation Using Functional Encryption: Opportunities and Research Directions2020 Second IEEE International Conference on Trust, Privacy and Security in Intelligent Systems and Applications (TPS-ISA)10.1109/TPS-ISA50397.2020.00038(226-235)Online publication date: Oct-2020
https://doi.org/10.1109/TPS-ISA50397.2020.00038
Riazi MJavaheripi MHussain SKoushanfar F(2019)MPCircuits: Optimized Circuit Generation for Secure Multi-Party Computation2019 IEEE International Symposium on Hardware Oriented Security and Trust (HOST)10.1109/HST.2019.8740831(198-207)Online publication date: May-2019
https://doi.org/10.1109/HST.2019.8740831
Riazi MWeinert CTkachenko OSonghori ESchneider TKoushanfar FKim JAhn GKim SKim YLopez JKim T(2018)ChameleonProceedings of the 2018 on Asia Conference on Computer and Communications Security10.1145/3196494.3196522(707-721)Online publication date: 29-May-2018
https://dl.acm.org/doi/10.1145/3196494.3196522
Riazi MSamragh MKoushanfar F(2017)CAMsureACM Transactions on Embedded Computing Systems10.1145/312654716:5s(1-20)Online publication date: 27-Sep-2017
https://dl.acm.org/doi/10.1145/3126547

View Options

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