An Attack on $p$-adic Lattice Public-key Cryptosystems and Signature Schemes
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912284878569472 |
|---|---|
| author | Zhang, Chi |
| author_facet | Zhang, Chi |
| contents | Lattices have many significant applications in cryptography. In 2021, the $p$-adic signature scheme and public-key encryption cryptosystem were introduced. They are based on the Longest Vector Problem (LVP) and the Closest Vector Problem (CVP) in $p$-adic lattices. These problems are considered to be challenging and there are no known deterministic polynomial time algorithms to solve them. In this paper, we improve the LVP algorithm in local fields. The modified LVP algorithm is a deterministic polynomial time algorithm when the field is totally ramified and $p$ is a polynomial in the rank of the input lattice. We utilize this algorithm to attack the above schemes so that we are able to forge a valid signature of any message and decrypt any ciphertext. Although these schemes are broken, this work does not mean that $p$-adic lattices are not suitable in constructing cryptographic primitives. We propose some possible modifications to avoid our attack at the end of this paper. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_08774 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Attack on $p$-adic Lattice Public-key Cryptosystems and Signature Schemes Zhang, Chi Cryptography and Security Number Theory Primary 11F85, Secondary 94A60 Lattices have many significant applications in cryptography. In 2021, the $p$-adic signature scheme and public-key encryption cryptosystem were introduced. They are based on the Longest Vector Problem (LVP) and the Closest Vector Problem (CVP) in $p$-adic lattices. These problems are considered to be challenging and there are no known deterministic polynomial time algorithms to solve them. In this paper, we improve the LVP algorithm in local fields. The modified LVP algorithm is a deterministic polynomial time algorithm when the field is totally ramified and $p$ is a polynomial in the rank of the input lattice. We utilize this algorithm to attack the above schemes so that we are able to forge a valid signature of any message and decrypt any ciphertext. Although these schemes are broken, this work does not mean that $p$-adic lattices are not suitable in constructing cryptographic primitives. We propose some possible modifications to avoid our attack at the end of this paper. |
| title | An Attack on $p$-adic Lattice Public-key Cryptosystems and Signature Schemes |
| topic | Cryptography and Security Number Theory Primary 11F85, Secondary 94A60 |
| url | https://arxiv.org/abs/2409.08774 |