Our regular Crypto Café seminars take place every other Monday 11am-12pm during the semester. We invite local and international experts on t opics in Mathematics and Computer Science related to Cryptography and Information Security.
Come and join us for freshly brewed coffee and interesting conversations on most exciting topics in cryptography.
Where: SE43 (Charles E. Schmidt College of Science) - Room 215 and via Zoom
You can catch up on the missed out meetings by following the below link:
April 10, 2023, SE-43, Room 215; 11:00 a.m. +Zoom: (click here)
Speaker: Cariel Cohen (CTO at Securily)
April 24, 2023, SE-43, Room 215; 11:00 a.m. +Zoom: (click here)
Speaker: Ryan Keegan (University of California, San Diego).
Bio : Keegan Ryan is a 4th year PhD student advised by Prof. Nadia Heninger at the University of California, San Diego. His research interests include practical cryptanalysis of real-world systems, particularly problems involving lattice reduction.
Title: Fast Practical Lattice Reduction through Iterated Compression
Abstract: We introduce a new lattice basis reduction algorithm with approximation guarantees analogous to the LLL algorithm and practical performance that far exceeds the current state of the art. We achieve these results by iteratively applying precision management techniques within a recursive algorithm structure and show the stability of this approach. We analyze the asymptotic behavior of our algorithm, and show that the heuristic running time is O(nω(C+n)1+ε) for lattices of dimension n, ω∈ (2,3] bounding the cost of size reduction, matrix multiplication, and QR factorization, and C bounding the log of the condition number of the input basis B. This yields a running time of O(nω(p + n)1+ε) for precision p=O(log|B|max) in common applications. Our algorithm is fully practical, and we have published our implementation. We experimentally validate our heuristic, give extensive benchmarks against numerous classes of cryptographic lattices, and show that our algorithm significantly outperforms existing implementations.