While reading through "Cryptographic Extraction and Key Derivation: The HKDF Scheme" by Hugo Krawczyk, I found the following text intriguing:

In some cases, well-defined combinatorial assumptions from the hash functions will suffice while in others one has to resort to idealized modeling and “random oracle” abstractions.

I assume it implies that: HKDF can be secure in certain cases even when the hash function is not a "random oracle".

When I recall that "a PRF appears random if it's selected randomly from the family of functions with the same domain", I think this means when the HMAC key is selected appropriately, the output from HMAC function should satisfy the requirements and goals of HKDF.

Is my reasoning true / somewhat plausible / wrong? Can HKDF be securely instantiated with HMAC-SWIFFT and in what situation?


The reasoning is wrong: the whole point of the paper is to establish a definition for secure general-purpose KDFs.

In definition 7 of the paper, it is defined that a KDF is secure, if it can withstand distinguishing game from an adversary with capability to query the KDF oracle - that's what something linear like SWIFFT cannot provide.

As for the quoted text in OP, it just means the author is proving his ideas using as few and as straightforwardly useful assumptions as possible, it did not imply what I thought it implied in OP.

  • $\begingroup$ So how would we create an HKDF using a lattice-based hashing algorithm? $\endgroup$ Jun 22 '19 at 18:44
  • $\begingroup$ @SteveMucci We would not. $\endgroup$
    – DannyNiu
    Jun 23 '19 at 3:09
  • $\begingroup$ That's kind of frustrating... Not you, the fact that we can't implement an HKDF. I guess with lattice-based cryptography we will discover new cryptographic concepts that are outside the realm of current cryptographic methods. That would make me happy. $\endgroup$ Jun 23 '19 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.