3
$\begingroup$

I'm wondering what does the "constant rate" mean in universal composable commitment scheme? I have known the rate of a commitment scheme is message length divided by the communication complexity of the scheme. What's the "constant" mean here? Must the constant be a number less than 1?

$\endgroup$
  • $\begingroup$ Can you please post a reference to a paper or something where you encountered this term? $\endgroup$ – SEJPM Dec 18 '18 at 17:21
4
$\begingroup$

Constant rate in general means that the overhead from a non-secure method is constant. So, in a simple way, if I am committing to an $\ell$-bit message, then the size of the commitment is $O(\ell)$. In some cases, however, one also allows an additive factor that is independent of the message size. Thus, for example, it could be that to commit to a message of size $\ell$ the amount is $O(\ell)+{\rm poly}(n)$, where $n$ is the security parameter.

Note that typically these are measured in an amortized manner. So, you have to send many commitments (or a long message) for it to be true. But, again, this depends on the exact scheme, so you'll have to read the details.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I have one more question: how large the size of the commitment is would be regarded as bad? For example, if the size of the commitment is O(nl) for committing l-bit message, where n is security parameter, is it bad? $\endgroup$ – CryptoLover Jan 10 at 16:50
  • $\begingroup$ Good or bad depends on your setting and what you want. In general, $O(n\cdot\ell)$ is of course much worse than $O(\ell)+poly(n)$, but if you want to commit to a little bit only, sometimes a simpler scheme is better. $\endgroup$ – Yehuda Lindell Jan 11 at 1:23

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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