Digital Signatures In The Standard Model:Constructions And Applications

In the area of information security,digital signature can provide services like identity authentication,protection of data integrity,nonrepudiation and anonymity,etc.Thus digital signature has become an important research topic in cryptography.The standard security notion of digital signature is unforgeability under adaptive chosen message attacks(cma security).The security proof generally proceeds by demonstrating a security reduction,i.e.,reducing the cma security to the hardness of some well-known problems.However,most of existing signature schemes and the corresponding security proofs in the standard model have the following features:·Loose security reduction.In most security proofs of signature schemes,the security loss factor will be at least qS,which is the maximal number of signing queries made by an adversary.As a consequence,to achieve a desired target security level,one has to increase the security parameter of the construction to compensate for the loose reduction,and this will lead to longer length of keys and signatures,thus increasing the running time of schemes.Therefore,a loose security reduction will bring about a dramatic impact on the efficiency of schemes.If the security loss factor is only constant or linear in the security parameter,then the security reduction is called an(almost)tight one.Therefore,it is meaningful and valuable to research on the construction of signature schemes with tight security.·Only security in single-user setting is considered.Generally,the cma security only considers the single-user setting,where the adversary obtains one verification key,and needs to output forgery with regard to this verification key.However,in the real life,signature schemes are usually deployed with many users,where the adversary could actually obtain many verification keys.By hybrid arguments,we can always reduce the cma security to cma security in the multi-user setting,but the security reduction will be more loose,i.e.,an extra factor n will be introduced in the the security loss factor,where n denotes the number of users.Therefore,it has more practical significance to consider the unforgeability under adaptive chosen message attacks in the multi-user setting(m-cma security)for signature schemes.·Lack of security against quantum attacks.With the development of quantum technology,large-scale quantum computers might be widely used in the near future.In an era of quantum,adversaries will be equipped with powerful quantum computing capability,and many traditional cryptographic primitives will collapse,since the number-theoretic problems,like the integer factorization or the discrete logarithm problems,can be easily solved by Shor's algorithm.In this way,how to construct signature schemes based on hardness problems that are immune to quantum attacks,like the LWE problem,the subset sum problem,etc.,has become an important research direction.Based on the above problems,this paper lucubrates tightly secure signature schemes in the multi-user setting and proposes two generic constructions of signature schemes.By instantiating these generic constructions,we obtain signature schemes from the DCR,matrix DDH assumptions,and quantum-secure signature schemes from the LWE as-sumption and the subset sum problems.These schemes are all tightly secure in the multi-user setting and the standard model.Moreover,we make in-depth research of sig-nature schemes with special properties,for example,the constructions of identity-based signature schemes and the application of linearly homomorphic signature schemes.Our contributions are as follows.·In the standard model,we propose the first generic construction of tightly secure signature in the multi-user setting.First,we exploit how to construct tightly secure signature schemes based on the DCR assumption.Then we extend this scheme to obtain the first generic construction of tightly secure signature in the multi-user setting and standard model,the security is based on the hardness of subset membership problem(SMP).By instantiating SMP with the DCR and Matrix DDH problems,we obtain tightly secure signature schemes based on the DCR and Matrix DDH assumptions,respectively.·Based on the LWE assumption,we construct tightly secure signature schemes in the multi-user setting and against quantum attacks.We first construct a new generic construction of tightly secure signature schemes in the multi-user setting and standard model,whose central building block is a partial one-time signature(POS)scheme with weak security and imperfect correctness.We give two instantiations of POS:one is based on the Ring-LWE assumption,the other one is based on the subset sum problem.By applying the POS from the Ring-LWE assumption,we obtain the first tightly secure signature scheme from the LWE assumption in the multi-user setting and in the standard model.By applying the POS from the subset sum assumption,we obtain the first almost tightly secure signature scheme from the subset sum problem in the multi-user setting and in the standard model.·We propose several tightly secure identity-based signature schemes.Bellare et al.proposed the the generic construction of identity-based signature schemes from the standard signature schemes.We apply our tightly m-cma secure signature schemes to the generic construction based on the DCR assumption,the matrix DDH assumption,the Ring-LWE assumption and the subset sum assumption.Then we obtain tightly(weak)secure identity-based signature schemes based on the DCR assumption,the matrix DDH assumption,the Ring-LWE assumption and the subset sum assumption,respectively.·We make use of the linearly homomorphic signatures in Proof of Retriev-ability(PoR),and propose the first generic construction of publicly verifiable dynamic PoR scheme which is secure in the standard model.We present a generic construction of publicly verifiable dynamic PoR from linearly homomor-phic signature scheme,whose Authenticity and Retrievability are both proved in the standard model.With an instantiation of a linearly homomorphic signature scheme proposed by Kiltz and Wee,we derive a publicly verifiable dynamic PoR scheme based on the matrix DDH assumption in the standard model.We further extend our PoR to support encoding-outsourcing,which further reduces the local computational cost of clients.