Exploring Post-Quantum Cryptography and Key Encapsulation Mechanisms
Delve into the theoretical aspects of post-quantum cryptography, Fujisaki-Okamoto transformation, key encapsulation mechanisms, cryptographic hashing, and random oracles. Understand concepts like IND-CCA security, OW-CCA security, and transformations in cryptographic systems.
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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Theoretical Aspects of Post-Quantum Cryptography II Postquantum Crypto Minischool Kai-Min Chung
Fujisaki-Okamoto(FO) Transformation OW/IND-CPA secure PKE ? ? IND-CCA secure KEM FO(? ?) FO Transformation NIST s final target is KEM instead of PKE Theory Cryptanalysis (security proof) 2 2025/4/3
Key Encapsulation Mechanism (KEM) Bob Public Channel Alice ?? (??,??) ???() K, ?? ??????(??) ?? K ??????(??,??) K Eve K Can I get K?
Fujisaki-Okamoto(FO) Transformation FO transformation OW-CCA PKE U trans. T trans. IND-CPA PKE IND-CCA KEM
Cryptographic Hash ? : Publicly Known Function Bob Public Channel Alice ?? ?????(??) ? = ?????(?) ?? = Eve x x ? G(x) x G(x) ? ? G(x) Attack?
Random Oracle RO: Random function in the air RO, sampled at random x x RO(x) RO(x) Bob Alice x RO(x) ?? ?????(??) ? = ?????(?) ?? = Eve Attack?
T Transformation Random Oracle G T[ , G] ???? = PKE = ??????,???,??? T[ , G] ?????? ,???, ??? Thm: IND-CPA PKE OW-CCA dPKE
T Transformation Theorem Random Oracle G PKE Deterministic PKE T[ ,G] OW-CCA adversary ?????? against that issues at most ?? queries to G and ???? queries to ??? ??, IND-CPA adversary ? against in ROM s.t. ??? ???? 1 2??? ?? ????????? ??+ 1 ???? 2 ? ??? 8 2025/4/3
T Transformation ?????????? ? r r m G(m) G(m) Derandomize
T Transformation ?????????? ? r r ct m G(m) G(m) Re-encryption
? ct m G(m)
T Transformation Theorem Random Oracle G PKE dPKE T[ ,G] OW-CCA adversary ?????? against that issues at most ?? queries to G and ???? queries to ??? ??, IND-CPA adversary ? against in ROM s.t. ??? ???? 1 2??? ?? ????????? ??+ 1 ???? 2 ? ??? 12 2025/4/3
Reduction IND-CPA secure PKE ? ? OW-CCA secure PKE ? ? T Transformation linear Break (With Advantage ? ?? ??+? security loss Break (With Advantage ?) ? ???? ? ?) ?????? ? = ?????? Reduction Proof
Goal: construct reduction R to break IND-CPA security of How can I make use of ??????? IND-CPA game R Ch ?? (??,??) ???() ?????? ??,?? ${?,?} ? ?? ?? = ?????(??) ? ??? ?? ? = ?
OW-CCA game ? RO R Ch ?????? ?(?) (??,??) ???() $? R acts as the challenger of OW-CCA game ? ??,?? ?? = ?????(?) Decryption oracle ?? ?????(??) R simulate the view for ?????? ?? ?? ? ??? ?? ? = ? 15 2025/4/3
Goal: construct reduction R to break IND-CPA security of OW-CCA game IND-CPA game ?????? ? Ch R ?(?) ??,?? ?? (??,??) ???() ??,?? ?? ${?,?} ? ?? ?? ?? = ?????(??) ? ? ??? ?? ? = ?
OW-CCA game IND-CPA game ?????? ? R Ch How to simulate RO? ?(?) First consider a weaker ??? does not querying Dec oracle! ?? (??,??) ???() ??,?? What ?0,?1 to send? ${?,?} ? ??,?? ?? ?? = ?????(??) ?? How to simulate Dec oracle? ?? ? ? OW to IND? ??? ?? ? = ?
OW-CCA game IND-CPA game ?????? ? R How to simulate RO? Ch ?(?) ?? (??,??) ???() ${?,?} ??,?? What ?0,?1 to send? ??,?? $? ? ??,?? ?? ?? = ?????(??) In OW-CCA GAME, the challenge ct has to be an encryption of uniformly sampled plaintext ? ? OW to IND? ??? ?? ? = ?
OW-CCA game IND-CPA game ?????? ? R Ch How to simulate RO? ?(?) ?? (??,??) ???() ${?,?} Lazy sampling! ??,?? $? ??,?? ? ??,?? ?? ?? = ?????(??) ? ? OW to IND? ??? ?? ? = ?
OW-CCA game IND-CPA game ?? ?????? R ?? ? Ch ?? ?? ? ?? ?? ?? (??,??) ???() ${?,?} ??,?? $ ? ?0,?1 ??,?? ?? ?? = ?????(??) ? ? OW to IND? ??? ?? ? = ?
OW-CCA game IND-CPA game ?? ?????? R Ch ?? ?? ? ?? ?? ?? ?? ? ?? ?? (??,??) ???() ${?,?} ??,?? $ ? ?0,?1 ??,?? ?? ?? = ?????(??) ? ? OW to IND? ??? ?? ? = ?
OW-CCA game IND-CPA game ?? ?????? R Ch ?? ?? ? ?? ?? ?? ?? ?? (??,??) ???() ${?,?} ??,?? $ ? ?0,?1 ??,?? ?? ?? = ?????(??) ? ? OW to IND? ??? ?? ? = ?
OW-CCA game IND-CPA game ?? ?????? R Ch ?? ?? ? ?? ?? ?? ?? ?? (??,??) ???() ??,?? ${?,?} $ ? ?0,?1 ??,?? ?? ?? = ?????(??) ?? ? = ?? / / ??: ? ?/? OW to IND? ? ? ??? ?? ? = ? ${?,?} ????: ?
OW-CCA game IND-CPA game ?????? ?? R Ch ?? ? ?? ?? ?? ?? ?? ?? (??,??) ???() ??,?? - ??,? is fixed in the What if ?? ?? ???????? ${?,?} $ ? ?0,?1 table at begin - r is not know by R ??,?? ?? ?? = ?????(??;?) ? ?? ?? ?????????? ?????????? ?? ? ? ? ???????? ?? ? = ?? / / ??: ? ?/? ? ? ??? ?? ? = ? ${?,?} ????: ?
OW-CCA game IND-CPA game ?????? ?? R Ch ?? ?? ? ?? ?? ?? ?? ?? (??,??) ???() ??,?? ${?,?} $ ? ?0,?1 ??,?? ?? ?? = ?????(??;?) ?? ?? / / ?? is queried on G: is queried on G: ? ?/? ???? ?? ? = ?? / / ??: ? ?/? ${?,?} ? ? ??? ?? ? = ? ????: ?
OW-CCA game IND-CPA game ?? ?????? R Ch ?? ?? ?? ? ?? ??,?? ?? ?? ?? $ ?? ?0,?1 ??,?? Observation 1 Pr Pr[??? ???] ?? ?? / / ?? is queried on G: is queried on G: ? ?/? Observation 2 Pr ??? ????? ?1 ? ?? ???? ?? ? = ?? / / ??: ? ?/? 1 Pr ??? ?????? ?1 ? Observation 3 Pr ? ??? =1 ${?,?} ? ????: ? 2 ? ??? ?? ? = ?
= Pr ? ??? + Pr ? ??? + Pr[ ? ???] Pr[? ???] Pr[ ] Pr[? ???| ] Pr Pr[ ? ????] Pr Pr[ ? ????] 1 2 Pr[ ??? ?????? ?1 ?] 1 Pr ??? ????? ?1 ? ?? 1 Pr Pr Observation 1 Pr Pr[??? ???] =1 2+1 ?? 1 2Pr Observation 2 Pr ??? ????? ?1 ? ?? Pr[Adv win] 1 Pr ??? ?????? ?1 ? Observation 3 Pr ? ??? =1 1 2+1 2Pr[Adv win] ??+ 1 2 27 2025/4/3
OW-CCA game IND-CPA game ?????? ?? R Ch ?? ? ?? ?? ??,?? (??,??) ???() $ ?0,?1 ${?,?} ?? ??,?? ? ?? = ?????(??) Original Dec oracle ?? Let s now consider Let s now consider Adv that queries Dec oracle! that queries Dec oracle! Adv Main challenge: R does not know sk! ?? ?? ?0 / ?1 is queried on G: ? 0/1 ???? ?? ? = ?0 / ?1: ? 0/1 ${0,1} ? ? ??? ?? ? = ? ????: ?
OW-CCA game IND-CPA game ?????? ?? R Ch ?? ? ? ?? search Not Found! ?(? ) ?? (??,??) ???() ??,?? ${?,?} $ ??,?? ? ?0,?1 ?? ?? = ?????(??) ?? ? ?? ?0 / ?1 is queried on G: ? 0/1 ???? ?? ? = ?0 / ?1: ? 0/1 ${0,1} ? ? ??? ?? ? = ? ????: ?
Original Dec oracle ??? Different only when Adv query a ct, s.t. m has not been queried on G ?????? ?????? ???? ??????? ?? ??? ???? ? ? ??? ?????? ?? ??? ???? ? ? Hybrid step ?-spreadness ? ct m R s simulation For any m, ct, Pr ??????;? $ = ?? 2 ? 30 2025/4/3
OW-CCA game IND-CPA game ?? Lazy sampling ?????? R Ch ?? ?? ? ?? ?? ?? ?? ?? (pk,sk) Gen() ${0,1} ??,?? $ ?0,?1 ? ??,?? ?? ct = Encpk(m?) ?? ??? ???? ?? ????????? ??+ ? ???? ? ????? ???? ? ? ?? ? ? ?? ?0 / ?1 is queried on G: ? 0/1 ???? ?? ? = ?0 / ?1: ? 0/1 ${0,1} ? ??? ?? ? = ? ????: ?
T Transformation OW-CCA adversary ?????? against that issues at most ?? queries to G and ???? queries to ??? ??, IND-CPA adversary ? against in ROM s.t. ??? 1 2??? ??? ???? ?? ????????? ??+ 1 ???? 2 ? 32 2025/4/3
