Quantum Classical Cryptography and Security Seminar Insights
Explore the world of quantum classical cryptography and security in this seminar, covering topics such as the unclonability of quantum states, one-shot primitives, signature delegation, and more. Discover advanced concepts and applications in the realm of blockchain-less cryptocurrency with classical communication protocols.
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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Unclonable Secret Keys Marios Georgiou, City University of New York CORELab Seminar
Quantum Classical No-Cloning Theorem For any quantum algorithm A, there is a quantum state that A cannot clone. Classically, we can always copy a bit-string.
Quantum Classical Unclonability of Useful Useful Quantum States? Useful: 1. It may have more structure. 2. It may come together with some auxiliary classical information, e.g., a verification key (Quantum Money) Question How much can we strengthen the No-Cloning Theorem?
Quantum Classical Motivation: Traitor Tracing [CFN94] ??1 ??2 ??3 ??4
Quantum Classical Leakage Detection ?? ??,??
Quantum Classical One-Shot Primitives [AG GKZ20] One-Shot Chameleon Hashing ??? ? ?,?? ??? ??,? ? such that ? ?,? = ? ? is collision resistant ?? must be unclonable One-Shot Signatures ??? ??? ??,?? ???? ??,? ? ??? ???,??,?,? ??????/?????? ??? ?? ?0,?0 ?1,?1 ? ?,? = ? ??? ???,??,?0,?0 = ??? ???,??,?1,?1 = 1 ?? ? ?
Quantum Classical Proofs Of Quantumness [BCM+18, AG GKZ20] ??? ?? ? ?
Quantum Classical Signature Delegation (Hash then Sign) [AG GKZ20] ? = ????(sk, ) ?? ??,?? Verification ??,?,?,? : 1. = ? ?,? 2. ??? ??, ,? ? ??? ??,?
Quantum Classical Signature Delegation (Hash then Sign) ? ? ? = ????(??,?) ?,? ?? ??,?? ?? ? ??? ??,? Verification ??,?,?,? ,? : 1. ? = ? ?,? 2. ? = ?(? ,?) 3. Ver ??,?,? ? ??? ?? ,?
Quantum Classical Blockchain-less Cryptocurrency with Classical Communcation Using one-shot signatures Mining using Proof of Work: Run ??,?? ??? ???until ?? starts with 80 zeroes Transfer: Delegation Protocol ??1 ??2 ?1 ???? ??0,??1 ??0 ?2 ???? ??1,??2 ??0,?1,??1 ??1,??1 ??2,??2 ??0,??0 Improvements: 1. Add SNARK to keep size of the chain small 2. Add ZK to ensure privacy No need to maintain a public ledger Consensus is required only on the ??? Sending money requires classical communication
Quantum Classical Budget Signatures Every public key comes with a budget: pk.budget (say 1) Every message comes with a cost: ?.cost (say 1) One can keep signing until the budget is depleted ??,?? ??,? ???? ??, ??0,??1 ??0,??0 ??0,?0 ???? ??0,? ??1,??1 ??1,?1 ????(??1, ??10,??11) ??10,??10 ??11,??11 Can use this in our cryptocurrency to spend fractions of a coin.
Quantum Classical Ordered Signatures [AG GKZ20] Key idea: Cannot sign past messages. Each message ?has a time attribute ?.? If I sign a message with time ?, I cannot sign any new message with time ? ?. Construction: Naor-Yung with One-Shot Signatures. ??1,??1 ??1,?1 ???? ??1,(??2,?2,?2) ??0,??0 ??0,?0 ???? ??0,(??1,?1,?1) ??2,??2 Each signature, includes all previous signatures and messages. To verify a signature, additionally check that ??> ?? 1. To burn a secret key, sign at time ? = .
Quantum Classical Single-Signer Signatures [AG GKZ20] One can sign arbitrarily many messages. ?0 ??0 ??,?0,?1 ??? ?0 ?1 ??1 1. ??? 0,1? 2. ?0 ?0,?1 ?1 3. ??? ???,??,?0,?0 = ??? ???,??,?1,?1 = 1 ?1 Theorem: Ordered Signatures are Single-Signer Signatures.
Quantum Classical More Applications Public-coin proofs of min-entropy Delayed Signatures One can sign one message every minute Using proofs of sequential work
Quantum Classical Single Decryptor Secret Secret-Key Encryption [G GZ20] ??? 1? ??,?? ??? ??,? ? ??? ??,? ? ?0 ??0 ? ?0,?1 ? ??1 ,?? ??? 1? ? 0,1 ? ??? ??,?? ? = ?0= ?1 ?? ?1 Selective Security: Adversary picks ?0,?1before seeing ??.
Quantum Classical Unclonable Encryption [BL19] ??? 1? ?? ??? ??,? ? ??? ??,? ? ?0 ?0 ?? ?0,?1 ?? ?1 ?? ??? 1? ? 0,1 ??? ??,?? ? = ?0= ?1 ?1 ? Theorem [BL19]: Unclonable Encryption exists in the ROM if the adversaries are not entangled.
Quantum Classical Equivalence [G GZ20] Theorem [GZ20]: Unclonable Encryption exists if and only if selectively secure single decryptor secret key encryption exists. Corollary: Selectively secure single decryptor encryption exists in the ROM if the adversaries are not entangled. Unclonable Encryption ?? ?? ? Single Decryptor ?? ?? ?? ? ?? = ??,?for random ? ?? = ?? ? ?? ? = ??,? ? ?? is random ?? ? = ??,?? ? ?? for a new ??,??
Quantum Classical Public Key with Dishonest Key Generation ??? ??,?0,?1 ? 0,1 ? = ?0= ?1
Quantum Classical Witness Encryption [GGSW13, GKPVZ13] ???,??? is an extractable witness encryption for a language ? if: Correctness: ??? ?,??? ?,? = ? for any message ? and ?,? ??. Security: For any adversary ? there is an extractor ? such that for any ?,?0,?1 and ???, If ? can distinguish between ???,?,??? ?0,? and ???,?,??? ?1,? then ? ?,??? can find a witness for ?.
Quantum Classical Construction Key idea: Witness encrypt with instance a random ?. Decryption needs a single signer signature on ?. Let ??? ,????,??? be a single signer signature. Define single decryptor encryption: ??? = ??? ??? ??,? : Sample ? 0,1? Return ?,??? ?,? , where ??? ,??? is a witness encryption for ? = ??? ??, ?,? : Return ??? ???? ??,? ,? ?,? :??? ??,?,? = 1 Theorem: If an adversary can decrypt, then there is an extractor that retrieves a signature.
Quantum Classical Attribute Based Encryption Single Decryptor Splittable ,?? where ? is a predicate. ??? ???,? ??? ???,??,?,? ?, where ? is an attribute. ,? ? ????? ???,? ??? ?,??? ? Correctness: decrypts correctly if ? ? = ???? ??? ??? ??? ??? ??? ??,?,?0,?1 ? 0,1 ? = ?0= ?1
Quantum Classical Construction [G GZ20] ? ???? , ??0,??1, ? ?? ??1,??1 ??0,??0 ??? ???,??,?,? : 1. ? 0,1? 2. Return ?,? ,??? where ??? ,??? is a witness encryption for ?,? ,? ?,? ,??? : ??? ?????? ??? ?? ??? ???? ??? ????????? ?? ? ??? ???? ????? ? ? ???? ? = ???? = ??,?,? ??? ,?? ????.???? ??? ? ?? ? ? ,???? ? ?
Quantum Classical Unclonable Broadcast Encryption [G GZ20] ??? ??1, ,??? ??? ??? ???,?,? ? such that ??? ?,?,???,? = ? if ? ?. Security: For any set ?, at most ? isolated adversaries can decrypt ??? ???,?,? . ??? and ? are independent of ?.
Quantum Classical Construction [G GZ20] ??? = ? 0, 1 = ????????? ??1,??2,??3,??4 ??? ???,?,? : 1. ? 0,1? and = ????????? ? where ??= ???? ? ? 2. Return ,? ,??? ??? ,??? is a witness encryption for 0= ? ??1,??2 1= ? ??3,??4 where ,? ,? ??1 ??2 ??3 ??4 ,? , ?,??,?,?,? : ???? ,?,? = ???? ???? ???,?,? = ?? ??? ??,?,? = 1 ? = ??2= ??2,?2
Quantum Classical Time-Released Encryption [G GZ20] ??? ??,?,????? ? One needs at least time ????? before they decrypt ?. Revocation: One can provide a proof of revocation of ?. If revocation happens before time ?????, then ? is undecryptable. Construction: Witness Encryption + Delay Signatures.
Quantum Classical One-Shot Chameleon Relative to an Oracle (for ? = 1) ??? ? : 1. Generate a uniform superposition of all ? 0,1?. 2. Evaluate ? to get uniform superposition of (?,? ? ). 3. Measure the output register. We end up with a random image ? and uniform superposition of its pre-images (??). ??? ??,? : 1. Using QFT ? QFT as the diffusion operator, apply Grover s algorithm to turn ?? into a uniform superposition of pre-images starting with ?. 2. Measure the state to retrieve one pre-image. 1,1,1,1 0,0,0,0 Partition the domain 0,1? into 2?/2 random ? Assign a distinct value ? to each affine subspace and set ? ? = ? if ? ?. Provide an additional oracle ? such that check membership in the orthogonal complement. 2 dimensional affine subspaces.
Open Problems [Mah18, ACGH20]: Privately Verifiable one-shot signatures imply classically verifiable quantum computation. What if we plug in publicly verifiable one-shot signatures? ?Non-interactive classically publicly verifiable quantum computation Public-key Quantum money [RZ20] Franchised Quantum Money from LWE. Applications to one-shot signatures? Applications to consensus?
