I am reading this paper "The security of Hidden Field Equations (HFE)"
and at the end of the page 3 the author wrote:

The random oracle paradigm would be to ignore that the function formulae exist.

I know what is the random oracle paradigm but sincerily I do not understand why the
"The random oracle paradigm would be to ignore that the function formulae exist."
Could you explain me please what that sentence means?


1 Answer 1


Random oracles are used in cryptographic proofs as a way to abstract away a complex function, making the analysis easier (ie "ignore the actual function, and model it as a random oracle instead").

In the paragraphs before the sentence you highlighted, they propose to measure the "complexity" of an equation / function by the degree of its multivariate polynomial representation over $GF(2)$.

In the context of the surrounding paragraphs, I would interpret that sentence to mean

The random oracle paradigm abstracts away the complexity of the function, which renders our complexity metric useless.

  • $\begingroup$ it is my poor english? or there is help of the author to confuse everybody? $\endgroup$
    – juaninf
    Commented Mar 2, 2016 at 21:01
  • $\begingroup$ No, I agree with you that the sentence could have been better worded. $\endgroup$ Commented Mar 2, 2016 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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