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 (M...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2023
|
| Subjects: | |
| Online Access: | http://psasir.upm.edu.my/id/eprint/118266/ http://psasir.upm.edu.my/id/eprint/118266/1/118266%20IR.pdf |
| _version_ | 1848867753240297472 |
|---|---|
| author | Abdul Jamal, Nurul Amiera Sakinah |
| author_facet | Abdul Jamal, Nurul Amiera Sakinah |
| author_sort | Abdul Jamal, Nurul Amiera Sakinah |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-15T14:41:30Z |
| format | Thesis |
| id | upm-118266 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T14:41:30Z |
| publishDate | 2023 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-1182662025-08-04T04:14:48Z http://psasir.upm.edu.my/id/eprint/118266/ New directions in forging multivariate signature schemes Abdul Jamal, Nurul Amiera Sakinah 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. 2023-08 Thesis NonPeerReviewed text en http://psasir.upm.edu.my/id/eprint/118266/1/118266%20IR.pdf Abdul Jamal, Nurul Amiera Sakinah (2023) New directions in forging multivariate signature schemes. Masters thesis, Universiti Putra Malaysia. http://ethesis.upm.edu.my/id/eprint/18369 Quantum computers Post-quantum cryptography Public key cryptography |
| spellingShingle | Quantum computers Post-quantum cryptography Public key cryptography Abdul Jamal, Nurul Amiera Sakinah New directions in forging multivariate signature schemes |
| title | New directions in forging multivariate signature schemes |
| title_full | New directions in forging multivariate signature schemes |
| title_fullStr | New directions in forging multivariate signature schemes |
| title_full_unstemmed | New directions in forging multivariate signature schemes |
| title_short | New directions in forging multivariate signature schemes |
| title_sort | new directions in forging multivariate signature schemes |
| topic | Quantum computers Post-quantum cryptography Public key cryptography |
| url | http://psasir.upm.edu.my/id/eprint/118266/ http://psasir.upm.edu.my/id/eprint/118266/ http://psasir.upm.edu.my/id/eprint/118266/1/118266%20IR.pdf |