0
$\begingroup$

I was reading this set of lecture notes on commitment schemes, where they define a commitment scheme $\text{Com}(b, r) = f(r), h(r) \oplus b$ as a secure commitment scheme. In this case, $f : \{0,1\}^n \rightarrow \{0,1\}^n$ is a one-way permutation, $h : \{0,1\}^n \rightarrow \{0,1\}$ is a hard-core bit of $f(\cdot)$, and $r$ appears to be a random string from $\{0,1\}^n$ (the notation is $r \leftarrow_R \{0,1\}^n$, but I'm not really sure what this actually means and it would be super helpful if someone could clarify what the notation means here!).

My question is what the $f(r), h(r) \oplus b$ means. What is the comma doing? Does this mean that the commitment scheme returns two outputs (I was under the impression that commitment schemes only return one output)? Or am I supposed to combine $f(r)$ with $h(r) \oplus b$ somehow? Thank you for your help!

$\endgroup$
0
$\begingroup$

Or am I supposed to combine $f(r)$ with $h(r) \oplus b$ somehow?

Yes, $\text{Com}(b, r)$ is a function which "combines" them. However it only "combines" them in the sense that it outputs the pair $f(r), h(r) \oplus b$

The main confusion here stems from not realizing that a tuple can be a perfectly valid singular output. (This is compounded by Boaz Barak writing the tuple without parentheses.)

From the lecture notes:

Definition 2 (Commitment schemes). A commitment scheme $Com$ is an unkeyed function that takes two inputs: a plaintext $x ∈ \{0,1\}^n$ ` and randomness $r$ chosen in $\{0,1\}^n$. The idea is that to commit to the winner I let $x$ be my prediction, choose $r \leftarrow_R \{0,1\}^n$ n and publish $y = Com(x, r)$. Later to prove I predicted $x$, I will publish $x$ and $r$.


(the notation is $r \leftarrow_R \{0,1\}^n$, but I'm not really sure what this actually means and it would be super helpful if someone could clarify what the notation means here!).

On page 3 of the notes, the author uses $R$ to indicate random. $\gets$ is assignment. $\gets_R$ is used for uniform random assignment.

For more see this answer.

$\endgroup$
2
  • 1
    $\begingroup$ "Yes, $\text{Com}(b, r)$ is a function which combines them." I'm not sure what you mean by that. It only "combines" them in the sense that it outputs the pair $(f(r),h(r)\oplus b)$. I think the main confusion in the question stems from not realizing that a tuple can be a perfectly valid singular output. (This is compounded by Boaz Barak writing the tuple without parentheses.) $\endgroup$
    – Maeher
    Dec 10 '20 at 11:24
  • $\begingroup$ Thank you so much! $\endgroup$
    – dfertrsfd
    Dec 11 '20 at 6:13

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.