ABSTRACT
This chapter provides an overview of reduction algorithms that shows people how an attack on the crypto systems by a polynomial-time adversary can be employed to solve some underlying hard computational problem in polynomial time. The importance of tight reduction is explained in the next section. There are several obstacles in achieving the tight reduction that involves an all-and-any strategy, in which the reduction algorithm must be able to answer private key queries for all identities as the challenge identity. Because the security proof for a crypto system is given by describing a reduction algorithm, it is important to research the reduction algorithms in cryptography. People instantiate the case of an identity-based encryption (IBE) system as one of the crypto systems. Typically, security proofs for IBE systems are given by describing a reduction algorithm. The existence of such a reduction algorithm shows that if some underlying problem is assumed to be difficult to solve, the IBE system is secure.
