格密码学习笔记(七):密码学中的q相关格、简介SIS问题和LWE问题

2023-10-09 07:59

本文主要是介绍格密码学习笔记(七):密码学中的q相关格、简介SIS问题和LWE问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • Q Q Q-相关格
  • Ajtai提出的单向函数(SIS)
  • Regev提出的容错学习问题(LWE)
  • 详细规约证明讲解
  • 致谢

Q Q Q-相关格

密码学中通常使用符合以下2个性质的(随机)格 Λ \Lambda Λ构造具体方案:

  • Λ ⊆ Z d \Lambda \subseteq \mathbb{Z}^d ΛZd是一个整数格;
  • q Z d ⊆ Λ q \mathbb{Z}^d \subseteq \Lambda qZdΛ对小整数 q q q取模后呈现周期性。

定义( q q q-相关格, q q q-ary lattice) 如果格 Λ \Lambda Λ满足 q Z n ⊆ Λ ⊆ Z n q \mathbb{Z}^n \subseteq \Lambda \subseteq \mathbb{Z}^n qZnΛZn,则称 Λ \Lambda Λ是一个 q q q-相关格。

注:这里的“-ary”有“与…有关”的意思,如果翻译为“阶”感觉怪怪的,如果是 q q q-阶群,感觉群里得有 q q q个元素,但定义里又没有体现。

什么是 q q q-相关格?举2个例子,对于任意 A ∈ Z q n × d \bm{A} \in \mathbb{Z}_q^{n \times d} AZqn×d,有

  • Λ q ( A ) = { x ∣ x m o d q ∈ A ⊤ Z q n } ⊆ Z d \Lambda_q(\bm{A}) = \{ \bm{x} | \bm{x} ~ \mathrm{mod} ~q \in \bm{A}^\top \mathbb{Z}^n_q \} \subseteq \mathbb{Z}^d Λq(A)={xx mod qAZqn}Zd
  • Λ q ⊥ ( A ) = { x ∣ A x = 0 m o d q } ⊆ Z d \Lambda^\perp_q(\bm{A}) = \{ \bm{x} | \bm{Ax} = \bm{0} ~ \mathrm{mod} ~ q \} \subseteq \mathbb{Z}^d Λq(A)={xAx=0 mod q}Zd

定理 对于任意格 Λ \Lambda Λ,以下3个 q q q-相关格判断条件是等价的:

  • q Z d ⊆ Λ ⊆ Z d q \mathbb{Z}^d \subseteq \Lambda \subseteq \mathbb{Z}^d qZdΛZd
  • 存在某些 A \bm{A} A满足 Λ = Λ q ( A ) \Lambda = \Lambda_q(\bm{A}) Λ=Λq(A)
  • 存在某些 A \bm{A} A满足 Λ = Λ q ⊥ ( A ) \Lambda = \Lambda^\perp_q(\bm{A}) Λ=Λq(A)

注意: 对于同一个 A \bm{A} A,格 Λ q ( A ) \Lambda_q(\bm{A}) Λq(A)和格 Λ q ⊥ ( A ) \Lambda^\perp_q(\bm{A}) Λq(A)是不同的。而对于一个 A ∈ Z q n × d \bm{A} \in \mathbb{Z}^{n \times d}_q AZqn×d,存在 A ′ ∈ Z q k × d \bm{A}' \in \mathbb{Z}^{k \times d}_q AZqk×d,使得 Λ q ( A ) = Λ q ⊥ ( A ′ ) \Lambda_q(\bm{A}) = \Lambda^\perp_q(\bm{A}') Λq(A)=Λq(A)。反过来亦如此。

对于同一个 A \bm{A} A Λ q \Lambda_q Λq Λ q ⊥ \Lambda_q^\perp Λq存在放缩对偶关系,即

  • Λ q ( A ) ∨ = 1 q Λ q ⊥ ( A ) \Lambda_q(\bm{A})^\vee = \frac{1}{q} \Lambda^\perp_q(\bm{A}) Λq(A)=q1Λq(A)
  • Λ q ⊥ ( A ) ∨ = 1 q Λ q ( A ) \Lambda^\perp_q(\bm{A})^\vee = \frac{1}{q} \Lambda_q(\bm{A}) Λq(A)=q1Λq(A)

Ajtai提出的单向函数(SIS)

Ajtai在1996年提出了基于 q q q相关随机格的单向函数(One-Way Function,OWF),并给出了安全性证明。这里的SIS是Short Integer Solution的缩写。该OWF构造如下图。在这里插入图片描述
定理 对于 m > n l g q m > n ~ \mathrm{lg} ~ q m>n lg q,若SIVP问题在最差情况下依旧是困难的,那么 f A ( x ) = A x m o d q f_{\bm{A}}(\bm{x}) = \bm{Ax} ~ \mathrm{mod} ~ q fA(x)=Ax mod q是单向函数。

这里简要给出抗碰撞单向的证明思路,后续公开课Daniele Micciancio教授有给出详细证明。

  • f A ( x ) = A x m o d q f_{\bm{A}}(\bm{x}) = \bm{Ax} ~ \mathrm{mod} ~ q fA(x)=Ax mod q,这里的 x \bm{x} x是一个短向量,即一个二进制向量;
  • f A f_{\bm{A}} fA q q q相关矩阵 Λ q ⊥ ( A ) \Lambda^\perp_q(\bm{A}) Λq(A),注意: ∀ v ∈ Λ q ⊥ ( A ) \forall \bm{v} \in \Lambda^\perp_q(\bm{A}) vΛq(A),有 f A ( v ) = 0 m o d q f_{\bm{A}}(\bm{v}) = \bm{0} ~ \mathrm{mod} ~ q fA(v)=0 mod q
  • 寻找碰撞 ( ( x , y ) s.t.  f A ( x ) = f A ( y ) ) \big( (\bm{x}, \bm{y}) ~ \text{s.t.} ~ f_{\bm{A}}(\bm{x}) = f_{\bm{A}}(\bm{y}) \big) ((x,y) s.t. fA(x)=fA(y))等价于寻找一个短向量 ( v = x − y ) ∈ Λ q ⊥ ( A ) ( \bm{v} = \bm{x} - \bm{y} ) \in \Lambda^\perp_q(\bm{A}) (v=xy)Λq(A),这里相当于求解了 Λ q ⊥ ( A ) \Lambda^\perp_q(\bm{A}) Λq(A)的SVP / SIVP问题;
  • f A ( x ) f_{\bm{A}}(\bm{x}) fA(x)求逆相当于求解伴随译码格式下的CVP问题,CVP问题的输入为 Λ q ⊥ ( A ) \Lambda^\perp_q(\bm{A}) Λq(A) t ∈ x + Λ q ⊥ ( A ) \bm{t} \in \bm{x} + \Lambda^\perp_q(\bm{A}) tx+Λq(A),伴随译码的定义可以翻阅《格密码学习笔记(六):格中模运算》。即已知 f A ( x ) f_{\bm{A}}(\bm{x}) fA(x),对其求逆得到一个长向量 t \bm{t} t t \bm{t} t x \bm{x} x Λ q ⊥ ( A ) \Lambda^\perp_q(\bm{A}) Λq(A)中对应同一个陪集,找到 x \bm{x} x,则 t − x \bm{t} - \bm{x} tx即CVP问题的格点解;
  • f A f_{\bm{A}} fA是一个压缩函数,那么 x \bm{x} x的长度需要大于 1 2 λ 1 ( Λ q ⊥ ( A ) ) \frac{1}{2}\lambda_1(\Lambda^\perp_q(\bm{A})) 21λ1(Λq(A))(这块个人不怎么理解)。

注意, S I S ≡ Approximate  A D D \mathsf{SIS} \equiv \text{Approximate} ~ \mathsf{ADD} SISApproximate ADD(绝对距离解码)。

Regev提出的容错学习问题(LWE)

Regev在2005年提出Learning With Errors(LWE)。Learning(学习) 这个词常见于机器学习中,一个完整的机器学习方法包括模型学习算法两部分,这里的“学习”可以理解成“figure out”,即求解出问题的解(从中学到某种知识)。LWE问题定义如下图。

在这里插入图片描述

LWE与SIS看起来有点不一样,但某种程度上这两者之间是对偶关系。在LWE问题中,输入和错误向量 e \bm{e} e比SIS的向量短得多,得到的函数是单射的,安全性证明难度更大。

定理 若SIVP问题在最坏情况下是困难的,则函数 g A ( s , e ) g_{\bm{A}}(\bm{s}, \bm{e}) gA(s,e)在多数情况下难以求逆。

  • 如果 e = 0 \bm{e} = \bm{0} e=0,那么 A s + e = A s ∈ Λ ( A ⊤ ) \bm{As} + \bm{e} = \bm{As} \in \Lambda(\bm{A}^\top) As+e=AsΛ(A),这里的转置请往上回翻 Λ q ( A ) \Lambda_q(\bm{A}) Λq(A)的定义;
  • e ≠ 0 \bm{e} \neq \bm{0} e=0,则相当于求解 q q q相关随机格 Λ ( A ⊤ ) \Lambda(\bm{A}^\top) Λ(A)和随机向量 t = A s + e \bm{t} = \bm{As} + \bm{e} t=As+e的CVP问题(注意这里没有SIS中的伴随译码形式,所以某种程度上与SIS之间存在对偶关系);
  • 一般情况下, e \bm{e} e的长度小于 1 2 λ 1 ( Λ ( A ⊤ ) ) \frac{1}{2}\lambda_1\big(\Lambda(\bm{A}^\top)\big) 21λ1(Λ(A)),且 e \bm{e} e是唯一确定的。

注意, L W E ≡ Approximate  B D D \mathsf{LWE} \equiv \text{Approximate} ~ \mathsf{BDD} LWEApproximate BDD(有界距离解码)。

详细规约证明讲解

推荐看Steven Yue大佬写的知乎文章(收录于稀有气体专栏)。

致谢

  • Simons格密码公开课官网
    Mathematics of Lattices - Simons Institute for the Theory of Computing
  • 哔哩哔哩中英双语视频(字幕组:重庆大学大数据与软件学院 后量子密码研究小组)
    【中英字幕】Simons格密码讲座第1讲:格的数学定义_哔哩哔哩_bilibili
  • 其它格密码讲解课程和博文
    Lattice学习笔记04:SIS与LWE问题
    公开学习资料的无私奉献者

这篇关于格密码学习笔记(七):密码学中的q相关格、简介SIS问题和LWE问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/171462

相关文章

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

JavaScript Array.from及其相关用法详解(示例演示)

《JavaScriptArray.from及其相关用法详解(示例演示)》Array.from方法是ES6引入的一个静态方法,用于从类数组对象或可迭代对象创建一个新的数组实例,本文将详细介绍Array... 目录一、Array.from 方法概述1. 方法介绍2. 示例演示二、结合实际场景的使用1. 初始化二

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给

Java程序运行时出现乱码问题的排查与解决方法

《Java程序运行时出现乱码问题的排查与解决方法》本文主要介绍了Java程序运行时出现乱码问题的排查与解决方法,包括检查Java源文件编码、检查编译时的编码设置、检查运行时的编码设置、检查命令提示符的... 目录一、检查 Java 源文件编码二、检查编译时的编码设置三、检查运行时的编码设置四、检查命令提示符