Exploring the World of Quantum Money and Cryptography
Delve into the realm of quantum money, computation, and cryptography, understanding the intricacies of semi-quantum money, consensus problems, post-quantum cryptography, and unique concepts like certifiable randomness and tokenized digital signatures.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Semi-Quantum Money arXiv:1908.08889 AFT 19 (1) Roy Radian Or Sattath (1) (1) Ben Gurion University of the Negev
Consensus Quantum Money Double Spending Problem
Structure Introduction to quantum computation Overview of quantum money Definition: Semi-Quantum Money Constructions: Semi-Quantum Money
Quantum Computation: Need to Know Qubit = quantum bit Measuring a qubit changes its state, irreversibly. Meaning there is no rewinding. Quantum information cannot be copied. This is called the no cloning theorem. There is still no efficient quantum hardware.
Results & Implications Black box search in O (Grover s algorithm) ? Polynomial factorization & discrete log (Shor s Algorithm)
Countermeasures Post-Quantum Cryptography NIST standardization
Quantum Cryptography Generalization of classical cryptography Quantum MAC [Barnum et al.02] Quantum homomorphic encryption [Mahadev18] Quantum one-time pad [Mosca et al.00]
Quantum Cryptography Concepts unique to the field Quantum money [Wiesner83] Certifiable randomness [Brakerski et al.18] Tokenized digital signature [Ben-David Sattath16]
Private Quantum Money Mint Verify user S
Mint Q Quantum Communication user
Verify Q Quantum Communication user
Counterfeiting Q user
Public Quantum Money Mint Verify Q user user P S P
Definition: Classical Verification [Gavinsky 12] Classical ? ! Classical Communication Q user
Definition: Classical Minting Classical Q Classical Communication user
Definition: Semi-Quantum Money Classical verification +Classical minting Semi-Quantum Money Classical communication with the (classical) bank
Advantages of Semi-Quantum Money No quantum communication infrastructure Classical communication can be resent Classical communication and a classical bank can be logged
Our Main Results Construction: Private Semi-Quantum Money Relying on the hardness of LWE and post-quantum secure MAC and encryption scheme Construction: Public Semi-Quantum Money Relying on a post-quantum secure digital signature scheme, and non-standard assumptions from [Zhandry19].
Definition: Trapdoor Claw-Free Function A function ? is claw-free if for each image ? there exist exactly two preimages ?1,?2 that are hard to find ? ?1 ? ?2 x
Definition: Trapdoor Claw-Free Function ? ?1 A claw-free function has a trapdoor if there is some information ? that allows to find ?1,?2 given ? ? ?2 x ?
TCF in the Quantum Setting We can construct a quantum state that holds information about a random ? s preimages, so when measured in a certain way ?? ?? It produces one of the preimages of ? But when measured in another way ? s.t. s.t.: : ?? It produces some other information regarding both preimages ? (?? ??) = ? Only one of the measurements can be performed!
Usage of TCF Certifiable randomness [Brakerski et al.18] Quantum homomorphic encryption [Mahadev18a] Classical verification of quantum computation [Mahadev18b]
TCF to Semi-Quantum Money No more than 50/50 chance to guess a measurement result We amplify the hardness using parallel repetition: By proving that for multiple such quantum states, the chance to guess the results of multiple measurements is exponentially small We use the hard TCF as a banknote
TCF to Classical Minting On minting, the user creates a set of quantum states as seen before and gets a set of some ?s He declares his ?s to the bank
TCF to Classical Verification On verification, the bank asks for a set of measurements randomly chosen as red or green for each ? And verifies the answers using the trapdoor From the hardness amplification, chance to counterfeit is exponentially small
Conclusions and Open Questions General semi-quantization Are computational assumptions necessary? There are quantum money schemes which are unconditionally secure
Thank You! Liang, M. (2013). Symmetric quantum fully homomorphic encryption with perfect security. Quantum information processing,12(12), 3675-3687. Barnum, H., Cr peau, C., Gottesman, D., Smith, A., & Tapp, A. (2002, November). Authentication of quantum messages. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. (pp. 449-458). IEEE. Zhandry, M. (2019, May). Quantum lightning never strikes the same state twice. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 408- 438). Springer, Cham. Coladangelo, A. (2019). Smart contracts meet quantum cryptography.arXiv preprint arXiv:1902.05214. Gavinsky, D. (2012, June). Quantum money with classical verification. In 2012 IEEE 27th Conference on Computational Complexity (pp. 42-52). IEEE. Mosca, M., Tapp, A., & de Wolf, R. (2000). Private quantum channels and the cost of randomizing quantum information. Wiesner, S. (1983). Conjugate coding. ACM Sigact News, 15(1), 78-88. Pironio, S., Ac n, A., Massar, S., de La Giroday, A. B., Matsukevich, D. N., Maunz, P., ... & Monroe, C. (2010). Random numbers certified by Bell s theorem.Nature, 464(7291), 1021. Ben-David, S., & Sattath, O. (2016). Quantum tokens for digital signatures. Brakerski, Z., Christiano, P., Mahadev, U., Vazirani, U., & Vidick, T. (2018, October). A cryptographic test of quantumness and certifiable randomness from a single quantum device. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) (pp. 320-331). IEEE.
Public Scheme - Elaboration Based on Quantum Lightning [Zhandry19] Quantum Lightning is a public scheme We semi-quantized the scheme, using Bolt-to-Certificate from [Coladangelo19] Bolt-to-Certificate is the notion of exchanging a quantum bolt to a classical certificate
Quantum Money VS Bitcoin Usually needs a trusted centralized bank No propagation through network No dependency on mining Transactions are private only known to sender and receiver (and sometimes the bank)
