双线性函数及其应用

i 本本科科生生毕毕业业论论文文 设设计计 题题 目 目 双线性函数及其应用双线性函数及其应用 专专 业 业 数学与应用数学数学与应用数学 学学 号号 学生姓名 学生姓名 i i 目目 录录 摘要 关键词 1 Abstract Key words 1 前言 2 1 常用的欧式空间 1 2 双线性函数 2 2 1 线性函数的简单性质 2 2 1 1 线性函数的定义 2 2 1 2 线性空间的性质 3 2 1 3 对偶基 3 2 2 双线性函数的内容及性质 3 2 2 1 双线性函数的性质 3 2 2 2 双线性函数的内容 3 3 双线性函数在不同基下的矩阵 4 3 1 双线性函数在不同基下的矩阵之间的关系 4 3 2 相同基下 不同的双线性函数所对应的矩阵 5 4 双线性函数与辛空间及对偶空间 6 4 1 双线性函数与辛空间 7 4 2 双线性函数与对偶空间 10 5 双线性函数的应用领域 13 6 结束语 14 参考文献 14 致谢 1 第 1 页 双线性函数及其应用 摘要摘要 在以往的密码学研究当中 双线性配对函数 Weil 配对和 Tate 配对 通常被用在密码 分析学中 通过使用配对函数 可以将某些椭圆曲线上的离散对数问题约减到有限域上的离 散对数问题 近些年来 密码学家发现 如果对配对函数进行适当的改动 并应用在某些合 适的椭圆曲线上 就可以构造出低带宽的 可证明安全的 provable secure 基于双线性配 对函数的加密 签名和密钥协商等协议 这些突破性的工作为密码协议的构造开辟了新的 思路 由于双线性配对函数所具有的特性 可以用来设计一些具有特殊性质的密码协议 这些 协议一般很难用其他方法实现 或者即使可以实现 其效率也没有基于双线性配对函数的高 例如短签名 三方一轮的密钥协商协议 基于身份的加密方案等 本文主要研究双线性 配对函数在构造新的密码协议方面的应用 主要研究内容包括 1 总结了双线性配对函数 的概念 所具有的特性 并介绍了 Diffie Hellman 难题以及双线性配对函数在密码学中的应 用 2 提出了一个使用双线性配对函数的前向安全的数字签名方案 在一个基于双线性配对 函数的签名方案的基础上构造了一个前向安全的签名方案 文中对方案的安全性进行了分 析 并与已有的一些前向安全的签名方案进行了比较 结果表明该方案在效率和签名长度上 有一定的优势 3 本文对这样一种情况提出了解决方案 多个用户将加密数据 使用 Alice 的 公钥 发送到不完全可信的数据存储服务器上 例如邮件服务器和文件服务器等 如果 Alice 想让服务器能够查询加密文档是否含有某些单词并反馈结果 但同时又不希望给予服 务器解密数据的能力 在这种情况下 需要特殊的技术来处理 本文构造了一个可查询的 基于公钥并与流密码结合的 使用双线性配对函数的加密系统 它能让服务器进行查询 而 又不失数据的机密性 在该方案中 服务器并不能了解比查询结果更多的关于明文的信息 且当只给定密文时 不被信任的服务器不能得到关于明文的信息 4 提出了一个盲聚合签 名方案 它结合了盲签名和聚合签名两者的优点 使生成的盲签名聚合为一个聚合签名 节省 了时间和存储空间 也降低了对传输带宽的要求 关键词 关键词 双线性函数 矩阵的合同 矩阵的相似 Abstract In the past the cryptography studies bilinear pairing function Weil pairing Tate and matching are usually used in analysis in learning password through the use of matching function can will some of the elliptic curve discrete logarithm problem about reduced to a limited domain of discrete logarithm problem In recent years cryptography home found that if properly to visual function changes and application in some appropriate elliptic curve it can be constructed out of the low bandwidth can prove safe provable secure based on bilinear pairings function of encryption signatures and key agreement protocol etc These breakthrough for the construction of the password agreement opened up a new train because bilinear pairings is the features of a function can be used to design some has certain types of password agreement these agreements with other method very hard commonly or even can realize its efficiency and no based on bilinear pairings function of high For example three square round short signature of key agreement protocol identity based encryption scheme This paper makes a study of the bilinear pairings function in the construction of new password agreement applications The main research contents include 1 summarized the bilinear pairings function concept has the characteristics and introduced the diffie hellman problem and bilinear pairings function in the application of cryptography 2 put forward a using bilinear pairings of function to safety before digital signature scheme in a based on bilinear pairing the signature scheme based on the structure of a prior to the safety of the signature scheme In this paper the safety of the scheme are analyzed and some have to safety before the signature schemes are compared and 双线性函数及其应用 第 2 页 the results show that the scheme in efficiency and signature length have a certain advantages 3 in this paper put forward such a solution multiple users will be encrypted data use Alice public key sent to not completely reliable data storage server such as mail servers and file servers etc If Alice wants to let the server can inquires documentation is contain certain words encryption and feedback result but at the same time and don t want to give the server decrypt data ability In this case the need for special technology to deal with This paper constructs a can inquire based on public key and and flow of the combination of the password using bilinear pairings function encryption system it can make the query server and do not break data confidentiality In this scheme the server and can t understand the results more than inquires about expressly information And when only a given ciphertext not trusted server can t get about expressly information 4 put forward a blind signature scheme polymerization it combines blind signature and polymerization signature advantage of the two to generate the blind signature polymerization as a signature polymerization saving time and storage space also reduced of transmission bandwidth requirements Key words Double linear function and the matrix of the contract the matrix of the similar 前言前言 双线性函数是线性代数理论的一个重要内容 它涉及很多内容 如对称阵 反 对称阵 二次型 正交阵 辛阵等 特别地双线性函数与线性函数有密切关系 由 于研究关联着多个因素的量所引起的问题 则需要考察多元函数 如果所研究的关 联性是线性的 那么称这个问题为线性问题 历史上线性代数的第一个问题是关于 解线性方程组的问题 而线性方程组理论的发展又促成了作为工具的矩阵论和行列 式理论的创立与发展 这些内容已成为我们线性代数教材的主要部分 最初的线性 方程组问题大都是来源于生活实践 正是实际问题刺激了线性代数这一学科的诞生 与发展 另外 近现代数学分析与几何学等数学分支的要求也促使了线性代数的进 一步发展 1 1 常用的欧式空间常用的欧式空间 常用的欧式空间 1 线性空间 对如下定义的内积构成欧式空间 R n nnbbbaaa 2121 nnbababa 2211 2 线性空间对如下定义的内积构成欧式空间 baCxgxfbaC dxxgxfgf b a 2 2 双线性函数双线性函数 2 12 1 线性函数的简单性质线性函数的简单性质 2 1 12 1 1 线性函数的定义线性函数的定义 设是 V 上的线性函数 则 0 0 ff ff 如果的线性组合 那么 是 s 21ss kkk 2211 ss kkkf 2211 定理 设 V 是 P 上一个 n 维线性空间 是 V 的一组基 而 n 21 双线性函数及其应用 第 3 页 是 P 中任意 n 个数 存在唯一的 V 上线性函数使 n aaa 21 ff i i a ni 2 1 2 1 22 1 2 线性函数空间的性质线性函数空间的性质 设 V 是数域上 P 线性空间 V 上的全体线性函数的集合记为 L V P 定义 加法 L V P V gf f g gf 数乘 kfkf pkpVf 则 也是一个 p 上的线性空间 并称 为的对偶空间 pV pV V 2 1 32 1 3 对偶基对偶基 设为 的一组基 定义 则是的 n 21 V ji f ij ij 0 1 n fff 21 PV 一组基 称 为的对偶基 n fff 21 n 21 定理 的维数等于的维数 而且是 的一组基 PV V n fff 21 PV 定理 设 及 是线性空间的两组基 它们的对偶基分别 n 21 1 2 n V 与及 如果由到 的过渡矩阵为 A 那 n fff 21 n ggg 21 n 21 1 2 n 么由到的过渡矩阵为 n fff 21 n ggg 21 1 A 2 22 2 双线性函数的定义及性质双线性函数的定义及性质 2 2 12 2 1 双线性函数的性质双线性函数的性质 双线性函数 设是数域 P 上一个线性空间 是上一个二元函数 即对中任意两个 V f VV 向量都唯一地对应 P 中的一个数 记为 如果有以下性质 f f k k f ij ij 0 1 1 f 1 2 f 2 22112211 fkfkkkf V 2121 pkk 21 则称 为 上的双线性函数 f V 2 2 22 2 2 双线性函数的定义双线性函数的定义 一般地 双线性函数的定义如下 设 X Y 和 Z 为相同域 K 上的三个线性空间 当二元映射 对两个自变量都是线性映射时 则这样的二元映射 f 称之为从线性空间 X Y 到 Z 的一个双线性映射或双线性函数 此时 即函数的值域 换句话说 双线性函数的本质特征是 如果保持双线性映射的任一个自变量固定 不变 并留下另一个自变量作变元 则结果都是一个线性函数 这就是双线性函数的 偏线性 即对于 及 都成立 和 双线性函数及其应用 第 4 页 如下图所示 3 3 双线性函数在不同基下的矩阵双线性函数在不同基下的矩阵 3 13 1 双线性函数在不同基下的矩阵之间的关系双线性函数在不同基下的矩阵之间的关系 在不同的基下 同一个双线性函数的度量矩阵一般是不同的 它们之间的什么关 系呢 设及是线性空间的两组基 n 21 n 21 V C nn 2121 是中两个向量 V 12121 XX nn 12121 YY nn 那么 11 CYYCXX 如果双线性函数在及下的度量矩阵分别为 则有 f n 21 n 21 BA 1111 YACCXCYACXAYXf 又 11 BYXf 因此 双线性函数及其应用 第 5 页 ACCB 这说明同一个双线性函数在不同基下的度量矩阵是合同的 3 23 2 相同基下 不同的双线性函数所对应的矩阵相同基下 不同的双线性函数所对应的矩阵 设是数域上维列向量构成的线性空间 再设是上级方阵 令 n PPn n PYX APn 1 AYXYXf 则是上的一个双线性函数 YXf n P 如果设 并设 2121nn yyyYxxxX nnnn n n aaa aaa aaa A 21 22221 11211 则 2 n i n j jiij yxaYXf 11 1 或 2 实际上是数域上任意维线性空间上的双线性函数的一般形 PnV f 式 可以如下地说明这一事实 取的一组基 设 Vn 21 X x x x n n n 21 2 1 21 Y y y y n n n 21 2 1 21 则 3 n i n j jiji n i n j jjii yxfyxff 1111 令 njifa jiij 2 1 双线性函数及其应用 第 6 页 nnnn n n aaa aaa aaa A 21 22221 11211 则 3 就成为 1 或 2 设是数域上维线性空间上的一个双线性函数 是的一 f PnV n 21 V 组基 则矩阵 4 21 22212 12111 nnnn n n fff fff fff A 叫做在下的度量矩阵 f n 21 上面的讨论说明 取定的一组基后 每个双线性函数都对应于一个 Vn 21 级矩阵 就是这个双线性函数在基下的度量矩阵 度量矩阵被双线性函数 nn 21 及基唯一确定 而且不同的双线性函数在同一基下的度量矩阵是不同的 反之 任给数域上一个级矩阵 Pn nnnn n n aaa aaa aaa A 21 22221 11211 对中任意向量及 其中 V X n 21 Y n 21 21n xxxX 用 21n yyyY n i n j jiij yxaAYXf 11 定义的函数是上一个双线性函数 容易计算出在下的度量矩阵就 V f n 21 是 A 因此 在给定的基下 上全体双线性函数与上全体级矩阵之间的一个双射 VPn 4 4 双线性函数与辛空间及对偶空间双线性函数与辛空间及对偶空间 4 14 1 辛空间辛空间 1 主要定义 双线性函数及其应用 第 7 页 1 辛空间中一定能找到一组基满足 fV nn 2121 1 1 nif ii 0 0 jinjinf ji 这样的基称为的辛正交基 还可看出辛空间一定是偶数维的 fV 2 任一级非退化反对称矩阵可把一个数域上维空间化成一个辛空间 n2KPn2V 且使为的某基下度量矩阵 又此辛空间在某辛正交基KV nn 2121 下的度量矩阵为 nn 2121 1 nn OE EO J 22 故合同于 即任一级非退化反对称矩阵皆合同于 KJn2J 两个辛空间及 若有到的作为线性空间的同构 它满足 11 fV 22 fV 1 V 2 V 21 KvKufvuf 则称 是到的辛同构 11 fV 22 fV 到的作为线性空间的同构是辛同构当且仅当它把的一组辛正 11 fV 22 fV 11 fV 交基变成的辛正交基 22 fV 两个辛空间是辛同构的当且仅当它们有相同的维数 辛空间到自身的 辛同构称为上的辛变换 取定的一组辛正交基 fV fV fV 上的一个线性变换 在该基下的矩阵为 nn 2121 VK DC BA K 其中皆为方阵 则 是辛变换当且仅当 亦即当且仅当下列条DCBA nn JJKK 件成立 EBCDABDDBACCA 且易证 及辛变换的乘积 辛变换的逆变换皆为辛变换 0 K 设是辛空间 满足 则称为辛正交的 fVVvu 0 vufvu 是的子空间 令WV 2 WwwufVuW 0 显然是的子空间 称为的辛正交补空间 WVW 双线性函数及其应用 第 8 页 定理定理 7 是辛空间 是的子空间 则 fVWV WVWdimdimdim 定义定义 9 为辛空间 为的子空间 若 则称为的迷向子 fVWV WWW fV 空间 若 即是极大的 按包含关系 迷向子空单间 也称它为拉格朗日 WWW 子空间 若 则称为的辛了空间 0 WW WW fV 例如 设是的辛正交基 则是迷向 nn 2121 fV 21k L 子空间 是极大迷向子空间 即拉格朗日子空间 21n L 是辛子空间 2121kk L 对辛空间的子空间 通过验证 并利用定理 7 可得下列性质 fVWU 1 WW 2 UWWU 3 若是辛子空间 则U UUV 4 若是迷向子空间 则UVUdim 2 1 dim 5 若是拉格朗日子空间 则UVUdim 2 1 dim 定理定理 8 设是辛空间的拉格朗日子空间 是的基 则它可扩L fV n 21 L 充为的辛正交基 fV 推论推论 设是的迷向子空间 是的基 则它可扩充成的W fV k 21 L fV 辛正交基 对于辛子空间 也是非退化的 同样也非退化 由定理 7 还有UUf Uf UUV 定理定理 9 辛空间的辛子空间的一组辛正交基可扩充成的辛正 fV UfU fV 交基 定理定理 10 令为辛空间 和是两个拉格朗日子空间或两个同维数的辛子空 fVUW 间 则有的辛变换把变成 fVUW 辛空间的两个子空间及之间的 线性 同构 若满足 fVVW VvWuKvKufvuf 双线性函数及其应用 第 9 页 则称 为与间的等距 VW Witt 定理定理 辛空间的两个子空间 之间若有等距 则此等距可扩充成 fVVW 的一个辛变换 fV 下面是辛变换的特征值的一些性质 是辛空间上的辛变换 则 的行列式为 1 fV 取定的辛正交基 设 在基下矩阵为 这时有 fV nn 2121 K JJKK 定理定理 11 设 是维辛空间中的辛变换 是 在某辛正交基下的矩阵 则它的n2K 特征多项式满足 若设 KEf 1 2 ff n nn nn aaaaf 212 12 1 2 0 则 niaa ini 1 0 2 由定理 11 可知 辛变换 的特征多项式的 复 根与是同时出现的 f 1 且具有相同的重数 它在中的特征值也如此 又等于的所有 复 根的积 而P K f 故特征值的重数为偶数 又不等于的复根的重数的和及空间的维数皆为偶1 K1 1 数 因此特征值为的重数也为偶数 1 定理定理 12 设是数域上辛空间上辛变换 在中的特征值 且 ji P fVP 设 分别是中对应于特征值及的特征子空间 则 1 ji i V j V V i j ji VvVu 有 即与是辛正交的 特别地 当时是迷向子空间 0 vuf i V j V 1 i i V 二 主要结论二 主要结论 1 设是上一个维线性空间 是的一组基 是中VPn n 21 V n aaa 21 P 任意个数 存在唯一的上线性函数使 nVf niaf ii 2 1 2 设及是线性空间的两组基 它们的对偶基分别为 n 21 n 21 V 及 如果由到的过渡矩阵为 那么由 n fff 21 n ggg 21 n 21 n 21 A 到的过渡矩阵为 n fff 21 n ggg 21 1 A 双线性函数及其应用 第 10 页 3 的维数等于的维数 而且是的一组基 PVLV n fff 21 PVL 4 是一个线性空间 是的对偶空间的对偶空间 到的映射V VVV V xx 是一个同构映射 5 在给定的基下 上全体双线性函数与上全体级矩阵之间的一个双射 VPn 6 同一个双线性函数在不同基下的度量矩阵是合同的 7 设是数域上维线性空间 是上对称双线性函数 则存在的一VPn fVV 组基 使在这组基下的度量矩阵为对角矩阵 n 21 f 8 两个辛空间是辛同构的当且仅当它们有相同的维数 9 是辛空间 是的子空间 则 fVWVWVWdimdimdim 4 2 对偶空间对偶空间 设是数域上一个维线性空间 上全体线性函数组成的集合记作 可VPnV PVL 以用自然的方法在上定义加法和数量乘法 PVL 设是的两个线性函数 定义函数如下 gf Vgf Vgfgf 也是线性函数 gf gfgf ggff gfgf gfkkgkfkgkfkgf 称为与的和 gf fg 还可以定义数量乘法 设是上线性函数 对于中任意数 定义函数如下 fVPkkf Vfkkf 称为与的数量乘积 易证也是线性函数 kfkfkf 容易检验 在这样定义的加法和数量乘法下 成为数域上的线性空间 PVLP 取定的一组基 作上个线性函数 使得V n 21 Vn n fff 21 1 2 1 0 1 nji ij ij f ji 双线性函数及其应用 第 11 页 因为在基上的值已确定 这样的线性函数是存在且唯一的 对中向量 i f n 21 V 有 n i ii x 1 2 ii xf 即是的第 个坐标的值 i f i 引理引理 对中任意向量 有V 3 n i ii f 1 而对中任意向量 有 PVLf 4 n i ii fff 1 定理定理 2 的维数等于的维数 而且是的一组基 PVLV n fff 21 PVL 定义定义 2 称为的对偶空间 由 1 决定的的基 称为的 VPLV PVL n 21 对偶基 以后简单地把的对偶空间记作 V V 例例 考虑实数域上的维线性空间 对任意取定的个不同实数Rn n xPV n 根据拉格朗日插值公式 得到个多项式 n aaa 21 n 2 1 111 111 ni aaaaaaaa axaxaxax xp niiiiii nii i 它们满足 2 1 0 1 nji ij ij ap ji 是线性无关的 因为由 21 xpxpxp n 0 2211 xpcxpcxpc nn 用代入 即得 i a nicapcapc iipi n k ikk 2 1 0 1 又因是维的 所以是的一组基 Vn 21 xpxpxp n V 设是在点的取值函数 2 1 niVLi i a 2 1 niVxpapxpL ii 双线性函数及其应用 第 12 页 则线性函数满足 i L 2 1 0 1 nji ji ji apxpL ijji 因此 是的对偶基 n LLL 21 21 xpxpxp n 下面讨论的两组基的对偶基之间的关系 V 设是数域上一个维线性空间 及是的两组基 它们的VPn n 21 n 21 V 对偶基分别是及 再设 n fff 21 n ggg 21 A nn 2121 Bfffggg nn 2121 其中 nnnn n n aaa aaa aaa A 21 22221 11211 nnnn n n bbb bbb bbb B 21 22221 11211 由假设 niaaa nniiii 2 1 2211 njfbfbfbg nnjjji 2 1 2211 因此 nji ji ji ababab aaafbg ninjijij nniii n k kkjij 2 1 0 1 2211 2211 1 由矩阵乘法定义 即得 EAB 即 1 AB 定理定理 3 设及是线性空间的两组基 它们的对偶基分别为 n 21 n 21 V 及 如果由到的过渡矩阵为 那么由 n fff 21 n ggg 21 n 21 n 21 A 到的过渡矩阵为 n fff 21 n ggg 21 1 A 双线性函数及其应用 第 13 页 设是上一个线性空间 是其对偶空间 取定中一个向量 定义的一VP VVx V 个函数如下 x Vfxffx 根据线性函数的定义 容易检验是上的一个线性函数 因此是的对偶空间 x V V 中的一个元素 VV 定理定理 4 是一个线性空间 是的对偶空间的对偶空间 到的映射V VVV V xx 是一个同构映射 这个定理说明 线性空间也可看成的线性函数空间 与实际上是互为线V VV V 性函数空间的 这就是对偶空间名词的来由 由此可知 任一线性空间都可看成某个线性 空间的线性函数所成的空间 这个看法在多线性代数中是很重要的 5 5 双线性函数的应用领域双线性函数的应用领域 5 15 1 基于精确线性化的基于精确线性化的 MIMOMIMO 双线性系统预测函数控制双线性系统预测函数控制 针对典型多输入多输出双线性系统 提出了基于非线性过程精确反馈解耦线性化的 预测函数控制方法 这是一种分层的控制策略 首先设计一个静态的非线性状态反馈 使 得闭环系统是输入输出解耦和线性的 然后设计一组单输入单输出预测函数控制器 下 层为上层预测函数控制提供一组单输入单输出模型 而上层预测函数控制以其固有的鲁 棒性来补偿参数变化和解耦线性化的近似性 并以纸机加压网前箱为例进行了仿真实验 结 果是令人满意的 5 25 2 双线性荷载传递函数的单桩荷载沉降关系统双线性荷载传递函数的单桩荷载沉降关系统 采用荷载传递函数法研究单桩的荷载沉降关系 因其形式简单 便于应用 而受到普 遍关注 常用的有双线性函数 双曲线函数 对数及指数函数等 其中 双线性函数 在模拟桩周土的软化特性上较其它函数有相对优势 然而 现有的基于双线性函数的 单桩荷载沉降关系解析解答只是针对某种特定工