Scopes of homomorphic encryption
I think many are already familiar with the concept of homomorphic encryption and are aware of the discovery of the first fully homomorphic cryptosystem by Craig Gentry in the year 2009. In recent years, the entire Internet is full of news on this topic, mainly English-language resources. But on Russian-language sites there is still not much information, especially regarding the application of this innovation. In this article I would like to talk about how the use of homomorphic encryption can be useful in various fields.
The idea and history of homomorphism are quite simply and clearly described on the Habré in the following articles: one , two , therefore, we will not dwell on them, but we will immediately get down to business. Let's start with the simplest examples.
Cloud systems - remote storage systems and services that allow the processing of this data. The thing is interesting and quite widespread. Of course, certain cryptographic mechanisms are provided to protect information. However, almost immediately, one drawback of such systems is discovered: to modify remote data, a secret key must be transmitted over the network, i.e. simply disclosing it, which puts security at risk
Imagine the following situation: a certain cloud server contains information about our income, the data from it is periodically processed by the tax service, thus calculating the amount of tax. But to perform the calculations, the service must have access to the decrypted information, which forces us to transmit the secret key to it through communication channels. Wouldn’t it be easier to use tools that allow you to handle encrypted data as well as open? Do such tools exist? The answer is yes, and this is homomorphic encryption.
Cryptography is now widely used in voting systems, excellent examples of which are bitcoins and blind signatures. But in this part of the article, of course, we will discuss how homomorphic encryption can help in the process of collective selection.
Let us have before us the task of choosing, for example, the best article on cryptography on a hub There is a set of candidates from which the list is formed, which is included in the ballot. The voting initiator owns a cryptosystem that has homomorphic properties with respect to, for example, addition operations (suppose that operations of addition and multiplication in clear texts correspond to the same operations in ciphertexts), and distributes the public key along with ballots to voters. So we have:
- a newsletter as a vector (K1 , K 2 , ..., K n )
- public key - OK.
Then, each of the voters makes a preference vector - (P 1 , P 2 , ..., P n ) , where each P i ∈ {0, 1} and then encrypts each element from it and sends a list of encrypted zeros and ones to the voting initiator. The last thing for the vote count is to add up the corresponding elements of the resulting arrays and decrypt. Due to the homogeneity of the initiator's cryptosystem, the index of the maximum element of the resulting vector will be the index of the winning candidate.
This is the simplest voting scheme using homomorphic encryption; of course, its modifications are possible. Attempts to find fault immediately raise questions like: how to ensure the integrity of the transmitted ballots? (the first solution that comes to mind is signing votes). I think you can still find problem areas, but do not dwell on them.
Nevertheless, the described procedure allows you to maintain the confidentiality of the choice of participants, is quite simple and can be used to organize voting on the network, which is a considerable plus.
It so happened that a person needs to work with information: be able to search for it, process it, assimilate it, and solve issues related to storage. Fortunately, today there are many services that simplify life in this regard and help to overcome some difficulties. However, they may not always meet customer requirements. For example, not all search engines currently support private search - i.e. a search in which the search server knows nothing about what requests users send to it. Although such a thing would be very necessary for people who want to maintain the confidentiality of their interests.
The most trivial solution to the above problem would be to transfer all the data from the server to the user. Then the owner of the database does not know exactly what the requestor needs. But what if there is a lot of data? If they still need to be encrypted? Compress? Serious problems arise with time and resources. But here homomorphic encryption comes to the rescue.
For simplicity, let's assume that an n- bit vector x is stored on some server , and the client needs to know the i- th bit, so that its request is confidential. The idea is very simple, like all ingenious. The user sends the server an encrypted binary vector, each bit of which is an encrypted zero (of course, using a homomorphic algorithm), except for ith bit. The server then performs scalar multiplication of the resulting vector by x . The result is transmitted to the client, who simply decrypts the received data and receives a response to his request.
1) DS Maimut, A. Patrascu, E. Simion. Homomorphic encryption schemes and applications for secure digital world // JMEDS - 2012 - No. 4.
2) M. van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan Fully homomorphic encryption over the integers // In Proc. of Eurocrypt, volume 6110 of LNCS - 2010 - 28 p.
The idea and history of homomorphism are quite simply and clearly described on the Habré in the following articles: one , two , therefore, we will not dwell on them, but we will immediately get down to business. Let's start with the simplest examples.
Cloud systems (cloud systems, cloud computing)
Cloud systems - remote storage systems and services that allow the processing of this data. The thing is interesting and quite widespread. Of course, certain cryptographic mechanisms are provided to protect information. However, almost immediately, one drawback of such systems is discovered: to modify remote data, a secret key must be transmitted over the network, i.e. simply disclosing it, which puts security at risk
Imagine the following situation: a certain cloud server contains information about our income, the data from it is periodically processed by the tax service, thus calculating the amount of tax. But to perform the calculations, the service must have access to the decrypted information, which forces us to transmit the secret key to it through communication channels. Wouldn’t it be easier to use tools that allow you to handle encrypted data as well as open? Do such tools exist? The answer is yes, and this is homomorphic encryption.
Electronic voting
Cryptography is now widely used in voting systems, excellent examples of which are bitcoins and blind signatures. But in this part of the article, of course, we will discuss how homomorphic encryption can help in the process of collective selection.
Let us have before us the task of choosing, for example, the best article on cryptography on a hub There is a set of candidates from which the list is formed, which is included in the ballot. The voting initiator owns a cryptosystem that has homomorphic properties with respect to, for example, addition operations (suppose that operations of addition and multiplication in clear texts correspond to the same operations in ciphertexts), and distributes the public key along with ballots to voters. So we have:
- a newsletter as a vector (K1 , K 2 , ..., K n )
- public key - OK.
Then, each of the voters makes a preference vector - (P 1 , P 2 , ..., P n ) , where each P i ∈ {0, 1} and then encrypts each element from it and sends a list of encrypted zeros and ones to the voting initiator. The last thing for the vote count is to add up the corresponding elements of the resulting arrays and decrypt. Due to the homogeneity of the initiator's cryptosystem, the index of the maximum element of the resulting vector will be the index of the winning candidate.
This is the simplest voting scheme using homomorphic encryption; of course, its modifications are possible. Attempts to find fault immediately raise questions like: how to ensure the integrity of the transmitted ballots? (the first solution that comes to mind is signing votes). I think you can still find problem areas, but do not dwell on them.
Nevertheless, the described procedure allows you to maintain the confidentiality of the choice of participants, is quite simple and can be used to organize voting on the network, which is a considerable plus.
Search without disclosure (private information retrieval)
It so happened that a person needs to work with information: be able to search for it, process it, assimilate it, and solve issues related to storage. Fortunately, today there are many services that simplify life in this regard and help to overcome some difficulties. However, they may not always meet customer requirements. For example, not all search engines currently support private search - i.e. a search in which the search server knows nothing about what requests users send to it. Although such a thing would be very necessary for people who want to maintain the confidentiality of their interests.
The most trivial solution to the above problem would be to transfer all the data from the server to the user. Then the owner of the database does not know exactly what the requestor needs. But what if there is a lot of data? If they still need to be encrypted? Compress? Serious problems arise with time and resources. But here homomorphic encryption comes to the rescue.
For simplicity, let's assume that an n- bit vector x is stored on some server , and the client needs to know the i- th bit, so that its request is confidential. The idea is very simple, like all ingenious. The user sends the server an encrypted binary vector, each bit of which is an encrypted zero (of course, using a homomorphic algorithm), except for ith bit. The server then performs scalar multiplication of the resulting vector by x . The result is transmitted to the client, who simply decrypts the received data and receives a response to his request.
Sources
1) DS Maimut, A. Patrascu, E. Simion. Homomorphic encryption schemes and applications for secure digital world // JMEDS - 2012 - No. 4.
2) M. van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan Fully homomorphic encryption over the integers // In Proc. of Eurocrypt, volume 6110 of LNCS - 2010 - 28 p.