Hash-based signatures ⇒ DS
Hash-based signatures implies DS.
Statement
Migrated verbatim from hash-function § Other results:
- If one-way functions exist, then many “Minicrypt” primitives exist, via the chain OWF → PRG (HILL99, GL89) → PRF (GGM86):
- Symmetric Key Encryption
- Pseudorandom Functions
- Pseudorandom Permutations
- Message Authentication Codes
- Digital Signatures (via Lamport one-time signatures Lam79 + Merkle trees Mer89)
Migrated verbatim from hash-function § Other results:
- Digital Signatures (via Lamport one-time signatures Lam79 + Merkle trees Mer89)
Notes
This relation is stated on 2 pages; the statements above are all of them.
Recorded during migration and not fixed — these are claims about the source text, not changes to it:
- The Merkle step needs collision resistance / UOWHFs (Naor-Yung, Rompel), uncited here and at digital-signature.md:179.
- Recorded here with ONE hypothesis but with TWO ({one-time-signature, hash-function}) at digital-signature.md:179 — inconsistent hypothesis sets for the same claim.
- one-time-signature has no wiki page.
- MOST COMPOSITE BULLET IN THE CHUNK: one bullet plus five sub-bullets encoding at least seven distinct reductions. Must be split.
- The conclusion ‘many “Minicrypt” primitives’ is not a single object; Minicrypt is an Impagliazzo world, with no page in content/.
- GL89 is the hard-core-predicate result used for the OWP/regular-OWF route to PRGs; the general OWF ⇒ PRG construction is HILL99. Citing both for one arrow conflates two different constructions.
- The Digital Signatures sub-bullet does NOT go through the PRG → PRF chain the parent asserts (it goes OWF ⇒ one-time signature ⇒ signature), so the parent’s ‘via the chain’ framing is wrong for that item.
- PRF ⇒ PRP is uncited: the Luby-Rackoff result (LR88) has no reference page in content/References/.
- The Merkle step from OWFs alone needs UOWHFs (Naor-Yung / Rompel), uncited here and at digital-signature.md:179.
- Recorded with one hypothesis here and two at digital-signature.md:179 — inconsistent hypothesis sets for one claim.
- COMPOSITE with two citations, one per link — the clearest split candidate in the chunk.
- Does not follow the parent bullet’s PRG → PRF chain (see the parent record).
- The Merkle step from OWFs alone needs universal one-way hash functions (Naor-Yung / Rompel), uncited here and on content/Primitives/digital-signature.md line 179.
- ‘one-time-signature’ has no slug.