当前位置： 首页 > news >正文

【格密码基础】：详解Ring-SIS问题

news 来源：原创 2024/5/12 3:58:09

目录

一. 介绍

二. Ring-SIS问题相关的参数

三. Ring-SIS问题定义

四. 相比SIS问题的优点

五. 与SIS问题之间的关系

一. 介绍

在1998年，有关多项式环密码系统NTRU被提出。Ajtai提出了原始的SIS问题。

在2002年，Micciancio发现可以将这两者结合，提出了效率更高的密码学上问题，也就是本文章将要介绍的SIS问题，已经对应的函数f_A。

在格密码专栏中，我将陆续更新Ring-SIS问题的定义，它与原始SIS问题的关系，其在最坏情况（worst case）下的困难性分析。而且还包含在环结构下，形成一个新的概念叫理想格（ideal lattice）。

二. Ring-SIS问题相关的参数

通常我们可以把环结构R看成一个次数为n的多项式，完整结构如下：

下面的多项式有f(x)有两者常用的结构。第一个是2002年提出的：

f(X)=X^n-1

第二个是2008年被提出，其指数是2的幂形式，如下：

f(X)=X^{2^k}+1

这个地方可以直观上把环R看成任意多项式模f(X)运算的结果，这样的话，最终就是一个整数的多项式，其次数小于n

环R内的每个元素，也有模的理解，通常写做：

||\cdot||

可以简单将其看成扩展的系数向量对应的模长。在环R上选择一个向量z，那么其模长可理解为：

如果对以上多项式的系数大小进行限制的话，那么可以把每个数都模q，那么可以形成新的环，如下：

R_q=R/qR=Z_q[X]/(f(X))

那么现在每个环上的元素代表次数小于n，系数从整数环Zq内进行选取的元素。

Ring-SIS问题的关键在于限定结果的模长，那么需要给定一个实数模的上限，如下：

\beta>0

样本的个数通常设定为m

在SIS问题中，同样的几个参数：次数n，模q，长度上限\beta。当然相比SIS问题中的m，Ring-SIS问题只需要少n倍的样本个数即可。

三. Ring-SIS问题定义

带参数的环SIS问题，可简写为如下：

给定m个均匀且随机分布的a，如下：

也可以将其写成向量的格式如下：

在满足如下等式的情况下：

我们的目标是寻找到对应的非零向量z，如下：

z\in R^m\quad ||z||\leq \beta

注意此处的z为m维向量，向量的每个位置都是一个多项式。

四. 相比SIS问题的优点

Ring-SIS问题的效率性更高一点。解释如下：

在Ring-SIS中，样本a的格式如下：

a_i\in R_q

为了需要保证短解的存在，样本的个数是有要求的：

然而在原始的SIS问题中，需要多n倍的样本，如下：

简单给个解释。从环内任意取一个元素：

z_i\in R

该元素就是一个次数小于n的多项式，所以其短的情况个数有：

2^{\Omega(n)}

这些短解将会作为a的系数。

然而在SIS问题中，a的格式如下：

a_i\in Z_q^n

其短解存在的个数会更少一些。

在计算意义上，环结构的效率也要更高一些。在Ring-SIS问题，我们需要计算如下：

利用FFT技术，我们计算的复杂度只需要拟线性（quasi-linear）时间，通常记为：

\tilde O(n)

选择合适的模数q和样本数m，那么计算如下函数也近似拟线性时间：

五. 与SIS问题之间的关系

SIS问题与Ring-SIS问题之间有相似的代数性质。在网络安全领域，一个密码系统两者之间往往可以互相转换。当然这种转换往往需要说清楚其中的安全性证明（security proof)。

在这里我将举一个例子来解释有环结构和无环结构之间的联系。

在Ring-SIS中，我们需要均匀且随机的取一个环元素，如下：

a_i\in R_q

在SIS中这对应着n维的向量，当然向量不同位置元素之间是有联系的，如下：

a_i\in Z_q^n

可以把此处的n看成整数Z上环R的系数（degree）。

那么借助这种理解，环-SIS问题的答案格式如下：

z_i\in R

就对应着SIS问题答案中的n个整数。

根据经验主义，原始SIS问题带有一种特殊的结构（instance），就可以形成Ring-SIS.

（1）利用格的观点看环多项式

可以把环R内的元素看成由整数格基产生，那么环R则是n维的，对应关系如下：

R\quad Z^n

类似的，可得：

R_q\quad Z_q^n

这种对应关系其实就是抽象代数中的加法群同态（additive group isomorphism）。在这种理解下，短解是可以类推的。

可以把环R的结构看成如下：

那么单项式X^i对应着第(i+1)个基向量e，如下：

e_{i+1}\in Z^n\quad i=0,\cdots,n-1

那么环-SIS问题中的z格式如下：

\vec{z}\in R^m

对应SIS中的维度也就是nm，如下：

z\in Z^{nm}

（2）环内乘法

如果从商环中选择一个元素a，如下：

a\in R_q

让后将任意其他环元素进行与之相乘，那么就相当于是一种Z-Linear函数运算过程：

R to Rq

将此相乘的过程可以看成乘以一个n维方阵，如下：

A_a\in Z_q^{n\times n}

看成矩阵相乘的话，那么这个过程对应着映射：

Z^n to Z_q^n

比如我们来看一个例子。

给定一个环结构如下：

那么商环Rq内的元素a就对应着循环矩阵，矩阵第一列的元素就是系数向量a。这样子来看的话，我们可以从Ring-SIS中给出一个instance，如下：

每一个ai都对应着一个循环矩阵，那么其在SIS中对应的instance如下：

以上理解的根源来自于抽象代数（abstract algebra），有很多跟群环域相关的理解，有时间的话，在本专栏会陆续补充相关的基础数学在网络安全中的应用。

相关文章：

  • 关于Python运用pyecharts实现简单的数据分析-——柱状图、饼状图
  • 计算机网络-数据交换方式（电路交换 报文交换 分组交换及其两种方式 ）
  • springboot(ssm同城上门喂遛宠物系统 宠物预约系统Java系统
  • 提升工作效率，畅享便捷PDF编辑体验——Adobe Acrobat Pro DC 2023
  • 分类预测 | Matlab实现DT决策树多特征分类预测
  • 计算机网络_1.3电路交换、分组交换和报文交换
  • 3338 蓝桥杯 wyz的数组IV 简单
  • 每次请求sessionid变化【SpringBoot+Vue】
  • Docker consul的容器服务更新与发现
  • k8s中调整Pod数量限制的方法
  • 【C++】STL之空间配置器（了解）
  • 【数据结构 08】红黑树
  • 2024前端面试总结—JS篇（文档持续更新中。。。）
  • EasyExcel导出Excel和多个图片到Zip，并实现超链接
  • 为什么pgsql(内关联查询或者with字句时)会导致索引失效
  • JavaScript-如何实现克隆(clone)函数
  • 【面试系列】之二：关于js原型
  • 【腾讯Bugly干货分享】从0到1打造直播 App
  • C++11: atomic 头文件
  • docker python 配置
  • Docker下部署自己的LNMP工作环境
  • Git同步原始仓库到Fork仓库中
  • Javascript编码规范
  • JS题目及答案整理
  • React的组件模式
  • Tornado学习笔记（1）
  • 探索 JS 中的模块化
  • 吐槽Javascript系列二：数组中的splice和slice方法
  • 第二十章：异步和文件I/O.（二十三）
  • ​卜东波研究员：高观点下的少儿计算思维
  • #前后端分离# 头条发布系统
  • %@ page import=%的用法
  • （Redis使用系列） SpringBoot 中对应2.0.x版本的Redis配置 一
  • (TipsTricks)用客户端模板精简JavaScript代码
  • （附源码）ssm教材管理系统 毕业设计 011229
  • （附源码）ssm跨平台教学系统 毕业设计 280843
  • (免费分享)基于springboot,vue疗养中心管理系统
  • （转载）Linux网络编程入门
  • ./mysql.server: 没有那个文件或目录_Linux下安装MySQL出现“ls: /var/lib/mysql/*.pid: 没有那个文件或目录”...
  • .equals()到底是什么意思？
  • .net core MVC 通过 Filters 过滤器拦截请求及响应内容
  • .NET 中 GetHashCode 的哈希值有多大概率会相同（哈希碰撞）
  • .Net多线程总结
  • .NET中统一的存储过程调用方法(收藏)
  • ::前边啥也没有
  • @RequestBody与@ModelAttribute
  • [ABC294Ex] K-Coloring
  • [APIO2012] 派遣 dispatching
  • [C/C++]数据结构 循环队列
  • [C++从入门到精通] 14.虚函数、纯虚函数和虚析构(virtual)
  • [CTF]2022美团CTF WEB WP
  • [FC][常见Mapper IRQ研究]
  • [Flutter]WindowsPlatform上运行遇到的问题总结
  • [IE6 only]关于Flash/Flex,返回数据产生流错误Error #2032的解决方式
  • [IE技巧] 让IE 以全屏模式启动