Enhancing Security Definitions for Functional Encryption

Slide Note

This study delves into the realm of functional encryption (FE) against probabilistic queries, highlighting the necessity for improved security definitions to address existing limitations such as counter-intuitive examples and impossibility results. The exploration leads to proposing a new security notion that surpasses both IND-security and SIM-security, aiming to support unbounded ciphertext and key queries while maintaining intuitive security guarantees for FE schemes.

kalila Follow

Uploaded on Apr 03, 2024 | 4 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.

E N D

Presentation Transcript

Functional Encryption against Probabilistic Queries: Definition, Construction and Applications Geng Wang, Shi-Feng Sun, Zhedong Wang and Dawu Gu Shanghai Jiao Tong University May 10 2023

Functional Encryption Master Secret Key User Data (plaintext) Data Provider FE.KeyGen Function Key FE.Enc FE.Dec Cloud Server User Data (ciphertext) Function Output (plaintext) Useful for Big Data Statistics [BSW11]: First formal definition of FE [JLS21],[GP21],[WW21]: ?? from FE for P/poly 2

IND-security for Functional Encryption ? ? ??? ? ?0 = ?(?1) for previously queried ? ? ??? KeyGen(???,?) Admissible condition ?0,?1 ? {0,1} ?? Enc(???,??) ? ? ?0 = ?(?1) for challenge ciphertexts ?0,?1 ??? KeyGen(???,?) ? IND-secure: Pr ? = ? 1/2 negligible for all **admissible** adversary 3

SIM-security for Functional Encryption Real Game Ideal Game ? ? ? ? ? ? ??? ??? ? ? ??? KeyGen(???,?) ??? ? ? ? ?(?) ?? Enc(???,?) ?? ? ? ? ??? KeyGen(???,?) ?(?) ??? ?,? ?,? 4

Limitations of IND-based and SIM-based Security Impossibility Results for SIM- secure FE: [BSW11]: SIM-secure FE for P/poly cannot be constructed for unbounded ciphertext queries before a single key query; [AGVW13]: SIM-secure FE for P/poly cannot be constructed for unbounded key queries before a single ciphertext query. [AKW18]: Impossibility results also hold under random oracle model. Counter-intuitive Examples for IND-secure FE : one-way permutations In an IND-security game, admissible adversaries are not allowed to make a single query FE degenerates into PKE, ?? = PKE.???(PKE.??,?) and ???= {PKE.??,?}; However, PKE.?? leaks the message ?, while intuitively secure FE should only leak ? ? (unable to recover ?). 5

The need for a new security definition We wish that a good security definition for FE should satisfy the following requirements: The new security notion must avoid the counter-intuitive example in the literature; There must be a construction of FE for P/poly under the new security notion that supports both unbounded ciphertext and key queries; Any SIM-secure FE scheme should satisfy the new security notion, so that we are able to discuss the unbounded ciphertext/key security for existing SIM-secure schemes; The new security notion should be stronger than IND-security, so that the properties for IND-security also hold for this new security notion. IND-security SIM-security good definition unbounded ct + key queries intuitively secure for OWFs 6

A (failed) attempt: Distributional Indistinguishability ? ? ??? ?0,?1: distributions on ? ?0 ??(?1) for previously queried ? ? ??? KeyGen(???,?) DI admissible condition ?0,?1 [0,1] ? {0,1} ?? ?? ?? Enc(???,??) ? ? ?0 ??(?1) for challenge distributions ?0,?1 ??? KeyGen(???,?) DI-secure: Pr ? = ? 1/2 negligible for all **admissible** adversary ? What s the problem? Let ? be a **trapdoor** function. Even if ? ?0 ??(?1), ? can still break the scheme while holding the trapdoor! 7

Strict Computational Indistinguishability Definition: Let ? be a p.p.t. algorithm that outputs a pair of distributions ?0,?1, we say that distributions from ? are strictly computationally indistinguishable, if there is no auxiliary string ??? corresponding with ?0,?1such that (?0,???) and (?1,???) are computational distinguishable. In the definition above, the auxiliary string ??? can be viewed as the trapdoor in distributions ?0,?1. This additional auxiliary string has no affect on function families without trapdoors. Just consider PKE, for ??,?? PKE.??????, ?? can be the auxiliary string if ?? is fixed, but if we choose random ??, then there is no such ??? as long as PKE has semantic security. 8

Our new definition: pIND-based security ? ? ??? ?,?0,?1: distributions ? ?0 ???(?1) for previously queried ? ? [0,1] ??? KeyGen(???,?) Our new admissible condition ?0,?1 [0,1] ? {0,1} ?? ?? ?? Enc(???,??) ? [0,1] ? ?0 ???(?1) for challenge distributions ?0,?1 ??? KeyGen(???,?) pIND-secure: Pr ? = ? 1/2 negligible for all **admissible** adversary ? 9

SIM-security implies pIND-security Theorem: If FE is a SIM-secure functional encryption scheme, then FE is also pIND- secure. Proof Sketch: Let FE be SIM-secure. Suppose that ? wins the pIND-security game with non-negligible advantage, we show that ? is not admissible, i.e. we can find an auxiliary string used to distinguish the two distributions ?(?0) and ?(?1). Note that ? can also be viewed as adversary in SIM-security game. Since ? has non-negligible advantage in distinguishing ?(?0)?(?1) in real game, it also has non-negligible advantage in the ideal game. We let all randomness used in a SIM-security game be the auxiliary string. Then the ideal game serves as a distinguisher between ?(?0) and ?(?1). 10

pIND imples IND & 1-CT implies many-CT Theorem: If FE is a pIND-secure functional encryption scheme, then FE is also IND- secure. Proof Sketch: An adversary in IND-security game is also adversary in pIND-security game. The result thus follows. Theorem: If FE is a 1-CT pIND-secure functional encryption scheme, then FE is also many-CT pIND-secure. Proof Sketch: Use standard hybrid arguments. From the theorem above, we see that pIND-security does not suffer from the [BSW11] impossible result. 11

Fully pIND-secure FE for P/poly: Construction The construction relies on the following primitives: Sel: A sel-IND secure pkFE for P/poly; OneCT: An ad-pIND secure 1-CT skFE scheme for P/poly; Sym: A pseudorandom symmetric encryption scheme; PRF: A pseudorandom function family. The construction is as follows (we omit some details): Setup: Return (??,???) from Sel.Setup. KeyGen: generates a function key for the following function ?(???,?,?): If ? = 1, output the symmetric decryption of a random value; Otherwise, output the OneCT function key of ? using ???. Enc: Encrypt the message using OneCT as ?0and the key of OneCT using Sel (other components are 0) as ?1. Dec: Decrypt ?0using the decryption of ?1from the function key. The proof is the same as [ABSV15], and we omit the details. 12

The existence of pIND-secure 1-CT skFE Existence of one-way functions [GVW12] consturction SIM-secure unbounded-CT 1-key message-private skFE SIM implies pIND pIND-secure unbounded-CT 1-key message-private skFE [BS15] lifting (extend to pIND) pIND-secure unbounded-CT 1-key function-private skFE swap Enc and KeyGen pIND-secure 1-CT unbounded-key function-private skFE 13

Message-privacy to Function-privacy for pIND The construction relies on the following primitives: skFE: An ad-pIND secure message-private skFE for P/poly; Sym: A pseudorandom symmetric encryption scheme; PRF: A pseudorandom function family. The construction is as follows (we omit some details): Setup: Return ??? from skFE.Setup along with 3 Sym keys ?1,?2,?3. KeyGen: Let ??= ???.???(??,?). Use skFE.KeyGen to generate a function key for the following function ??1,?2,?3(?,?1,?2,?3,?): For each ? = 1,2,3, if ?? , let ? = ???.???(??,??) and return ?(?); Otherwise return . Enc: Sample a random seed ? and encrypt (?,?1, , ,?) using ???. Dec: Decrypt directly using skFE.Dec. The proof is similar to [BS15], we refer readers to our paper. 14

Application: Blind Hash System KeyGen ??? Hash Function Blinded Hash ? HashGen One-wayness: unable to recover ? (?) = ?(?) Enc Message ? Ciphertext ? 15

Blind Hash System: Construction Let FE be a pIND-secure functional encryption scheme, we construct a one-way blind hash system as follows: Setup: Run FE.Setup and output the public key ?? and the master secret key ???. HashGen(???, ): Let be the function which pads the output of h from ? bits into ? bits by filling 0s. Let function ? be defined as: ? (?||?) = (?)||?. Calculate ??? ??.??????(???,? ). Let the blinded hash ?(?) be defined as: Let ? ??.???(??? ,?); Output the first ? bits of ?. Enc(??,?): Let ? {0,1}?, output ??.???(??,?||?). The one-wayness of the construction above requires pIND-secure FE, since IND-secure FE cannot handle (one-way) hash functions. 16

Application: Semi-universal Proxy Re-encryption PRE.ReKeyGen RSA.Dec RSA.?? ??PRE RSA ECC.Dec PRE. Enc ECC.?? PRE. ?? ??PRE ECC ? ? . ??PRE LWE PRE. ReEnc LWE.Dec LWE.?? 17

Semi-universal PRE: Construction Let FE be a pIND-secure functional encryption scheme, we construct a semi-universal PRE scheme as follows: KeyGen: Output ??,?? FE.?????. Enc(??,?): Sample a random seed ?, and output ?? FE.???(??,?||?). ReKeyGen(???,PKE,???): Sample a random key ?, and let ?(?||?):= PKE.???(???,?;PRF(?,?)). Return FE.??????(???,?). ReEnc(??? ?,??): Output FE.???(??? ?,??). The IND-CPA of the construction above requires pIND-secure FE, since IND-secure FE cannot handle public-key encryption. We note that the construction above cannot use DI-secure FE or IND-secure randomized FE. 18

Conclusion and Future Works Our Contribution: New security definition for FE between SIM and IND: pIND-security Construction of pIND-secure FE for P/poly supporting unbounded ciphertext and key queries Applications from pIND-secure FE: blind hash system and semi-universal proxy re-encryption Future Works: Direct constructions for pIND-secure FE More applications from pIND-secure FE Using pIND-secure FE to simplify the construction of iO 19