Find the ideal Trapdoor Permutation

Content

Trapdoor Permutation Trapdoor Permutation first appeared in the thesis "Theory and Application of Trapdoor Functions" [Yao82] by Mr. Yao Qizhi, and it is an important foundation of public key cryptography. In the FLS transformation given in the previous section, an idealized Trapdoor Permutation is required. The so-called idealization means that each n-bit string can uniquely become another n-bit string and will not appear "Many-to-one" mapping relationship. Alice needs to randomly sample an Index and send it to Bob, and then Bob can check whether the F() corresponding to this Index is a "perfect" replacement. The question is, how can Bob check it out in polynomial time? If Bob cannot check, then Alice can sample an imperfect Permutation (such as a "many-to-one" function), which may cheat and destroy the "Soundness" property. Bellare and Yung's 1996 paper first noticed This, but it does not completely solve this problem [BY96].

How to find a bridge that can appropriately abstract Trapdoor Permutation and connect to the implementation of cryptographic tools is an extremely challenging task. Subsequently, various cryptographers (including Oded Goldreich) studied this area for a long time and published many papers. Various types of Trapdoor Permutation were defined and studied, but they were still unsatisfactory. Until recently (2018), Ran Canetti and Amit Lichtenberg proposed a new type of Certifiable Injective Trapdoor Function [RL18], and proved that this kind of Trapdoor Permutation can finally meet the FLS transformation requirements. But is this the end of the story? Theoretical cryptographers are not expected to stop exploring.

In addition to FLS transformation based on Trapdoor Permutation, there are various solutions to upgrade Hidden Bits Model, such as Invariant Signature [BG90], or Verifiable Random Generator [DN00] to achieve Hidden Bits transformation, or weakly verifiable random Function [BGRV09], there is also a scheme called publicly-verifiable trapdoor predicates [CHK03].

Over the past 30 years, there have been many NIZK schemes invented by cryptographers, but the Hidden Bits method is the only known method. (1) Shared CRS based on "consistent distribution", (2) NIZK Proofs in any NP language (Not Arguments!).