The search functionality is under construction.

The search functionality is under construction.

Sieve algorithms are regarded as the best algorithms to solve the shortest vector problem (SVP) on account of its good asymptotical quality, which could make it outperform enumeration algorithms in solving SVP of high dimension. However, due to its large memory requirement, sieve algorithms are not practical as expected, especially on high dimension lattice. To overcome this bottleneck, TupleSieve algorithm was proposed to reduce memory consumption by a trade-off between time and memory. In this work, aiming to make TupleSieve algorithm more practical, we combine TupleSieve algorithm with SubSieve technique and obtain a sub-exponential gain in running time. For 2-tuple sieve, 3-tuple sieve and arbitrary *k*-tuple sieve, when selecting projection index *d* appropriately, the time complexity of our algorithm is *O*(2^{0.415(n-d)}), *O*(2^{0.566(n-d)}) and $O(2^{rac{kmathrm{log}_2p}{1-k}(n-d)})$ respectively. In practice, we propose a practical variant of our algorithm based on GaussSieve algorithm. Experimental results show that our algorithm implementation is about two order of magnitude faster than FPLLL's GuassSieve algorithm. Moreover, techniques such as XOR-POPCNT trick, progressive sieving and appropriate projection index selection can be exploited to obtain a further acceleration.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.4 pp.714-722

- Publication Date
- 2021/04/01

- Publicized
- 2020/10/22

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.2020EAP1064

- Type of Manuscript
- PAPER

- Category
- Cryptography and Information Security

Zedong SUN

the State Key Laboratory of Mathematical Engineering and Advanced Computing,the Henan Key Laboratory of Network Cryptography Technology

Chunxiang GU

the State Key Laboratory of Mathematical Engineering and Advanced Computing,the Henan Key Laboratory of Network Cryptography Technology

Yonghui ZHENG

the State Key Laboratory of Mathematical Engineering and Advanced Computing,the Henan Key Laboratory of Network Cryptography Technology

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Zedong SUN, Chunxiang GU, Yonghui ZHENG, "Using SubSieve Technique to Accelerate TupleSieve Algorithm" in IEICE TRANSACTIONS on Fundamentals,
vol. E104-A, no. 4, pp. 714-722, April 2021, doi: 10.1587/transfun.2020EAP1064.

Abstract: Sieve algorithms are regarded as the best algorithms to solve the shortest vector problem (SVP) on account of its good asymptotical quality, which could make it outperform enumeration algorithms in solving SVP of high dimension. However, due to its large memory requirement, sieve algorithms are not practical as expected, especially on high dimension lattice. To overcome this bottleneck, TupleSieve algorithm was proposed to reduce memory consumption by a trade-off between time and memory. In this work, aiming to make TupleSieve algorithm more practical, we combine TupleSieve algorithm with SubSieve technique and obtain a sub-exponential gain in running time. For 2-tuple sieve, 3-tuple sieve and arbitrary *k*-tuple sieve, when selecting projection index *d* appropriately, the time complexity of our algorithm is *O*(2^{0.415(n-d)}), *O*(2^{0.566(n-d)}) and $O(2^{rac{kmathrm{log}_2p}{1-k}(n-d)})$ respectively. In practice, we propose a practical variant of our algorithm based on GaussSieve algorithm. Experimental results show that our algorithm implementation is about two order of magnitude faster than FPLLL's GuassSieve algorithm. Moreover, techniques such as XOR-POPCNT trick, progressive sieving and appropriate projection index selection can be exploited to obtain a further acceleration.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2020EAP1064/_p

Copy

@ARTICLE{e104-a_4_714,

author={Zedong SUN, Chunxiang GU, Yonghui ZHENG, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Using SubSieve Technique to Accelerate TupleSieve Algorithm},

year={2021},

volume={E104-A},

number={4},

pages={714-722},

abstract={Sieve algorithms are regarded as the best algorithms to solve the shortest vector problem (SVP) on account of its good asymptotical quality, which could make it outperform enumeration algorithms in solving SVP of high dimension. However, due to its large memory requirement, sieve algorithms are not practical as expected, especially on high dimension lattice. To overcome this bottleneck, TupleSieve algorithm was proposed to reduce memory consumption by a trade-off between time and memory. In this work, aiming to make TupleSieve algorithm more practical, we combine TupleSieve algorithm with SubSieve technique and obtain a sub-exponential gain in running time. For 2-tuple sieve, 3-tuple sieve and arbitrary *k*-tuple sieve, when selecting projection index *d* appropriately, the time complexity of our algorithm is *O*(2^{0.415(n-d)}), *O*(2^{0.566(n-d)}) and $O(2^{rac{kmathrm{log}_2p}{1-k}(n-d)})$ respectively. In practice, we propose a practical variant of our algorithm based on GaussSieve algorithm. Experimental results show that our algorithm implementation is about two order of magnitude faster than FPLLL's GuassSieve algorithm. Moreover, techniques such as XOR-POPCNT trick, progressive sieving and appropriate projection index selection can be exploited to obtain a further acceleration.},

keywords={},

doi={10.1587/transfun.2020EAP1064},

ISSN={1745-1337},

month={April},}

Copy

TY - JOUR

TI - Using SubSieve Technique to Accelerate TupleSieve Algorithm

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 714

EP - 722

AU - Zedong SUN

AU - Chunxiang GU

AU - Yonghui ZHENG

PY - 2021

DO - 10.1587/transfun.2020EAP1064

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E104-A

IS - 4

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - April 2021

AB - Sieve algorithms are regarded as the best algorithms to solve the shortest vector problem (SVP) on account of its good asymptotical quality, which could make it outperform enumeration algorithms in solving SVP of high dimension. However, due to its large memory requirement, sieve algorithms are not practical as expected, especially on high dimension lattice. To overcome this bottleneck, TupleSieve algorithm was proposed to reduce memory consumption by a trade-off between time and memory. In this work, aiming to make TupleSieve algorithm more practical, we combine TupleSieve algorithm with SubSieve technique and obtain a sub-exponential gain in running time. For 2-tuple sieve, 3-tuple sieve and arbitrary *k*-tuple sieve, when selecting projection index *d* appropriately, the time complexity of our algorithm is *O*(2^{0.415(n-d)}), *O*(2^{0.566(n-d)}) and $O(2^{rac{kmathrm{log}_2p}{1-k}(n-d)})$ respectively. In practice, we propose a practical variant of our algorithm based on GaussSieve algorithm. Experimental results show that our algorithm implementation is about two order of magnitude faster than FPLLL's GuassSieve algorithm. Moreover, techniques such as XOR-POPCNT trick, progressive sieving and appropriate projection index selection can be exploited to obtain a further acceleration.

ER -