CHAPTER 3 Families of Post-quantum Schemes 31 Hash functions are one-way functions that map bit strings of an arbitrary length to relatively short, fixed-length bit-strings called hash values. There are three properties that are required for a cryptographic hash function: 1. Preimage resistance: Itmust be hard to compute a preimage of a hash value, i.e., a bit string that once hashed results in a given hash value. 2. Second preimage resistance: Given a bit string, itmust be hard to find a different bit string that has the same hash value. 3. Collision resistance: It must be hard to find two arbitrary bit strings that have the same hash value. Grover’s algorithm gives at most the usual square-root speedup on brute-force preimage computations 4. The best known classical algorithms for computing hash collisions are based on the birthday paradox and give a square-root speedup over brute-force search 48. Grover’s algorithm improves upon this speedup and gives at most a cube-root speedup on brute-force collision search 13 — but the impact of this improvement is under dispute 7. Hash functions are not affected by Shor’s polynomial-time quantum algorithm. Therefore, hash functions are good candidates for the construction of post-quantum schemes. However, since by definition it is not computationally feasible to compute the inverse of a hash function, it is not known how to construct public-key encryption schemes using hash functions. Nevertheless, it is possible to construct signature schemes using only hash functions as building blocks. As a basic example for the functionality of hash-based signatures consider the following scenario using a hash function h: Alice wants to sign a single-bit message. She creates a private signature key by randomly choosing two bit strings r0 and r1. She computes her public key as {s0 = h(r0), s1 = h(r1)} and publishes {s0, s1}. Bob receives the public key and verifies that {s0, s1} belongs to Alice. Eventually, when Alice wants to sign a one-bit message m ∈{0, 1}, she publishes rm together with the message. For example, let 1 encode »true« and 0 encode »false«. For signing the message »true«, Alice publishes r1. Bob can easily verify the signature by computing h(r1) and comparing it to the public key element s1. The signature must be from Alice since only she knew the preimage r1 of s1 and since it is computationally infeasible for an attacker to compute a preimage from s1. However, this example describes a one time signature scheme: Alice can no longer use this
PQC_for_Dummies
To see the actual publication please follow the link above