Cargando…
Solving HNP with One Bit Leakage: An Asymmetric Lattice Sieving Algorithm
The Hidden Number Problem (HNP) was introduced by Boneh and Venkastesan to analyze the bit-security of the Diffie–Hellman key exchange scheme. It is often used to mount a side-channel attack on (EC)DSA. The hardness of HNP is mainly determined by the number of nonce leakage bits and the size of the...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
MDPI
2022
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9857384/ https://www.ncbi.nlm.nih.gov/pubmed/36673190 http://dx.doi.org/10.3390/e25010049 |
_version_ | 1784873856020774912 |
---|---|
author | Shi, Wenhao Jiang, Haodong Ma, Zhi |
author_facet | Shi, Wenhao Jiang, Haodong Ma, Zhi |
author_sort | Shi, Wenhao |
collection | PubMed |
description | The Hidden Number Problem (HNP) was introduced by Boneh and Venkastesan to analyze the bit-security of the Diffie–Hellman key exchange scheme. It is often used to mount a side-channel attack on (EC)DSA. The hardness of HNP is mainly determined by the number of nonce leakage bits and the size of the modulus. With the development of lattice reduction algorithms and lattice sieving, the range of practically vulnerable parameters are extended further. However, 1-bit leakage is still believed to be challenging for lattice attacks. In this paper, we proposed an asymmetric lattice sieving algorithm that can solve HNP with 1-bit leakage. The algorithm is composed of a BKZ pre-processing and a sieving step. The novel part of our lattice sieving algorithm is that the lattice used in these two steps have different dimensions. In particular, in the BKZ step we use more samples to derive a better lattice basis, while we just use truncated lattice basis for the lattice sieving step. To verify our algorithm, we use it to solve HNP with 1-bit leakage and 116-bit modulus. |
format | Online Article Text |
id | pubmed-9857384 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2022 |
publisher | MDPI |
record_format | MEDLINE/PubMed |
spelling | pubmed-98573842023-01-21 Solving HNP with One Bit Leakage: An Asymmetric Lattice Sieving Algorithm Shi, Wenhao Jiang, Haodong Ma, Zhi Entropy (Basel) Article The Hidden Number Problem (HNP) was introduced by Boneh and Venkastesan to analyze the bit-security of the Diffie–Hellman key exchange scheme. It is often used to mount a side-channel attack on (EC)DSA. The hardness of HNP is mainly determined by the number of nonce leakage bits and the size of the modulus. With the development of lattice reduction algorithms and lattice sieving, the range of practically vulnerable parameters are extended further. However, 1-bit leakage is still believed to be challenging for lattice attacks. In this paper, we proposed an asymmetric lattice sieving algorithm that can solve HNP with 1-bit leakage. The algorithm is composed of a BKZ pre-processing and a sieving step. The novel part of our lattice sieving algorithm is that the lattice used in these two steps have different dimensions. In particular, in the BKZ step we use more samples to derive a better lattice basis, while we just use truncated lattice basis for the lattice sieving step. To verify our algorithm, we use it to solve HNP with 1-bit leakage and 116-bit modulus. MDPI 2022-12-27 /pmc/articles/PMC9857384/ /pubmed/36673190 http://dx.doi.org/10.3390/e25010049 Text en © 2022 by the authors. https://creativecommons.org/licenses/by/4.0/Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). |
spellingShingle | Article Shi, Wenhao Jiang, Haodong Ma, Zhi Solving HNP with One Bit Leakage: An Asymmetric Lattice Sieving Algorithm |
title | Solving HNP with One Bit Leakage: An Asymmetric Lattice Sieving Algorithm |
title_full | Solving HNP with One Bit Leakage: An Asymmetric Lattice Sieving Algorithm |
title_fullStr | Solving HNP with One Bit Leakage: An Asymmetric Lattice Sieving Algorithm |
title_full_unstemmed | Solving HNP with One Bit Leakage: An Asymmetric Lattice Sieving Algorithm |
title_short | Solving HNP with One Bit Leakage: An Asymmetric Lattice Sieving Algorithm |
title_sort | solving hnp with one bit leakage: an asymmetric lattice sieving algorithm |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9857384/ https://www.ncbi.nlm.nih.gov/pubmed/36673190 http://dx.doi.org/10.3390/e25010049 |
work_keys_str_mv | AT shiwenhao solvinghnpwithonebitleakageanasymmetriclatticesievingalgorithm AT jianghaodong solvinghnpwithonebitleakageanasymmetriclatticesievingalgorithm AT mazhi solvinghnpwithonebitleakageanasymmetriclatticesievingalgorithm |