Signatures with Tight Adaptive Corruptions from Search Assumptions

In this paper, we show that tightly secure signature schemes in the multi-user setting with adaptive corruptions can be achieved from various weak assumptions, such as classical discrete logarithm, RSA, factoring, and even the post-quantum group action discrete logarithm assumption, at the cost of signature length. To this end, we introduce a new framework to construct a signature scheme. Our construction is a combination of an identification scheme with multiple secret keys per public key (with additional specific features) and (randomized) Fischlin transformation. From the straight-line extractability of the transformation, intuitively unforgeability can be tightly reduced to the soundness of an identification scheme in the programmable random oracle model (PROM). Our careful security proof succeeds in a tight reduction in the non-programmable random oracle model (NPROM).As a complementary study, we analyze the multi-user security of hash-based signatures. Although hash-based signatures seem to be tightly secure in the multi-user setting with adaptive corruptions (at the cost of signature lengths similar to our construction), their security has not been closely analyzed. We show the tight security based on collision resistance of the underlying hash function by modeling the pseudo-random function for key generation as a (programmable) random oracle. By using a hash function whose security is tightly reduced to other assumptions, such as the discrete logarithm problem, we also obtain a tightly secure signature based on them. However, the concrete signature size is larger than our proposal based on an identification scheme, and the security reduction is in the PROM in contrast to our new framework.