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

research-article

Post‐quantum protocol for computing set intersection cardinality with linear complexity

Authors:

Sumit Kumar Debnath,

Pantelimon Stănică,

Tanmay Choudhury,

Nibedita KunduAuthors Info & Claims

IET Information Security, Volume 14, Issue 6

Pages 661 - 669

https://doi.org/10.1049/iet-ifs.2019.0315

Published: 01 November 2020 Publication History

Abstract

Nowadays, the necessity of electronic information increases rapidly. As a consequence, often, that information needs to be shared among mutually distrustful parties. In this area, private set intersection (PSI) and its variants play an important role when the participants wish to do secret operations on their input sets. Unlike the most modern public key cryptosystems relying on number theoretic problems, lattice‐based cryptographic constructions provide security in the presence of a quantum computer. Consequently, developing PSI and its variants using lattice based cryptosystem becomes an interesting direction for research. This study presents the first size‐hiding post quantum PSI cardinality (PSI‐CA) protocol whose complexity is linear in the size of the sets of the participants. The authors use space‐efficient probabilistic data structure (Bloom filter) as its building block. Further, they extend the authors’ PSI‐CA to its authorised version, i.e. authorised PSI‐CA. Security for both of them is achieved in the standard model based on the hardness of the decisional learning with errors problem.

8. References

[1]

Freedman M.J. Nissim K. Pinkas B.: ‘Efficient private matching, set intersection’. Advances in Cryptology – EUROCRYPT 2004, Switzerland, IBM Zurich Research Laboratory, 2004, pp. 1–19

[2]

Hazay C. Nissim K.: ‘Efficient set operations in the presence of malicious adversaries ’. Public Key Cryptography – PKC 2010, Paris, France, 2010, pp. 312–331

[3]

Kissner L. Song D.: ‘Privacy‐preserving set operations ’. Advances in Cryptology – CRYPTO 2005, Santa Barbara, CA, USA, 2005, pp. 241–257

[4]

Bruekers F. Katzenbeisser S. Kursawe K. et al.: ‘Privacy‐preserving matching of DNA profiles ’. IACR Cryptology ePrint archive, 2008

[5]

De Cristofaro E. Gasti P. Tsudik G.: ‘Fast and private computation of cardinality of set intersection and union ’. Cryptology and Network Security, Darmstadt, Germany, 2012, pp. 218–231

[6]

Agrawal R. Evfimievski A. Srikant R.: ‘Information sharing across private databases ’. Proc. of the 2003 ACM SIGMOD int. Conf. on Management of Data ACM, San Diego, CA, USA, 2003, pp. 86–97

[7]

Hohenberger S. Weis S.A.: ‘Honest‐verifier private disjointness testing without random oracles ’. Privacy Enhancing Technologies, Cambridge, UK, 2006, pp. 277–294

[8]

Goldreich O.: ‘Foundations of cryptography: volume 2, basic applications ’ (Cambridge university Press, New York, USA, 2009 )

[9]

De Cristofaro E. Tsudik G.: ‘Practical private set intersection protocols with linear complexity ’. Int. Conf. on Financial Cryptography and Data Security, Tenerife, Canary Islands, Spain, 2010, pp. 143–159

[10]

Camenisch J. Zaverucha G.M.: ‘Private intersection of certified sets ’. Financial Cryptography and Data Security, Accra Beach, Barbados, 2009, pp. 108–127

[11]

Ateniese G. De Cristofaro E. Tsudik G.: ‘If size matters: size‐hiding private set intersection ’. Int. Workshop on Public Key Cryptography, Taormina, Italy, 2011, pp. 156–173

[12]

Debnath S.K. Dutta R.: ‘Secure and efficient private set intersection cardinality using bloom filter ’. Int. Information Security Conf., Trondheim, Norway, 2015, pp. 209–226

[13]

Lindell Y. Pinkas B.: ‘Privacy preserving data mining ’. Annual Int. Cryptology Conf., Santa Barbara, CA, USA, 2000, pp. 36–54

[14]

Bursztein E. Hamburg M. Lagarenne J. et al.: ‘Openconflict: preventing real time map hacks in online games ’. 2011 IEEE Symp. on Security and Privacy, Oakland, CA, USA, 2011, pp. 506–520

[15]

Nagaraja S. Mittal P. Hong C.‐Y. et al.: ‘Botgrep: finding p2p bots with structured graph analysis ’. USENIX Security Symp., Washington, DC, USA, 2010, vol. 10, pp. 95–110

[16]

Li M. Cao N. Yu S. et al.: ‘Findu: privacy‐preserving personal profile matching in mobile social networks ’. 2011 Proc. IEEE INFOCOM, Shanghai, People's Republic of China, 2011, pp. 2435–2443

[17]

Narayanan A. Thiagarajan N. Lakhani M. et al.: ‘Location privacy via private proximity testing ’. NDSS, San Diego, CA, USA, 2011, vol. 11

[18]

Jarecki S. Liu X.: ‘Fast secure computation of set intersection ’. Security and Cryptography for Networks, Amalfi, Italy, 2010, pp. 418–435

[19]

De Cristofaro E. Tsudik G.: ‘Experimenting with fast private set intersection ’. Trust and Trustworthy Computing, Vienna, Austria, 2012, pp. 55–73

[20]

Huang Y. Evans D. Katz J.: ‘Private set intersection: are garbled circuits better than custom protocols ’. Network and Distributed System Security Symp. (NDSS). The Internet Society, San Diego, USA, 2012

[21]

Dong C. Chen L. Wen Z.: ‘When private set intersection meets big data: an efficient and scalable protocol ’. Proc. of the 2013 ACM SIGSAC Conf. on Computer & Communications Security, ACM, Berlin, Germany, 2013, pp. 789–800

[22]

Pinkas B. Schneider T. Zohner M.: ‘Faster private set intersection based on to extension ’. USENIX Security, San Diego, CA, USA, 2014, vol. 14, pp. 797–812

[23]

Freedman M.J. Hazay C. Nissim K. et al.: ‘Efficient set intersection with simulation‐based security ’, J. Cryptol., 2016, 29, (1 ), pp. 115–155

[24]

Hua Shi R. Mu Y. Zhong H. et al.: ‘An efficient quantum scheme for private set intersection ’, Quantum Inf. Process., 2016, 15, (1 ), pp. 363–371

[25]

Chen H. Laine K. Rindal P.: ‘Fast private set intersection from homomorphic encryption ’. Proc. of the 2017 ACM SIGSAC Conf. on Computer and Communications Security ACM, 2017, pp. 1243–1255

[26]

Rindal P. Rosulek M.: ‘Malicious‐secure private set intersection via dual execution ’. Proc. of the 2017 ACM SIGSAC Conf. on Computer and Communications Security ACM, Dallas, TX, USA, 2017, pp. 1229–1242

[27]

Hazay C. Venkitasubramaniam M.: ‘Scalable multi‐party private set‐intersection ’. IACR Int. Workshop on Public Key Cryptography, Amsterdam, The Netherlands, 2017, pp. 175–203

[28]

Kolesnikov V. Matania N. Pinkas B. et al.: ‘Practical multi‐party private set intersection from symmetric‐key techniques ’. Proc. of the 2017 ACM SIGSAC Conf. on Computer and Communications Security ACM, Dallas Texas USA, 2017, pp. 1257–1272

[29]

Kiss Á. Liu J. Schneider T. et al.: ‘Private set intersection for unequal set sizes with mobile applications ’. Proc. Privacy Enhancing Technol., 2017, 2017, (4 ), pp. 177–197

[30]

Cerulli A. De Cristofaro E. Soriente C.: ‘Nothing refreshes like a repsi: reactive private set intersection ’. International Conference on Applied Cryptography and Network Security ACNS 2018: Applied Cryptography and Network Security, Lecture Notes in Computer Science, Leuven, Belgium, 2018, vol. 16, pp. 280–300

[31]

Ciampi M. Orlandi C.: ‘Combining private set‐intersection with secure two‐party computation ’, IACR ePrint, 105:2018, 2018

[32]

Falk B.H. Noble D. Ostrovsky R.: ‘Private set intersection with linear communication from general assumptions ’, 2018

[33]

Ghosh S. Simkin M.: ‘The communication complexity of threshold private set intersection ’. Annual Int. Cryptology Conf. – CRYPTO 2019, Santa Barbara, CA, USA, 2019, pp. 3–29

[34]

Groce A. Rindal P. Rosulek M.: ‘Cheaper private set intersection via differentially private leakage ’, IACR ePrint, 239:2019, 2019

[35]

Pinkas B. Schneider T. Tkachenko O. et al.: ‘Efficient circuit‐based psi with linear communication ’. Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques – EUROCRYPT 2019, Darmstadt, Germany, 2019, pp. 122–153

[36]

Ghosh S. Nilges T.: ‘An algebraic approach to maliciously secure private set intersection ’. Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques – EUROCRYPT 2019, Darmstadt, Germany, 2014, pp. 154–185

[37]

Pinkas B. Rosulek M. Trieu N. et al.: ‘Spot‐light: lightweight private set intersection from sparse of extension ’. Annual Int. Cryptology Conf.‐CRYPTO 2019, Santa Barbara, CA, USA, 2019, pp. 401–431

[38]

Pinkas B. Rosulek M. Trieu N. et al.: ‘Psi from paxos: fast, malicious private set intersection ’. Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques – EUROCRYPT 2020, Zagreb, Croatia, 2020

[39]

Debnath S.K. Dutta R.: ‘Efficient private set intersection cardinality in the presence of malicious adversaries ’. Provable Security, Kanazawa, Japan, 2015, pp. 326–339

[40]

Hua Shi R. Mu Y. Zhong H. et al.: ‘Quantum private set intersection cardinality and its application to anonymous authentication ’, Inf. Sci., 2016, 370, pp. 147–158

[41]

Dong C. Loukides G.: ‘Approximating private set union/intersection cardinality with logarithmic complexity ’, IEEE Trans. Inf. Forensics Sec., 2017, 12, (11 ), pp. 2792–2806

[42]

Flajolet P. Martin G N.: ‘Probabilistic counting algorithms for data base applications ’, J. Comput. Syst. Sci., 1985, 31, (2 ), pp. 182–209

[43]

Lv S. Ye J. Yin S. et al.: ‘Unbalanced private set intersection cardinality protocol with low communication cost ’, Future Gener. Comput. Syst., 2020, 102, pp. 1054–1061

[44]

De Cristofaro E. Kim J. Tsudik G.: ‘Linear‐complexity private set intersection protocols secure in malicious model ’. Advances in Cryptology‐ASIACRYPT 2010, Singapore, 2010, pp. 213–231

[45]

Stefanov E. Shi E. Song D.: ‘Policy‐enhanced private set intersection: sharing information while enforcing privacy policies ’. Int. Workshop on Public Key Cryptography, Darmstadt, Germany, 2012, pp. 413–430

[46]

Kerschbaum F.: ‘Outsourced private set intersection using homomorphic encryption ’. Proc. of the 7th ACM Symp. on Information, Computer and Communications Security, Seoul, Republic of Korea, 2012, pp. 85–86

[47]

Shor P.W: ‘Polynomial‐time algorithms for prime factorization and discrete logarithms on a quantum computer ’, SIAM Rev., 1999, 41, (2 ), pp. 303–332

[48]

Regev O.: ‘On lattices, learning with errors, random linear codes, and cryptography ’, J. ACM (JACM), 2009, 56, (6 ), p. 34

[49]

Brakerski Z. Perlman R.: ‘Lattice‐based fully dynamic multi‐key FHE with short ciphertexts ’. Annual Int. Cryptology Conf., Santa Barbara, CA, USA, 2016, pp. 190–213

[50]

Mukherjee P. Wichs D.: ‘Two round multiparty computation via multi‐key FHE ’. Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, 2016, pp. 735–763

[51]

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

[52]

Bai S. Galbraith S.D.: ‘An improved compression technique for signatures based on learning with errors ’. Cryptographers Track at the RSA Conf., San Francisco, CA, USA, 2014, pp. 28–47

[53]

Rivest R.L Shamir A. Adleman L.: ‘A method for obtaining digital signatures and public‐key cryptosystems ’, Commun. ACM, 1978, 21, (2 ), pp. 120–126

Cited By

Azogagh SBirba ZGambs SKillijian MVilela JSchulmann HLi N(2024)Crypto'Graph: Leveraging Privacy-Preserving Distributed Link Prediction for Robust Graph LearningProceedings of the Fourteenth ACM Conference on Data and Application Security and Privacy10.1145/3626232.3653257(199-210)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1145/3626232.3653257
Morales DAgudo ILopez J(2023)Private set intersectionComputer Science Review10.1016/j.cosrev.2023.10056749:COnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.cosrev.2023.100567

Recommendations

Distributed signing protocol for IEEE P1363‐compliant identity‐based signature scheme

The identity‐based signature (IBS) scheme is one of the most promising secure and widely used cryptographic primitives for electronic commerce applications. For example, ID‐based signing in a multi‐party setting, without ever revealing any private and ...
Secure hierarchical authentication protocol in VANET

The 5G technology will promote the development of vehicle ad hoc networks (VANET). However, almost all the existing authentication protocols rely on a completely trusted authority (TA), which undoubtedly raises a heavy burden on the TA. On the other hand, ...
Efficient post-quantum private set-intersection protocol

Private set intersection (PSI) is a cryptographic protocol that enables two parties to securely determine the intersection of their private datasets without revealing anything except the intersection. Most of the existing PSI protocols are based on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IET Information Security

IET Information Security Volume 14, Issue 6

November 2020

178 pages

EISSN:1751-8717

DOI:10.1049/ise2.v14.6

Issue’s Table of Contents

© 2020 The Institution of Engineering and Technology.

Publisher

John Wiley & Sons, Inc.

United States

Publication History

Published: 01 November 2020

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 08 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Azogagh SBirba ZGambs SKillijian MVilela JSchulmann HLi N(2024)Crypto'Graph: Leveraging Privacy-Preserving Distributed Link Prediction for Robust Graph LearningProceedings of the Fourteenth ACM Conference on Data and Application Security and Privacy10.1145/3626232.3653257(199-210)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1145/3626232.3653257
Morales DAgudo ILopez J(2023)Private set intersectionComputer Science Review10.1016/j.cosrev.2023.10056749:COnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.cosrev.2023.100567

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents