For a given security parameter $\kappa$. what does $poly(\kappa)$ mean?

Henry Garrett

11/15/22, 3:45 PM

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?

0 + 3

homomorphic-encryption

notation

Hilder Vitor Lima Pereira

11/15/22, 3:52 PM

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)...).

Yehuda Lindell

11/15/22, 6:49 PM

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.

Henry Garrett

11/15/22, 7:15 PM

thanks. so in practice how would I create such a function because as m is arbitrary surely s can be anything

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: For a given security parameter $\kappa$. what does $poly(\kappa)$ mean?

TH: สำหรับพารามิเตอร์ความปลอดภัยที่กำหนด $\kappa$ $poly(\kappa)$ หมายถึงอะไร

RO: Pentru un parametru de securitate dat $\kappa$. ce înseamnă $poly(\kappa)$?

RU: Для заданного параметра безопасности $\kappa$. что означает $poly(\kappa)$?

VI: Đối với một tham số bảo mật nhất định $\kappa$. $poly(\kappa)$ nghĩa là gì?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.