Cryptographic algorithms for privacy-preserving online applications

Ruinian Li; Yinhao Xiao; Cheng Zhang; Tianyi Song; Chunqiang Hu

doi:10.3934/mfc.2018015

Article Contents

2018, Volume 1, Issue 4: 311-330. Doi: 10.3934/mfc.2018015

This issue Previous Article Next Article Privacy preserving feature selection and Multiclass Classification for horizontally distributed data

Cryptographic algorithms for privacy-preserving online applications

1.
Computer Science Department, Bowling Green State University, Bowling Green, Ohio 43401, USA
2.
Computer Science Department, George Washington University, 2121 I St NW, Washington, DC 20052, USA
3.
School of Big Data and Software Engineering, Chongqing University, Chongqing, China

^* Corresponding author: Chunqiang Hu
^* Corresponding author: Chunqiang Hu

Received: August 2018

Revised: September 2018

Published: December 2018

Abstract Full Text(HTML) Figure(6) / Table(3) Related Papers Cited by

Abstract

Privacy in online applications has drawn tremendous attention in recent years. With the development of cloud-based applications, protecting users' privacy while guaranteeing the expected service from the server has become a significant issue. This paper surveyed the most popular cryptographic algorithms in privacy-preserving online applications to provide a tutorial-like introduction to researchers in this area. Specifically, this paper focuses on introduction to homomorphic encryption, secret sharing, secure multi-party computation and zero-knowledge proof.

Keywords:

Mathematics Subject Classification: Primary: 94A60.

Citation:

Full Text(HTML)

Figure 1. General Online Application Architecture

Download: Full-size image PowerPoint slide

Figure 2. Blakley's Secret Share Scheme [1]

Download: Full-size image PowerPoint slide

Figure 3. Garbled Circuits Overview

Download: Full-size image PowerPoint slide

Figure 4. Garbled Circuits Mappings

Download: Full-size image PowerPoint slide

Figure 5. A ZKP Example [2]

Download: Full-size image PowerPoint slide

Figure 6. An Online Auction Scheme Model

Download: Full-size image PowerPoint slide

Table 1. Comparison of Homomorphic Schemes

Scheme	Additive-Homo	Multi-Homo	Full-Homo
GM(Goldwasser) and Micali 1982 [34]	$\surd$
Exponential Elgamal [44]	$\surd$
Benaloh 1994 [9]	$\surd$
NS (Naccache and Stern) 1998 [62]	$\surd$
OU (Okamoto and Uchiyama) 1998 [64]	$\surd$
Paillier 1999 [65]	$\surd$
DJ (Damgad and Jurik) 2001 [24]	$\surd$
KTX (Kawachi, Tanaka and Xagawa)[46] 2007	$\surd$
RSA 1978 [73]		$\surd$
Elgamal 1985 [25]		$\surd$
Gentry 2009 [30]			$\surd$
GH(Gentry and Halevi)[31] 2011			$\surd$
>Coron 2011 [21]			$\surd$
BGV (Brakerski, Gentry and Vaikuntanathan)2011 [82]			$\surd$
LTV (Lopez-Alt, Tromer and Vaikuntanathan)2012 [57]			$\surd$
JFV(Junfeng Fan, Frederik and Vercauteren) 2012 [27]			$\surd$
GSW (Gentry-Sahai-Waters) 2013 [32]			$\surd$
Gorti's EHC (Enhanced homomorphic Cryptosystem) 2013 [70]			$\surd$

| Show Table

DownLoad: CSV

Table 2. Multi-party Computation Implementations

Scheme	Feature	Party
FairPlay [58]	Boolean Circuits	Two-Party
SPDZ [23]	Arithmetic Circuits	Two-Party
MASCOT [47]	Arithmetic Circuits	Two-Party
Tasty [40]	Boolean & Arithmetic Circuits	Two-Party
Sharemind [14]	Boolean Circuits	Three-Party
FairPlayMP [8]	Boolean Circuits	Two or More
VIFF [22]	Arithmetic Circuits	Two or More

| Show Table

DownLoad: CSV

Table 3. Recent Hot Research Topics that in Privacy-Aware Computing

	Homomorphic Encryption	Secret Sharing/MPC	Zero-knowledge Proof
Electronic Voting	$\surd$	$\surd$	$\surd$
Online Auction	$\surd$	$\surd$	$\surd$
Smart Grid	$\surd$	$\surd$	$\surd$
Gene Testing	$\surd$	$\surd$
Social network	$\surd$	$\surd$	$\surd$
Blockchain	$\surd$	$\surd$	$\surd$

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	Secret sharing, 2018, https://en.wikipedia.org/wiki/Secret_sharing.
[2]	Zero-knowledge proof, 2018, https://en.wikipedia.org/wiki/Zero-knowledge_proof.
[3]	A. Acar, H. Aksu, A. S. Uluagac and M. Conti, A survey on homomorphic encryption schemes: Theory and implementation, ACM Computing Surveys (CSUR), 51 (2018), Article No. 79. doi: 10.1145/3214303.
[4]	A. Alhothaily, A. Alrawais, T. Song, B. Lin and X. Cheng, Quickcash: Secure transfer payment systems, Sensors, 17 (2017), 1376. doi: 10.3390/s17061376.
[5]	A. Alhothaily, C. Hu, A. Alrawais, T. Song, X. Cheng and D. Chen, A secure and practical authentication scheme using personal devices, IEEE Access, 5 (2017), 11677-11687. doi: 10.1109/ACCESS.2017.2717862.
[6]	M. Andrychowicz, S. Dziembowski, D. Malinowski and L. Mazurek, Secure multiparty computations on bitcoin, in Security and Privacy (SP), 2014 IEEE Symposium on, IEEE, 2014, 443-458. doi: 10.1109/SP.2014.35.
[7]	F. Armknecht, C. Boyd, C. Carr, K. Gjøsteen, X. Jäschke, C. A. Reuter and M. Strand, A guide to fully homomorphic encryption, IACR Cryptology ePrint Archive, 2015 (2015), 1192.
[8]	A. Ben-David, N. Nisan and B. Pinkas, Fairplaymp: A system for secure multi-party computation, in Proceedings of the 15th ACM Conference on Computer and Communications Security, ACM, 2008, 257-266. doi: 10.1145/1455770.1455804.
[9]	J. Benaloh, Dense probabilistic encryption, in Proceedings of the Workshop on Selected Areas of Cryptography, 1994, 120-128.
[10]	J. Benaloh and J. Leichter, Generalized secret sharing and monotone functions, in Proceedings on Advances in Cryptology, Springer-Verlag New York, Inc., 403 (1990), 27-35. doi: 10.1007/0-387-34799-2_3.
[11]	M. Bertilsson and I. Ingemarsson, A construction of practical secret sharing schemes using linear block codes, in International Workshop on the Theory and Application of Cryptographic Techniques, Springer, 1992, 67-79. doi: 10.1007/3-540-57220-1_53.
[12]	G. R. Blakley et al., Safeguarding cryptographic keys, in Proceedings of the National Computer Conference, 48 (1979), 313-317.
[13]	M. Blum, P. Feldman and S. Micali, Non-interactive zero-knowledge and its applications, in Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, ACM, 1988, 103-112. doi: 10.1145/62212.62222.
[14]	D. Bogdanov, S. Laur and J. Willemson, Sharemind: A framework for fast privacy-preserving computations, in European Symposium on Research in Computer Security, Springer, 2008, 192-206.
[15]	Z. Brakerski and V. Vaikuntanathan, Fully homomorphic encryption from ring-lwe and security for key dependent messages, in Annual Cryptology Conference, Springer, 2011, 505-524. doi: 10.1007/978-3-642-22792-9_29.
[16]	Z. Brakerski and V. Vaikuntanathan, Efficient fully homomorphic encryption from (standard) lwe, SIAM Journal on Computing, 43 (2014), 831-871. doi: 10.1137/120868669.
[17]	E. F. Brickell, Some ideal secret sharing schemes, in Workshop on the Theory and Application of of Cryptographic Techniques, Springer, 434 (1990), 468-475. doi: 10.1007/3-540-46885-4_45.
[18]	N. Busom, R. Petrlic, F. Sebé, C. Sorge and M. Valls, Efficient smart metering based on homomorphic encryption, Computer Communications, 82 (2016), 95-101. doi: 10.1016/j.comcom.2015.08.016.
[19]	Z. Cai, Z. He, X. Guan and Y. Li, Collective data-sanitization for preventing sensitive information inference attacks in social networks, IEEE Transactions on Dependable and Secure Computing, 15 (2018), 577-590. doi: 10.1109/TDSC.2016.2613521.
[20]	Z. Cai and X. Zheng, A private and efficient mechanism for data uploading in smart cyber-physical systems, IEEE Transactions on Network Science and Engineering, (2018), 1-1. doi: 10.1109/TNSE.2018.2830307.
[21]	J.-S. Coron, D. Naccache and M. Tibouchi, Public key compression and modulus switching for fully homomorphic encryption over the integers, in Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 7237 (2012), 446-464. doi: 10.1007/978-3-642-29011-4_27.
[22]	I. Damgård, M. Geisler, M. Krøigaard and J. B. Nielsen, Asynchronous multiparty computation: Theory and implementation, in International Workshop on Public Key Cryptography, Springer, 5443 (2009), 160-179. doi: 10.1007/978-3-642-00468-1_10.
[23]	I. Damgård, V. Pastro, N. Smart and S. Zakarias, Multiparty computation from somewhat homomorphic encryption, in Advances in Cryptology-CRYPTO 2012, Springer, 7417 (2012), 643-662. doi: 10.1007/978-3-642-32009-5_38.
[24]	I. Damgard and M. Jurik, A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system, in Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptosystems, 2001, 119-136.
[25]	T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Transactions on Information Theory, 31 (1985), 469-472. doi: 10.1109/TIT.1985.1057074.
[26]	B. Ewanick, Zero knowledge proof, Google Scholar.
[27]	J. Fan and F. Vercauteren, Somewhat practical fully homomorphic encryption, IACR Cryptology ePrint Archive, 2012 (2012), 144.
[28]	P. Feldman, A practical scheme for non-interactive verifiable secret sharing, in Foundations of Computer Science, 1987., 28th Annual Symposium on, IEEE, 1987, 427-438. doi: 10.1109/SFCS.1987.4.
[29]	C. Fontaine and F. Galand, A survey of homomorphic encryption for nonspecialists, EURASIP Journal on Information Security, 2007 (2007), 15.
[30]	C. Gentry, Fully homomorphic encryption using ideal lattices, Proceedings of the 41st Annual Acm Symposium on Symposium on Theory of Computing-stoc'09, (2009), 169-178.
[31]	C. Gentry and S. Halevi, Fully homomorphic encryption without squashing using depth-3 arithmetic circuits, in Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, IEEE, 2011, 107-116. doi: 10.1109/FOCS.2011.94.
[32]	C. Gentry, A. Sahai and B. Waters, Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based, in Advances in Cryptology-CRYPTO 2013, Springer, 2013, 75-92. doi: 10.1007/978-3-642-40041-4_5.
[33]	O. Goldreich and Y. Oren, Definitions and properties of zero-knowledge proof systems, Journal of Cryptology, 7 (1994), 1-32. doi: 10.1007/BF00195207.
[34]	S. Goldwasser and S. Micali, Probabilistic encryption and how to play mental poker keeping secret all private information, in Proceedings 14th ACM Symposium on the Theory of Computing, vol. 4, 1982.
[35]	S. Goldwasser, S. Micali and C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, 18 (1989), 186-208. doi: 10.1137/0218012.
[36]	J. Groth, Short pairing-based non-interactive zero-knowledge arguments, in International Conference on the Theory and Application of Cryptology and Information Security, Springer, 2010, 321-340. doi: 10.1007/978-3-642-17373-8_19.
[37]	J. Groth, Efficient zero-knowledge arguments from two-tiered homomorphic commitments, in International Conference on the Theory and Application of Cryptology and Information Security, Springer, 7073 (2011), 431-448. doi: 10.1007/978-3-642-25385-0_23.
[38]	J. Groth, R. Ostrovsky and A. Sahai, Perfect non-interactive zero knowledge for np, in Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 4004 (2006), 339-358. doi: 10.1007/11761679_21.
[39]	Z. He, Z. Cai and J. Yu, Latent-data privacy preserving with customized data utility for social network data, IEEE Transactions on Vehicular Technology, 67 (2018), 665-673. doi: 10.1109/TVT.2017.2738018.
[40]	W. Henecka, A.-R. Sadeghi, T. Schneider, I. Wehrenberg et al., Tasty: Tool for automating secure two-party computations, in Proceedings of the 17th ACM Conference on Computer and Communications Security, ACM, 2010, 451-462. doi: 10.1145/1866307.1866358.
[41]	C. Hu, R. Li, W. Li, J. Yu, Z. Tian and R. Bie, Efficient privacy-preserving schemes for dot-product computation in mobile computing, in Proceedings of the 1st ACM Workshop on Privacy-Aware Mobile Computing, ACM, 2016, 51-59. doi: 10.1145/2940343.2948717.
[42]	C. Hu, R. Li, B. Mei, W. Li, A. Alrawais and R. Bie, Privacy-preserving combinatorial auction without an auctioneer, EURASIP Journal on Wireless Communications and Networking, 2018 (2018), 38. doi: 10.1186/s13638-018-1047-z.
[43]	M. Ito, A. Saito and T. Nishizeki, Secret sharing scheme realizing general access structure, Electronics and Communications in Japan (Part Ⅲ: Fundamental Electronic Science), 72 (1989), 56-63. doi: 10.1002/ecjc.4430720906.
[44]	M. Jakobsson and A. Juels, Addition of el gamal plaintexts, in International Conference on the Theory and Application of Cryptology and Information Security, Springer, 1976 (2000), 346-358. doi: 10.1007/3-540-44448-3_26.
[45]	S. JohnWalker, Big data: A revolution that will transform how we live, work, and think, International Journal of Advertising, The Review of Marketing Communications, 33 (2014), 181-183. doi: 10.2501/IJA-33-1-181-183.
[46]	A. Kawachi, K. Tanaka and K. Xagawa, Multi-bit cryptosystems based on lattice problems, in International Workshop on Public Key Cryptography, Springer, 4450 (2007), 315-329. doi: 10.1007/978-3-540-71677-8_21.
[47]	M. Keller, E. Orsini and P. Scholl, Mascot: faster malicious arithmetic secure computation with oblivious transfer, in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, ACM, 2016, 830-842. doi: 10.1145/2976749.2978357.
[48]	M. Larson, C. Hu, R. Li, W. Li and X. Cheng, Secure auctions without an auctioneer via verifiable secret sharing, in Proceedings of the 2015 Workshop on Privacy-Aware Mobile Computing, ACM, 2015, 1-6. doi: 10.1145/2757302.2757305.
[49]	M. Larson, R. Li, C. Hu, W. Li, X. Cheng and R. Bie, A bidder-oriented privacy-preserving vcg auction scheme, in International Conference on Wireless Algorithms, Systems, and Applications, Springer, 2015, 284-294. doi: 10.1007/978-3-319-21837-3_28.
[50]	R. Li, H. Li, X. Cheng, X. Zhou, K. Li, S. Wang and R. Bie, Perturbation-based private profile matching in social networks, IEEE Access, 5 (2017), 19720-19732. doi: 10.1109/ACCESS.2017.2748958.
[51]	R. Li, B. Mei, C. Hu, W. Li, M. Larson, X. Cheng and R. Bie, A cloud-based framework for verifiable privacy-preserving spectrum auction, suibmitted to "EURASIP Journal on Wireless Communications and Networking".
[52]	R. Li, T. Song, N. Capurso, J. Yu, J. Couture and X. Cheng, Iot applications on secure smart shopping system, IEEE Internet of Things Journal, 4 (2017), 1945-1954. doi: 10.1109/JIOT.2017.2706698.
[53]	R. Li, T. Song, B. Mei, H. Li, X. Cheng and L. Sun, Blockchain for large-scale internet of things data storage and protection, IEEE Transactions on Services Computing, (2018), 1-1. doi: 10.1109/TSC.2018.2853167.
[54]	R. Li, C. Sturtivant, J. Yu and X. Cheng, A novel secure and efficient data aggregation scheme for iot, IEEE Internet of Things Journal, (2018), 1-1. doi: 10.1109/JIOT.2018.2848962.
[55]	W. Li, M. Larson, C. Hu, R. Li, X. Cheng and R. Bie, Secure multi-unit sealed first-price auction mechanisms, Security and Communication Networks, 9 (2016), 3833-3843. doi: 10.1002/sec.1522.
[56]	Y. Liang, Z. Cai, J. Yu, Q. Han and Y. Li, Deep learning based inference of private information using embedded sensors in smart devices, IEEE Network Magazine, 32 (2018), 8-14. doi: 10.1109/MNET.2018.1700349.
[57]	A. López-Alt, E. Tromer and V. Vaikuntanathan, On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption, in Proceedings of the forty-fourth annual ACM symposium on Theory of computing, ACM, 2012, 1219-1234. doi: 10.1145/2213977.2214086.
[58]	D. Malkhi, N. Nisan, B. Pinkas, Y. Sella et al., Fairplay-secure two-party computation system., in USENIX Security Symposium, vol. 4, San Diego, CA, USA, 2004, 9pp.
[59]	B. Mei, Y. Xiao, R. Li, H. Li, X. Cheng and Y. Sun, Image and attribute based convolutional neural network inference attacks in social networks, IEEE Transactions on Network Science and Engineering, (2018), 1-1. doi: 10.1109/TNSE.2018.2797930.
[60]	P. Mell, T. Grance et al., The nist definition of cloud computing, National Institute of Standards and Technology Special Publication 800-145, (2011), 7pp. doi: 10.6028/NIST.SP.800-145.
[61]	C. Moore, M. O'Neill, E. O'Sullivan, Y. Doroz and B. Sunar, Practical homomorphic encryption: A survey, in Circuits and Systems (ISCAS), 2014 IEEE International Symposium on, IEEE, 2014, 2792-2795. doi: 10.1109/ISCAS.2014.6865753.
[62]	D. Naccache and J. Stern, A new public key cryptosystem based on higher residues, in Proceedings of the 5th ACM Conference on Computer and Communications Security, ACM, 1998, 59-66. doi: 10.1145/288090.288106.
[63]	M. Ogburn, C. Turner and P. Dahal, Homomorphic encryption, Procedia Computer Science, 20 (2013), 502-509. doi: 10.1016/j.procs.2013.09.310.
[64]	T. Okamoto and S. Uchiyama, A new public-key cryptosystem as secure as factoring, in International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 1403 (1998), 308-318. doi: 10.1007/BFb0054135.
[65]	P. Paillier, Public-key cryptosystems based on composite degree residuosity classes, in International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 1592 (1999), 223-238. doi: 10.1007/3-540-48910-X_16.
[66]	T. P. Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing, in Annual International Cryptology Conference, Springer, 576 (1992), 129-140. doi: 10.1007/3-540-46766-1_9.
[67]	J.-J. Quisquater, M. Quisquater, M. Quisquater, M. Quisquater, L. Guillou, M. A. Guillou, G. Guillou, A. Guillou, G. Guillou and S. Guillou, How to explain zero-knowledge protocols to your children, in Conference on the Theory and Application of Cryptology, Springer, 1989, 628-631. doi: 10.1007/0-387-34805-0_60.
[68]	T. Rabin and M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, in Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, ACM, 1989, 73-85. doi: 10.1145/73007.73014.
[69]	C. Rackoff and D. R. Simon, Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack, in Annual International Cryptology Conference, Springer, 1991, 433-444. doi: 10.1007/3-540-46766-1_35.
[70]	G. V. S. Rao and G. Uma, An efficient secure message transmission in mobile ad hoc networks using enhanced homomorphic encryption scheme, Global Journal of Computer Science and Technology.
[71]	O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM (JACM), 56 (2009), Art. 34, 40 pp. doi: 10.1145/1568318.1568324.
[72]	R.L. Rivest, L. Adleman and M.L. Dertouzos, On data banks and privacy homomorphisms, Foundations of Secure Computation, 4 (1978), 169-179.
[73]	R.L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, 21 (1978), 120-126. doi: 10.1145/359340.359342.
[74]	C.-P. Schnorr, Efficient signature generation by smart cards, Journal of Cryptology, 4 (1991), 161-174.
[75]	A. Shamir, How to share a secret, Communications of the ACM, 22 (1979), 612-613. doi: 10.1145/359168.359176.
[76]	I. Sharma, Fully homomorphic encryption scheme with symmetric keys, preprint, arXiv: 1310.2452.
[77]	N. P. Smart and F. Vercauteren, Fully homomorphic encryption with relatively small key and ciphertext sizes, in International Workshop on Public Key Cryptography, Springer, 6056 (2010), 420-443. doi: 10.1007/978-3-642-13013-7_25.
[78]	T. Song, R. Li, B. Mei, J. Yu, X. Xing and X. Cheng, A privacy preserving communication protocol for iot applications in smart homes, IEEE Internet of Things Journal, 4 (2017), 1844-1852. doi: 10.1109/IIKI.2016.3.
[79]	M. Stadler, Publicly verifiable secret sharing, in International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 1996, 190-199. doi: 10.1007/3-540-68339-9_17.
[80]	M. Van Dijk, C. Gentry, S. Halevi and V. Vaikuntanathan, Fully homomorphic encryption over the integers, in Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 6110 (2010), 24-43. doi: 10.1007/978-3-642-13190-5_2.
[81]	J. Wang, Z. Cai, Y. Li, D. Yang, J. Li and H. Gao, Protecting query privacy with differentially private k-anonymity in location-based services, Personal and Ubiquitous Computing, 22 (2018), 453-469. doi: 10.1007/s00779-018-1124-7.
[82]	M. Yagisawa, Fully homomorphic encryption without bootstrapping, IACR Cryptology ePrint Archive, 2015 (2015), 474.
[83]	A. C. Yao, Protocols for secure computations, in Foundations of Computer Science, 1982. SFCS'08. 23rd Annual Symposium on, IEEE, 1982, 160-164.
[84]	A. C.-C. Yao, How to generate and exchange secrets, in Foundations of Computer Science, 1986., 27th Annual Symposium on, IEEE, 1986, 162-167. doi: 10.1109/SFCS.1986.25.
[85]	X. Zheng, Z. Cai, J. Li and H. Gao, Location-privacy-aware review publication mechanism for local business service systems, in The 36th Annual IEEE International Conference on Computer Communications (INFOCOM 2017), 2017, 1-9. doi: 10.1109/INFOCOM.2017.8056976.
[86]	X. Zheng, Z. Cai and Y. Li, Data linkage in smart iot systems: A consideration from privacy perspective, IEEE Communications Magazine.
[87]	X. Zheng, Z. Cai, J. Yu, C. Wang and Y. Li, Follow but no track: Privacy preserved profile publishing in cyber-physical social systems, IEEE Internet of Things Journal, 4 (2017), 1868-1878. doi: 10.1109/JIOT.2017.2679483.
[88]	X. Zheng, G. Luo and Z. Cai, A fair mechanism for private data publication in online social networks, IEEE Transactions on Network Science and Engineering, (2018), 1-1. doi: 10.1109/TNSE.2018.2801798.