Hawk: Module LIP makes Lattice Signatures Fast, Compact and Simple
Hawk: Module LIP makes Lattice Signatures Fast, Compact and Simple
复制标题
Hawk：LIP 模块使 Lattice 签名变得快速、紧凑且简单
DOI：
10.1007/978-3-031-22972-5_3
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
W. V. Woerden
中科院分区：
文献类型：
--
作者：
L. Ducas;Eamonn W. Postlethwaite;L. Pulles;W. V. Woerden
我们提出了签名方案Hawk，它是使用格同构问题(LIP)作为关注简单性的密码学的基础的建议的具体实例。这种简单性源于LIP，它允许使用Z等晶格，导致签名算法没有浮点、没有拒绝采样和紧凑的预计算分布。这种设计特征对于受限设备以及在FHE或MPC内计算签名时是可取的。与最近的LIP提议相比，最重大的变化是使用了模格，重新使用了NTRUSign和Falcon的算法和想法。它的简单性使霍克具有竞争力。我们为HAWK的设计提供了密码分析的实验依据，并实现了两个参数集，HAWK-512和HAWK-1024。在x86架构上，使用HAWK-512和HAWK-1024进行签名的速度比在Falcon上快四倍，生成的签名紧凑约15%，并且针对格点缩减攻击的伪造稍微更安全一些。当浮点数不可用时，霍克的签名速度是猎鹰的15倍。我们给出了模块LIP的平均情况简化的最坏情况。对于Hawk的某些参数，这适用于密钥恢复，我们将随机预言模型中的签名伪造简化为一个新的问题，称为One More Short向量问题。
We propose the signature scheme Hawk, a concrete instantiation of proposals to use the Lattice Isomorphism Problem (LIP) as a foundation for cryptography that focuses on simplicity. This simplicity stems from LIP, which allows the use of lattices such as Z, leading to signature algorithms with no floats, no rejection sampling, and compact precomputed distributions. Such design features are desirable for constrained devices, and when computing signatures inside FHE or MPC. The most significant change from recent LIP proposals is the use of module lattices, reusing algorithms and ideas from NTRUSign and Falcon. Its simplicity makes Hawk competitive. We provide cryptanalysis with experimental evidence for the design of Hawk and implement two parameter sets, Hawk-512 and Hawk-1024. Signing using Hawk-512 and Hawk-1024 is four times faster than Falcon on x86 architectures, produces signatures that are about 15% more compact, and is slightly more secure against forgeries by lattice reduction attacks. When floating-points are unavailable, Hawk signs 15 times faster than Falcon. We provide a worst case to average case reduction for module LIP. For certain parametrisations of Hawk this applies to secret key recovery and we reduce signature forgery in the random oracle model to a new problem called the one more short vector problem.
DOI：
10.1007/978-3-030-56880-1_12
发表时间：
2020-08
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Dana Dachman-Soled;L. Ducas;Huijing Gong;Mélissa Rossi
通讯作者：
Dana Dachman-Soled;L. Ducas;Huijing Gong;Mélissa Rossi