FLS transformation: from Hidden Bits to NIZK

Content

Next, we upgrade the protocol again to remove the hidden features in the "hidden bit string" and turn it into a "common reference string" CRS. Here we need to use a cryptographic tool-Trapdoor Permutation, trapdoor replacement.

The so-called trapdoor permutation refers to a permutation function F(x), x is an element in a set S, and then the function F(x) maps x to another element y in S. At the same time, F(x) satisfies unidirectionality, that is, it is difficult to inversely calculate x through y; but if anyone has the trapdoor t, the reverse calculation F^(-1)(t,y)=x can be realized. Trapdoor permutation can also match a Hardcore Predicate, h(x)=0/1, which can generate a uniformly distributed 0/1 bit based on the elements in the S set. After the introduction, are you a little dizzy? It doesn't matter, you will get used to it. In a word, trapdoor permutation can convert between common reference string and Hidden Bits.

Let's assume that there is such a cryptographic tool, and then we upgrade the protocol.

We regard the public reference string as a list, y1, y2, y3, …, yn, each item in the list is an element in the set S. Then, each bit in Hidden Bits is generated by Hardcore Predicate. But please note that here you cannot directly generate Hidden Bits through h(y)=b, because then Bob can calculate all Hidden Bits by himself, which violates the agreement in the previous section. In order to ensure the hiding of Bob, we need to use the original image of the public reference string, that is, x1, x2, x3, …, xn to generate Hidden Bits, h(x)=b. Although Bob can’t calculate b1, b2, b3, …, bn by himself, once he gets an x, he can check F(x)?=y to determine whether x corresponds to the public reference string, and then calculate h(x) =b Get the Hidden Bits that are revealed, b.

We can use a less accurate but more intuitive way to understand that Alice is equivalent to generating a pair of public and private keys by herself. Then Alice regards the public reference string as a piece of "ciphertext". Since Alice has a private key, she can decrypt the ciphertext and get the plaintext. These plaintexts are equivalent to Hidden Bits for Bob. When Alice wants to "reveal" Hidden Bits, she will show the corresponding plaintext fragment and bring the public key. Then Bob can use the public key to "encrypt" the plaintext again and compare it with the ciphertext of the public reference string to ensure that Alice does not Cheating during the reveal process.