Confidential Computation Protocol

In cryptography, the protocol of confidential computing (also secure, secure or secret multi-party computing) is a cryptographic protocol that allows several participants to perform a calculation depending on the secret input data of each of them, so that no participant was able to get any information about other people's secret input. The problem of confidential computing was first raised by Andrew Yao in 1982 in an article ^[1] . Two millionaires, Alice and Bob, want to find out which of them is richer, while they do not want to divulge the exact amount of their wealth. Yao proposed in his article an original way to solve this problem, later called the problem of millionaires. Much later, in 2004, Yehuda Lindell and Benny Pinkas provided a mathematically rigorous proof of the correctness of the Yao protocol in ^[2] . The task of confidential computing is closely related to the task of sharing the secret .

Content

Formalized statement of the problem

The confidential calculation involves N participants p ₁ , p ₂ , ..., p _N. Each participant has a secret input d ₁ , d ₂ , ..., d _N, respectively. Participants want to find the value of F (d ₁ , d ₂ , ..., d _N ) , where F is a computable function of N arguments known to all participants. It is assumed that among the participants there will be semi-honest violators , that is, those who faithfully follow the protocol, but try to obtain additional information from any intermediate data.

Security Requirements

The security of confidential computing protocols is usually subject to different requirements. Here are the basic requirements.

Confidentiality. None of the participants should be able to obtain more information than prescribed.
Correctness. Each participant must be guaranteed to receive the correct data.
Guaranteed information. Participants should not have the opportunity to prevent other participants from receiving output.

An example of solving the problem of millionaires

Let millionaires Alice and Bob want to find out whose condition is greater without disclosing the exact amount of their fortunes. For definiteness, suppose Alice has i million, and Bob has j , where 1 <i and j <10 . First, Alice and Bob will need a reliable public-key cryptosystem , for example, RSA ^[3] . Let E _a be an arbitrary encryption function for a key a , and D _a be a private key decryption function for public key a . Let a be Alice’s public key. Then the protocol looks like this:

Bob picks a random integer x from N bits and confidentially considers k = E _a (x) ;
Bob sends Alice the number k-j + 1 ;
Alice confidentially considers the values y _u = D _a (k-j + u) for u = 1,2, ..., 10 ;
Alice selects a random prime number p from N / 2 bits so that the numbers z _u = y _u mod (p) differ by at least 2 modulo p for all u and sends the number p to Bob;
Alice sends the numbers z ₁ , z ₂ , ..., z _i followed by the numbers z _{i + 1} +1, ..., z ₁₀ +1 ; numbers are taken modulo p;
Bob, who knows how much money he has ( j ), compares the number with number j with the number x selected in the first step, and if they are equal, then Bob concludes that i ⩾ j , and i <j in otherwise;
Bob reports the result to Alice.

It can be seen that the protocol allows you to uniquely determine whose state is greater, and at the same time, participants cannot recognize each other's state.

Implementations

There are two different approaches to protocol implementation. The first approach is usually based on sharing the secret and works on representing the calculated function as an arithmetic circuit ( English arithmetic circuit ), as, for example, in the BGW protocols (Ben-Or, Goldwasser and Wigderson) ^[4] and CCD (Chaum, Crepeau and Damgard) ^[5] . This approach is usually applied when it is known that most participants are honest (which is possible only if the number of participants is more than two). Another approach represents a function in the form of a logical circuit . This approach was used by Andrew Yao to construct a distorted circuit ( English garbled circuit ) ^[6] , as well as in the GMW protocol (Goldreich, Micali and Wigderson) ^[7] .

The arithmetic contour method is better suited for performing addition and multiplication operations (where participants have fractions of a secret, and you can recreate the secret only if you receive information from each of the participants), but it is not suitable for performing comparison operations. This approach has achieved great success in the SIMAP project ^[8] .

The logical loop method performs addition and multiplication operations with less efficiency, but can easily perform binary operations, such as comparisons. This second approach, on which the Andrew Yao system is based for the case of two participants, was implemented by Malkhi in the fair play system ^[9] . This system also provides the opportunity to implement the necessary functionality, represented by a high-level programming language in the form of a logical circuit, which is then interpreted by the runtime and safely executed. There is also a FairplayMP system ^[10] , which is an extension of Fairplay for more than two participants. A significant advantage of systems based on the logical circuit method is that they are performed for a constant number of information exchanges, while the advantage of systems based on the arithmetic circuit method is the ability to perform arithmetic operations very quickly (addition and multiplication).

Protocol Example

For simplicity, suppose that two participants participate in the calculation, that is, N = 2 , and the participants need to calculate the function F.

We represent the function F in the form of a logical circuit , that is, we represent the input data of the function F in binary form, and we implement the function using the operations AND, OR and NOT. Then the bits of all the arguments of the function F are fed to the input of the logical circuit, and the circuit itself consists of the logical gates AND, OR, and NOT, and at the output it gives the result of the function F in binary format.
Member p ₁ generates for each wire of the logic circuit two different random numbers k ⁰ u k ¹ . The numbers represent the encrypted zero and one in this wire, respectively.
Member p ₁ creates an encrypted calculation table for each circuit. For a binary OR gate, such a table would look like this:

Input wire w ₁	Input wire w ₂	Output wire w ₃	Encrypted Calculation Table
$k_{1}^{0}$ ${\ displaystyle k_ {1} ^ {0}}$	$k_{2}^{0}$ ${\ displaystyle k_ {2} ^ {0}}$	$k_{3}^{0}$ ${\ displaystyle k_ {3} ^ {0}}$	$c_{1}=E_{k_{1}^{0}}(E_{k_{2}^{0}}(k_{3}^{0}))$ ${\ displaystyle c_ {1} = E_ {k_ {1} ^ {0}} (E_ {k_ {2} ^ {0}} (k_ {3} ^ {0})}}$
$k_{1}^{0}$ ${\ displaystyle k_ {1} ^ {0}}$	$k_{2}^{1}$ ${\ displaystyle k_ {2} ^ {1}}$	$k_{3}^{1}$ ${\ displaystyle k_ {3} ^ {1}}$	$c_{2}=E_{k_{1}^{0}}(E_{k_{2}^{1}}(k_{3}^{1}))$ ${\ displaystyle c_ {2} = E_ {k_ {1} ^ {0}} (E_ {k_ {2} ^ {1}} (k_ {3} ^ {1})}}$
$k_{1}^{1}$ ${\ displaystyle k_ {1} ^ {1}}$	$k_{2}^{0}$ ${\ displaystyle k_ {2} ^ {0}}$	$k_{3}^{1}$ ${\ displaystyle k_ {3} ^ {1}}$	$c_{3}=E_{k_{1}^{1}}(E_{k_{2}^{0}}(k_{3}^{1}))$ ${\ displaystyle c_ {3} = E_ {k_ {1} ^ {1}} (E_ {k_ {2} ^ {0}} (k_ {3} ^ {1})}}$
$k_{1}^{1}$ ${\ displaystyle k_ {1} ^ {1}}$	$k_{2}^{1}$ ${\ displaystyle k_ {2} ^ {1}}$	$k_{3}^{1}$ ${\ displaystyle k_ {3} ^ {1}}$	$c_{4}=E_{k_{1}^{1}}(E_{k_{2}^{1}}(k_{3}^{1}))$ ${\ displaystyle c_ {4} = E_ {k_ {1} ^ {1}} (E_ {k_ {2} ^ {1}} (k_ {3} ^ {1})}}$

Here $E_{k}(x)$ ${\ displaystyle E_ {k} (x)}$ means the result of encrypting the value of x with the key k , and $D_{k}(y)$ ${\ displaystyle D_ {k} (y)}$ - respectively, the decryption of the ciphertext y with the key k . You should choose a symmetric encryption scheme that has one additional property: when you try to decrypt text with the wrong key, the algorithm returns an error.

The meaning of this table is as follows: if we know the encrypted values of the signal k ₁ u k ₂ on the input wires of the valve w ₁ u w _2, respectively, then we can calculate the encrypted signal value by calculating the value for all i = 1 ... 4 $d_{i}=D_{k_{2}}(D_{k_{1}}(c_{i}))$ ${\ displaystyle d_ {i} = D_ {k_ {2}} (D_ {k_ {1}} (c_ {i}))}$ . In three cases out of four, an error should occur, and in the remaining fourth we get the encrypted value k _{3 of the} signal at the output of the valve.

Member p ₁ transfers the logic circuit and encrypted calculation tables for all loops to participant p ₂ .
Participant p ₁ passes to participant p _{2 the} encrypted values of the input wire signals for those inputs that correspond to the input of participant p ₁ .
For each input wire w _i corresponding to the input data p ₂ , participant p ₁ passes the number p ₂ to the participant p ₂ using the forgetful protocol $k_{i}^{b_{i}}$ ${\ displaystyle k_ {i} ^ {b_ {i}}}$ where b _i is the value of the bit of secret input data of the participant p ₂ . With this transfer, participant p ₁ does not recognize the value of b _i . Since for each wire its random numbers were previously randomly selected, which are zero and one, the participant p ₂ will not be able to find out which number is zero and which is the unit for the input wires of the participant p ₁ , and therefore will not be able to recognize the input participant data p ₁ .
Now the participant p ₂ has an encrypted logic circuit and encrypted values of all input wires. It calculates in encrypted form (as described above) all the gates of the circuit one after another and then transfers the encrypted result to participant p ₁ .
Participant p ₁ decrypts the result and reports it to participant p ₂ .

Protocols Used

An important component of a confidential computing protocol can be forgetful transmission .
The protocol of virtual participants is a protocol that hides the identity of participants ^[11] .
Secure amount protocols allow collaborating participants to calculate some functions of their individual information without divulging this information to each other ^[12] .

Practical Application

Electronic voting . For example, each participant can vote for or against, then the result of voting of n participants will be the function F (x ₁ , ..., x _n ) , where x _i can take the values 0 (against) and 1 (for).
Electronic auctions. Each participant offers a price x _i , and the function F (x ₁ , ..., x _n ) returns the maximum number x _i .
Statistics. Suppose students want to know the best or average grade without showing grades to each other.
Databases For example, let a user want to fulfill a query to a database and get a response without opening a query. The owner of the server with the database wants that when requesting, no information other than the response to the request does not reach the user. In this case, both the user and the server will be participants in the protocol of confidential computing.
Distributed Certificate Authority . Suppose you need to create a certification authority that will issue certificates to users by signing them with some secret key. To protect the key, the key can be divided between several servers so that each server stores its own part of the key. Then a problem arises: how to perform a cryptographic operation (in this example, issuing a signature) without transferring all parts of the key to one computer. This problem is solved using a confidential computing protocol, where the input to the confidential computing function is the key parts and the message to be signed, and the output is the signed message.

Notes

↑ Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982: 160-164
↑ Yehuda Lindell, Benny Pinkas: A Proof of Yao's Protocol for Secure Two-Party Computation, Cryptology ePrint Archive, Report 2004/175
↑ Solution to the Millionaire's Problem Archived on May 19, 2008.
↑ M. Ben-Or, S. Goldwasser and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In 20th STOC, 1-10, 1988.
↑ P. Bogetoft, DL Christensen, I. Damgard, M. Geisler, T. Jakobsen, M. Kroigaard, JD Nielsen, JB Nielsen, K. Nielsen, J. Pagter, M. Schwartzbach and T. Toft. Secure multiparty computation goes life. In Financial Cryptography and Data Security - FC 2009
↑ A. Yao. How to generate and exchange secrets. In 27th FOCS, 162-167, 1986.
↑ Goldreich, S. Micali and A. Wigderson. How to play any mental game - A completeness theorem for protocols with honest majority. In 19th STOC, 218-229, 1987.
↑ P. Bogetoft, I. Damgard, T. Jakobsen, K. Nielsen, J. Pagter. and T. Toft. A practical implementation of secure auctions based on multiparty integer computation. In Financial Cryptography and Data Security - FC 2006, Springer-Verlag LNCS 4107, 142-147, 2006.
↑ D. Malkhi, N. Nisan, B. Pinkas and Y. Sella. Fairplay - a secure two-party computation system. In Proc. of 13th USENIX Security Symposium, 2004.
↑ A. Ben-David, N. Nisan and B. Pinkas. FairplayMP: a system for secure multi-party computation. In Computer and Communications Security - CCS 2008, ACM, 257-266, 2008.
↑ Pathak Rohit, Joshi Satyadhar, Advances in Information Security and Assurance, Springer Berlin / Heidelberg, ISSN 0302-9743 (Print) 1611-3349 (Online), ISBN 978-3-642-02616-4 , DOI 10.1007 / 978-3 -642-02617-1
↑ Rashid Sheikh, Brijesh Kumar and Durgesh Kumar Mishra, Privacy Preserving k-secure sum protocols, International Journal of Computer Science and Information Security, ISSN 1947-5500 (Online), Vol.6, No.2, Nov. 2009

[1] Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982: 160-164

[2] Yehuda Lindell, Benny Pinkas: A Proof of Yao's Protocol for Secure Two-Party Computation, Cryptology ePrint Archive, Report 2004/175

[3] Solution to the Millionaire's Problem Archived on May 19, 2008.

[4] M. Ben-Or, S. Goldwasser and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In 20th STOC, 1-10, 1988.

[5] P. Bogetoft, DL Christensen, I. Damgard, M. Geisler, T. Jakobsen, M. Kroigaard, JD Nielsen, JB Nielsen, K. Nielsen, J. Pagter, M. Schwartzbach and T. Toft. Secure multiparty computation goes life. In Financial Cryptography and Data Security - FC 2009

[6] A. Yao. How to generate and exchange secrets. In 27th FOCS, 162-167, 1986.

[7] Goldreich, S. Micali and A. Wigderson. How to play any mental game - A completeness theorem for protocols with honest majority. In 19th STOC, 218-229, 1987.

[8] P. Bogetoft, I. Damgard, T. Jakobsen, K. Nielsen, J. Pagter. and T. Toft. A practical implementation of secure auctions based on multiparty integer computation. In Financial Cryptography and Data Security - FC 2006, Springer-Verlag LNCS 4107, 142-147, 2006.

[9] D. Malkhi, N. Nisan, B. Pinkas and Y. Sella. Fairplay - a secure two-party computation system. In Proc. of 13th USENIX Security Symposium, 2004.

[10] A. Ben-David, N. Nisan and B. Pinkas. FairplayMP: a system for secure multi-party computation. In Computer and Communications Security - CCS 2008, ACM, 257-266, 2008.

[11] Pathak Rohit, Joshi Satyadhar, Advances in Information Security and Assurance, Springer Berlin / Heidelberg, ISSN 0302-9743 (Print) 1611-3349 (Online), ISBN 978-3-642-02616-4 , DOI 10.1007 / 978-3 -642-02617-1

[12] Rashid Sheikh, Brijesh Kumar and Durgesh Kumar Mishra, Privacy Preserving k-secure sum protocols, International Journal of Computer Science and Information Security, ISSN 1947-5500 (Online), Vol.6, No.2, Nov. 2009