这种形式的Diffie-Hellman是可行的和量子弹性吗？

Question

在这个纸中，作者建议使用Diffie-Hellman的一个变体，在产生共享秘密时涉及任意大小的浮点数。没有素数，计算是执行\bmod{1}的

简单地说：

1. 爱丽丝选择x (一个十进制数)和a (一个随机整数)。她生成a'=ax\bmod{1}并与x一起发送给Bob。
2. 鲍勃生成b'=bx\mod{1}并发送给艾丽斯。
3. a'b \mod{1} \equiv b'a\bmod{1}，根据a和b的大小，精确到一定数量的数字。

我已经检查过了，而且非常显著(至少对我来说)对称性是有效的。

在最后一段中，作者认为这种方法对量子计算机是有弹性的：

与Diffie-Hellman有限域方法相比，所建议的协议除了对量子计算机具有弹性外，其最大的成就是使用了超越数的十进制部分，而不是大的有限整数。从本质上说，先验数的使用并不像整数那样限制计算中的数字数。在有限域情况下，秘密数受有限域q阶的限制，对于蛮力猜测，只需系统地尝试所有小于q的数，用该方法，传输数a_ 0和b_0中的数字数有另一个界。然而，Shor和Grover算法所提供的密码分析似乎并不会对这一过程构成威胁。

问题

1. 这实际上是一种可行的密钥交换方法吗？
2. 它真的能适应量子计算机吗？
3. \bmod{1}计算是否为已知的单向/对称函数，它是否在其他地方使用？

Answer 1

简单地评论一下：

1. \bmod 1计算是否为已知的单向/对称函数，它是否在其他地方使用？

弗格留在他的回答中提到：

模模整数是单向函数的一个常见的构造块，例如(在Diffie-Hellman中) k\to g^k\bmod p，其中p是素数，q=(p−1)/2是素数，g^q+1\bmod p=0是素数。但是，由公共常数(如问题的文章中使用的)进行的模乘并不是单向的。

我将要说的并不与此相矛盾，相反，它显示了模“乘”被认为是单向的。正如fgrieu所提到的，a\bmod 1\equiv b\iff pa\bmod p\equiv bp for p\in\mathbb{N}，因此\bmod 1和\bmod p之间的区别在于缩放。

如果我们考虑缩放的模方程ax\bmod p\equiv b，并进一步限制一切都是整数(因此，除非缩放因子很大，否则没有任意浮动来启动\bmod 1 )，有几种方法可以稍微修改这一点，以实现被认为是单向的函数。

1. 基于LWE的密码系统--相反，使用函数\langle \vec{a}, \vec{b}\rangle + e\bmod p \equiv b.在这里，您将得到一个模块标量乘积(而不是乘法)，它还带有“噪声”(e是从某些“集中”错误分布中提取的)。
2. 基于RLWE的密码系统--这里，函数的形式是a\cdot b + e\bmod I，其中I是“代数数域中的理想”，a, b, e是“整数”多项式。形式化更需要更多的工作，但对于数学上“广义”形式的整数，可以将(整数)标量乘积更改为“实际乘法”。
3. 基于RLWR的密码系统--在这里，函数是\lfloor a\cdot b\rceil \bmod I形式的，其中\lfloor\cdot \rceil以一种标准的(公开的)方式对产品进行“舍入”(我相信它只是将每个坐标舍入到最近的整数)。

要回答你的问题，取决于作者。我见过一些在\bmod 1计算方面描述了上述格式的方案(例如，如果我记得正确的话，TFHE方案 )。

上述方案最终有许多不同的可能变体--并不是所有的方案都被认为是安全的！

快速描述您可以选择的各种参数(不幸的是，实际上可能有更多的参数，但这些参数在某种程度上是“核心”参数)：

1. 模量q的大小；
2. 噪音\sigma的“大小”(通常被看作是q的一小部分)--如果你可以用\sigma任意大的东西获取信息--理论上是安全的，但我们不再知道如何从它构建密码；
3. a, b的“维数”(作为向量\vec{a}, \vec{b}或作为“广义整数”)；
4. 使用“通用整数”的特定选择(有一个社区标准，但不是100%的社区支持此标准)。

您不能构建“真正的”DH类型的方案，这是从后量子，但你可以建立“噪音”-DH类型的方案。这里最大的区别是，“嘈杂”方案似乎需要再进行半个来回的通信才能发送数据(我相信)。

我认为可以通过让客户端持有服务器的长期公钥，或者使用另一种称为“基于等价类密码”的PQ密码(上面的是“基于格的密码”)来绕开这半轮旅行，但我对异构密码并不熟悉。