Title: Algorithms for the minimal rational fraction representation of sequences revisited

Keynote Speaker: Tian Chengliang

Abstract:

Given a binary sequence with a bit length of n, determining its minimal rational fraction representation (MRFR) has important applications in the design and cryptanalysis of stream cipher. In Crypto’95, Klapper and Goresky firstly introduced this problem and presented an adaptive rational approximation algorithm with a time complexity of O(n^2 log n log log n). In this paper, we revisited the currently efficient algorithms for this problem and, compared with the prior arts, we make substantially new advances in the following four aspects. Firstly, by giving a thorough and more general theoretical analysis on the Lagrange reduced basis of 2-dimensional lattices, we improve the currently fastest adaptive algorithm recently presented by Li et al. in DCC 2019. Secondly, by optimizing a time-consuming step of the well-known Lagrange reduction algorithm for 2-dimensional lattices, we present a non-adaptive yet faster practical algorithm, named global Euclidean algorithm, for MRFR problem. Thirdly, we point out a severe theoretical flaw in the design of the Euclidean algorithm for MRFR problem proposed by Arnault et al. in IEEE TIT 2004 and IEEE TIT 2008, and design a revised Euclidean algorithm, named partial Euclidean algorithm, based on half-gcd algorithm which reduces the time complexity of the proposed algorithm to O(n log^2n loglog n). Finally, we give a comprehensive experimental comparative analysis on the above algorithms to validate our theoretical analysis.

Introduction to the Speaker:

Tian Chengliang, PhD, is an Associate Professor of College of Computer Science & Technology, Qingdao University. Currently, he is mainly engaged in the research on lattice-based cryptography and privacy protection in cloud computing/edge computing. He has presided over a multiple of scientific research projects, such as the Youth Program of National Natural Science Foundation of China, the National Cryptography Development Fund during the "13^th Five-Year Plan" period, and the Youth Program of Natural Science Foundation of Shandong Province, and published over 10 papers on IEEE TSC, Information Sciences, Science China: Information Sciences and other top computer science journals at home and abroad.

Inviter:

Wang Mingqiang Professor in the School of Mathematics

Time:

10:00-11:00 on September 27 (Sunday)

Location:

Tencent Conference, conference ID: 735 341 911

Click the link to attend the meeting, or add to the meeting list:

https://meeting.tencent.com/s/dzm1Aw676fYF

Sponsored by: School of Mathematics, Shandong University