In modern public-key cryptography, new constructions are usually supported by formal security proofs. Such a formal proof consists of reductions (in the complexity theory sense) which tie the security of a cryptosystem to the hardness of an intractable problem, and show that if an adversary can efficiently break the security of a cryptosystem then we can use this adversary to solve a well-understood intractable problem efficiently.
The tightness of the relation between the security of a scheme and the hardness of the problem influences directly the key length of the scheme and thus its efficiency. Moreover, the tighter the relation is, the stronger security guarantee a scheme gives. As a result of that, constructing schemes with tight reductions constitutes an important research direction in cryptography.
More precisely, the tightness of a security reduction is measured by comparing the success probability and running time of a reduction to those of an adversary. We say a reduction is tight if its success probability and running time are about the same as those of the adversary.
The main guiding questions in this area are whether we can improve the tightness of the existing non-tight schemes or whether we can prove that the existing reductions for these non-tight schemes are already optimal. If the existing non-tight reductions are optimal, we then attempt to construct novel efficient schemes with tight reductions. In this talk, I will outline the current state of the art and I will consider digital signature schemes as an example to illustrate an interesting technique for constructing tightly secure public-key schemes. At the end of the talk, I will conclude with some interesting open problems.