Dual System Encryption: Concept, History, and Recent Works
Explore the concept and history of dual system encryption, including the strategy of security proof, partitioning technique, and the adaptive security model. Understand how security is ensured through mathematical problem complexities and adversary challenges.
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
Dual System Encryption: Concept, History and Recent works Jongkil Kim
Introduction Strategy of Security Proof Partitioning Technique Dual System Encryption Semi-functionality Nominally Semi-functionality Encodings References
Strategy of Security Proof Claim: Our Construction is secure under a security model Mathematical problem is hard Proof by contradiction Assume that Our Construction is not secure under a security model Mathematical Problem is not hard
Strategy of Security Proof Assume that Our Construction is not secure under a security model Mathematical Problem is not hard Assume there exists an adversary to harm our security model We can break mathematical hard problem using the adversary Show that our security model equals to mathematical hard problem.
Strategy of Security Proof Harms the security model ? An adversary having non-negligible advantage to win security games. Notation and Definition X: a decryption, Y: a predicate , R: Function Between X and Y R(X,Y) = 1, then a key can decrypt the ciphertext. Otherwise (R(X,Y) = 0), it does not. Example, in IBE, R(IDA, IDA) = 1, but R(IDA, IDB) = 0 Public key encryption system consists of four radnomized algorithms: Setup, KeyGen, Enc, Dec
Adaptive security model (CPA Security) Selective Adversary Simulator Y Public key query Setup Run Setup Public key ? [1,?1] Private key query (Xi; ) Phase I Run KeyGen(MSK,PP, Xi) Private key Challenge query (M0, M1, Y) Challenge B {0,1} ?.?.? {Xi;? [1,?1]} Run Enc(PP, MB ,Y) Challenge Cipehrtext Private key query (Xi; ) ? [?1+ 1,?] Phase II ?.?. Run KeyGen(MSK, PP, Xi) Private key ? {Xi;? [?1+ 1,?]} Guess? 0 or 1 Guess
Partitioning Technique Key Space Key Space X1 X1 Phase I Phase II X8 X8 X2 X2 X9 X9 X5 X5 Challenge Y Y X4 X4 Xq Xq X7 X7 X6 X6 X10 X10 Partitioning the key space => Only Selective Security if functionality of Public key scheme become complecate. (such as ABE, IPE, Spatial Encryption , )
Dual System Encryption Introduced by Waters [Crypto 2009] It uses semi-functional ciphertext and semi- functional keys which are only used in the security proof. In Dual System Encryption, the security of an encryption scheme is proved by showing following Semi-functional ciphertext invariance Semi-functional key invariance Semi-functional security
Semi-functionality Decrypt? Normal Key Semi-functional Key Normal Ciphertext Yes! Yes! Semi-functional Ciphertext Yes! No We must show that two security games are invariant GameReal: All keys and the challenge ciphertext are normal GameFinal: All keys and the challenge ciphertext are semi- functional. Additionally, the message are replaced by the random message. Between both, Game0, Game1, Game2, Gameq
Semi-functional Ciphertext Invariance Invariance between GameReal andGame0 Simulator Adversary Public key query Setup Public key Private key query (X) Phase I GameReal Private key (Invariant) Challenge query (M0, M1, Y) Semi-functional Challenge B {0,1} Challenge Cipehrtext (MB) Game0 Private key query (X) Phase II Private key Guess? 0 or 1 Guess
Invariance of two games Assume that two games are indistinguishable Mathematical Problem is hard Assume there exists an adversary who distinguishes two games We can break mathematical hard problem using the adversary Show that distinguishing two games equals to mathematical hard problem.
Semi-functional Ciphertext Invariance Invariance between Game0 and Gameq Simulator Game0 Adversary Private key query (X1) Semi-functional Phase I Game1 Game2 Private key1 Private key query (X2) Semi-functional Private key2 Challenge query (M0, M1, Y) Semi-functional Challenge B {0,1} Challenge Cipehrtext (MB) Private key query (Xq) Semi-functional Phase II Gameq Private keyq
Semi-functional Key Invariance Semi-functional Key Invariance Mathematical Induction We already showed Game0 is invariant with GameReal We now show Gamek is invariant with Gamek-1 This is a critical part of the security proof because the relation between kth key and challenge ciphertext is changed. We must proof the normal key which can decrypt the normal CT is indistinguishable from the semi- function key which cannot.
Semi-functional Key Invariance Invaraiace between Gamek-1 and Gamek Assume there exists an adversary who distinguishes two games We can break mathematical hard problem using the adversary Show that distinguishing two games equals to mathematical hard problem. No limitation for the simulator in the security model! + The simulator can distinguish the kth key by generating valid semi- functional ciphertext for kth key and trying to decrypt it with the kth key.
Dual System Encryption How to prevent this paradox In Waters construction, If the simulator generate the semi-functional ciphertext to distinguish Tagc must be equal to Tagk. Tagc = F(IDY) = A IDY + B Tagk = F(IDX) = A IDX + B But, this is hidden by pair wise independent argument because IDX does not equal to IDY if A and B are initially information theoretically hidden.
Nominally Semi-functionality Introduced by Lewko and Waters[TCC 2010] Similar with Water s Construction If the simulator generates a semi-functional ciphertext for testing whether kth key is semi- functional or normal, semi-functional part is going to be cancel out. So, kth key is nominally semi-functional because it can decrypt the semi-functional challenge ciphertext.
How to hide the Nominality We also must show that this nominally semi-functional key is invariant with Semi-functional key. In other words, we must show that the correlation between semi-functional parts in the nominally semi- functional key and the challenge ciphertext is hidden. By using following Pair wise independent n-wise independent Linearly independent Information Theoretically Hidden Maybe there are some more but not so many!
Hidden Lemma General Lemma for semi-functional key invariance Assume there exists an adversary who distinguishes Gamek-1 and Gamek We can break mathematical hard problem(SD) using the adversary But, this is the abstract of two lemmas
Nominally Semi-functionality IBE in composite order KeyGen(PP, MSK, ID) -> SKID = {K1, K2} K1:= g1 + r(A ID + B) Z1, K2:= g1 r Z2 Enc(PP, ID) -> CTID = {C, C1, C2} C:= M e(g1, g1) s, C1:= g1 s, C2:= g1 s(A ID +B) SFKeyGen(PP, MSK, ID) -> SKID = {K1, K2} K1:= g1 + r(A ID + B) g2r aZ1, K2:= g1 r g2 r Z2 SFEnc(PP, ID) -> CTID = {C, C1, C2} C:= M e(g1, g1) s, C1:= g1 s g2 s , C2:= g1 s(A ID +B) g2 s b
Hidden Lemmas Let Gamek is the game identical with Gamek-1 , but the kth key is nominally semi functional. Assume there exists an adversary who distinguishes Gamek-1 and Gamek We can break mathematical hard problem using the adversary NSFKeyGen(PP, MSK, ID) -> SKID = {K1, K2} K1:= g1 + r(A ID + B) g2r (A ID + B ) Z1, K2:= g1 r g2r Z2 SFEnc(PP,ID) -> CTID = {C, C1, C2} C:= M e(g1, g1) s, C1:= g1 s g2 s , C2:= g1 s(A ID +B) g2 s (A ID +B )
Hidden Lemmas Let Gamek is the game identical with Gamek-1 , but the kth key is nominally semi functional. Assume there exists an adversary who distinguishes Gamek and Gamek We can break information theoretically hidden argument using the adversary NSFKeyGen(PP, MSK, ID) -> SKID = {K1, K2} K1:= g1 + r(A ID + B) g2r (A ID +B )Z1, K2:= g1 r g2 r Z2 SFEnc(PP, ID) -> CTID = {C, C1, C2} C:= M e(g1, g1) s, C1:= g1 s g2 s , C2:= g1 s(A ID +B) g2 s (A ID + B ) a b
Why this is possible? The semi-functional parts of private key and ciphertext are just twins of their normal parts But, why is applying information hidden argument possible? Public key and other semi- functional keys does not reveal any information about the semi- functional parts!
Semi-functional Security Invariance between Gameq andGameFinal Simulator Adversary Public key query Setup Public key Private key query (X) Semi-functional Phase I Gameq Private key (Invariant) Challenge query (M0, M1, Y) Semi-functional Challenge R: Rand message B {0,1} Challenge Cipehrtext (MB) R GameFinal Private key query (X) Semi-functional Phase II Private key Guess? 0 or 1 Guess
DSE via Encodings Pair Encoding [Eurocrypto 2014] and Predicate Encoding [TCC 2014] Many public key schemes proved by Dual System Encryption share a same proof strategy. It means it can be formalized! => New direction of the security proof! We only need our new scheme satisfy following properties Linearity Parameter Vanishing Perfect Master key hiding
DSE via Encoding Linearity K( ;x,h,r ) + K( ;x,h,r ) Parameter vanishing K( ;x,h,0) = K( ;x,h ,0) Perfect master key hiding Given c(s;y,h), for all , , If R(x,y)=0, K( ;x,h,r) and K( ;x,h,r) are statistically invariant. = K( + ;x,h,r +r )
Encoding example (IBE) Construction Setup( ) -> N = p1p2p3, PP = { g1A, g1B }, MSK = { , X3} KeyGen(PP, MSK, ID) -> SKID = {K1, K2} K1:= g1 + r(A ID + B) Z1, K2:= g1 r Z2 Enc(PP, ID) -> CTID = {C, C1, C2} C:= M e(g1, g1) s, C1:= g1 s, C2:= g1 s(A ID +B) Dec(SKID, CTID) M = C e(K2, C2)/e(K1, C1)
Encoding example Encoding K( ;ID,(A,B),r) = ( + r(A ID + B), r) c(s;ID,(A,B)) = (s, s(A ID + B)) Linearity ( + r(A ID + B), r) + ( + r (A ID + B), r ) =( + + (r+r ) (A ID + B), r+r ) Parameter vanishing ( + 0 (A ID + B), 0) + ( + 0(A ID + B ), 0)
Encoding example Encoding K( ;ID,(A,B),r) = ( + r(A ID + B), r) c(s;ID,(A,B)) = (s, s(A ID + B)) Perfect Master key hiding Given (s, s(A ID* + B)) For ID which does not equal to ID*, A ID + B is randomly distributed (pairwise independent). Hence, ( + r(A ID + B),r) is statistically invariant with ( + r(A ID + B),r) to the adversary
References [Eurocrypto 2014] N. Attrapadung. Dual system encryption via doubly selective security: Framework, fully secure functional encryption for regular languages, and more. In P. Q. Nguyen and E. Oswald, editors, EUROCRYPT, volume 8441 of Lecture Notes in Computer Science, pages 557{577. Springer, 2014. [Crypto 2009] B. Waters. Dual system encryption: Realizing fully secure ibe and hibe under simple assumptions. In S. Halevi, editor, CRYPTO, volume 5677 of Lecture Notes in Computer Science, pages 619{636. Springer, 2009. [TCC 2014] H. Wee. Dual system encryption via predicate encodings. In Y. Lindell, editor, TCC, volume 8349 of Lecture Notes in Computer Science, pages 616{637. Springer, 2014. [TCC 2010] A. Lewko and B. Waters. New techniques for dual system encryption and fully secure hibe with short ciphertexts. In TCC, 2010.
