Hash functions are a basic cryptographic primitive. Certain hash functions try to prove security against collision and preimage attacks by reductions to known hard problems. These hash functions usually have some additional properties that allow for that reduction. Hash functions which are additive or multiplicative are vulnerable to a quantum attack using the hidden subgroup problem algorithm for quantum computers. Using a quantum oracle to the hash, we can reconstruct the kernel of the hash function, which is enough to find collisions and second preimages. When the hash functions are additive with respect to the group operation in an Abelian group, there is always an efficient implementation of this attack. We present concrete attack examples to provable hash functions, including a preimage attack to $\oplus$-linear hash functions and for certain multiplicative homomorphic hash schemes.


翻译:散列函数是一种基本的加密原始功能。 某些散列函数试图通过减少已知的硬性问题来证明碰撞和预示攻击的安全性。 这些散列函数通常有一些额外的特性可以减少这种危险。 散列函数是添加或倍增的, 使用量子计算机的隐藏子组问题算法很容易受到量子攻击。 使用散列的量子晶体, 我们可以重建散列函数的内核, 这足以找到碰撞和第二次预想。 当散列函数对于Abelian集团的集团操作是累加的时, 总是能够有效地实施这种攻击。 我们为可变散列函数提供了具体的攻击例子, 包括以 $\ o+$ 线性散列散列函数和某些多倍的同质散变办法。

0
下载
关闭预览

相关内容

【经典书】模式识别导论,561页pdf
专知会员服务
81+阅读 · 2021年6月30日
专知会员服务
84+阅读 · 2020年12月5日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
已删除
将门创投
5+阅读 · 2019年4月15日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Quantum Technology for Economists
Arxiv
0+阅读 · 2021年10月8日
Principal Neighbourhood Aggregation for Graph Nets
Arxiv
17+阅读 · 2020年6月7日
Feature Denoising for Improving Adversarial Robustness
Arxiv
15+阅读 · 2018年12月9日
VIP会员
相关VIP内容
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
已删除
将门创投
5+阅读 · 2019年4月15日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员