Cryptology ePrint Archive: Report 2020/989

Algorithm for SIS and MultiSIS problems

Igor Semaev

Abstract: SIS problem has numerous applications in cryptography. The known algorithms for solving that problem are exponential in complexity. A new algorithm is suggested in this note, its complexity is sub-exponential for a range of parameters.

Category / Keywords: foundations / SIS problem, MultiSIS problem, matrices, complexity

Date: received 16 Aug 2020

Contact author: igor at ii uib no

Available format(s): PDF | BibTeX Citation

Version: 20200818:083913 (All versions of this report)

Short URL: ia.cr/2020/989


[ Cryptology ePrint archive ]