基于矩阵分解的方案报告

基于矩阵分解的公钥加密方案一、预备工作1、代数学基础I半群：若定义在非空集合A上的一个二元运算（乘法）满足结合律，则称该集合A为一个半群。即对任意,,xyzA，有()()xyzxyz。II交换幺半群：如果一个半群含有幺元且为交换的，则称其为交换幺半群。III半环：称,,.,0,1A为一个半环，其中A为集合，,,0A对为交换幺半群，,.,0A对.为幺半群，且满足分配律及000aa。IV环：非空集合,,.R称为一个环，如果满足：对加法是一个加群（交换群），对乘法是一个半群，两个分配律都成立，则称其为一个环。2、按位异或1、定义：对两个整数,ab，按位异或就是将其转化为二进制数后，将对应位做异或运算。即若对应位相同，其异或结果为0，否则为1。在Matlab中，两个整数,ab的异或操作为bitxor(,)ab。2、性质：对任意整数,,abcI交换律：^^abba。II结合律：(^)^^(^)abcabc。III(^)0aa，(^0)aa。IV自反性：^^^0aabbb，^^^0abbaa。V不满足对加法的分配律，即：^()^^abcabac。VI不满足对乘法的分配律，即：^()(^)(^)abcabac。VII不满足对乘法的结合律，即：(^)^()abcabc。二、方案1、参数设置：I安全参数s为所用矩阵及向量元素绝对值的上限，n为所用多项式次数。偶数m为所用矩阵阶数。II任取1212,,,llrrN及2m维方阵221212,,,mmLLRRN，构造分块对角矩阵：11100lLMlI，22200llIML，11100RRMrI，22200rrIMR2、密钥生成：（接收方Bob）I构造任意整系数n次多项式：1212,,,PxPxPyPy，其系数绝对值不能大于s。II计算：1122()()llXPxMPxM，1122()()rrYPyMPyM。安全否？III计算：任取方阵mmQN，计算AXQY。IV输出公钥：{,}pkAQ，{,}skXY。3、加密：（发送方Alice）I对明文消息t，按某种方式构造对应矩阵mmTN。II构造任意整系数n次多项式：1212,,,PuPuPvPv，其系数绝对值不能大于s。III计算：1122()()llUPuMPuM，1122()()rrVPvMPvM。IV计算加密算子：UAV，解密算子：UQV。V计算密文：CTUAVT。VI输出密文：(C,)D。4、解密：（接收方Bob）I接收密文：(C,)D。II计算：TXYCXUQVYUAVTXUQVYUXQYVTXUQVYXUQVYTT。5、安全性：6、同态性：11CT，22CT，I加法：记12CCC1()T2()TII乘法：记12CCC1()T2()T