Tutorial on
Quantum Computing Essentials for Financial Cryptographers
2022

In Association with Financial Cryptography 2022

February 18, 2022

Postponed to May 6, 2022

Radisson Grenada Beach Resort
Grenada

Date and Venue

• February 18, 2022

  Postponed to May 6, 2022
• Venue: Radisson Grenada Beach Resort Grenada

Goal of the tutorial

From our experience, the cryptocurrency community is mostly unaware of some of the relevant developments in quantum computing.

One such issue is to understand quantum mining, i.e., mining in the presence of a quantum computer, and understand the optimal strategy in it. Until a few years ago, it was believed that the transition to post-quantum digital signatures is the only ingredient missing to make cryptocurrencies secure in the quantum era. The belief was that quantum mining would only increase the difficulty. Yet, this turned out to be incorrect. Among classical strategies, the optimal strategy that maximizes the expected mining reward in Bitcoin is that of brute force. Since the probability of finding the target in classical brute search increases linearly with each query, finding a block by a miner is independent of other miners. However, in the quantum search algorithm Grover’s search,the success probability increases quadratically with the number of steps, and the algorithm could be terminated at any step. Therefore a quantum miner might stop Grover’s algorithm as soon as she sees a successful block being mined and output that block (hoping to win the block-race, and receive the mining reward), see [SAT'20]. As a result, the probability that two miners successfully find the same block will increase. This will result in a higher fork rate of the blockchain, which we know is a security threat to Bitcoin. Moreover, even if we mend the rules in order to account for quantum mining, the optimal quantum strategy is complicated, and only partly understood, see [LRS'19].

Another such issue to understand how quantum money compare to cryptocurrencies. Unforgeable quantum money is a primitive in which quantum states are used as money states. Usually, a quantum money scheme has a key-generation algorithm that produces a key(s), a mint algorithm that uses the key to generate a quantum state which is the money state, and a verification algorithm which given the key, verifies an alleged money state. The guarantee is that a valid money state from the mint always passes verification, and given a money state, an adversary cannot pass two verifications. The underlying principle that allows quantum money is the no-cloning theorem. Recently, some variants of quantum money schemes have come up that are suited to the decentralized setting, such as Bitcoin (see [AGK+20] and [CS20]), which makes it relevant to the cryptocurrency community.

The goal of this tutorial will be to address these two aspects.

Schedule for the tutorial: https://fc22.ifca.ai/quantum/program.html

Organizing Committee (Alphabetical Order)

• Or Sattath, Ben-Gurion University
• Mark Zhandry, Princeton University

Key Dates

• Tutorial:

  February 18, 2022

  May 6, 2022, 2022