向量压缩的方法和装置.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN112398488A(43)申请公布日2021.02.23(21)申请号202011594840.7(22)申请日2020.12.29(71)申请人支付宝（杭州）信息技术有限公司地址310000浙江省杭州市西湖区西溪路556号8层B段801-11(72)发明人黄章杰马宝利(74)专利代理机构北京亿腾知识产权代理事务所(普通合伙)11309代理人孙欣欣周良玉(51)Int.Cl.H03M13/29(2006.01)权利要求书3页说明书10页附图5页(54)发明名称向量压缩的方法和装置(57)摘要本说明书实施例提供一种向量压缩的方法和装置，尤其适用于对偶LPN中的向量压缩，方法包括：获取待压缩的第一向量，所述第一向量的维度为n；生成低密度校验LDPC码的(n‑m)×n维的校验矩阵，所述校验矩阵为稀疏矩阵；所述校验矩阵对应于m×n维的生成矩阵，其中m为预设的压缩后的维度；通过所述校验矩阵，构造第一LDPC编码电路，所述第一LDPC编码电路实现输入向量乘以所述生成矩阵的计算功能；对所述第一LDPC编码电路进行翻转处理，得到第二编码电路，所述第二编码电路实现所述生成矩阵乘以输入向量的计算功能；将所述第一向量输入所述第二编码电路，以对所述第一向量进行向量压缩，得到第二向量。能够降低计算复杂性。CN112398488ACN112398488A权利要求书1/3页1.一种向量压缩的方法，所述方法包括：获取待压缩的第一向量，所述第一向量的维度为n；生成低密度校验LDPC码的(n-m)×n维的校验矩阵，所述校验矩阵为稀疏矩阵；所述校验矩阵对应于m×n维的生成矩阵，其中m为预设的压缩后的维度；通过所述校验矩阵，构造第一LDPC编码电路，所述第一LDPC编码电路实现输入向量乘以所述生成矩阵的计算功能；对所述第一LDPC编码电路进行翻转处理，得到第二编码电路，所述第二编码电路实现所述生成矩阵乘以输入向量的计算功能；将所述第一向量输入所述第二编码电路，以对所述第一向量进行向量压缩，得到第二向量。2.如权利要求1所述的方法，其中，所述生成LDPC码的(n-m)×n维的校验矩阵，包括：生成(n-m)×n维的矩阵，使得该矩阵的每一列均有d个非零元素，将该矩阵作为LDPC码的(n-m)×n维的校验矩阵。3.如权利要求1所述的方法，其中，所述通过所述校验矩阵，构造第一LDPC编码电路，包括：对所述校验矩阵进行上三角化处理，得到包括多个子矩阵的校验处理矩阵；所述多个子矩阵均为稀疏矩阵，且所述多个子矩阵中位置处于左上角的子矩阵为上三角矩阵；根据所述校验矩阵与所述生成矩阵的关系，得到所述校验处理矩阵包括的多个子矩阵与输出向量的第一关系；将输入向量作为输出向量的转换向量的一个子向量，基于所述第一关系，通过所述多个子矩阵建立所述输出向量的转换向量的其他子向量与所述输入向量之间的第二关系；根据所述第二关系，确定出输入向量和输出向量之间的第三关系，构造对应于所述第三关系的第一LDPC编码电路。4.如权利要求3所述的方法，其中，所述对所述校验矩阵进行上三角化处理，包括：将第一置换矩阵乘以所述校验矩阵，再乘以第二置换矩阵，得到包括多个子矩阵的校验处理矩阵。5.如权利要求4所述的方法，其中，所述根据所述校验矩阵与所述生成矩阵的关系，得到所述校验处理矩阵包括的多个子矩阵与输出向量的第一关系，包括：根据所述生成矩阵与所述校验矩阵的转置矩阵的乘积为0，得到所述校验处理矩阵乘以第二置换矩阵的逆矩阵再乘以所述输出向量的结果为0，从而得到所述第一关系；将第二置换矩阵的逆矩阵乘以所述输出向量作为输出向量的转换向量。6.如权利要求1所述的方法，其中，所述对所述第一LDPC编码电路进行翻转处理，得到第二编码电路，包括：对所述第一LDPC编码电路的输入和输出进行互换，并将所述第一LDPC编码电路的扇出门变成加法门、加法门变成扇出门，得到第二编码电路。7.如权利要求1所述的方法，其中，所述第二向量的转置等于所述第一向量乘以压缩矩阵；所述压缩矩阵为所述生成矩阵的转置矩阵。8.一种用于隐私保护的向量压缩的方法，所述方法由安全多方计算涉及的多方中的任一方执行，所述方法包括：2CN112398488A权利要求书2/3页获取待压缩的第一向量，所述第一向量的维度为n；生成低密度校验LDPC码的(n-m)×n维的校验矩阵，所述校验矩阵为稀疏矩阵；所述校验矩阵对应于m×n维的生成矩阵，其中m为预设的压缩后的维度；通过所述校验矩阵，构造第一LDPC编码电路，所述第一LDPC编码电路实现输入向量乘以所述生成矩阵的计算功能；对所述第一LDPC编码电路进行翻转处理，得到第二编码电路，所述第二编码电路实现所述生成矩阵乘以输入向量的计算功能；将所述第一向量输