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

更多资讯

Java聊天系统设计与实现：Socket多线程并发编程实战

DouK-Downloader 完整教程：三步快速批量下载抖音和 TikTok 作品

Spring Boot外卖点餐系统实战：角色权限、订单状态机与部署排错全解析

G-Helper 完全指南：华硕笔记本性能控制如何做到轻量又够用

YOLO-IOD: Towards Real Time Incremental Object Detection——迈向实时增量目标检测

第六篇：Sim2Real 深度解析——如何让仿真中的智能体走进现实

今日更新

Linux 内核 ARM 虚拟内存布局全解析：从 4GB 地址空间划分到源码级验证

AIGC降重工具测评与教育应用指南

数据容灾核心指标与实战方案解析

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

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