Bridging the Gap Between Lattice Coding and Lattice Cryptography - Post-Quantum Cryptography

格子在工程和计算机科学的各个领域中扮演着重要的角色。在编码理论上，格码具有实现具体、降低复杂度等显著优点，克服了随机码在实际应用中的局限性。最近，人们普遍认识到格码的代数结构极大地促进了无线网络中多个用户之间的协调。在存在量子计算机的世界中，现有的公钥密码方案将变得容易受到利用量子力学性质的攻击。这是我们现代数据驱动社会的一个核心问题，政府、公司和研究机构都对此进行了广泛考虑。例如，美国国家标准与技术研究所(NIST，USA)在2016年发起了一项呼吁，要求对量子抵抗密码术进行标准化。在有望实现后量子密码学的方法中，基于格的密码学被认为是领跑者。这种形式的密码学探索格子理论和格子相关问题的难度，以构建诸如加密方案、单向函数、数字签名和完全同态加密等原语。虽然格子编码和格子密码学都涉及相同的数学对象-格-但它们从不同的有利位置考虑这些对象。编码理论使用格子来保护正确性不受噪声的影响，而密码学则增加噪声来保护安全性。因此，这两个领域对格提出了不同的问题：编码理论主要关注容易破译的格，而密码学关注的是坚硬的格。尽管有这些不同的观点，格编码对格密码学有很大的贡献。首先，为了加密消息，我们需要对它们进行编码，我们的编码方案越有效，密文就越小。这一点特别重要，因为密文的大小是基于格的密码术的主要缺点之一。也就是说，这些方案通常非常快，但会产生很大的密文。其次，格编码已经并且可以用于提高基于格的密码学的安全性分析。在这一领域，我们研究了破解密码方案的算法，以便我们能够以这种方式选择参数来避免此类攻击。

Lattices play an important role in various areas of engineering and computer science. In coding theory, lattice codes bring significant advantages such as concrete implementation and complexity reduction, thus overcoming the limitation of random codes in practical applications. More recently, it became widely appreciated that algebraic structures of lattice codes greatly facilitate coordination among multiple users in wireless networks.In a world where quantum computers exist, current public key cryptographic schemes will become vulnerable to attacks that exploit the nature of quantum mechanics. This is a central concern to our modern data-driven society, which has been extensively considered by governments, companies and research institutions. For instance, the National Institute of Standards and Technology (NIST, USA) launched in 2016 a call for the standardisation of quantum-resistant cryptography. Among the prospective methods which are expected to be implemented for post-quantum cryptography, lattice-based cryptography figures as a front runner. This form of cryptography explores the theory of lattices and the hardness of lattice-related problems to build primitives such as encryption schemes, one-way functions, digital signatures and fully-homomorphic encryption.While both lattice coding and lattice cryptography are concerned with the same mathematical objects --- lattices --- they consider these objects from disparate vantage points. Coding theory uses lattices to protect correctness against noise, whereas cryptography adds noise to protect security. As a consequence, both fields ask different questions of lattices: coding theory is mainly concerned with lattices that are easy to decode, whereas cryptography is focused on lattices that are hard.Despite these different perspectives, lattice coding has a lot to contribute to lattice cryptography. Firstly, in order to encrypt messages we need to encode them and the more efficient our coding schemes, the smaller will be our ciphertexts. This is particularly relevant since the size of ciphertexts is one of the key drawbacks of lattice-based cryptography. That is, these schemes are typically very fast but produce large ciphertexts. Secondly, lattice coding has and can be used to improve the security analysis of lattice-based cryptography. In this area, we study algorithms for breaking cryptographic schemes so that we can pick parameters in such a way to avoid such attacks.