Cryptography in Bounded Storage Model: Ensuring Secure Communication
Cryptography in the Bounded Storage Model provides insights into securing communication with secrecy and authenticity. The model limits adversaries' memory without runtime restrictions, ensuring unconditional security for various primitives. Explore how this model safeguards messages from eavesdroppers and guarantees the message's origin, offering efficient protection against potential threats.
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
Authentication in the Bounded Storage Model Yevgeniy Dodis Willy Quach Daniel Wichs New York University Northeastern University Northeastern University NTT Reseach EUROCRYPT 2022
Cryptography 101: Secure Communication Secrecy: message is hidden from Eve Eve Authenticity: Bob is convinced message comes from Alice (and not from Eve) Alice Bob Hello! Without restriction on adversaries, key |message|[Shannon49] Key can only be reused a few times Public-key setting impossible
Cryptography 101: Secure Communication Secrecy: message is hidden from Eve Eve Authenticity: Bob is convinced message comes from Alice (and not from Eve) Alice Bob Hello! Without restriction on adversaries, key |message|[Shannon49] Restrict to efficient adversaries: typically polynomial run-time Requires computational assumptions: at least ? ?? Cryptographers seldom sleep well
The Bounded Storage Model (BSM) [Maurer92] Secrecy: message is hidden from Eve Eve Authenticity: Bob is convinced message comes from Alice (and not from Eve) Alice Bob Hello! Alternative assumption on adversaries: limited memory No restriction on runtime of adversaries Honest users use much less memory than the adversary Surprisingly, unconditional security for many primitives in that model!
The Bounded Storage Model (BSM) [Maurer92] Blah Blah Secrecy: message is hidden from Eve Blah Eve Authenticity: Bob is convinced message comes from Alice (and not from Eve) Alice Bob Blah Blah Blah Alternative assumption on adversaries: limited memory No restriction on runtime of adversaries Honest users use much less memory than the adversary Surprisingly, unconditional security for many primitives in that model!
The Bounded Storage Model (BSM) [Maurer92] ??? Blah Blah Secrecy: message is hidden from Eve Blah Eve Authenticity: Bob is convinced message comes from Alice (and not from Eve) Alice Bob Blah BlahBlah Blah BlahBlah Blah Blah Blah Alternative assumption on adversaries: limited memory No restriction on runtime of adversaries Honest users use much less memory than the adversary Surprisingly, unconditional security for many primitives in that model!
The (Streaming) BSM [Raz16,GuanZhandry19,DodisQuachWichs21] Memory ? Memory ? Memory ? Blah Blah Blah Blah Users stream their messages Messages are possibly long, of size ? Generated and processed using memory ? Adversary has memory ? ?, and unbounded runtime
Prior Work in the BSM Adversary/Honest Memory Gap Symmetric-Key Encryption [Maurer92, ,Vadhan04,Raz16] [Cachin-Maurer97, , Guan-Zhandry19] Key Agreement (!) Oblivious Transfer, MPC Unconditional security in the BSM (!) Schemes are reusable (up to an exponential number of times) Security power of the adversary (compared to honest users)
Prior Work in the BSM Adversary/Honest Memory Gap ? = 2?(?) Symmetric-Key Encryption [Maurer92, ,Vadhan04,Raz16] ? = ?(?2)* [Cachin-Maurer97, , Guan-Zhandry19] Key Agreement (!) ? = ?(?2)* Oblivious Transfer, MPC Unconditional security in the BSM (!) Schemes are reusable (up to an exponential number of times) Security power of the adversary (compared to honest users) If ? is exponential, honest users need to stream exponentially many bits For polynomially efficient honest users, use ? = poly(?) What about authentication? *Can make gap exponential at the cost of much larger communication and interaction [DQW21]
Our Results: Authentication in the BSM 1. Symmetric-key authentication with long tags Tags are larger than the adversary memory Up to exponential gap: ? = 2?(?) 2. Symmetric-key authentication with short tags Tags fit in honest user memory Quadratic gap: ? = ?(?2) (tight) All schemes have unconditional security and are reusable 3. Public-Key Signatures Quadratic gap: ? = ?(?2) (tight)
Our Results: Authentication in the BSM 1. Symmetric-key authentication with long tags Tags are larger than the adversary memory Up to exponential gap: ? = 2?(?) 2. Symmetric-key authentication with short tags Tags fit in honest user memory Quadratic gap: ? = ?(?2) (tight) All schemes have unconditional security and are reusable 3. Public-Key Signatures Quadratic gap: ? = ?(?2) (tight)
Symmetric-Key Authentication (MACs) in the BSM Alice ? Bob ? potentially large: ? streamed sk sk Correctness: Bob accepts messages authenticated by Alice
Symmetric-Key Authentication (MACs) in the BSM Eve ? Alice ? Bob ? potentially large: ? streamed sk sk Correctness: Bob accepts messages authenticated by Alice Unforgeability:
Symmetric-Key Authentication (MACs) in the BSM Eve ? Alice ? Bob ? potentially large: ? streamed sk sk Correctness: Bob accepts messages authenticated by Alice Unforgeability: Reusability: Eve can see arbitrarily many authentications
Symmetric-Key Authentication (MACs) in the BSM Eve ? Alice ? Bob ? potentially large: ? streamed sk sk Correctness: Bob accepts messages authenticated by Alice Unforgeability: Reusability: Eve can see arbitrarily many authentications
Symmetric-Key Authentication (MACs) in the BSM Eve ? Alice ? Bob ? potentially large: ? streamed sk sk Correctness: Bob accepts messages authenticated by Alice Unforgeability: Reusability: Eve can see arbitrarily many authentications
Symmetric-Key Authentication (MACs) in the BSM Eve ? Alice ? Bob ? sk sk Correctness: Bob accepts messages authenticated by Alice Unforgeability: Eve cannot make Bob accept fake authentications Reusability: Eve can see arbitrarily many authentications
Symmetric-Key Authentication (MACs) in the BSM Eve ? Alice ? Bob ? sk sk Correctness: Bob accepts messages authenticated by Alice Unforgeability: Active Eve cannot make Bob accept fake authentications Streaming channel with Alice to receive authentication of her choice Streaming channel with Bob to check whether authentications are accepted Can modify authentications on the fly (in a streaming manner, using memory ?)
Symmetric-Key Authentication (MACs) in the BSM Eve ? Alice ? Bob ? sk sk Correctness: Bob accepts messages authenticated by Alice Unforgeability: Active Eve cannot make Bob accept fake authentications Streaming channel with Alice to receive authentication of her choice Streaming channel with Bob to check whether authentications are accepted Can modify authentications on the fly (in a streaming manner, using memory ?)
Symmetric-Key Authentication (MACs) in the BSM Eve ? Alice ? Bob ? sk sk Correctness: Bob accepts messages authenticated by Alice Unforgeability: Active Eve cannot make Bob accept fake authentications Streaming channel with Alice to receive authentication of her choice Streaming channel with Bob to check whether authentications are accepted Can modify authentications on the fly (in a streaming manner, using memory ?)
Constructing MACs with Long Tags Eve ? Alice ? Bob ? sk sk Main idea: encrypt tags of an information-theoretic one-time MAC Symmetric-key encryption in the BSM Intuition for security:
Constructing MACs with Long Tags Eve ? Alice ? Bob ? sk sk Main idea: encrypt tags of an information-theoretic one-time MAC Symmetric-key encryption in the BSM Intuition for security: 1. If Eve passively observes authentications, security of applies
Constructing MACs with Long Tags Eve ? Alice ? Bob ? sk sk Main idea: encrypt tags of an information-theoretic one-time MAC Symmetric-key encryption in the BSM Intuition for security: 1. If Eve passively observes authentications, security of applies 2. If Eve tries to relay one authentication to Bob, one-time MAC security applies Can still hurt security of MAC needs to authenticate the encryption too
Constructing MACs with Long Tags Eve ? Alice ? Bob ? ? = 2?(?) large tags sk sk Main idea: encrypt tags of an information-theoretic one-time MAC Symmetric-key encryption in the BSM Intuition for security: 1. If Eve passively observes authentications, security of applies 2. If Eve tries to relay one authentication to Bob, one-time MAC security applies Can still hurt security of MAC needs to authenticate the encryption too In general Eve can delay/mix her input/output streams Still works
Our Results: Authentication in the BSM 1. Symmetric-key authentication with long tags Tags are larger than the adversary memory Up to exponential gap: ? = 2?(?) 2. Symmetric-key authentication with short tags Tags fit in honest user memory Quadratic gap: ? = ?(?2) (tight) All schemes have unconditional security and are reusable 3. Public-Key Signatures Quadratic gap: ? = ?(?2) (tight)
MAC with Short Tags In previous construction, tags don t even fit in Eve s memory ? How short can the tags be? Can we have tags that fit in honest users memory ?? No need to stream nor send long messages! Impossible if ? ?2 (Eve cannot store too many tags) Eve ? Alice ? Bob ? We (surprisingly) can! Small: ?? sk sk
MAC with Short Tags from Razs Lower Bound [Raz16] proves that learning parities is hard using bounded memory 0,1? Rephrasing: ???? ??, ??,? is an unconditionally secure weak PRF against adversaries with memory ? = ? ?2 (tight) Noiseless LPN? MACs from LPN? Generic construction from key-homomorphic weak PRFs [DodisKiltzPietrzakWichs12] in the standard sense. More work required in the bounded memory setting Gives a MAC in the BSM with short tags, where ? = ?(?2) (tight)
MAC with Short Tags from Razs Lower Bound [Raz16] proves that learning parities is hard using bounded memory 0,1? Rephrasing: ???? ??, ??,? is an unconditionally securekey-homomorphic weak PRF against adversaries with memory ? = ? ?2 (tight) Noiseless LPN? MACs from LPN? Generic construction from key-homomorphic weak PRFs [DodisKiltzPietrzakWichs12] in the standard sense. More work required in the bounded memory setting Gives a MAC in the BSM with short tags, where ? = ?(?2) (tight)
Our Results: Authentication in the BSM 1. Symmetric-key authentication with long tags Tags are larger than the adversary memory Up to exponential gap: ? = 2?(?) 2. Symmetric-key authentication with short tags Tags fit in honest user memory Quadratic gap: ? = ?(?2) (tight) All schemes have unconditional security and are reusable 3. Public-Key Signatures Quadratic gap: ? = ?(?2) (tight)
Signatures in the (Streaming) BSM Public, long, authenticated stream, once for all verification key Alice ? Bob ? potentially large: ? vd sk Small verification digest Small signing key Verify vd,?,? = Sign(sk,?) Potentially long, streamed
Signatures in the (Streaming) BSM Public, long, authenticated stream, once for all verification key Alice ? Bob ? potentially large: ? vd sk Small verification digest Small signing key Verify vd ,?,? = Sign(sk,?) Potentially long, streamed
Signatures in the (Streaming) BSM Public, long, authenticated stream, once for all verification key Alice ? Bob ? potentially large: ? vd sk Small verification digest Small signing key Eve ?
Signatures in the (Streaming) BSM Public, long, authenticated stream, once for all verification key Alice ? Bob ? potentially large: ? vd sk Small verification digest Small signing key Verify vd,?,? = Sign(sk,?) Eve ?
Constructing Signatures (1) Public, long, authenticated stream, once for all verification key Alice ? Bob ? Key agreement potentially large: ? sk sk Small signing key BSM MAC MAC(sk,?) Potentially long, streamed
Constructing Signatures (1) Public, long, authenticated stream, once for all verification key Alice ? Bob ? Key agreement potentially large: ? sk sk Small signing key BSM MAC MAC(sk,?) Potentially long, streamed
Constructing Signatures (1) Public, long, authenticated stream, once for all verification key Alice ? Eve ? Key agreement potentially large: ? sk sk Small signing key BSM MAC MAC(sk,?) Potentially long, streamed
Constructing Signatures (1) Public, long, authenticated stream, once for all verification key Alice ? Eve ? Key agreement potentially large: ? sk sk Small signing key How to agree on a key using a single broadcast message ?
Set Key Agreement Public, long, authenticated stream Alice ? Bob ? potentially large: ? sk = sk1, ,sk? sk?= sk? ? ?,? [?] 1. Alice and Bob share |?| keys
Set Key Agreement Public, long, authenticated stream Alice ? Bob ? potentially large: ? sk = sk1, ,sk? sk?= sk? ? ?,? [?] 1. Alice and Bob share |?| keys
Set Key Agreement Public, long, authenticated stream Alice ? Bob ? potentially large: ? sk = sk1, ,sk? sk?= sk? ? ?,? [?] ??? ??? 1. Alice and Bob share |?| keys 2. Some sk?,? ? looks uniform to Eve even given all the other keys The index ?depends on Eve Alice and Bob don t know ?
Constructing Signatures (2) Public, long, authenticated stream, once for all verification key Alice ? Bob ? Set key agreement potentially large: ? Small signing key sk? sk BSM MAC MAC sk?,? Potentially long, streamed ? [?] Security inherits from MAC security with sk?
Summary We study authentication in the (streaming) bounded storage model Adversaries have unlimited computational power, but limited memory Enables unconditional security and reusability (!) We give three constructions: 1. A MAC with long tags Adversaries have exponentially large memory ? = 2?(?), but tags are even larger 2. A MAC with short tags: tags fit in honest users memory (!), no need to stream Adversaries have quadratic memory ? = ?(?2) (tight) 3. A signature scheme Adversaries have quadratic memory ? = ?(?2) (tight) Both verification keys and signatures are longer than ? Thanks for listening! https://ia.cr/2022/690 Thanks Eysa Lee for the drawings!
