How to realize secret computation without knowing the secret value?

2020-12-08 12:28:55 Ontology

In the last issue, we introduced what is “ secure multi-party computation ”： It is an important area of data privacy protection, which was introduced by Mr. Yao Qizhi, a Turing prize winner, through the millionaire problem .

This is from the Internet

Yao's million question can be expressed as ：Alice and Bob It's two millionaires , They want to know who is richer , But they don't want to reveal any information about their wealth to each other . In this case , Both sides don't want to reveal their true information , Compare the wealth of two people , And give credible proof .

We from

1.1 Security model （ Malicious adversary model ）

1.2 Circuit selection （ Boolean circuits and arithmetic circuits ）

Two aspects are introduced . This issue will focus on the calculation process .

2. The calculation process

In the case of arithmetic circuit model and malicious adversary model , Secure multiparty computation can be reduced to the following problem ： Suppose and have two secret values respectively （ be called secret）, How to make the participants without knowing （ except I know , know ） Work out the sum ？

1. First of all, we should let all the participants get the relevant information , That is, how to disclose part of the information to the participants . Secret sharing （Secret Sharing） The solution is an important way to solve this problem . Consider from the characteristics of arithmetic circuits , Linear secret sharing is a good way to think about it . One of the simplest ways , namely , Random selection , bring , And let the corresponding participants grasp , Each is called a participant about share. This process can be implemented as follows ： Every random selection , And tell , Set up . It can be noted that , This random selection process can be completed in advance by preprocessing before calculation , In the calculation process, as long as the random number selected in advance can be told to the data owner .

2. Suppose each participant has secretly owned and , And satisfy and . here , We need to consider how to add and multiply .

- For addition , Yes . therefore , It's very simple for addition , Each participant can add their secret values together , namely

And the result .

- Multiplication is a little more complicated .. In order to ensure safety , This will involve public key cryptography . therefore , The amount of calculation in this step is relatively large .

Using the idea of randomization to establish a preprocessing process can reduce the amount of calculation . Suppose there are random values that satisfy , Design and , that Well . therefore , Think of sum as a constant , If each participant grasps satisfaction , and , Then each participant only needs to do a simple linear calculation

And the result .

What you can see is , The value of is selected randomly , It has nothing to do with , It can be established in advance by preprocessing . therefore , The question becomes how to randomize the participants Of , And meet the conditions .

In every known case , Each can compute and broadcast locally and . When participants receive all and , Add to get the sum .

2.1 The guarantee of correct calculation

In the process of operation , There's an important question to consider , How to know that the participants have calculated correctly , That is, how to ensure that the correct values are calculated and published .

This is from the Internet

Because secrets are shared linearly , Message authentication code using linear structure （Message Authentication Code,MAC） Certification is the right choice . Through 1 and 2 Calculation method of , You can see ,MAC It is also required to provide a calculation method in accordance with these two formulas , That is the two one. MAC Value addition ,MAC Value multiplication constant ,MAC Value plus constant .

This is from the Internet

An effective way to reduce the amount of data is to use global MAC programme , Using the same key pair secret Conduct authentication . without doubt , This violates the one-time Principles of use , Linearly constructed MAC Will no longer be safe . A common way to solve this problem is to construct -time Of MAC. Another consideration is to disperse authentication key and authentication code , After the calculation , Combine the key and authentication code to verify .

Because of the dispersion of authentication codes and keys ,MAC Can be simplified to . At the same time, we need to satisfy MAC The calculation of additive constants requires , The final MAC structure by , Where is a constant （ Take zero ）. The key can be defined as , Where is the random number selected by the participants . therefore , Also need to be certified . The authentication is achieved by holding the key , To authenticate . meanwhile , The certification results also need to be decentralized , The process of dispersion is similar to that of share The dispersion of .

To be continued ......

▿ Click on the past to read the original

The source and reprint of the original text are detailed in the text , If there is any infringement , Please contact the yunjia_community@tencent.com Delete .

Original publication time ： 2020-11-24

Participation of this paper Tencent cloud media sharing plan , You are welcome to join us , share .

https://chowdera.com/2020/12/20201208122832798x.html