A Gentle Introduction to Lattice-Based Cryptography 第四章：容错学习（LWE）问题部分练习题-北京尧图网络

《A Gentle Introduction to Lattice-Based Cryptography》格密码学温和入门是密码学界知名学者、滑铁卢大学University of Waterloo教授Alfred Menezes编写的一份高质量开源讲义。这份讲义专门为高年级本科生和初入学的研究生设计旨在用最通俗易懂、循序渐进的方式揭开后量子密码学Post-Quantum Cryptography, PQC中“格密码”的神秘面纱。练习 4.1编写一个程序寻找满足以下实例的所有解思路对于这种小规模的 LWE 实例我们依旧可以使用暴力搜索。但是如果同时搜索共种可能和共种可能总的组合数会达到。我们可以利用公式的等价变形来极大缩减搜索空间由于误差向量 $e$ 的每一个分量都必须落在临界的区间内即模 $53$ 意义下的。我们只需要对秘密向量的所有可能进行网格搜索只需搜索万个点对每个候选的计算出对应的误差。检查这个的每个分量是否都满足临界条件。如果满足则该为可行解对应的也能直接算出来。完整代码如下所示import numpy as np # 1. 初始化输入数据 A np.array([ [24, 4, 37], [51, 41, 17], [ 2, 11, 13], [44, 52, 50], [ 1, 0, 2] ]) b np.array([5, 3, 12, 10, 6]) m 5 n 3 q 53 B 2 # 2. 生成 s 的全部搜索空间 # s 的每个分量取值在 [0, q-1] s_vals np.arange(q) # 使用 meshgrid 生成 3 维网格并重塑为 (53^3, 3) grid np.meshgrid(s_vals, s_vals, s_vals, indexingij) S_space np.stack(grid, axis-1).reshape(-1,3) # 3. 批量计算并求解误差 e # 计算 A * s (mod q) # A 形状为 (5, 3)S_space.T 形状为 (3, 148877) - AS 形状为 (5, 148877) AS np.dot(A, S_space.T) % q # 计算误差 e (b - As) (mod q)结果形状为 (5, 148877) E_space (b.reshape(-1,1) - AS) % q # 4. 筛选满足短整数约束的列 # 在模 53 意义下满足 |e_i| 2 的合法误差取值集合为 {0, 1, 2, 51, 52} vaild_errors [0, 1, 2, q-2, q-1] # 使用 np.isin 检查 E_space 中每个元素是否在合法集合中 # np.isin 得到一个形状相同的布尔矩阵再用 np.all(..., axis0) 确保该列的所有 5 个误差全都合规 mask1 np.isin(E_space, vaild_errors) mask np.all(mask1, axis0) # 5. 输出最终解 (s, e) matching_s S_space[mask] matching_e E_space[:, mask].T # 将模 53 下的误差 [51, 52] 映射回负数 [-2, -1] 便于直观观察 matching_e_mapped np.where(matching_e q // 2, matching_e - q, matching_e) print(f共找到 {len(matching_s)} 组解\n) for i in range(len(matching_s)): print(f解对 {i1}:) print(f s {matching_s[i]}) print(f e {matching_e_mapped[i]})练习 4.2寻找满足以下实例的所有解具体思路可以参考上一题的解题思路import numpy as np # 1. 初始化数据 A np.array([ [ 5, 22, 14, 47], [45, 25, 17, 49], [39, 14, 26, 51], [31, 9, 46, 24] ]) b np.array([36, 14, 46, 30]) q 53 B 3 # 边界 beta 3 # 2. 生成短秘密 s 的搜索空间 s_vals np.array(range(-B, B 1)) # [-3, -2, -1, 0, 1, 2, 3] grid np.meshgrid(s_vals, s_vals, s_vals, s_vals, indexingij) S_space np.stack(grid, axis-1).reshape(-1,4) # 3. 批量计算误差 e AS np.dot(A, S_space.T) % q E_space (b.reshape(-1,1) - AS) % q # 4. 筛选合格的误差 e # 合法误差值在 [-3, 3] 区间模 53 映射为 {0, 1, 2, 3, 50, 51, 52} vaild_errors [0, 1, 2, 3, q-3, q-2, q-1] mask np.all(np.isin(E_space, vaild_errors),axis0) # 5. 输出结果 matching_s S_space[mask] matching_e E_space[:, mask].T matching_e_mapped np.where(matching_e q // 2, matching_e - q, matching_e) print(f共找到 {len(matching_s)} 组解\n) for i in range(len(matching_s)): print(f解对 {i1}:) print(f s {matching_s[i]}) print(f e {matching_e_mapped[i]})

A Gentle Introduction to Lattice-Based Cryptography 第四章：容错学习（LWE）问题部分练习题

相关推荐

智慧出入口管理系统是什么？如何提升园区人车通行管理效率

深入解析TMS320F2838x I2C驱动：从寄存器到Driverlib函数映射与实战

Freeze.rs快速上手：3分钟生成你的第一个EDR绕过Payload

更多资讯

电工证复训什么意思值不值得考

低压电工作业检查怎么考不白交钱？网上查询全搞定

国家低压电工证难考吗？官方报名入口详解+备考攻略

石河子低压电工证千万别踩坑：证书过期了不知道怎么复审延期怎么办

装修半截换电工证吗？工地太忙根本没时间复习考试，多久拿证能解决这个问题？

工地太忙根本没时间复习考试？郑州理工电工证多久拿证，看这里！

今日更新

金坛办电工证在哪里？考前押题能帮你少走弯路

怎样查看真假电工证怎么考

史密斯内部电工证值不值得考？怕考不过白交培训费的看过来

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？