Bhaskar Roberts

Zhandry recently defined a new cryptographic object called quantum lightning, which has a number of useful applications, including a strong form of quantum money. Further, Zhandry proposed a construction of quantum lightning based on superpositions of low-rank matrices. The scheme is unusual, so it is difficult to analyze whether the scheme is secure and difficult to base the scheme’s security on any widespread computational assumptions. Instead, Zhandry proposed a new hardness assumption that, if true, could be used to prove security. While the new hardness assumption is plausible, it has not been rigorously analyzed. In this work, we analyze the hardness assumption to determine how, if at all, it can be justified. We show that Zhandry’s hardness assumption is in fact false, so the proof of security for Zhandry’s scheme does not hold. While the scheme itself has not been proven insecure, our analysis suggests an approach to developing attacks that might prove the scheme insecure.

Classical bits can be copied, but quantum bits, in general, cannot. As a result, there is interest in creating uncounterfeitable quantum money, in which a set of qubits can be spent as money but cannot be duplicated. To function as money, there must be a way to verify that a given state is a valid banknote and not a counterfeit. Many recent efforts have tried to allow public key verification, where any untrusted user, even a would-be counterfeiter, can verify the banknotes. However, despite many attempts, a secure construction of public-key quantum money has remained elusive. Here we introduce franchised quantum money, a new notion that is weaker than public key quantum money but brings us closer to realizing it. Franchised quantum money allows any untrusted user to verify banknotes using a unique secret key. Furthermore, we give a construction of franchised quantum money and prove security assuming the quantum hardness of the short-integer solution problem (SIS). This is the first construction of quantum money that allows an untrusted user to verify the banknotes, and which has a proof of security based on widespread assumptions. It is therefore an important step toward public key quantum money. Under franchised quantum money, untrusted users receive unique secret verification keys. With their key, a user can verify banknotes without the mint involved, but they cannot create counterfeit money that would fool another user. This is different from public key quantum money because the verification key may actually enable counterfeiting, but the only person that the counterfeiter can fool is themselves. Here is how franchised quantum money might be useful: consider a group of large corporations, mutually distrustful, that nevertheless want to make transactions with each other. Further, a trusted third party, the mint, will administer the money system. While the mint cannot make verification public-key, it can franchise the ability to verify banknotes to the group of untrusted corporations. The mint gives each corporation a unique secret verification key that allows them to verify banknotes from another corporation. Now what if one corporation decides to start using its key to copy money? Since each corporation gets a different key, any banknotes that the corporation produces will fail to verify when a different key is used. Therefore the dishonest corporation will not be able to fool anyone but themselves. Public key quantum money has eluded sophisticated attempts to construct it directly, so franchised quantum money is useful as a stepping stone. Although franchised quantum money is not public-key, it still enables verification without the mint involved, which is the main feature of interest for public key quantum money. Further, we give a construction of franchised quantum money with a proof of security based on widely-held assumptions about the SIS problem. Franchised quantum money offers greater security than existing constructions of quantum money, and brings us closer to public-key verification.