New Assumptions for Achieving Chosen Ciphertext Security in Cryptography

This research work focuses on presenting new assumptions for achieving chosen ciphertext security in public key encryption. The study aims to clarify the necessary and sufficient assumptions to realize general cryptographic primitives, particularly focusing on CCA secure PKE and KEM. The ultimate goal is to map out the implications and separations of various cryptographic primitives, with an emphasis on security against Bleichenbacher's attacks and its implications on NM and UC security. The research investigates different primitives that imply CCA secure PKE/KEM, such as NIZK, CPA, IBE, Lossy PKE, and more. It also explores the concept of plaintext awareness, weak simulatability, and the relationships between different security parameters in encryption schemes.

• Cryptography
• Chosen Ciphertext Security
• Public Key Encryption
• Cryptographic Primitives
• New Assumptions

ktenn Follow

Uploaded on Dec 07, 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. PKC 2016 @Taipei, Taiwan 3/7 - 3/9 ePrint 2016/235 Trading Plaintext-Awareness for Simulatability to Achieve Chosen Ciphertext Security Takahiro Matsuda ( Goichiro Hanaoka ( ) ) t-matsuda@aist.go.jp 2016/3/7 Mon. This work presents new assumptions for CCA PKE 1 1 1

2. Background It is important to clarify (necessary and) sufficient assumption to realize general cryptographic primitives To better understand how & why we can construct/prove security of the primitives Ultimate goal: Draw a complete map among all cryptographic primitives About implications & separations This work focuses on CCA secure PKE (and KEM) CCA ??? Desirable security for PKE Security against Bleichenbacher s attack Implication to NM, UC security PKE/KEM 2

3. Background Q. Which primitive(s) implies CCA secure PKE/KEM ?? CCA ??? PKE/KEM [DDN91] [HLW12] [CHK04,Kiltz06] [PW08,RS09,KMO10,Wee10] Detectable CCA PKE CPA PKE + NIZK IBE (or TBE) TDF w/ additional properties [HO13] [HO12] [MH14b] [MH14a] Lossy PKE w. large PT space Hom. PKE w/ additional properties CPA PKE + UCE CPA PKE + Point Obf. [HK15] [Dac14] [MH15] [SW14] 1-bit PKE w/ circular security & reproducibility PKE satisfying sPA1 (for many keys) & weak simulatability Sender NCE + KDM SKE iO + OWF 3

4. Dachman-Soled@PKC14 [Dac14] PKE satisfying (Statistical) Plaintext Aware1 under 2k+2 keys (sPA12k+2) & Weak Simulatability CCA PKE k: security parameter Plaintext-Awareness (PA) [BR94,BP04] If you generate a ciphertext you must know the plaintext Standard model PA[BP04] has several variations Our focus is on Statistical PA1 (sPA1), and its many keys extension C.f.) CPA + PA1 CCA1 Weak Simulatability [DN00, MMS12] Ciphertext(-like strings) can be sampled obliviously, w/o knowing plaintext m > CPA security 4

5. [Dac14] sPA12k+2, Weakly Simulatable PKE CCA PKE Motivation PA typically requires a knowledge assumption In addition, [Dac14] needs a multi-key extension of PA: sPA1 under 2k + 2 keys[MSS12] denoted by sPA12k + 2 If x > y 1, then sPA1x sPA1y, but the opposite implication/separation is unknown [Dac14] observed that it seems difficult to replace PA1 with CCA1 security in her construction k: security parameter The number of keys We investigate whether the strength of PA in [Dac14] can be weakened, thereby contribute to clarifying new general assumptions for CCA PKE 5

6. Our Results Based on [Dac14], we show 2 CCA PKE constructions whose assumptions are a trade-off with that of [Dac14] + + sPA12, CPA PKE Trapdoor- Simulatable PKE CCA PKE Const- ruction1 (Actually, we construct KEMs) sPA11, 1-Bounded CCA PKE Trapdoor- Simulatable PKE Const- ruction2 CCA PKE

7. [Dac14] vs. Ours [Dac14] sPA12k+2, Weakly Simulatable PKE Ours sPA12, CPA PKE + sPA11, 1-BCCA Trapdoor- Simulatable PKE CCA PKE CCA PKE PKE + Trapdoor- Simulatable PKE CCA PKE sPA12k+2> sPA12> sPA11 Weak simulatability < Trapdoor-simulatability These are formally incomparable Ours do not require PA and simulatability to be satisfied by a single building block PKE (qualitatively) Ours trade the strength of PA for simulatability in [Dac14] Our constructions give new recipes for CCA PKE/KEM 7

8. Talk Outline Building Blocks Proposed Constructions Security Proof Overview Overview of Proposed Constructions Based on the double-layered construction [MS09,HLW12] Trapdoor Simulatable Puncturable TBE [MH14] Trapdoor- Simulatable Commitment Outer encryption CCA KEM Double Layer [MS09] sPA12, CPA KEM sPA11, 1-Bounded CCA KEM Inner encryption or Building blocks for outer encryption can be constructed only from Trapdoor simulatable PKE 8

9. Key Encapsulation Mechanism (KEM) = public-key part of hybrid encryption Syntax Key Generation: (pk, sk) KKG(1k) Encapsulation: (C, K) Encap(pk) K: a session-key used by SKE Decapsulation: K or Decap(sk, C) CCA Security: b {0,1} Real K*1 Random K*0 pk, C*, K*b C C* C Dec. Oracle K = Decap(sk, C) A K PPT A: |Pr[b = b] 1/2| = neg. b Useful composition result [Cramer- Shoup03] + 9 CCA SKE CCA KEM CCA PKE

10. (KEMs) Statistical PA1 (sPA1) [BP04] PPT(ciphertext creator) , Stateful PPT(extractor) , st0= (pk, rA) pk, rA Ci Update state st Ki Pr[ i : Ki Decap(sk,Ci) ] = neg. 10

11. (KEMs) sPA1 in the Presence of Keys (sPA1 ) [MSS12] PPT(ciphertext creator) , Stateful PPT(extractor) , pk1, , pk , rA st0= (pk1 , , pk ,rA) ( ji, Ci ) Update state st Ki Pr[ i : Ki Decap(skji,Ci) ] = neg. 11

12. Simulatable PKE and Variants Simulatable PKE [DN00] pk and c can be sampled obliviously , w/o knowing actual randomness and/or plaintext, and Honestly generated pk and c can be explained that they are generated by oblivious sampling (Simplified) Syntax (PKG, Enc, Dec) & (oSamp, rSamp) (pk, c) oSamp(1k; r ) r rSamp(pk, c) s.t. oSamp(1k; r ) = (pk, c) (r is a randomness for oblivious sampling) Weak Simulatability [MSS12,Dac14] Only c is obliviously samplable Trapdoor Simulatability [CDMW09] rSamp can use randomness and plaintext used to generate pk and c Weak Simulatability and Trapdoor Simulatability are incompatable (However, W-sim. can be seen weaker because it need not obliviously sample pk) 12

13. Simulatable PKE and Variants Q. What kinds of PKE satisfy (Trapdoor/Weak) Simulatability? A. PKEs s.t. pk and c look like a pseudorandom string Ex1: PKE based on LWE or (Low-noise) LPN Ex2: ElGamal (and variants) over a suitable elliptic curve ( simulatable group [Dent06]) Can be instantiated from standard assumptions 13

14. Puncturable Tag-Based Encryption (PTBE)[DDN91,MH14] TBE with two modes for decryption Core structure of the Dolev-Dwork-Naor construction [DDN91] (pk, sk) c m / psktag* TKG(1k) TEnc(tpk, tag, m) TDec (tsk, tag, c) Punc(sk, tag*) Key Generation Encryption Decryption Puncturing SK Punctured Decryption tag* m / PTDec(psktag*, tag, c) Correctness of punctured decryption for non-punctured point tag tag tag*, c TEnc(pk, tag, m): TDec(sk, tag, c) = PTDec(psktag*, tag, c) = m Extended CPA security [MH14] CPA security in the presence of psktag* 14

15. How to Build Trapdoor Simulatable PTBE/COM from Trapdoor Simulatable PKE Generate 2k key pairs Encrypt m independently by k keys chosen by tag Defined analogously to PKE (oSamp need to generate psktag* in addition to (pk, c) Trapdoor Simulatable PTBE Trapdoor Simulatable PKE Trapdoor Simulatable Commitment Trapdoor Simulatability + (Target) Binding 15

16. Proposed KEMs Overview Adapt the Double-Layered structure of [MS09,HLW12] Trapdoor Simulatable Commitment Trapdoor Simulatable Punc. TBE Outer Encryption CCA KEM Double- Layer sPA12, CPA KEM Inner Encryption In our 2nd construction, sPA11, 1-Bounded CCA KEM 16

17. Our 1st Construction TS Punc. TBE TS Com Outer CCA KEM sPA12& CPA KEM Inner KKG: Double-layered structure Inner encryption does multiple encryption by 2 KEMs Randomness for outer encryption is generated from inner KEM In Decap, the validity of outer CT is checked by re-encryption (pkin0, skin0) KKGin (pkin1, skin1) KKGin (tpk, tsk) TKG ck CKG PK = (pkin0, pkin1, tpk, ck) SK = (skin0, skin1, tsk) 1. 2. 3. 4. Encap(PK): (cin0, 0) Encapin(pkin0) (cin1, 1) Encapin(pkin1) (rC|| rT|| K) 0xor 1 tag Com(ck, (cin0||cin1); rC) c TEnc(tpk, tag, (cin0||cin1); rT) C (tag, c) Return (C, K) Decap(SK, C = (tag, c) ): (cin0|| cin1) TDec(tsk, tag, c) 0 Decapin(skin0, cin0) 1 Decapin(skin1, cin1) (rC|| rT|| K) 0xor 1 If Com(ck, (cin0||cin1); rC) = tag and TEnc(tpk, tag, (cin0||cin1); rT) = c then return K else 1. 1. 2. 2. 3. 3. 4. 4. 5. 5. 17 6. 7.

18. Our 2nd Construction TS Punc. TBE TS Com Outer CCA KEM sPA11& 1-BCCA KEM Inner KKG: Inner encryption is replaced by one invocation of KEM (pkin, skin) KKGin 1. (tpk, tsk) TKG ck CKG PK = (pkin, tpk, ck) SK = (skin, tsk) 2. 3. Encap(PK): (cin, ) Encapin(pkin) Decap(SK, C = (tag, c) ): (cin0|| cin1) TDec(tsk, tag, c) Decapin(skin, cin) 1. 1. 2. (rC|| rT|| K) tag Com(ck, cin c TEnc(tpk, tag, cin C (tag, c) Return (C, K) 2. ; rC) (rC|| rT|| K) If Com(ck, cin and TEnc(tpk, tag, cin then return K else 3. 3. ; rT) ; rC) = tag 4. 4. 18 ;rT) = c 5. 6.

19. Ideas for Security Proofs are very similar to [Dac14] Using a CCA adversary for the proposed KEMs, we construct a reduction (CPA adversary) for the inner KEM Binding of commitment allows us to reject all dec. queries (tag, C) s.t. tag* = tag tag* Q. How to answer dec. queries? A. For outer decryption, use punctured SK of PTBE For inner decryption, use a PA1-extractor 19

20. Illustration of Reduction CPA instance of inner KEM pkin, cin*, * Reduction (CPA Adv.) PK = (pkin, tpk, ck) C* = (tag*, c*) K* tag* ??? Inner CT cin Punc TDec C = (tag, c) Dec. Result K or CCA Adv. Validity Check by Re-encryption 20

21. sPA1Security of KEM (shown again) PPT(ciphertext creator) , Stateful PPT(extractor) , pk1, pk , rA st0= (pk1 , , pk ,rA) ( ji, Ci ) Update state st A Ki Pr[ i : Ki Decap(skji,Ci) ] = neg. 21

22. Technical Subtleties (1/2) Q1: How to prepare the initial state of ? A1: Use oblivious-sampling algorithms of outer trapdoor-simulatable PTBE & Com 22

23. Illustration of Reduction CPA instance of inner KEM pkin, cin*, * Reduction (CPA Adv.) Obliviously sample tpk, ck, tag*, c* Randomness r for oblivious sampling PK = (pkin, tpk, ck) C* = (tag*, c*) K* tag* pkin0, pkin1, r Inner CT cin Punc TDec C = (tag, c) Dec. Result K or CCA Adv. Validity Check by Re-encryption 23

24. Technical Subtleties (2/2) Q2: Is the decryption using consistent with the decryption using the normal decryption algo.? A2: Yes. Thanks to the security properties of the inner KEM, can detect if it did an inconsistent answer to a dec. query from 1st construction: multiple-encryption by 2 KEM and sPA12 For one position, embeds its CPA instance, and the secret key of the another position is used to detect inconsistency Idea from [Dec14] (1-bounded PCA) is sufficient Actually, 1-bounded plaintext- checking attack security 2nd construction: 1-bounded CCA and sPA11 1 time dec. query by Idea from the double-layered constructions papers [MS09,HLW12] can be used to detect inconsistency

25. Why the Tradeoffs in Assumption with [Dac14]? [Dac14] Weak Simulatability only guarantees oblivious sampling for ciphertexts, and hence, the initial state of has to contain public keys for outer encryption as well Outer encryption in [Dac14] is arranged like DDN-lite construction sPA1O(k) is required Ours Trapdoor Simulatability allows oblivious sampling also for public keys of outer encryption All information for outer encryption is obliviously samplable sPA1O(1) is sufficient 25

26. eprint 2016/235 Summary New recipes for CCA PKE Our results: 2 CCA secure KEMs + + sPA12, CPA PKE Trapdoor- Simulatable PKE CCA KEM Const- ruction1 sPA11, 1-Bounded CCA PKE Trapdoor- Simulatable PKE Const- ruction2 CCA KEM sPA12k+2, Weakly Simulatable PKE CCA PKE C.f.) [Dac14]

27. On sPA11& 1-Bounded CCA KEM sPA11, 1-Bounded CCA KEM sPA1O(k), CPA KEM We can construct from based on [DF14] s CPA-to-1-bounded CCA PKE construction However, if we use such construction to obtain CCA KEM, there is no merit compared to our first construction The merit of the second construction is that in the future, someone may come up with a direct construction better than known methods. As noted in the previous slide, 1-bounded CCA can be weakened to 1-bounded PCA security. Could this help ? 27