Volume 30, January 2014, Pages 91–97

Towards provably secure proxy signature scheme based on Isomorphisms of Polynomials ^☆

• Shaohua Tang^, , ,  

Lingling Xu 

DOI: 10.1016/j.future.2013.06.003

------------------------------------------------------------------------------------------------------

Highlights

1) We propose a proxy signature scheme based on IP (Isomorphism of Polynomials) problem.
2) An attractive advantage is to potentially resist attacks of quantum computers.
3) Our scheme is proven strictly to be secure through a formal security proof.
4) This is a valuable attempt to explore the provable security in the area of MPKC.
5) Our scheme is implemented in C/C++ and the performance shows that it is efficient.

------------------------------------------------------------------------------------------------------

Abstract

Proxy signatures are important cryptosystems that are widely adopted in different applications. Most of the proxy signature schemes so far are based on the hardness of integer factoring, discrete logarithm, and/or elliptic curve. However, Peter Shor proved that the emerging quantum computers can solve the problem of prime factorization and discrete logarithm in polynomial time, which threatens the security of current RSA, ElGamal, ECC, and the proxy signature schemes based on these problems. We propose a proxy signature scheme based on the problem of Isomorphism of Polynomials (IP) which belongs to a major category of Multivariate Public Key Cryptography (MPKC). The most attractive advantage of our scheme should be its feature to potentially resist the future quantum computing attacks. A formal security proof is also given, which shows that our scheme can reach Existential Unforgeability under an Adaptive Chosen Message Attack with Proxy Key Exposure   assuming that the underlying IP signature is Existential Unforgeability under an Adaptive Chosen Message Attack  . It is a valuable attempt to explore the provable security in the area of MPKCs. The scheme is implemented in C/C++ programming language, and the performance shows that the scheme is efficient. The parameters we choose can let the security level of our implementation up to 2^86.59.

------------------------------------------------------------------------------------------------------

Paper publish online:  http://www.sciencedirect.com/science/article/pii/S0167739X13001179 

Access via DOI: http://dx.doi.org/10.1016/j.future.2013.06.003    

Download PDF file of this paper:  http://www.sciencedirect.com/science/article/pii/S0167739X13001179/pdfft?md5=0f3e31d3b3b5c5566096edaffaf74b15&pid=1-s2.0-S0167739X13001179-main.pdf 

------------------------------------------------------------------------------------------------------