TY - GEN
T1 - Parallel lattice basis reduction - The road to many-core
AU - Backes, Werner
AU - Wetzel, Susanne
PY - 2011
Y1 - 2011
N2 - This paper introduces a new parallel algorithm that allows for an efficient LLL reduction using today's emerging many-core systems. This work develops suitable methods that efficiently implement the idea of splitting a lattice basis into smaller sub problems, LLL reducing the sub problems, and recombining the sub problems afterwards to obtain an overall LLL reduced basis. The new many-core algorithm outperforms any current parallel LLL algorithm. Experiments on a 48-core test system show a speed-up of approximately 10 for SVP challenge type lattice bases and a remarkable speed-up of approximately 50 for knapsack type lattice bases.
AB - This paper introduces a new parallel algorithm that allows for an efficient LLL reduction using today's emerging many-core systems. This work develops suitable methods that efficiently implement the idea of splitting a lattice basis into smaller sub problems, LLL reducing the sub problems, and recombining the sub problems afterwards to obtain an overall LLL reduced basis. The new many-core algorithm outperforms any current parallel LLL algorithm. Experiments on a 48-core test system show a speed-up of approximately 10 for SVP challenge type lattice bases and a remarkable speed-up of approximately 50 for knapsack type lattice bases.
KW - cryptanalysis
KW - lattice basis reduction
KW - many-core
KW - parallel algorithms
UR - http://www.scopus.com/inward/record.url?scp=81555209724&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=81555209724&partnerID=8YFLogxK
U2 - 10.1109/HPCC.2011.61
DO - 10.1109/HPCC.2011.61
M3 - Conference contribution
AN - SCOPUS:81555209724
SN - 9780769545387
T3 - Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 -Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011
SP - 417
EP - 424
BT - Proc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 - Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011
T2 - 13th IEEE International Workshop on FTDCS 2011, the 8th International Conference on ATC 2011, the 8th International Conference on UIC 2011 and the 13th IEEE International Conference on HPCC 2011
Y2 - 2 September 2011 through 4 September 2011
ER -