1997-HashCash invented by adamback (an example of work certificate system)

200 1- Ron Rivest, adi shamir and Yale Tauman put forward ring signature to the encryption world.

2004-Patrick P. Tsang and Victor K. proposed to use ring signature system for voting and electronic cash;

2008-Satoshi Nakamoto publishes a white paper on Bitcoin.

20 1 1 year-Anonymity Analysis in Bitcoin System, by Fegor Reid and Martin Harrigan.

20 12- destination address bitcoin anonymous (one-time address in CryptoNote).

Secure multi-party computing originated from the millionaire problem in Yao Qizhi in 1982. Later, Oder Godrich had a detailed and systematic discussion.

Yao's millionaire problem was first put forward by Professor China, a Turing Prize winner. The question is expressed as follows: two millionaires, Alice and Bob, want to know which of them is richer, but neither of them wants to let the other know any information about their wealth. This question has some practical applications: suppose Alice wants to buy some goods from Bob, but the maximum amount she is willing to pay is X yuan; Bob wants the lowest price to be y yuan. Alice and Bob are eager to know which is bigger, X or Y. Y, they can all start bargaining; If z

This scheme is used to compare two numbers to determine which number is larger. Alice knows an integer I; Bob knows an integer J. Alice and B0b want to know I >: =j or j> me, but they don't want each other to know their numbers. For simplicity, it is assumed that the values of j and i are in the range of [1, 100. Bob has a public key Eb and a private key Db.

The research of secure multi-party computing is mainly aimed at how to calculate the appointment function safely without a trusted third party. Secure multiparty computing plays an important role in electronic election, electronic voting, electronic auction, secret sharing and threshold signature.

Homomorphic encryption is an open question put forward by cryptographers a long time ago. As early as 1978, Ron Rivest, Leonard Adleman and Michael L. Dertouzos put forward this concept with the application background of banks [RAD78]. Yes, you are not mistaken. Ron Rivest and Leonard Adleman are R and A respectively in the famous RSA algorithm.

What is homomorphic encryption? Craig Gentry was the first person to construct a complete homomorphic encryption [Gen09], and he gave the best intuitive definition: a method of entrusting data processing without revealing access to data.

What does this mean? General encryption schemes pay attention to the security of data storage. That is, I want to send encrypted things to others, or I want to save things on a computer or other server. I want to encrypt data before sending or storing it. Users without keys cannot get any information about the original data from the encrypted results. Only the user with the key can correctly decrypt and obtain the original content. We noticed that in this process, users can't do anything with the encrypted results, but only store and transmit them. Any operation on the encrypted result will lead to incorrect decryption, or even decryption failure.

The most interesting thing about homomorphic encryption scheme is that it pays attention to the security of data processing. Homomorphic encryption provides the function of processing encrypted data. In other words, others can process the encrypted data, but the process will not reveal any original content. At the same time, after the user who owns the key decrypts the processed data, what he gets is the processed result.

A little abstract? Let's give an example from real life. A user named Alice bought a big piece of gold, and she wanted the workers to make it into a necklace. But workers may steal gold during the construction process. After all, even a gram of gold is worth a lot of money ... So, is there a way for workers to entrust processing your data, but if they don't give up access, they won't get any bonus? Of course there is a way. Alice can do this: Alice locks the gold in a closed box with a glove in it. Workers can wear these gloves to handle the gold in the box. But the box is locked, so workers can't get not only the gold nuggets, but also any gold dropped during processing. After the processing is completed. Alice got the box back, opened the lock and got the gold.

The corresponding relationship is: box: the lock on the encryption algorithm box: the user key puts the gold nugget in the box and locks it with the lock: the data is encrypted by homomorphic encryption scheme: the encrypted result is directly processed and unlocked when the data cannot be obtained by applying homomorphic characteristics; the result is decrypted and the processed result is directly obtained. Where can homomorphic encryption be used? I thought the concept of cloud computing was put forward only in recent years. Homomorphic encryption is almost tailor-made for cloud computing! Let's consider the following scenario: a user wants to process a data, but his computer computing ability is weak. This user can use the concept of cloud computing, and let the cloud handle it for him and get the result. But if the data is directly handed over to the cloud, the security is not guaranteed! So, he can use homomorphic encryption, and then let the cloud directly process the encrypted data and return the processing results to him. In this way, the user pays the cloud service provider to get the processing result; Cloud service providers earn fees and correctly process data without knowing user data;

Aggregation signature was put forward by Boneh et al. It mainly improves the efficiency of signature and verification by aggregating multiple signatures into one signature. In order to sign the data of multiple users, aggregate signature can greatly reduce the computational complexity of signature. CL is a collection signature.

There are two participants in the zero-knowledge proof process, one is the prover and the other is the verifier. The witness holds a secret. He wants the verifier to believe that he holds the secret, but he doesn't want to reveal it to the verifier.

According to an agreement, through a series of interactions, the verifier will finally come to a clear conclusion, whether the prover knows the secret or not.

Take Bitcoin as an example. Whether the transfer transaction is legal only needs to prove three things:

The money sent belongs to the person who sent the transaction.

The amount sent by the sender is equal to the amount received by the receiver.

The sender's money was indeed destroyed.

In the whole process of giving evidence, miners don't really care about how much money they spend, who is the sender and who is the recipient. Miners only care about whether the money in the system is conserved.

Zcash realized the privacy transaction with this idea.

The correspondence of three properties of zero knowledge proof;

(1) completeness. If the prover and the verifier are honest and follow every step of the proof process and make correct calculations, then the proof must be successful and the verifier must be able to accept the prover.

(2) Rationality. No one can impersonate the certifying party to prove it successfully.

(3) zero knowledge. After the proof process is completed, the verifier only gets the information that "the prover owns this knowledge", but does not get any information about the knowledge itself.

There are only ring members, no managers, and no cooperation among ring members. The signer can use his own private key and the public keys of other members of the collection to sign independently without the help of others, and other members of the collection may not know that they are included.

Ring signature can be used as a way to reveal secrets. For example, ring signatures can be used to provide anonymous signatures from "senior White House officials" without revealing which official signed the message. Ring signature is suitable for this application, because the anonymity of ring signature is irrevocable, and the group used for ring signature can be created temporarily.

1) key generation. Generate a key pair (public key PKi, private key SKi) for each member in the ring.

2) signature. The signer uses his own private key and the public keys of any n ring members to generate a signature A for message M.

3) Signature verification. According to the ring signature and message m, the signer verifies whether the signature is signed by the members in the ring. If it is valid, it is received; If it is invalid, it is discarded.

General process of group signature

Blind digital signature (hereinafter referred to as blind signature) is a way of digital signature. The message content is invisible to the signer until it is signed. In 1982, David Chom first proposed the concept of blind signature. Blind signature has been widely used in e-commerce and e-election because it is blind and can effectively protect the specific content of the signed message.

Example of analogy: to sign a document is to put carbon paper in an envelope. When the signer signs the envelope, his signature will be signed on the document through carbon paper.

The so-called blind signature is to put the hidden document into the envelope first, and the process of removing the blind factor is to open the envelope. When the document is in an envelope, no one can understand it. Signing a document means putting carbon paper in an envelope. When the signer signs the envelope, his signature will be signed on the document through carbon paper.

Generally speaking, a good blind signature should have the following properties:

Unforgettable. No one can generate a valid blind signature in his own name except the signer himself. This is a basic attribute.

There is no denying it. Once the signer signs the message, he can't deny his signature.

Although the blind signer signed the message, he could not get the specific content of the message.

It's untraceable Once the signature of a message is made public, the signer cannot be sure when he signed it.

Blind signatures satisfying the above properties are considered to be secure. These four properties are not only the standards we should follow in designing blind signatures, but also the basis for judging the performance of blind signatures.

In addition, the operability and efficiency of the scheme are also very important when designing blind signatures.

Factors. The operability and implementation speed of blind signature depend on the following aspects:

1, the length of the key;

2. The length of blind signature;

3. Blind signature algorithm and verification algorithm.

Specific steps of blind signature

1, the receiver first performs blind transformation on the data to be signed, and sends the transformed blind data to the signatory.

2. Signed by the signer and sent to the recipient.

3. The blind signature of the signer on the original data is obtained by the blind transformation of the signature by the receiver.

4, thus satisfying the condition 1. To satisfy the condition ②, the signer must not be associated with the blind data when he sees the blind signature afterwards, which is usually realized by some protocol.