layout: cp
title: Research post-quantum strategies for Monero
author: Insight
date: May 20, 2020
amount: 576
milestones:
- name: Initial payout
funds: 100% (576 XMR)
done: 14 July 2020
status: finished
- name: Identify and document existing vulnerabilities in Monero
funds: 0% (0 XMR)
done: September 2020
status: finished
- name: Research Monero-compatible post-quantum cryptography methods
funds: 0% (0 XMR)
done: September 2020
status: finished
- name: Communicate and Educate
funds: 0% (0 XMR)
done: October 2020
status: finished
payouts:
- date: 14 July 2020
amount: 576
Identifying practical post-quantum strategies for Monero
Motivation:
Monero transactions created between 2014 and 2020 utilize cryptographic mechanisms that were not designed to be private or secure against quantum computers. Algorithms that could theoretically circumvent several of Monero's security and privacy features are already known, such as Shor's algorithm (which breaks security based on the discrete logarithm problem) and Grover's algorithm (which could be used to forge blocks).
Let us define a hypothetical “practical” quantum computer as any device that enables an adversary to effectively circumvent some security expectation provided by cryptographic mechanisms. This is not defined by some magic number of qubits or any particular configuration; it refers to the capability to leverage methods such as Fourier fishing, Grover's algorithm, or Shor's algorithm with enough complexity to tackle modern cryptography. Speculation on whether practical quantum computers will ever exist, and when they might arrive, is outside the scope of this cryptography research proposal.
There are several ways that a sophisticated quantum adversary might access funds and sensitive information that would otherwise be cryptographically obfuscated:
- Deriving private keys from public keys: A quantum adversary that has obtained your public wallet address can derive your private key. This enables them to learn your entire (past and subsequent) transaction history, and steal any current/future funds by forging a transaction from you to themselves.
- Deriving private keys from key images: A quantum adversary can also break the privacy of some features for every transaction already recorded on the ledger, by using key images to derive transaction private keys.
- Deobfuscating the transaction graph: Each ring signature references several (currently 11) past outputs, only one of which is truly being spent. Deobfuscation refers to analyzing the true flow of funds to eliminate the privacy provided by ring signatures and stealth addresses. Graph matching analyses are already parallelizable on traditional computers, and may be easier for quantum computers.
- Consensus mechanism & blockchain immutability: Monero's proof-of-work algorithm (RandomX) involves chaining several (currently 8) operations by a VM, designed like a one way function (such that the input to produce a given output can only be found by brute force). We will evaluate whether this approach can be exploited by quantum computers leveraging methods such as Fourier fishing or Grover's algorithm. The potential ability to forge blocks with a specific hash would defeat blockchain immutability, however this can be mitigated with the addition (i.e. concatenation) of post-quantum hash functions and checksums.
Retroactive deanonymization puts today's Monero users at the hands of tomorrow's [quantum or classical] adversaries. If practical quantum computers that can break Monero's encryption arrive at any point in the future, then users' lifelong transaction history willl become public for ingestion by the AdTech industry, stalkers, criminals, and governments. It is irrelevant which party publishes a de-anonymized copy of the Monero blockchain first - the universal evaporation of privacy is irreversible.
Thankfully, cryptographers have developed several post-quantum security and privacy schemes that may be adaptable to Monero. Promising techniques include zero-knowledge lattice cryptography based on the shortest vector problem. Methods such as hash-based ring signatures, GLYPH (Schnorr-like lattice-based signature scheme), and the cohort of NIST post-quantum candidates were all designed to enable security in a post-quantum world. The quantum resistant ledger is of particular interest due to its extensibility, immutability, and RandomX integration - however no privacy features are currently implemented. Other designs for anonymous post-quantum cryptocash have been considered, and the Halo recursive zero-knowledge proving system offers plausible post-quantum security. Each approach has its own benefits, drawbacks, and space/time complexity - our research recommendations will take into account these practical considerations in addition to theoretical compatibility.
This research will (1) study and simulate the threats listed above to assess Monero's vulnerability to quantum computers, (2) evaluate post-quantum cryptography scheme candidates to create a roadmap for hardening Monero against quantum adversaries, and (3) openly communicate the results for a variety of audiences.
The advent of powerful quantum computers will wreak havoc on almost every aspect of our digital infrastructure. Access to sound money (which requires privacy) is a fundamental human right and should be considered a high priority for hardening against quantum adversaries. To our knowledge, there are currently no plausibly post-quantum anonymous currencies in use today, meaning that only short-to-intermediate term financial privacy is available with current technology. The first coin to implement long-term post-quantum privacy features will be in a strong position for adoption, even long before quantum computers arrive.
"A post-quantum world would destroy Amazon, Wells Fargo, Visa, and most world governments. But there's no reason it has to also destroy Monero."
Surae Noether
Overview:
R & D Institution: Insight
Funding Institution: Monero CCS
Duration: 3 months (June - August 2020)
Contributors:
- Researcher in Residence: Adam Corbo
- Principal Investigator: Mitchell Krawiec-Thayer
- Other Insight contributors
- Code & documentation reviewers will be assigned as milestones near completion.
- Additional thanks to office staff, accounting, etc for creating a productive workspace.