# Notation for commitment schemes

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!

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.

• "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.) Dec 10, 2020 at 11:24