哪种对称加密系统、伪随机数生成器和哈希函数最适合可逆计算机？

Question

可逆计算指的是将要删除的数据量最小化的计算类型，通常是为了节省能源(可逆计算也可以是阻挠侧信道攻击)。在自由市场中，节能可逆计算机还不存在，尽管有些已经建造了原型，它们应该成为未来的计算机。在可逆计算中，AND和OR门被禁止，因为它们删除了数据(和门有两个输入，但有一个输出，因此必须删除一个比特)。

对于完全可逆的计算，由于非双射门删除了信息，所以只允许双射逻辑门进行计算。例如，CNOT $(x，y)\mapsto(x，x\oplus y)$，Toffoli $(x，y，z)\mapsto(x，y，(x\楔子y)\oplus z)$和Fredkin $(0，y，z)\mapsto(0，y，z)，(1，y，z)\mapsto(1，z，y)$门都是可逆的。

虽然可逆计算理论上应该节省能源，但它通常需要更多的步骤来可逆地计算某事，而不是不可逆地执行相同的计算。然而，在对称密码学中，可以设计密码系统，例如加密系统、哈希函数、(密码和非加密)伪随机数字生成器，这些生成器不包含任何此类算法开销(密码哈希函数所要求的唯一不可逆转性是，除非希望永远保持散列，否则必须最终删除哈希)。

( 1)是否有专门为可逆计算机设计的对称密码系统？

( 2)是否有任何对称密码系统不一定被设计成可供可逆计算机使用，但恰好是可逆的？

( 3)是否有几乎可逆的对称密码系统？

以下是可逆密码系统中的一些特性。

理想情况下，-The密码系统应该使用完全可逆的门来计算，而不需要任何垃圾位、ancilla位、不可计算或不可逆的门。

包含在密码系统中的所有部分的-The逆应与正方向完全相同(例如，Keccak中的逆$\chi$与正向计算不同；$\chi$具有代数度2，而$\chi$的逆具有代数度3(见这些幻灯片第16页)。

-The密码系统不需要任何不计算。尽管不可逆计算不需要任何不计算，但在可逆计算中出现了一种开销。

-The密码系统不应使用任何查找表。

-The密码体制不应使用模乘、有限域乘法或有限场反演等运算，所有这些运算都需要计算量。

Answer 1

我们可以把加密看作是一个确定性函数，它从密钥$C$、明文$P$生成密文$P$，对于确定性加密，我们可以将它看作是一个额外的输入$R$，用于随机性/初始化向量。函数$(K，R，P)\mapsto C$不能既安全又可逆。证明:由于可逆性，从$C$获得$(K，R，P)$是可能的，也可以从提取的$P$中获得$(K，R，P)，这与安全目标是背道而驰的。

同样的推理表明，一个完全可逆的TRNG不可能是安全的，或者是一个完全可逆的哈希函数，首先是抗预图像的。

然而，我们可以可逆地实现所有的步骤，除了放弃一些最终的结果。特别是对于任何保持大小的对称密码，原则上我们可以可逆地实现$(K，R，P)\mapsto(G，C)$，使用与$K$相同宽度的垃圾$G$ (以及与$R$和$P$之和相同宽度的$C$ )，并从输出中丢弃$G$。对于分组密码，即$(K，P)\mapsto(G，C)$ (证明和/或矫正欢迎；Scott，Daniel，Luke的可逆位运算的分类将是一个有用的参考)。

利用可逆密码的概念，可以丢弃键宽的垃圾，我试着回答：

1. 是的，如果你的以类似Toffoli的门的简单实现取代符合条件。
2. 是。AES分组密码是一个经过充分研究的例子，它的所有标准模式都是合格的.有关AES-128的可逆结构，请参见。
   • Kamalika Datta，Vishal Shri瓦斯in，Indranil Sengupta，Hafizur Rahaman's AES算法的可逆逻辑实现，in 2013年年DTIS会议记录。我的理解是，它报告使用小于$2{17}$ Toffoli的AES-128实现$(K，P)\mapsto(G，C)$。
   • 马库斯·格拉斯( Markus )、布兰登·朗根伯格( Brandon )、马丁·罗泰勒( Martin )、雷纳·施泰因万特( Rainer )的Grover算法在AES中的应用:量子资源估计在2016年年PQCrypto会议纪要里，似乎用另一种方法略高于2美元(20美元)的托波利盖茨( Toffoli )。

3. 而不是。使事情容易逆转，当它们不是，将是一个巨大的设计变化，很可能损害安全。这尤其适用于使用大的不可逆圆函数的Feistel块密码，我猜很难将其重新表示为可逆的。

我知道DES的成本有多高。

Answer 2

似乎大多数对称密码系统都可以修改成完全可逆的密码系统，而不需要垃圾或安西拉位，这样的话，安全级别可能会增加而不是降低。

可逆计算接收干净的数据，并返回垃圾数据，这些垃圾数据必须通过取消计算的过程来清理。但是，为了加密的目的，清理任何生成的垃圾数据没有多大意义，因为垃圾数据提供了混乱和扩散。坚持在ancilla位的输入上使用干净的0位也没有太大的意义，因为使用脏的ancilla位也会带来混乱和扩散。当然，这些修改会改变分组密码的设计，因此需要对它们进行研究和优化，但这些修改可能会增加分组密码的安全性。

假设$S：{0，1}^{n}\右旋{0，1}^{n}${n}$是用于对称加解密算法的$S$-box或其他双射函数。

假设现在有一个有效的可逆电路$C:{0,1}^{n}\times{0,1}^{m}\rightarrow{0,1}^{n}\times{0,1}^{m}$，使得$C(\mathbf{x}，\mathbf{0})=(S(\mathbf{x})，G(mathbf{x}))$(在这里$G(\mathbf{x})$是通过计算$S(\mathbf{x})$产生的垃圾数据)。为了使分组密码可逆，可以用函数$(mathbf{x}，\mathbf{y})\mapsto (mathbf{x}，\mathbf{y})$代替$S$-box {x}\mapsto S(\mathbf{x}) $ (\mathbf{x} )$。

同样，如果$D$是一个可逆电路，使得$D(\mathbf{x}，\mathbf{0})=(S^{-1}(mathbf{x})，H(mathbf{x}))$，则可以用可逆映射$(mathbf{x}，\mathbf{y})\mapsto D{-1}(\mathbf{x}，\mathbf{x}，\mathbf{x})$替换$$D(mathbf{x}，\mathbf{0})=(mathbf{x}，\mathbf{y})$。