Post-Quantum Cryptography Insights

sphincs n.w
1 / 25
Embed
Share

Undoubtedly discover the groundbreaking SPHINCS+ cryptographic approach to post-quantum security with hash-based signatures, multi-target attack resilience, tweakable hash functions, and few-time signature schemes, as proposed in the NIST project by Daniel J. Bernstein and team.

  • Cryptography
  • Post-Quantum
  • Security
  • SPHINCS+
  • Hash Functions
rayaanacharya
merrigan_m Follow

Uploaded on | 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. 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.

Download 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.

E N D

Presentation Transcript

  1. SPHINCS+ Submission to the NIST post-quantum project Daniel J. Bernstein, Christoph Dobraunig, Maria Eichlseder, Scott Fluhrer, Stefan-Lukas Gazdag, Andreas H lsing, Panos Kampanakis, Stefan K lbl, Tanja Lange, Martin M. Lauridsen, Florian Mendel, Ruben Niederhagen, Christian Rechberger, Joost Rijneveld, Peter Schwabe

  2. Stateless hash-based signatures https://sphincs.org 2

  3. Goldreich Security parameter ? = 128 Use binary tree as in Merkle, but... to prevent OTS reuse pick leaf index i at random; use huge tree to avoid index collisions (e.g., height h = 2? = 256). for efficiency: use binary certification tree of OTS; all OTS secret keys are generated pseudorandomly. OTS OTS OTS Even with optimization (using WOTS-16 as OTS): 0.6 MB signature. OTS OTS OTS OTS OTS OTS https://sphincs.org 3

  4. The SPHINCS Approach Use a hyper-tree of total height h Parameter ? 1, such that ? | Each (Merkle) tree has height /? ( /?)-ary certification tree https://sphincs.org 4

  5. The SPHINCS Approach Pick index (pseudo-)randomly Messages signed with few-time signature scheme Significantly reduce total tree height Require ? [0, ](Pr[r times index collision] ????EU CMA HORST(?,? = ?)) = negl(?) https://sphincs.org 5

  6. SPHINCS+ https://sphincs.org 6

  7. Adding multi-target attack resilience Preimage search: Multi-target preimage search: Multi-function multi-target preimage search https://sphincs.org 7

  8. Tweakable hash functions ??: ?? ?32 ?? ??, md ??(??.seed,????,?) Generates new keys and bitmasks for each call from PK.seed and ADRS. Allows to embed one challenge per call in reduction https://sphincs.org 8

  9. Few-Time Signature Schemes https://sphincs.org 9

  10. Recap LD-OTS Message M = b1, ,bn, OWF H = n bit * SK sk1,0 sk1,1 skn,0 skn,1 H H H H H H PK pk1,0 pk1,1 pkn,0 pkn,1 b1 b2 bn Mux Mux Mux Sig sk1,b1 skn,bn https://sphincs.org 10

  11. HORS [RR02] Message M, OWF H, CRHF H = n bit Parameters t=2a,k, with m = ka (typical a=16, k=32) * SK sk1 sk2 skt-1 skt H H H H H H PK pk1 pk1 pkt-1 pkt https://sphincs.org 11

  12. HORS mapping function Message M, OWF H, CRHF H = ? bit Parameters ? = 2?,?, with ? = ?? (typical ? = 16,? = 32) * M H b1 b2 ba bar ik i1 https://sphincs.org 12

  13. HORS Message M, OWF H, CRHF H = ? bit Parameters ? = 2?,?, with ? = ?? (typical ? = 16,? = 32) * sk1 sk2 skt-1 skt SK H H H H H H PK pk1 pk1 pkt-1 pkt b1 b2 ba ba+1 bka-2bka-1 bka H (M) i1 ik Mux Mux Sig skik ski1 https://sphincs.org 13

  14. HORS Security ? mapped to ? element index set ?? {1, ,?}? Each signature publishes ? out of ? secrets Either break one-wayness or ?for ? r-Subset-Resilience: After seeing index sets ?? messages ????,1 ? ?, hard to find ????+1 ???? such that ??+1 1 ? ??? ?. ? Best generic attack: Succr-SSR(A,q) = q(rk/ t)k Security shrinks with each signature! https://sphincs.org 14

  15. HORST Using HORS with MSS requires adding PK (?? bits) to MSS signature. (SPHINCS-256: ? = 256,? = 216, ? = 32) HORST: Merkle Tree on top of HORS-PK New PK = Root Publish Auth-Paths for HORS signature values PK can be computed from Sig With optimizations: ?? (? log? ? + 1 + 2?)? E.g. SPHINCS-256: 2 MB 16 KB Use randomized message hash https://sphincs.org 15

  16. FORS Shortcomings of HORST index collisions Allows to search for weak messages (no impact on SPHINCS as hash randomized) Still reduces security Indices are in unordered list Authentication paths will most likely contain redundant nodes Variable size signatures could go lower but requires complicated algorithm (and protocols have to reserve worst-case size) https://sphincs.org 16

  17. FORS FORS (Forest of random subsets) No index collisions One tree per index Ordered list of indices Signature size same as worst-case variable signature size ( at same security level ) Only need authpaths in small trees Simple to compute https://sphincs.org 17

  18. FORS Parameters t, a = log t, k such that ka = m ... ... ... ... ... https://sphincs.org 18

  19. Verifiable index selection (and optionally non-deterministic randomness) SPHINCS: (idx||?) = ???(??.prf,?) md = ?msg(?,PK,?) SPHINCS+: ? = ???(??.prf,OptRand,?) (md||idx) = ?msg(?,PK,?) https://sphincs.org 19

  20. Optionally non-deterministic randomness Non-deterministic randomness complicates side- channel attacks Bad randomness in worst-case still leads to secure pseudorandom value https://sphincs.org 20

  21. Verifiable index selection Improves FORS security SPHINCS: Attacks could target weakest HORST key pair SPHINCS+: Every hash query ALSO selects FORS key pair Leads to notion of interleaved target subset resilience https://sphincs.org 21

  22. Instantiations SPHINCS+-SHAKE256 SPHINCS+-SHA-256 SPHINCS+-Haraka https://sphincs.org 22

  23. Instantiations (small vs fast) https://sphincs.org 23

  24. Summary of SPHINCS+ Strengthened security gives smaller signatures Collision- and multi-target attack resilient Fixed length signatures (far easier to compute than Octopus (-> Gravity-SPHINCS)) Small keys, medium size signatures (lv 3: 17kB) Sizes can be much smaller if q_sign gets reduced THE conservative choice No citable speeds yet https://sphincs.org 24

  25. Thank you! Questions? Visit us at https://sphincs.org https://sphincs.org 25

Related


No related presentations.

More Related Content