Adaptive Security for Attribute-Based Encryption
Explore the complexities and challenges involved in achieving adaptive security for attribute-based encryption, including the importance of hardness assumption reduction and the difficulties in proving security. Dive into the various phases and requirements of this encryption method, along with the need for collusion resilience and efficient decryption capabilities.
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
Limits on Adaptive Security for Attribute-Based Encryption Zvika Brakerski, Stav Medina Weizmann Institute of Science TCC 2024
Motivation Public Key Encryption PK Bob ? = Decrypt(CT, SK Bob) CT = Encrypt(?, PK Bob) Bob Alice PK Bob,SKBob ?
PP(Public Parameters) MSK Motivation Attribute-Based Encryption ? set of attributes set of policies ?:? {0,1} Master SK?= KeyGen(MSK, ?, PP) CT?= Encrypt(?,?, PP) ? = Decrypt(CT?, SK ?,PP) only when ? ? = 1 Alice ? Bob
Motivation Security of Attribute-Based Encryption Master Security requirement Collusion Resilience SK?1, SK?2, SK?3 CT?= Encrypt(?,?, PP) If ??? = 0 for all ?, then cannot decrypt CT? Alice Adversary
Adaptive Security of ABE PP 1. Setup Phase ? 2. Query Phase I SK? ? 3. Challenge Phase Encrypts ?0\?1 CT? Challenger Adversary ? 4. Query Phase II SK? 5. Guess ?0/?1 If the guess is correct and all policies satisfy ? ? = 0 Adversary wins
Adaptive Security of ABE Proving security = efficiently reducing hardness assumption to an adversary. Hardness Assumption Reduction Adversary
Adaptive Security of ABE ? SK? Hardness Assumption Reduction Adversary ? SK ? The reduction should be able to decrypt any ciphertext by itself Full security costs in terms of functionality and simplicity [Wat09, Tsa19] Is this necessary?
Why Proving Adaptive Security is Difficult Allison Lewko & Brent Waters, 2014 No straight-line (non-rewinding)security reductions for checkable ABE Outline use Meta-Reduction : Utilize reduction algorithm to break the hardness assumption w/o adversary Simulate adversary interface for Rewind to extract additional secret keys The simulated adversary (meta-reduction) can decrypt any challenge efficiently breaks the hardness assumption (for us) Simulation must be consistent requiring canonical decryption ABE checkability
ABE Checkability Allison Lewko & Brent Waters, 2014 Verification procedures: SKCheck SK?,?,PP CTCheck CT?,?,PP {True,False} Correctness: Honestly generated ciphertexts and secret keys are valid Soundness: Valid secret keys decrypt every valid ciphertext the same way Intuitively, different users should decrypt the same ciphertext to the same message natural property Our contribution: Simpler checkability criteria
Our Results Informally: No black-box adaptive-security reduction for checkable ABE Even if the reduction is rewinding Application to [BGG+14]
Proof Overview ?0, SK0 ?1, SK1 Rewind ? ? Meta- Reduction Hardness Assumption Simulated Hypothetical adversary Adversary Reduction ? s.t. ?0? = 1 and ?1? = 0 ? (possibly interactive) hardness assumption ? hypothetical inefficient adversary (left) forwards the communication of ? and (right) simulates the hypothetical adversary ? If ? breaks ?, then can break ? as well, in polynomial time.
Proof Overview The Rewinding Challenge (our main technical innovation) What happens if rewinds the adversary ? Recursive rewindings Possibly exponential runtime [LW14] Considering only straight-forward black-box reductions Solution: Apply delicate rewinding mechanism Inspired by Pass 2011 in the context of witness-hiding protocols
The Slot Technique PP Slot ? is good if: ?1 SK??is a valid key No external communication No too many inner slots 1. Slot ?1 SK?1 2. Reduction ?2 3. Slot ?2 SK?2 Need to prove: Recursion Tree size is bounded Runtime of is bounded by a polynomial
Proof Overview Reduction is only average case might not answer some key queries... Solution: Use a special set of policies ? induced from pairwise independent hash family Both Hypothetical and simulated adversaries sample random policies from ?
Pairwise-Friendliness 1 By design, every ? ? covers poly log ? of ? Random ? ?has a somewhat random set of accepted attributes ? 11 ? The reduction cannot misbehave too much extracts poly(log ? ) additional keys enough to cover all ? Even if the reduction unpredictably refuses to some key queries The scheme should support ? Pairwise-Friendliness Commonly Satisfied any scheme that supports log(log ? )-depth circuits
Wrapping Things Up To prove adaptive security, one must eliminate the possibility of checkability Requires more complex and unnatural methods [Wat09, Tsa19] Application to [BGG+14]
