Improvements And Security Analysis For Several Multivariate Cryptography Schemes

Nowadays,most of the public key cryptography schemes are based on the integer factor problem,discrete logarithm problem or discrete logarithm on elliptic curve.In 1993,Shor pro-posed some polynomial time algorithms to solve integer factor problem and discrete logarithm on quantum computers,which poses a serious threat to the popular public key cryptography.After that,Post-Quantum-Cryptography,which is secure against attacks by quantum computer,became a very important research area.Multivariate Public Key Cryptography(MPKC)is one of the most promising candidates in Post-Quantum-Cryptography.Over the past three decades,MPKC has undergone a rapid development,and many en-cryption and signature schemes have been proposed.The public key of the multivariable public key cryptography generally consists of some nonlinear multivariable polynomials over finite field.The encryption and verification process only requires exultations of those polynomials,which is extremely fast.Therefore,MPKC is very suitable for resource-limited environment.At present,there is no effective quantum algorithm can harm the security of multivariable public key cryptography,so the multivariable public key cryptography is a research direction with high value.However,MPKC currently has some problems need to be solved.The key size of MPKC is always too large for many applications,decryption and signing process of MPKC are much s-lower compared with encryption and verification process of MPKC,the security of MPKC is not well understood,and there is no practical MPKC scheme suitable for wireless sensor networks.In this paper,I first focus on the first two problem.I propose Circulant UOV and Circulant Rainbow with faster signing process and smaller private key size,and then I propose Circulant SRP with faster decryption process and smaller private key size.Then I carefully analyze the security of those schemes and give overall comparisons with their corresponding schemes.At last,I propose an online/offline UOV signature scheme,which is suitable for wireless sensors network.In chapter 3,I propose a new UOV variant with faster signing process and smaller private key size.I introduce some rotating relations into small parts of UOV central map.Those rotating relations will result in a circulant matrix during the signing process.This will improve the signature generation speed while reducing the private key size.In terms of security,I analyze the impact of rotating relations in UOV central map and analyze its security against various attacks on UOV.In terms of performance,I give the formula of full rank probability of a random circulant matrix over finite field,and compare the performance of our new UOV variant with regular UOV.I prove the efficiency claims from theoretical and experimental aspects.In chapter 4,I first analyze the security of a few Rainbow variant with sparse private key and revise their security parameters.Then I propose a new Rainbow variant with faster signing process and smaller private key size.It can be viewed as an extension of our new UOV variant.I introduce rotating relations,which will result in a circulant matrix during the signing process,into small parts of Rainbow central map.In terms of security,I analyze the impact of rotating relations in Rainbow central map and analyze its security against various attacks on Rainbow.In terms of performance,I combine the theoretical analysis and experimental comparison to demonstrate the efficiency of our new Rainbow variant.In chapter 5,I propose a new SPR variant with faster decryption algorithm and smaller private key size.At first,I analyze the reason for the existence of redundant Oil-Vinegar poly-nomials in SRP,then I propose a new way to reduce them.This can help us to improve the speed of encryption and decryption as well as reduce the key size of SRP.After that,I insert some rotating relations in small parts of SRP central map.These rotating relations will help us to get a circulant matrix rather than normal matrix during the decryption process,thus to further improve decryption speed while reducing the private key size.I analyze the security of our new SRP variant against rank attack,differential attack and linear attack.In order to demonstrate the efficiency claims,I compare our new SRP variant with other encryption schemes through experiments.In chapter 6,I propose an online/offline UOV signature for wireless sensor network.It combines energy harvesting technology with precomputation technique to reduce run-time la-tency and energy consumption of wireless sensor node.The security of this scheme is equivalent to Circulant UOV and the performance is confirmed by both simulation and practical experi-ments.