A Brief Overview of Privacy-Preserving Software Methods
A very brief overview of privacy-preserving technologies follows for anyone who’s interested in starting out in this area. I cover symmetric encryption, asymmetric encryption, homomorphic encryption, differential privacy, and secure multi-party computation.
Symmetric Encryption
What is it? An alternative nomenclature for symmetric encryption is private key encryption, which means that both encryption and decryption are performed using the same key that is kept hidden from everyone but the parties that want to communicate securely. This includes block ciphers (e.g., AES-GCM) and some stream ciphers (e.g., one-time pads), among others.
What is a practical application? File sharing (e.g., over the HTTPS protocol) and hard drive encryption.
Pro. Symmetric schemes allow for faster encryption and decryption than asymmetric ones, which will be discussed in the next section. Symmetric schemes are also mathematically simpler.
Con. The encryption/decryption key has to be exchanged over a secure channel; i.e., a communication channel where the message being sent cannot be read or tampered with
Some seminal papers
Schneier, Bruce. “Description of a new variable-length key, 64-bit block cipher (Blowfish).” International Workshop on Fast Software Encryption. Springer, Berlin, Heidelberg, 1993.
Schneier, Bruce, et al. “Twofish: A 128-bit block cipher.” NIST AES Proposal 15 (1998): 23.
Standard, NIST-FIPS. “Announcing the advanced encryption standard (AES).” Federal Information Processing Standards Publication 197 (2001): 1–51.
Software
https://github.com/bcgit/
https://github.com/weidai11/cryptopp
https://dev.gnupg.org/source/libgcrypt/
https://github.com/openssl/openssl
https://www.wolfssl.com/products/wolfcrypt/
Asymmetric Encryption
What is it? Asymmetric encryption is also referred to as public key encryption, which includes the RSA cryptosystem and ElGamal, among others. These schemes require a private key to decrypt but, unlike symmetric schemes, the encryption key is public. Crucially, asymmetric encryption schemes enable two parties to securely exchange the necessary keys (e.g., for future communication secured using symmetric encryption) without worrying about the level of security of the exchange channel [1].
What is a practical application? Asymmetric and symmetric schemes are commonly combined to provide the best of both worlds. A sender may encrypt a secret key for a symmetric cipher using a receiver’s public key, then send the encrypted key to the receiver, who in turn decrypts it. Encrypted communication can then be more efficient, since both the sender and receiver now have the key to the same symmetric cipher [1].
Pro. Removes the need for communication over a secure channel.
Con. Slow.
Some seminal papers
Diffie, Whitfield, and Martin Hellman. “New directions in cryptography.” IEEEtransactions on Information Theory 22.6 (1976): 644–654.
ElGamal, Taher. “A public key cryptosystem and a signature scheme based on discrete logarithms.” IEEE transactions on information theory 31.4 (1985): 469–472.
Koblitz, Neal. “Elliptic curve cryptosystems.” Mathematics of computation 48.177 (1987): 203–209.
Miller, Victor S. “Use of elliptic curves in cryptography.” Conference on the theory and application of cryptographic techniques. Springer, Berlin, Heidelberg, 1985.
Rivest, Ronald L., Adi Shamir, and Leonard Adleman. “A method for obtaining digital signatures and public-key cryptosystems.” Communications of the ACM 21.2 (1978): 120–126.
Software
https://github.com/bcgit/
https://github.com/weidai11/cryptopp
https://dev.gnupg.org/source/libgcrypt/
https://github.com/openssl/openssl
https://www.wolfssl.com/products/wolfcrypt/
Homomorphic Encryption
What is it? The concept of homomorphic encryption is said to be invented by Rivest et al. (1978) [2]. Using homomorphic encryption schemes, a user is able to encrypt data then send the data to an untrusted server that performs computations on the encrypted data. The server then returns the result of those computations to the user. Finally, the user decrypts the result. This scheme allows one, for example, to encrypt the numbers 2 [i.e., e(2)] and 3 [i.e., e(3)] and perform e(2) + e(3), decrypt the result, and get 5. Certain schemes can only perform addition, others only multiplication, and others still both multiplication and addition. Notably, the Paillier cryptosystem can only perform addition and is thus said to be additively homomorphic. One can perform only multiplication using RSA, for instance, making it multiplicatively homomorphic. Lattice-based encryption schemes are a favourite, since they are additively and multiplicaticatively homomorphic, as well as quantum-safe.
What is a practical application? This technology is fairly new for commercial applications. In practice, it has been used in the financial and healthcare sectors.
Pro. Homomorphic encryption allows for double-blind computations. That is, a server is blind to a user’s data and the user is blind to the intricacies of the server’s algorithms.
Con. Non-linear operations must rely on user-server communication, where the data to be computed on is sent to the user with some noise added to it. The user then performs the computation and sends it back to the server. Examples of such operations would be logarithms, sines, cosines, etc. Generally, a huge benefit of homomorphic encryption is its low communication costs between the user(s) wishing to perform a computation and the server performing it. Requiring user-server communication for operations which are otherwise trivial to perform limits the practicality of HE.
Some seminal papers
Brakerski, Zvika, and Vinod Vaikuntanathan. “Efficient fully homomorphic encryption from (standard) LWE.” SIAM Journal on Computing 43.2 (2014): 831–871.
Gentry, Craig. A fully homomorphic encryption scheme. Stanford University, 2009.
Paillier, Pascal. “Public-key cryptosystems based on composite degree residuosity classes.” International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1999.
Van Dijk, Marten, et al. “Fully homomorphic encryption over the integers.” Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2010.
Software
https://github.com/shaih/HElib
https://git.njit.edu/palisade/PALISADE
https://github.com/iamtrask/PySEAL
https://github.com/tfhe/tfhe
Differential Privacy
What is it? Differential privacy allows one to learn general information about a population within a database or within aggregated datasets without learning anything about a specific individual. A common example of a useful task for differential privacy is using a database to determine whether smoking causes cancer [3]. In that situation, one is discovering a general fact about a population (i.e., smokers) without requiring any individually identifiable details.
What is a practical application? Apple uses differential privacy to improve QuickType predictions, as well as some of their recommendations to users. Briefly, only a certain portion of a user’s true actions are sent to Apple to train their models. It is impossible for Apple to distinguish between a user’s true action and a randomized action. However, the majority of information they receive is accurate and therefore improves predictions [4].
Pro. The risk of identifying a single anonymized person in a dataset can be accurately quantified as a function of the parameters used. This is mathematically provable.
Con. Loss of data precision. The more deidentified or noisy that a dataset is, the less useful it becomes. This is definitely not the right solution if one needs exact answers to very specific queries (e.g., how many people in a certain dataset have cancer).
Some seminal papers
Dwork, Cynthia. “Differential privacy: A survey of results.” International Conference on Theory and Applications of Models of Computation. Springer, Berlin, Heidelberg, 2008.
Dwork, Cynthia, and Aaron Roth. “The algorithmic foundations of differential privacy.” Foundations and Trends® in Theoretical Computer Science 9.3–4 (2014): 211–407.
Software
https://beta.dataverse.org/custom/DifferentialPrivacyPrototype/
https://github.com/uber/sql-differential-privacy
https://github.com/brubinstein/diffpriv
Secure Multi-Party Computation
What is it? This is used when multiple parties have a portion of data necessary for computing the result of a function, but do not want to reveal their data to any of the other parties. Garbled circuits, or circuits which hide all information going through them except for the final output, are used for MPC.
What is a practical application? Deriving genomic diagnoses without revealing patient genomes [5].
Pro. Very low computational cost.
Con. Little research done on performing comparison (<, >, ==, !=) within MPC protocols [6].
Some seminal papers
Beaver, Donald, Silvio Micali, and Phillip Rogaway. “The round complexity of secure protocols.” Proceedings of the twenty-second annual ACM symposium on Theory of computing. ACM, 1990.
Ben-David, Assaf, Noam Nisan, and Benny Pinkas. “FairplayMP: a system for secure multi-party computation.” Proceedings of the 15th ACM conference on Computer and communications security. ACM, 2008.
Ben-Or, Michael, Shafi Goldwasser, and Avi Wigderson. “Completeness theorems for non-cryptographic fault-tolerant distributed computation.” Proceedings of the twentieth annual ACM symposium on Theory of computing. ACM, 1988.
Chaum, David, Claude Crépeau, and Ivan Damgard. “Multiparty unconditionally secure protocols.” Proceedings of the twentieth annual ACM symposium on Theory of computing. ACM, 1988.
Goldreich, Oded, Silvio Micali, and Avi Wigderson. “How to play any mental game.” Proceedings of the nineteenth annual ACM symposium on Theory of computing. ACM, 1987.
Software
https://github.com/bristolcrypto/SPDZ-2
https://github.com/rdragos/awesome-mpc
https://github.com/cryptobiu/libscapi
For a more complete list: http://www.multipartycomputation.com/mpc-software
Other notable software
https://github.com/OpenMined
https://github.com/nucypher
Acknowledgements
Thank you to Dr. Siavash Kazemian, Kelly Langlais, Michael Chiu, and Simon Emond for their feedback on this post and to Dr. Parinaz Sobhani for telling me about Apple’s great use case of differential privacy.
References
[1] Fontaine, Caroline, and Fabien Galand. “A survey of homomorphic encryption for nonspecialists.” EURASIP Journal on Information Security 2007 (2007): 15.
[2] Rivest, Ronald L., Len Adleman, and Michael L. Dertouzos. “On data banks and privacy homomorphisms.” Foundations of secure computation 4.11 (1978): 169–180.
[3] Dwork, Cynthia. “Differential privacy: A survey of results.” International Conference on Theory and Applications of Models of Computation. Springer, Berlin, Heidelberg, 2008.
[4] https://www.engadget.com/2016/06/14/apple-differential-privacy/
[5] http://science.sciencemag.org/content/357/6352/692
[6] Laud, Peeter, and Liina Kamm, eds. Applications of Secure Multiparty Computation. Vol. 13. Ios Press, 2015.
