XiaoMi-AI文件搜索系统
World File Search System哈希
同态哈希功能的量子碰撞发现
abtract。哈希功能是基本的加密原始功能。某些哈希功能试图通过减少已知的严重问题来证明对碰撞和前图攻击的安全性。这些哈希功能通常具有一些允许减少的额外属性。哈希函数是加性或乘法的，使用量子计算机的隐藏子组问题算法容易受到量子攻击的影响。使用量子甲骨文到哈希，我们可以重建哈希函数的内核，这足以找到碰撞和第二次预示。当哈希函数相对于Abelian组中的组操作是加法的时，总会有足够的实现此攻击。我们将具体的攻击示例提交了可证明的哈希功能，包括对⊕线性哈希函数的前攻击和某些乘法同构哈希方案。
使用低量子随机存取存储器对 AES 类哈希算法进行量子碰撞攻击
摘要。在 EUROCRYPT 2020 上，Hosoyamada 和 Sasaki 提出了第一个专门针对哈希函数的量子攻击——反弹攻击的量子版本，利用概率太低而无法在经典环境中使用的微分。这项工作为哈希函数抵御量子攻击的安全性开辟了一个新视角。特别是，它告诉我们，对微分的搜索不应止步于经典的生日界限。尽管这些有趣且有希望的含义，但 Hosoyamada 和 Sasaki 描述的具体攻击利用了大型量子随机存取存储器 (qRAM)，这种资源在可预见的未来是否可用即使在量子计算界也存在争议。如果没有大型 qRAM，这些攻击会导致时间复杂度显著增加。在这项工作中，我们通过执行基于具有非全活动超级 S 盒的微分的量子反弹攻击来减少甚至避免使用 qRAM。在此过程中，提出了一种基于 MILP 的方法来系统地探索针对反弹攻击的有用截断差分的搜索空间。 结果，我们获得了对 AES - MMO 、 AES - MP 的改进攻击，以及对 4 轮和 5 轮 Grøstl - 512 的第一个经典碰撞攻击。 有趣的是，在 AES - MMO 的分析中使用非全活动超级 S 盒差分会导致收集足够起点的新困难。 为了克服这个问题，我们考虑涉及两个消息块的攻击以获得更多的自由度，并且我们成功地将对 AES - MMO 和 AES - MP (EUROCRYPT 2020) 的碰撞攻击的 qRAM 需求从 2 48 压缩到 2 16 到 0 的范围，同时仍然保持可比的时间复杂度。据我们所知，这是第一次专门针对哈希函数的量子攻击，其性能略优于 Chailloux、Naya-Plasencia 和 Schrottenloher 的通用量子
缩放哈希函数原像的量子搜索
摘要。我们在量子模拟器中介绍了 Grover 算法的实现，以对两个缩放哈希函数的原像进行量子搜索，其设计仅使用模加、字旋转和按位异或。我们的实现提供了精确评估门数和成熟量子电路深度缩放的方法，该量子电路旨在查找给定哈希摘要的原像。量子预言机的详细构造表明，与门、或门、位移位和计算过程中初始状态的重用，与基于模加、异或门和旋转的其他哈希函数相比，需要额外的量子资源。我们还跟踪了计算过程中每一步量子寄存器中存在的纠缠熵，表明它在量子预言机的第一个动作的内核处达到最大值，这意味着基于张量网络的经典模拟将不相关。最后，我们表明，基于在 Grover 算法的几个步骤之后对量子寄存器进行采样的快捷策略只能在减少错误方面提供一些边际实际优势。
利用 SAT 技术构造最小完美哈希函数
最小完美哈希函数 (MPHF) 用于有效访问大型字典 (键值对集) 的值。发现构建 MPHF 的新算法是一个活跃的研究领域，尤其是从存储效率的角度来看。MPHF 的信息论极限为 1 ln 2 ≈ 1.44 位/键。当前最佳实用算法的范围是每个键 2 到 4 位。在本文中，我们提出了两种基于 SAT 的 MPHF 构造。我们的第一个构造产生的 MPHF 接近信息论极限。对于这种构造，当前最先进的 SAT 求解器可以处理字典包含多达 40 个元素的情况，从而优于现有的 (蛮力) 方法。我们的第二个构造使用 XOR-SAT 过滤器来实现一种实用方法，每个键的长期存储量约为 1.83 位。
使用概率小于生日界限的差分轨迹寻找与量子计算机的哈希碰撞
摘要：本文重点研究了针对具体哈希函数的专用量子碰撞攻击，目前此类攻击尚未引起太多关注。在经典环境下，查找 n 位哈希函数碰撞的一般复杂度为 O(2 n/ 2)，因此基于差分密码分析的经典碰撞攻击（如反弹攻击）会以高于 2 − n/ 2 的概率构建差分轨迹。同理，通用量子算法（如 BHT 算法）会以复杂度 O(2 n/ 3) 找到碰撞。利用量子算法，可以以复杂度 p − 1 / 2 生成一对满足概率 p 的差分轨迹的消息。因此，在量子环境下，一些在经典环境下无法利用的概率高达 2 − 2 n/ 3 的差分轨迹可能会被利用来在量子环境下发起碰撞攻击。特别是，被攻击的轮数可能会增加。在本文中，我们攻击了两个国际哈希函数标准：AES-MMO 和 Whirlpool。对于 AES-MMO，我们提出了一个概率为 2-80 的 7 轮差分轨迹，并使用它来查找与反弹攻击的量子版本的碰撞，而在经典设置中只能攻击 6 轮。对于 Whirlpool，我们基于经典反弹区分器的 6 轮差分轨迹发起碰撞攻击，其复杂度高于生日界限。这将 5 轮的最佳经典攻击提高了 1。我们还表明，这些轨迹在我们的方法中是最佳的。我们的结果有两个重要含义。首先，似乎存在一个普遍的信念，即经典安全的哈希函数将保持对量子对手的安全性。事实上，NIST 后量子竞赛中的几个第二轮候选人使用现有的哈希函数（例如 SHA-3）作为量子安全函数。我们的结果推翻了这种普遍的看法。其次，我们的观察表明，差分线索搜索不应以概率 2 − n/ 2 停止，而应考虑最多 2 − 2 n/ 3 。因此，值得重新审视以前的差分线索搜索活动。
![练习3：哈希[上次更新1月22日] ...](/simg/e/e27da91d810d00573e3ca2c788b9139b51c0291d.webp)
练习3：哈希[上次更新1月22日] ...
2。基于我在课堂上提供的用户名和哈希密码的简单方案，以及您自己忘记密码的经验，描述用户忘记他/她的密码并单击登录页面上的“忘记密码”链接时通常会做什么。以一个简单的情况，网络服务器将新（随机生成的）密码发送给用户。3。假设您可以窃取带有用户名和哈希密码的系统文件，并假设您知道用于密码的哈希功能。这会让您访问系统上的用户帐户吗？4。假设您知道某人的登录名，并且知道一个与他们的密码不同的密码，但是其他密码具有与密码相同的哈希值。这是否可以让您登录他们的帐户？5。假设您使用开放的哈希（链接），并插入以下键：5、28、19、15、20、33、12、17、10和m = 9。为简单起见，在这里我们没有将密钥与其哈希码区分开，因此我们假设H（key）=键。发生碰撞发生哪些插槽？6。现在假设您使用线性探测使用封闭的散列，并且插入了与上面相同的键。发生的碰撞比上一个问题发生的更多。碰撞在哪里发生，钥匙最终到达哪里？7。Java具有一个称为Hashset 的类，用于表示E类型E类型的对象。Ashset使用E类E类的HashCode（）方法和Hashmap 使用k类HashCode（）类方法和两者都使用hash表。在每种情况下，在哈希表存储桶中存储了什么？8。（假设打开哈希，即链接列表。）对于二次探测，请注意，如果m = 2500，则二次步骤大小将导致步骤i = 50的“自碰撞”，因为i*i = 50*50 =2500。但是，课堂上给出的结果表明，直到i = m/2，第一次自我碰撞才会发生。这似乎是一个矛盾。这个论点有什么问题？9。[1月18日更新]这个问题假设您在基本概率理论中具有一些背景。假设n键是随机选择的，哈希函数在{0，1，…，M-1}上随机分配键。
