Algebraic Statistics and the Study of Multistate Models: Theory and Applications, April 1-4, 2025, Aalto and U. Helsinki
We discuss the LAC cryptosystem, which was presented to the NIST contest and although discarded in the outcome of the third round, was seriously considered as a rival for Kyber and is recently regaining attention from other different public committees. One of the main features of LAC is the small modulus size, which is taken of the order of bytes, in comparison with Kyber, where q is at least 3329. This fact renders LAC one of the most compact cryptosystems, suitable to be used for small devices and with the same reduction security warranties as other RLWE-based schemes. However, the smallness of q brings an extra difficulty: the absence of NTT, which implies an obvious decrease in efficiency. This is overcome by the use of error correction in the cyphertext. As proved by the authors, LAC outperforms Kyber at 128 and 256 bits security levels in terms of key size and cyphertext size while remaining more geneours in the security margin. It is true that these security levels are not recommended nowadays by NIST anymore, but the authors also suggested that LAC-192-v3b may be considered to achieve NIST Security Level 5 since it outperforms Kyber 1024 at this level. The goal of this talk is to report about this claim after the introduction of the foundations of the cryptosystem.
Thesis is available at: https://math.aalto.fi/en/current/#2188. For Zoom streaming, click 'further info'.
Linear codes are designed to protect data from loss and distortion. Data is stored with some redundancy that allows for the recovery of erasures or correction of errors. Decoding algorithms for linear codes typically take as input all symbols of a received word and attempt to determine the original codeword. In this talk, we focus on strategies that support error correction and erasure recovery using fewer bits than traditional approaches.
Function-correcting codes (FCCs), introduced by Lenz et al. (2023), generalize classical error correction by guaranteeing correct evaluation of a target function even when the transmitted data is corrupted. This talk begins with an overview of FCCs and the associated notation, then introduces locally (ρ,λ)-bounded functions, i.e., functions that take at most λ values within any Hamming ball of radius ρ. This local structure provides a natural setting for FCC design. An upper bound on redundancy is derived via the minimum length of an error-correcting code with given codebook size and distance, and a sufficient condition for optimality is established for the case λ=4. Further, it has been shown that any function can be represented in this framework, illustrated through Hamming-weight distribution functions. Lastly, the talk briefly discusses a generalized setting of FCCs that also considers data protection.
Page content by: webmaster-math [at] list [dot] aalto [dot] fi