Security proof of identity-based signature under RSA assumption, reconsidered
Shogo Kimura, Kazuki Yoneyama · International Symposium on Information Theory and its Applications · 2016
No direct security proof of Shamir's identity-based signature (Shamir-IBS) is known, as far as we know. In EU-ROCRYPT2004, Bellare et al. introduce a generic conversion to IBS from standard identification, and the security of the Shamir-IBS is indirectly proved from the RSA assumption with the conversion. However, in the indirect security proof, the gap between advantages of the RSA problem and the scheme may be larger than proving the security directly from the RSA assumption. In this paper, we give a direct security proof of the Shamir-IBS. We show a comparison between reduction costs of the indirect and direct security proofs. As a result, in a practical parameter setting, the direct proof is better than the indirect proof. By improving the reduction cost, the parameter size which is required to achieve the same bit-security is reduced.