Cryptography in the Bounded Storage Model: Revisited - Eurocrypt 2023

Cryptography researchers revisit the Bounded Storage Model (BSM) to enhance security in transmitting messages while considering limited storage capacities. The BSM restricts adversaries to limited storage, enabling unconditional security. The model aims to address challenges in message transmission to Bob while keeping messages hidden from Eve. The work explores streaming BSM, where honest users stream long messages with small internal memory, illustrating the concept of "speak much, remember little."

• Cryptography
• Bounded Storage Model
• Security
• Transmission
• Eurocrypt

loc_bod Follow

Uploaded on Sep 20, 2024 | 0 Views

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.

Presentation Transcript

1. Speak Much, Remember Little: Cryptography in the Bounded Storage Model, Revisited Yevgeniy Dodis Willy Quach Daniel Wichs New York University Northeastern University Northeastern University NTT Reseach EUROCRYPT 2023

2. Cryptography 101 Eve Task: Transmit message to Bob Security: Message hidden from Eve Alice Bob Hello! Model for adversaries? If no constraints: key |message| [Shannon49] Key can only be reused a few times Public-key setting impossible Standard modeling: Adversaries limited to run in polynomial-time Requires computational assumptions (at least ? ??) Cryptographers seldom sleep well

3. The Bounded Storage Model (BSM) [Maurer92] Eve Task: Transmit message to Bob Security: Message hidden from Eve Alice Bob Hello! Model for adversaries? If no constraints: key |message| [Shannon49] Key can only be reused a few times Public-key setting impossible Bounded Storage Model: Adv. only restricted to limited storage capacity Enables unconditional security (!)

4. The Bounded Storage Model (BSM) [Maurer92] Eve Task: Transmit message to Bob Security: Message hidden from Eve Alice Bob Model for adversaries? If no constraints: key |message| [Shannon49] Key can only be reused a few times Public-key setting impossible Bounded Storage Model: Adv. only restricted to limited storage capacity Enables unconditional security (!)

5. The Bounded Storage Model (BSM) [Maurer92] ???? Eve Task: Transmit message to Bob Security: Message hidden from Eve Alice Bob Model for adversaries? If no constraints: key |message| [Shannon49] Key can only be reused a few times Public-key setting impossible Bounded Storage Model: Adv. only restricted to limited storage capacity Enables unconditional security (!) How to model algorithms?

6. This Work: Streaming BSM Honest users stream long messages using small internal memory ? speak much, remember little Eve ? Adversaries receive stream using larger memory ? ? Alice Bob ? ? Blah Blah Blah Blah ? Bounded Storage Model: Adv. only restricted to limited storage capacity Potentially large total communication ? ? ? Measure of security: how large can ? be compared to ??

7. ? Prior Constructions in the BSM ? Prior work: Symmetric-key encryption Alice Bob Hello! Exponential gap ? = 2?(?)(poly if efficient protocol) [Maurer92,DR02,ADR02,DM02,Lu02,Vadhan04,Raz16,KRT17,Raz17,GRT18, ] Alice Bob Prior work: Key agreement and beyond Public-key crypto, Oblivious transfer, MPC Quadratic gap ? = ?(?2)[CM97, CCM98, Din01, HCR02, DHRS07, GZ19] Hello! Theorem [Dziembowski-Maurer04]: ? = ?(?2)tight for key agreement Are we done?

8. Our core observation: ? ? The [Dziembowski-Maurer04] lower bound only holds for a restricted model of protocols Only allows a single long message of size ? ? Our main question: Can we get key agreement (KA) (and more?) with ? (?2)? Our main result: Unconditionally-secure (key agreement/OT/MPC) in the BSM with arbitrary gaps adv. vs honest users for all ? ??(?)(poly. for poly-time protocols)

9. Modeling the BSM and Prior Work Prior work: traditional BSM [Maurer92,CM97,CCM98,ADR02,DM02,Lu02,Vadhan04,DHRS07 ] This work: streaming BSM Trusted third party generates one long random string ? Honest parties only need local access Adversary only restricted to remember little about ? Less restrictive model Potential add-ons (a) Single long round [Ding01]: Oblivious Transfer using several long rounds MPC requires many long rounds (b) Uniformly random long rounds (c) All parties only need local access (d) Unlimited local memory for adv.

10. Modeling the BSM and Prior Work Prior work: traditional BSM [Maurer92,CM97,CCM98,ADR02,DM02,Lu02,Vadhan04,DHRS07 ] This work: streaming BSM Add-ons (a), (b), (c), (d) Some works on MPC without (a) Less restrictive model Potential add-ons Prior work: Raz-style BSM [Raz16,KRT17,Raz17,GRT18,GZ19 ] (a) Single long round Add-on (a) only [DziembowskiMaurer04] lower bound for KA doesn t apply to the general streaming BSM Crucially assumes (a) (b) Uniformly random long rounds (c) All parties only need local access (d) Unlimited local memory for adv. This work: Sacrifice (a) for better gap (b), (c), (d) maintained Future work? Any combination of add-ons interesting!

11. Our main question: Can we get key agreement (and more) with ? (?2)? ? ? ? ?? ? #Rounds: ? Theorem 1: there exists KA for any ? 2?(?) ? ?? ? Total communication: ? ? ? ?? pol?(?) #Rounds: ? Theorem 2: there exists OT(/MPC) for any ? 2?(?) ? ?? poly(?) Total comm: ? = ? ? Simulation-secure! Does #rounds / total communication have to scale with gap ?vs ??

12. Our main question: Can we get key agreement (and more) with ? (?2)? ? ? ? ?? ? #Rounds: ? Theorem 1: there exists KA for any ? 2?(?) ? ?? ? Total communication: ? ? ? ?? pol?(?) #Rounds: ? Theorem 2: there exists OT(/MPC) for any ? 2?(?) ? ?? poly(?) Total comm: ? = ? ? Simulation-secure! Theorem 3: Lower bound: large communication/interaction is necessary for KA/OT/MPC ?/? ? ?2 #Rounds (*) ?/? ? ?2 Total comm: ? ?

13. Theorem 1: Key Agreement Main technical lemma: ? 0,12?has high entropy Many individual bits of ? have high entropy Eve ? Alice Bob Consequence: ? ? ,?[?] have a lot of entropy (constant) conditioned on Eve s state ? ? 0,12? ? ? ?,? ? ?[2?] Store ? ? ? ?[2?] Store ? ?[?] Repeat if fail Optimizations: Use randomness extractors Remember many bits Extend keys w/ symmetric-key BSM

14. Theorem 2: Oblivious Transfer ? Alice Bob Additional tool: Interactive hashing [NOVY93] ? ? ? 0,12? Security: Store ? ? b ?[2?] Store ? ? ? ?[2?] Bounded storage for malicious receiver No restrictions on malicious sender (!) Simulation-secure Interactive hashing Input ? ?0,?1s.t. One ??= ? [NOVY93] Handling details more technical: Introduce set interactive hashing for honest-user memory-efficiency tradeoffs Simulation security w/ careful rewinding see paper Send ? if one ??= ? If ? = ?, output ? = ?[?] If yes, output ? = ?[?]

15. Theorem 3: Lower Bound Lower bound for KA of [Dziembowski-Maurer04] Random variable ? s.t. If Alice and Bob share no info., then stateAand stateBshare almost no info conditioned on ? Eve ? 0,1?2 ? Alice Bob ? ? 0,1? ? ? Doesn t seem to extend directly to interaction Main idea: stateA stateB Abstract it as round-reduction compiler apply it iteratively Consequence: #Rounds/Total comm. necessarily scales with gap ? vs ?

16. ? Summary ? Bounded storage model enables unconditionally secure symmetric-key/public-key cryptography Technically: Conceptually: Streaming BSM as right base notion Break quadratic barrier ? ? ?2 for key agreement via interaction Construction of KA/OT/MPC with exponentially large gap ? = 2?(?) Potential add-ons as bonuses Lower bound: interaction is necessary Thank you!