Shi Bai

Dr. Shi Bai

orcid

Research Focus & Metrics

Academic Career Length

15Years (2012-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
21 July 2016
Verified
Book Chapter
Closed access
PDF file
MAMartin Albrecht
Martin Albrecht
SBShi Bai
Shi Bai
LDLéo Ducas
Léo Ducas


1 January 2014
Verified
Book Chapter
Closed access
PDF file
SBShi Bai
Shi Bai
SGSteven D. Galbraith
Steven D. Galbraith

28 August 2017 in Journal of Cryptology
Verified
Journal Article
Closed access
PDF file
SBShi Bai
Shi Bai
TLTancrède Lepoint
Tancrède Lepoint
ARAdeline Roux-Langlois
Adeline Roux-Langlois
Amin SakzadAmin Sakzad
Amin Sakzad
DSDamien Stehlé
Damien Stehlé
RSRon Steinfeld
Ron Steinfeld

1 January 2015
Verified
Book Chapter
Closed access
PDF file
SBShi Bai
Shi Bai
ARAdeline Roux-Langlois
Adeline Roux-Langlois
TLTancrède Lepoint
Tancrède Lepoint
DSDamien Stehlé
Damien Stehlé
RSRon Steinfeld
Ron Steinfeld

26 August 2016 in LMS Journal of Computation and Mathematics
Verified
Journal Article
Open access
PDF file
SBShi Bai
Shi Bai
TLThijs Laarhoven
Thijs Laarhoven
DSDamien Stehlé
Damien Stehlé
Lattice sieving is asymptotically the fastest approach for solving the shortest vector problem (SVP) on Euclidean lattices. All known sieving algorithms for solving the SVP require space which (heuristically) grows as $2^{0.2075n+o(n)}$ , where $n$ is the lattice dimension. In high dimensions, the memory requirement becomes a limiting factor for running these algorithms, making them uncompetitive with enumeration algorithms, despite their superior asymptotic time complexity.We generalize sieving algorithms to solve SVP with less memory. We consider reductions of tuples of vectors rather than pairs of vectors as existing sieve algorithms do. For triples, we estimate that the space requirement scales as $2^{0.1887n+o(n)}$ . The naive algorithm for this triple sieve runs in time $2^{0.5661n+o(n)}$ . With appropriate filtering of pairs, we reduce the time complexity to $2^{0.4812n+o(n)}$ while keeping the same space complexity. We further analyze the effects of using larger tuples for reduction, and conjecture how this provides a continuous trade-off between the memory-intensive sieving and the asymptotically slower enumeration.