New directions in forging multivariate signature schemes

Quantum computer is a revolution in the realm of cryptography, as it can break conventional cryptographic hard problems such as RSA and DLP. Transitioning to post-quantum cryptography requires new hard problems that resist to quantum computer attacks, such as the multivariate quadratic problem (MQP). MQP is a hard problem in multivariate cryptography, where one needs to find a solution to a system of multivariate quadratic equations. This thesis focuses on attacking MQP under four distinct cases. In these scenarios, the rogue certificate authority (RCA) intervenes during the key generation of multivariate public key cryptosystems (MPKC). The first case considers polynomials in MQP can be expressed as multiples of other polynomials within the same system. By inheriting these characteristics, MQP can be resolved by finding a solution to only one polynomial from MQP system of equations. The second case considers polynomials in MQP can be expressed as additions of two other polynomials within the same system. The second case of MQP is solvable by finding a solution to any two polynomials within the same MQP system of equations. The first and second cases are vulnerable to forgery due to the potential for RCA to generate weak public keys with characteristics inherited from both cases. Therefore, two strategies to identify the generated weak public key by RCA are laid out for the users. The assumption in the third case is, after generating the public-private key pair the RCA computes one solution vector, prior handing over the key pair to the owner. An adversary who receives the solution vector can produce a valid forged signature for any message. The fourth case assumes that the public key system is constructed from slightly modified secret keys based on quadratic factorisation formula. By substituting one designated value for the first variable, one can solve the whole public key system. This forgery mechanism allows an adversary to produce many forged signatures for any message. To identify the forged signatures of the third and fourth cases is still an open question. The forgery mechanisms that are based on the four cases are executed on two significant multivariate signature schemes, namely UOV and Rainbow. We show that UOV signature scheme is vulnerable in all four cases since the form of secret central map is easy to satisfy. Whereas Rainbow signature scheme is safe from forgery in the first, second and fourth cases. It is only vulnerable to the third case as the forgery strategy does not involve any amendment on either the public key or the private key.

Text 118266 IR.pdf Download (1MB) Official URL or Download Paper: http://ethesis.upm.edu.my/id/eprint/18369

Actions (login required)

View Item