Tightly Secure Public-Key Cryptographic Schemes from One-More Assumptions

A tightly secure cryptographic scheme refers to a construction with a tight security reduction to a hardness assumption, where the reduction loss is a small constant. A scheme with tight security is preferred in practice since it could be implemented using a smaller parameter to improve efficiency. Recently, Bader et al. (EUROCRYPT 2016) have proposed a comprehensive study on the impossible tight security reductions for certain (e.g., key-unique) public-key cryptographic schemes in the multi-user with adaptive corruptions (MU-C) setting built upon non-interactive assumptions. The assumptions of one-more version, such as one-more computational Diffie-Hellman (n-CDH), are variants of the standard assumptions and have found various applications. However, whether it is possible to have tightly secure key-unique schemes from the one-more assumptions or the impossible tight reduction results also hold for these assumptions remains unknown. In this paper, we give affirmative answers to the above question, i.e., we can have efficient key-unique public-key cryptographic schemes with tight security built upon the one-more assumptions. Specifically, we propose a digital signature scheme and an encryption scheme, both of which are key-unique and have tight MU-C security under the one-more computational Diffie-Hellman (n-CDH) assumption. Our results also reflect from another aspect that there indeed exists a gap between the standard assumptions and their one-more version counterparts.