Implementing quantum multi-collision algorithm on Qiskit

[ace314]

Abstract

Finding collisions for a many to one mapping is a fundamental problem in cryptography. In this project, we would implement quantum multi-collision algorithm on Qiskit. Rather then simply applying Grover search, which gives a quadratically speed up, we would like to realize more efficient algorithms to attack the multi-collision problem.

Description

The multi-collision problem states as follows: For given finite sets and with   , and a function , the s-collision finding problem is to find a set of distinct inputs such that

.

For s=2 cases, the problem corresponds to the well-known "birthday paradox", which shows that the probability to find two people sharing the same birthday in a banquet is much more larger than one may intuitively think. In fact, the probability reaches 50% with only 23 people in a room. One can use Grover search to solve the multi-collision problem for     expected evaluations. Moreover, the optimized algorithm so called "BHT algorithm" gives     for s=2 and any arbitrary function (arXiv:quant-ph/9705002). Recently, some algorithms have been proposed with higher efficiency or for more complicated conditions such as s>2 and different features of (arXiv:1911.02822). In this project, we would look into the algorithms already proposed and try to do the implementation on Qiskit. Then based on that, we optimize the algorithm as far as possible during the hackathon.

Members

• @abtmy - Slack: @Tomoya Abe
• @r1t0o0 - Slack: @Rito
• @ace314 - Slack: @Che Chiang
• @BOBO1997
• @starktech23
• @githubhandle - Slack: @slackhandle email: [email protected]
• Qiskit Coach: @atilag

Deliverable

GitHub repo

[R07222062]

I'm very interesting in this topic. I've finish reading the papers and had some thoughts. Maybe we can discuss some ideas through email?

[ace314]

I'm very interesting in this topic. I've finish reading the papers and had some thoughts. Maybe we can discuss some ideas through email?

Tnx for your noticing! Feel free to email me at any time. It would be nice if you could post your thoughts here :)

[abtmy]

I'm interested in this project. This algorithm is used when we consider post-quantum security of hash functions.

[ace314]

I'm interested in this project. This algorithm is used when we consider post-quantum security of hash functions.

I am glad to here that. Maybe we can discuss the details tomorrow. See you then :)

[r1t0o0]

It sounds interesting to me, count me in

[r1t0o0]

@1ucian0 please assign me to this group

[BOBO1997]

@1ucian0 please add me to this group, thank you!

[starktech23]

interested. Samanvay Sharma, Computer Science.

[mf-22]

Masahiro Fujii, Computer science

[BOBO1997]

BOBO1997, Yang Bo, Computer Science

[r1t0o0]

Yu GUO, Computer Science, familiar with classical algorithm

[abtmy]

abtmy, Tomoya Abe, computer science

[ace314]

https://github.com/ace314/Quantum-Multi-collision-Problem