Quantum-Resistant Cryptography via Universal Gröbner Bases
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911205755453440 |
|---|---|
| author | Da Silva, Sergio Stewart, Aniya |
| author_facet | Da Silva, Sergio Stewart, Aniya |
| contents | In this article, we explore the use of universal Gröbner bases in public-key cryptography by proposing a key establishment protocol that is resistant to quantum attacks. By utilizing a universal Gröbner basis $\mathcal{U}_I$ of a polynomial ideal $I$ as a private key, this protocol leverages the computational disparity between generating the universal Gröbner basis needed for decryption compared with the single Gröbner basis used for encryption. The security of the system lies in the difficulty of directly computing the Gröbner fan of $I$ required to construct $\mathcal{U}_I$. We provide an analysis of the security of the protocol and the complexity of its various parameters. Additionally, we provide efficient ways to recursively generate $\mathcal{U}_I$ for toric ideals of graphs with techniques which are also of independent interest to the study of these ideals. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_10429 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum-Resistant Cryptography via Universal Gröbner Bases Da Silva, Sergio Stewart, Aniya Information Theory Commutative Algebra Combinatorics Primary: 94A60, 13P10, Secondary: 05E40, 14M25 In this article, we explore the use of universal Gröbner bases in public-key cryptography by proposing a key establishment protocol that is resistant to quantum attacks. By utilizing a universal Gröbner basis $\mathcal{U}_I$ of a polynomial ideal $I$ as a private key, this protocol leverages the computational disparity between generating the universal Gröbner basis needed for decryption compared with the single Gröbner basis used for encryption. The security of the system lies in the difficulty of directly computing the Gröbner fan of $I$ required to construct $\mathcal{U}_I$. We provide an analysis of the security of the protocol and the complexity of its various parameters. Additionally, we provide efficient ways to recursively generate $\mathcal{U}_I$ for toric ideals of graphs with techniques which are also of independent interest to the study of these ideals. |
| title | Quantum-Resistant Cryptography via Universal Gröbner Bases |
| topic | Information Theory Commutative Algebra Combinatorics Primary: 94A60, 13P10, Secondary: 05E40, 14M25 |
| url | https://arxiv.org/abs/2510.10429 |