格密码基础:NTRU格
目录
一. 介绍
NTRU是1998年由 Brown大学三位数学家 Silverman、Hoffstein和 Pipher提出的公钥密码算法,将其命名为NTRUEncrypt。该密码算法是基于格的,所以被认为具有抵抗量子计算攻击能力。又因为已知 NTRU公钥求解私钥的问题可规约到相应格中求解最短向量问题。有关格上最短向量问题,大家可以看这篇博客:
格密码基础:详解最短向量问题(SVP)以及攻击算法_svp加密-CSDN博客
所以除了利用传统方法对 NTRU 密码安全性进行分析,也可以通过求解格中最短向量恢复 NTRU 密钥.
NTRU密码的发展历程大概如下:
- 2003年日本索尼公司与 NTRU 公司合作,将基于 NTRU 的数字签名算法 NTRUSign应用于嵌入式设备和IC卡等领域;
- 2008年恩智浦半导体公司与 NTRU 公司合作,推出了首款用于通用型 ARM7微控制器的基于软件的加密解决方案;
- 2008年基于 NTRU 的加密算法和签名算法的标准IEEEp1361.1正式通过;
- 2017 年 11 月开始征集后量子密码算法, 三个 NTRU 加密算法(NTRUEncrypt, NTRU Prime, NTRU HRSS)和两个 NTRU 签名算法(pqNTRUSign, Falcon)进入了第一轮评估;
?
NTRU密码系统是第一个基于多项式环结构设计出的密码系统,也就是所谓的代数结构格(所以有的时候也会出现“NTRU格”的说法)。
二. NTRU加密方案
2.1 公共参数
选择一个多项式f(x),如下:
要求该多项式的次数n为素数。
该多项式还有另外一个选择:
此时要求该多项式的次数n为2的指数形式(也就是)(a power of two)。
备注:这样选的原因参照抽象代数中多项式环的理解。
接着根据该多项式可形成如下多项式环(polynomial ring):
选择一个足够大的素数q,就可以形成如下商环(quotient ring):
2.2 公钥
从环R中选择两个多项式,要求这两个多项式的系数相对较小,接着计算:
此处的h即为公钥,可以公开。
2.3 私钥
元素s即为私钥。要求私钥s可逆,更准确来讲要求在模q和模2情况下都要可逆。很明显,已知两个多项式相乘的结果,推导任何一个多项式都是困难的,也就是已知公钥推导私钥是难的。
2.4 加密过程
将需要加密的明文编码进一个短的,该项又被称之为short error term。
密码学的加密过程需要选择随机数,此处从环R中随机取一个元素,接着借助公钥计算如下:
2.5 解密过程
将私钥直接乘以密文,得到:
接着对该结果进行模2运算,便可以得到es,其中s为私钥是已知的,接着便可以恢复出e,也就是恢复出明文比特。
其实以上过程还有个更加直观的理解。如果私钥选择的特征如下:
那么可得:
三. NTRU困难问题
备注:密码学中通常将困难问题分成search问题与decision问题。
NTRU密码方案相关的search问题:从公钥推私钥;公布方案的语义安全(semantic security);
NTRU密码方案相关的decision问题:区分公钥分布和均匀分布;
补充此处谈到的语义安全:
公钥密码体制的安全性可通过语义安全性、不可区分性、不可扩展安全性 、明文可意识性等加密效果来评估 。
语义安全:无法从密文中提取任何明文信息 ,则从语义上说这种加密是安全的。因此 ,语义安全性是保密性的直接决定因素 。相对 Shannon的绝对安全理论,可将语义安全性视作计算版本的绝对安全性。
NTRU密码为啥跟格密码相关呢?请看四:
四. NTRU格
4.1 介绍
NTRU格本质上是多项式环上的q元格。
从多项式环上取两个短向量,计算:
当然还有另外一种计算方式:
类比SIS问题,NTRU对应的q元垂直格如下:
看过我之前博客的小伙伴可能会知道,这个和整数环Z上定义的q元垂直格是类似的。其中h可以看成公钥(为一个多项式),“1”也可以看成多项式,那么x则包含二维多项式,所以,垂直格的运算本质就是模q为0.
于是乎,我们可以得到NTRU的q元垂直格的陪集:
类似将q元垂直格平移了向量u
基于以上信息, NTRU 的加密方案使用 q 元格构造:
解密相当于求解格 上的最近向量问题(closest vector problem, CVP)。该问题与带错误的学习问题 (learning with errors, LWE) 相似。
NTRU的签名方案使用 q 元垂直格的陪集构造:
签名与非齐次短整数解问题 (inhomogeneous short integer solution, ISIS) 相似, 即求垂直格的短向量:
4.2 NTRU与短向量
通过以上讨论,我们发现NTRU假设是指已知h , 求f和g是困难的。短向量f和g目前有两种抽样的方法, 一种是每个系数从 或 中选取, 有固定个数的 1 及–1。采用这类分布时,很难讲NTRU 假设归约到格上的困难问题。
另一种分布是系数取自高斯分布, Stehlé和Steinfeld将采用高斯分布情况下的 NTRU 假设归约到了理想格上最坏情况下的困难问题, 在一定程度上得到了理论归约的保证, 但此时参数要求过大, 不适用于实用的方案。
小结
基于 NTRU格实现的方案具有结构简洁、密钥密文尺寸小的优点, 是利于实用化的方案。虽然目前在理论归约方面还未能获得保证, 但提出以后还无有效的攻击算法, 从攻击角度在方案安全性方面得到了保证。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!