access icon free Post-quantum protocol for computing set intersection cardinality with linear complexity

© The Institution of Engineering and Technology
Received 26/06/2019, Accepted 08/06/2020, Revised 16/05/2020, Published 10/06/2020

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.

Inspec keywords: public key cryptography; cryptographic protocols; cryptography; data privacy; data structures; quantum computing

Other keywords: size-hiding post quantum PSI cardinality protocol whose complexity; secret operations; input sets; linear complexity; electronic information increases; number theoretic problems; authorised PSI-CA; quantum computer; modern public key cryptosystems; mutually distrustful parties; lattice based cryptosystem; intersection cardinality; private set intersection; lattice-based cryptographic constructions; post-quantum protocol; authors

Subjects: Protocols; Data security; Cryptography; File organisation; Quantum computation

References

    1. 1)
      • 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.
    2. 2)
      • 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.
    3. 3)
      • 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.
    4. 4)
      • 30. Cerulli, A., De Cristofaro, E., Soriente, C.: ‘Nothing refreshes like a repsi: reactive private set intersection’. International Conference on Applied Cryptography and Network SecurityACNS 2018: Applied Cryptography and Network Security, Lecture Notes in Computer Science, Leuven, Belgium, 2018, vol. 16, pp. 280–300.
    5. 5)
      • 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.
    6. 6)
      • 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.
    7. 7)
      • 7. Hohenberger, S., Weis, S.A.: ‘Honest-verifier private disjointness testing without random oracles’. Privacy Enhancing Technologies, Cambridge, UK, 2006, pp. 277–294.
    8. 8)
      • 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.
    9. 9)
      • 10. Camenisch, J., Zaverucha, G.M.: ‘Private intersection of certified sets’. Financial Cryptography and Data Security, Accra Beach, Barbados, 2009, pp. 108–127.
    10. 10)
      • 19. De Cristofaro, E., Tsudik, G.: ‘Experimenting with fast private set intersection’. Trust and Trustworthy Computing, Vienna, Austria, 2012, pp. 55–73.
    11. 11)
      • 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.
    12. 12)
      • 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.
    13. 13)
      • 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.
    14. 14)
      • 18. Jarecki, S., Liu, X.: ‘Fast secure computation of set intersection’. Security and Cryptography for Networks, Amalfi, Italy, 2010, pp. 418–435.
    15. 15)
      • 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.
    16. 16)
      • 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.
    17. 17)
      • 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.
    18. 18)
      • 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.
    19. 19)
      • 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.
    20. 20)
      • 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.
    21. 21)
      • 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.
    22. 22)
      • 17. Narayanan, A., Thiagarajan, N., Lakhani, M., et al: ‘Location privacy via private proximity testing’. NDSS, San Diego, CA, USA, 2011, vol. 11.
    23. 23)
      • 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.
    24. 24)
      • 32. Falk, B.H., Noble, D., Ostrovsky, R.: ‘Private set intersection with linear communication from general assumptions’, 2018.
    25. 25)
      • 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.
    26. 26)
      • 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.
    27. 27)
      • 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.
    28. 28)
      • 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.
    29. 29)
      • 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.
    30. 30)
      • 42. Flajolet, P., Martin G, N.: ‘Probabilistic counting algorithms for data base applications’, J. Comput. Syst. Sci., 1985, 31, (2), pp. 182–209.
    31. 31)
      • 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.
    32. 32)
      • 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.
    33. 33)
      • 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.
    34. 34)
      • 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.
    35. 35)
      • 8. Goldreich, O.: ‘Foundations of cryptography: volume 2, basic applications’ (Cambridge university Press, New York, USA, 2009).
    36. 36)
      • 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.
    37. 37)
      • 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.
    38. 38)
      • 51. Bloom, B.H: ‘Space/time trade-offs in hash coding with allowable errors’, Commun. ACM, 1970, 13, (7), pp. 422–426.
    39. 39)
      • 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.
    40. 40)
      • 13. Lindell, Y., Pinkas, B.: ‘Privacy preserving data mining’. Annual Int. Cryptology Conf., Santa Barbara, CA, USA, 2000, pp. 36–54.
    41. 41)
      • 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.
    42. 42)
      • 3. Kissner, L., Song, D.: ‘Privacy-preserving set operations’. Advances in Cryptology – CRYPTO 2005, Santa Barbara, CA, USA, 2005, pp. 241–257.
    43. 43)
      • 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.
    44. 44)
      • 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.
    45. 45)
      • 31. Ciampi, M., Orlandi, C.: ‘Combining private set-intersection with secure two-party computation’, IACR ePrint, 105:2018, 2018.
    46. 46)
      • 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.
    47. 47)
      • 48. Regev, O.: ‘On lattices, learning with errors, random linear codes, and cryptography’, J. ACM (JACM), 2009, 56, (6), p. 34.
    48. 48)
      • 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.
    49. 49)
      • 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.
    50. 50)
      • 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. 51)
      • 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.
    52. 52)
      • 4. Bruekers, F., Katzenbeisser, S., Kursawe, K., et al: ‘Privacy-preserving matching of DNA profiles’. IACR Cryptology ePrint archive, 2008.
    53. 53)
      • 34. Groce, A., Rindal, P., Rosulek, M.: ‘Cheaper private set intersection via differentially private leakage’, IACR ePrint, 239:2019, 2019.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2019.0315
Loading

Related content

content/journals/10.1049/iet-ifs.2019.0315
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading