Trap-door one-way permutation

This idea is trap-door one-way permutations, i.e., permutations that are no longer one-way if one knows some secret trap-door information. More precisely, one should speak of trap-door onc-y/ay families of permutations. Such a family is defined as follows There are three algorithms, called gen,f, and/". A participant can use gen to generate a pair (sk, pk) of a secret and a public key for the family of permutations. Everyone who knows the public key can compute a certain permutation, f(pk, ), from the family, whereas only the secret key enables its owner to compute the inverse of this permutation. 

A third important question is if the signature scheme can be broken without breaking the trap-door one-way permutations. However, this question only came up later see Section 2.5. 

Existential forgery is even possible with a key-only attack in all signature schemes built from trap-door one-way permutations as described in Section 2.4 The attacker chooses a value and calls it a signature, computes the permutation with the pubhc key, and calls the result a message. 

By the way, the situation with the ElGamal scheme is similar to that with RSA, although that scheme is not directly constructed from trap-door one-way permutations Existential forgery is possible with a key-only attack. However, no method for selective forgery with an active attack is known. 

A trap-door one-way family of permutations was proposed in [RiSA78]. It was called RSA later. The essential part of the secret key is two large primes... 

Usually, the secrecy and signature schemes constructed from this trap-door one-way family of permutations are also called RSA. However, there are several variants of those, as will be seen in Section 2.5. This can lead to confusion. 

A recent technique is to show that at least the general principle of such a combined construction is sound by proving that the construction would be secure if the chaotic element were replaced by a random oracle [BeRo93]. Soundness in this sense was shown for the combination of trap-door one-way families of permutations and hash functions. 

Subsequently, one tried to find constructions on possibly weaker abstract assumptions. In [BeMiSS, BeMi92], the assumption is the existence of a trap-door one-way family of permutations. This assumption was used for the efficient construction in [DiHe76] (see Section 2.4) however, a much more complicated construction was needed to avoid the problems mentioned in Section 2.5. It has a lot in common with one-time signatures and tree authentication. The constructions could be extended to arbitrary one-way permutations, i.e., not necessarily with trapdoors, in [NaYu89]. In a sense, this is not too surprising because no trap-doors were needed in the informal constructions of one-time signatures md tree authentication (see Section 2.4) either. Finally, the result was extended to any oneway function [Romp90]. The main problem in the last two cases was to construct appropriate hash functions. 

---