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.