Let ($Gen,Enc,Dec$) be an LHE scheme with security parameter $\kappa$ and message space $M$. Assume that a multiplication operation exists in $M$, i.e., is a finite ring. Let $F : \{0, 1\}^s × L → M$ be a pseudo-random function with seed space $ \{0, 1\}^s$ ( $s=poly(κ)$) and the label space $L$.

I understand what $\kappa$ is as the security parameter of the encryption scheme, but I'm unfamiliar with the notation $poly()$.

The only reference I can find to it through Google is as a function in R but the function in R requires more arguments than given and even if it did have enough arguments the documentation says that $poly()$ returns all orthogonal polynomials with the given arguments as its attributes.

But this doesn't make sense in this scenario because how can you raise a set to a list of values?

  • $\begingroup$ it means that $s$ is polynomial in the security parameter, i.e., there is some constant $m$ such that $s \le \kappa^m$. Probably they are supposing that we can evaluate the pseudo-random function in time polynomial in $s$, so they also want it to be polynomial in $\kappa$ (poly(s) = poly(poly(k)) = poly(k)...). $\endgroup$ Jul 15 at 15:52
  • $\begingroup$ I would only add to stress that it means there exists a specific polynomial. I know that's what the other comment meant, but I wanted to stress it. $\endgroup$ Jul 15 at 18:49
  • $\begingroup$ thanks. so in practice how would I create such a function because as m is arbitrary surely s can be anything $\endgroup$ Jul 15 at 19:15

Your Answer

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

Browse other questions tagged or ask your own question.