Advances in Mathematics of Communications (AMC)

Private set intersection: New generic constructions and feasibility results
Pages: 481 - 502, Issue 3, August 2017

doi:10.3934/amc.2017040      Abstract        References        Full text (556.5K)           Related Articles

Paolo D'Arco - Dipartimento di Informatica, University of Salerno, 84084 Fisciano (SA), Italy (email)
María Isabel González Vasco - MACIMTE, Area de Matemática Aplicada, U. Rey Juan Carlos, c/ Tulipán, s/n, 28933, Móstoles, Madrid, Spain (email)
Angel L. Pérez del Pozo - MACIMTE, Area de Matemática Aplicada, U. Rey Juan Carlos, c/ Tulipán, s/n, 28933, Móstoles, Madrid, Spain (email)
Claudio Soriente - Telefónica Research, Barcelona, Spain (email)
Rainer Steinwandt - Florida Atlantic University (FAU), 777 Glades Rd, Boca Raton, FL 33431, United States (email)

1 M. Abdalla, F. Benhamouda, O. Blazy, C. Chevalier and D. Pointcheval, SPHF-friendly non-interactive commitments, in Adv. Crypt. - ASIACRYPT 2013, Springer, 2013, 214-234.       
2 F. Armknecht, D. Augot, L. Perret and A.-R. Sadeghi, On constructing homomorphic encryption schemes from coding theory, in Crypt. Coding (ed. L. Chen), Springer, 2011, 23-40.       
3 G. Ateniese, E. De Cristofaro and G. Tsudik, (If) size matters: size-hiding private set intersection, in Publ. Key Crypt. - PKC 2011 (eds. D. Catalano et al), Springer, 2011, 156-173.       
4 P. Baldi, R. Baronio, E. De Cristofaro, P. Gasti and G. Tsudik, Countering GATTACA: efficient and secure testing of fully-sequenced human genomes, in ACM Conference on Computer and Communications Security - CCS 2011 (eds. Y. Chen ea al), ACM, 2011, 691-702.
5 J. Camenisch and G. M. Zaverucha, Private intersection of certified sets, in Financial Crypt. Data Sec. - FC 2009 (eds. R. Dingledine et al), IFCA, Springer, 2009, 108-127.
6 M. Chase and I. Visconti, Secure database commitments and universal arguments of quasi knowledge, in Advances in Cryptology - CRYPTO 2012 (eds. R. Safavi-Naini et al), Springer, 2012, 236-254.       
7 H. Chen and R. Cramer, Algebraic geometric secret sharing schemes and secure multi-party computations over small fields, in Adv. Crypt. - CRYPTO 2006 (ed. C. Dwork), Springer, 2006, 521-536.       
8 R. Cramer, Introduction to secure computation, in Lect. Data Sec. (ed. I. Damgård), Springer, 1999, 16-62.       
9 R. Cramer and V. Shoup, Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption, in Adv. Crypt. - EUROCRYPT 2002 (ed. L.R. Knudsen), Springer, 2002, 45-64.       
10 E. De Cristofaro, S. Faber and G. Tsudik, Secure genomic testing with size- and position-hiding private substring matching, in ACM Workshop Priv. Electr. Soc. - WPES'13 (eds. A.-R. Sadeghi et al), ACM, 2013, 107-118.
11 E. De Cristofaro, S. Jarecki, J. Kim and G. Tsudik, Privacy-preserving policy-based information transfer, in Priv. Enhanc. Techn. - PETS 2009 (eds. I. Goldberg et al), Springer, 2009, 164-184.
12 E. De Cristofaro, J. Kim and G. Tsudik, Linear-complexity private set intersection protocols secure in malicious model, in Adv. Crypt. - ASIACRYPT 2010 (ed. M. Abe), Springer, 2010, 213-231.
13 E. De Cristofaro and G. Tsudik, Practical private set intersection protocols with linear complexity, in Financial Crypt. Data Sec. - FC 2010 (ed. R. Sion), IFCA, Springer, 2010, 143-159.
14 D. Dachman-Soled, T. Malkin, M. Raykova and M. Yung, Efficient robust private set intersection, in Appl. Crypt. Netw. Sec. - ACNS 2009 (eds. M. Abdalla et al), Springer, 2009, 125-142.       
15 D. Dachman-Soled, T. Malkin, M. Raykova and M. Yung, Secure efficient multiparty computing of multivariate polynomials and applications, in Applied Cryptography and Network Security - ACNS 2011 (eds. J. Lopez et al), Springer, 2011, 130-146.
16 P. D'Arco, M. I. González Vasco, A. L. Pérez del Pozo and C. Soriente, Size-hiding in private set intersection: existential results and constructions, in Progr. Crypt. - AFRICACRYPT 2012 (eds. A. Mitrokotsa et al), Springer, 2012, 378-394.       
17 C. Dong, L. Chen and Z. Wen, When private set intersection meets big data: an efficient and scalable protocol, in ACM SIGSAC Conf. Comp. Commun. Sec. - CCS 2013 (eds. A.-R. Sadeghi et al), ACM, 2013, 789-800.
18 S. Even, O. Goldreich and A. Lempel, A randomized protocol for signing contracts, Commun. ACM, 28 (1985), 637-647.       
19 M. J. Freedman, Y. Ishai, B. Pinkas and O. Reingold, Keyword search and oblivious pseudorandom functions, in Theory Crypt. - TCC 2005 (ed. J. Kilian), Springer, 2005, 303-324.       
20 M. J. Freedman, K. Nissim and B. Pinkas, Efficient private matching and set intersection, in Adv. Crypt. - EUROCRYPT 2004 (eds. C. Cachin et al), Springer, 2004, 1-19.       
21 K. Frikken, Privacy-preserving set union, in Applied Crypt. Netw. Sec. - ACNS 2007 (eds. J. Katz et al), Springer, 2007, 237-252.
22 R. Gennaro and Y. Lindell, A framework for password-based authenticated key exchange (extended abstract), in Adv. Crypt. - EUROCRYPT 2003 (ed. E. Biham), Springer, 2003, 524-543.       
23 O. Goldreich, Foundations of Cryptography, Volume II. Basic Applications, Cambridge Press, 2004.       
24 C. Hazay and Y. Lindell, Constructions of truly practical secure protocols using standard smartcards, in Proc. 15th ACM Conf. Comp. Commun. Sec., ACM, 2008, 491-500.
25 C. Hazay and Y. Lindell, Efficient protocols for set intersection and pattern matching with security against malicious an covert adversaries, in Theory Crypt. - TCC 2008 (ed. R. Canetti), Springer, 2008, 155-175.       
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 Soc., 2012.
27 S. Jarecki and X. Liu, Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection, in Theory Crypt. - TCC 2009 (ed. O. Reingold), Springer, 2009, 577-594.       
28 S. Jarecki and X. Liu, Fast secure computation of set intersection, in Sec. Crypt. Netw. - SCN 2010 (eds. J.A. Garay et al), Springer, 2010, 418-435.
29 J. Katz and Y. Lindell, Introduction to modern cryptography, in Cryptography and Network Security Series, Chapman & Hall/CRC, 2007.       
30 F. Kerschbaum, Outsourced private set intersection using homomorphic encryption, in ACM Symp. Inf. Comp. Commun. Sec. - ASIACCS 2012, ACM, 2012, 85-86.
31 L. Kissner and D. Song, Privacy-preserving set operations, in Adv. Crypt. - CRYPTO 2005 (ed. V. Shoup), Springer, 2005, 241-257.       
32 Y. Lindell, K. Nissim and C. Orlandi, Hiding the input-size in secure two-party computation, in Adv. Crypt. - ASIACRYPT 2013 (eds. K. Sako et al), Springer, 2013, 421-440.       
33 R. Miranda, Algebraic Curves and Riemann Surfaces, volume 5, 1995.       
34 C. Moreno, Algebraic Curves over Finite Fields, Cambridge Univ. Press, 1991.       
35 M. Naor and O. Reingold, Number-theoretic constructions of efficient pseudo-random functions, J. ACM, 51 (2004), 231-262.       
36 R. Nojima and Y. Kadobayashi, Cryptographically secure bloom-filters, Trans. Data Privacy, 2 (2009), 131-139.       
37 P. Paillier, Public-key cryptosystems based on composite degree residuosity classes, in Adv. Crypt. - EUROCRYPT'99 (ed. J. Stern), Springer, 1999, 223-238.       
38 B. Pinkas, T. Schneider, G. Segev and M. Zohner, Phasing: private set intersection using permutation-based hashing, in 24rd USENIX Sec. Symp., USENIX Assoc., 2015, 515-530.
39 B. Pinkas, T. Schneider and M. Zohner, Faster private set intersection based on OT extension, in 23rd USENIX Sec. Symp., USENIX Assoc., 2014, 797-812.
40 M. Rabin, How to Exchange Secrets by Oblivious Transfer, Technical Report TR-81, Aiken Comput. Lab., Harvard Univ., 1981.
41 R. Rivest, Unconditionally secure commitment and oblivious transfer schemes using private channels and a trusted initializer, 1999, available at http://people.csail.mit.edu/rivest/publications.html

Go to top