Areas of application 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 (Fully homomorphic cryptosystem) by Craig Gentry in the 2009th year. In recent years, the entire Internet is full of news on this topic, mostly English-speaking resources. And on the Russian-language sites there is still not much information, especially regarding the application of this innovation. In this article I would like to tell how the use of homomorphic encryption can be useful in various areas.
The idea and history of homomorphism is quite simply and clearly described in the following articles in Habré: one , two , therefore we will not dwell on them here, but get right to the point. Let's start with the simplest examples.
Cloud systems are remote data 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 detected: to modify remote data, a private 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, data from it are periodically processed by the tax service, thus calculating the amount of tax. But in order to perform the calculations, the service must have access to the decrypted information, which forces us to transfer the secret key to it via communication channels. Wouldn't it be easier to use tools that allow you to operate with encrypted data as well as open data? Are there such tools? The answer is yes, and this is homomorphic encryption.
')
Cryptography has now found wide application 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 carrying out the procedure of collective choice.
Let us before us is the task of choosing, for example, the best article on cryptography on Habré. There is a set of candidates from which the list is formed, which is included in the newsletter. The initiator of the voting owns a cryptosystem that has homomorphic properties with respect to, for example, the addition operation (suppose that the addition and multiplication operations on open text correspond to the same operations on ciphertexts), and distributes the public key to voters along with the ballots. So, we have:
- bulletin as a vector (K 1 , K 2 , ..., K n )
- public key - OK
Then each of the voters makes up a vector of preferences - (P 1 , P 2 , ..., P n ) , where each P i ∈ {0, 1} , then encrypts each element from it and sends a list of encrypted zeros and units to the voting initiator . The last one for the counting of votes is only to add up the corresponding elements of the received arrays and perform the decoding. By virtue of the initiator cryptosystem homomorphism, the index of the maximum element of the resultant vector is the index of the winning candidate.
This is the simplest voting scheme using homomorphic encryption, its modifications are possible, of course. Attempts to cavil immediately give rise to questions like: how to ensure the integrity of the transmitted bulletins? (the first solution to this problem that comes to mind is the signing of votes). I think you can still find problem areas, but do not dwell on them.
However, the described procedure allows you to maintain the confidentiality of the choice of participants, is quite simple and can be used to organize a vote 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, deal with 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. Search, in which the search server does not know anything about what requests are sent to it by users. Although such a thing would be very useful for people who want to keep their interests confidential.
The most trivial solution to the above problem would be to transfer all data from the server to the user. Then the owner of the database will not know exactly what the requester needs. But what if there is a lot of data? If they still need to encrypt? Compress? There are serious problems 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 brilliant. The user sends to the server an encrypted binary vector, each bit of which is an encrypted zero (of course, using a homomorphic algorithm), except for the i -th bit. The server then performs a scalar multiplication of the resulting vector by x . The result is transmitted to the client, who simply decrypts the incoming data and receives an answer to his request.
1) DS Maimut, A. Patrascu, E. Simion. Homomorphic encryption schemes for the secure digital world // JMEDS - 2012 - №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 is quite simply and clearly described in the following articles in Habré: one , two , therefore we will not dwell on them here, but get right to the point. Let's start with the simplest examples.
Cloud systems (cloud systems)
Cloud systems are remote data 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 detected: to modify remote data, a private 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, data from it are periodically processed by the tax service, thus calculating the amount of tax. But in order to perform the calculations, the service must have access to the decrypted information, which forces us to transfer the secret key to it via communication channels. Wouldn't it be easier to use tools that allow you to operate with encrypted data as well as open data? Are there such tools? The answer is yes, and this is homomorphic encryption.
')
Electronic voting
Cryptography has now found wide application 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 carrying out the procedure of collective choice.
Let us before us is the task of choosing, for example, the best article on cryptography on Habré. There is a set of candidates from which the list is formed, which is included in the newsletter. The initiator of the voting owns a cryptosystem that has homomorphic properties with respect to, for example, the addition operation (suppose that the addition and multiplication operations on open text correspond to the same operations on ciphertexts), and distributes the public key to voters along with the ballots. So, we have:
- bulletin as a vector (K 1 , K 2 , ..., K n )
- public key - OK
Then each of the voters makes up a vector of preferences - (P 1 , P 2 , ..., P n ) , where each P i ∈ {0, 1} , then encrypts each element from it and sends a list of encrypted zeros and units to the voting initiator . The last one for the counting of votes is only to add up the corresponding elements of the received arrays and perform the decoding. By virtue of the initiator cryptosystem homomorphism, the index of the maximum element of the resultant vector is the index of the winning candidate.
This is the simplest voting scheme using homomorphic encryption, its modifications are possible, of course. Attempts to cavil immediately give rise to questions like: how to ensure the integrity of the transmitted bulletins? (the first solution to this problem that comes to mind is the signing of votes). I think you can still find problem areas, but do not dwell on them.
However, the described procedure allows you to maintain the confidentiality of the choice of participants, is quite simple and can be used to organize a vote 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, deal with 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. Search, in which the search server does not know anything about what requests are sent to it by users. Although such a thing would be very useful for people who want to keep their interests confidential.
The most trivial solution to the above problem would be to transfer all data from the server to the user. Then the owner of the database will not know exactly what the requester needs. But what if there is a lot of data? If they still need to encrypt? Compress? There are serious problems 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 brilliant. The user sends to the server an encrypted binary vector, each bit of which is an encrypted zero (of course, using a homomorphic algorithm), except for the i -th bit. The server then performs a scalar multiplication of the resulting vector by x . The result is transmitted to the client, who simply decrypts the incoming data and receives an answer to his request.
Sources
1) DS Maimut, A. Patrascu, E. Simion. Homomorphic encryption schemes for the secure digital world // JMEDS - 2012 - №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.
Source: https://habr.com/ru/post/230645/
All Articles