Linearly Homomorphic Signatures over Binary Fields and New Tools for Lattice-Based Signatures
Linearly Homomorphic Signatures over Binary Fields and New Tools for Lattice-Based Signatures
复制标题
DOI：
10.1007/978-3-642-19379-8_1
复制
发表时间：
2011-03
期刊：
影响因子：
--
通讯作者：
D. Boneh;D. Freeman
中科院分区：
文献类型：
--
作者：
D. Boneh;D. Freeman
我们提出了一个线性同态签名方案，它可以认证给定环境空间中的矢量子空间。我们的系统具有一些以前的方案中没有的新性质：它是第一个认证定义在二进制域上的向量的方案；以前的方案只能认证系数较大或增长的向量；它是第一个基于整数格中的短向量限制问题的此类方案，因此具有基于格的密码系统的最坏情况下的安全性保证。我们的方案可以用于认证签名数据的线性变换，例如在计算平均值和傅里叶变换时或在使用网络编码的网络中。该方案的安全性(在随机预言模型中)是基于格上的一个新的困难问题，称为−SIS，它归结为标准的平均情况和最坏情况的格问题。本文提出的k−SIS问题增加了格密码学的“工具箱”，并可用于构造其他基于格的密码系统。作为Newk−SIS工具的第二个应用，我们构造了一个普通的签名方案，并在假设k−SIS问题的难度的情况下在标准模型下证明了它在k时间不可伪造。我们的构造可以看作是从Gentry、Peikert和Vaikuntanathan的签名中“移除随机预言”，代价是只允许少量的签名。
We propose a linearly homomorphic signature scheme that authenticates vector subspaces of a given ambient space. Our system has several novel properties not found in previous proposals:It is the first such scheme that authenticates vectors defined overbinary fields; previous proposals could only authenticate vectors with large or growing coefficients.It is the first such scheme based on the problem offinding short vectors in integer lattices, and thus enjoys the worst-case security guarantees common to lattice-based cryptosystems.Our scheme can be used to authenticate linear transformations of signed data, such as those arising when computing mean and Fourier transform or in networks that use network coding. Our construction gives an example of a cryptographic primitive — homomorphic signatures over— that can be built using lattice methods, but cannot currently be built using bilinear maps or other traditional algebraic methods based on factoring or discrete log type problems.Security of our scheme (in the random oracle model) is based on a new hard problem on lattices, calledk−SIS, that reduces to standard average-case and worst-case lattice problems. Our formulation of thek−SISproblem adds to the “toolbox” of lattice-based cryptography and may be useful in constructing other lattice-based cryptosystems.As a second application of the newk−SIStool, we construct an ordinary signature scheme and prove itk-time unforgeable in the standard model assuming the hardness of thek−SISproblem. Our construction can be viewed as “removing the random oracle” from the signatures of Gentry, Peikert, and Vaikuntanathan at the expense of only allowing a small number of signatures.