数论/代数与格型密码学的关系

Question

我是一名实习生(我昨天开始)，在一个基于格的密码学研究实验室，我有一个更多的数学背景，特别是代数。

我想知道什么类型的代数问题介入格基础密码学？

我应该读博士学位，我想在密码学的代数方面做更多的工作，但我不知道该去哪里看。

Answer 1

研究格(和基于格的方案)没有必要涉及代数数论(或其他一些高级课题)。安全简化使用了复杂性理论和概率的更多方面。而求解网格问题(如SVP、CVP、BDD等)的算法一般采用线性代数。

我认为您应该检查基于格的问题的结构化版本(如RLWE和RSIS)。例如，RLWE的描述通常涉及循环数字段及其整数环。

手动一种环形LWE密码工具箱可以是一个很好的起点。

但是，即使它们使用了数论和代数数论中的许多概念，它们也不一定是基于这些领域研究的问题(基于LWE和SIS的环变体的方案的安全性基本上依赖于这样一个假设，即SVP和其他格问题仍然很难超越由这些结构化问题生成的格格。例如理想格)。

在密码学中，一个可能与代数有关但也被研究的问题是寻找主理想的短生成元的问题。你很容易就能找到关于它的文件。例如，这一个：环中主理想的短生成元的恢复。