Tag Info

The answer you posted is actually correct (more or less, see below): have each participant commit to their random number $r_i$ by publishing, e.g., $\mathcal{H}(r_i)$ in the first round. And then in the second round, each participant opens the commitment by publishing $r_i$ and everyone checks that it matches the committed value by hashing it. The final ...

The problem pointed out by JGWeissman on Bitcoin.SE is only an issue if the hash function lacks collision resistance. Admittedly, collision resistance is one of the strongest properties usually demanded of hash functions, and collision attacks have been found for some hash functions commonly used in the past, such as MD5, but still, any secure cryptographic ...

Yes, $p$, $g$ and $h$ are system parameters. $g$ and $h$ only need to generate large prime subgroups of $\mathbb{F}_p^{*}$, and the equation $p=2g+1$ is not required. (In fact, if I understand what you mean correctly, it does not always suffice as $-1/2$ has the same order as $2$) It is important that $g$ and $h$ not be related by a known equation of the ...

Commitment functions should be at least hiding and binding, and in your case, you want non-malleable. Using a hash function as a commitment does require addition assumptions on the hash that are not covered by (second) pre-image and collision resistance for both non-malleability (as you point out) and hiding: the hash can be assumed to not reveal the ...

Say $m$ persons meet physically and want to draw a positive integer $x$ less than $n$. Each person $j$ secretly selects a positive integer $x_j$ less than $n$, writes it down on a piece of paper, and fold it to hide her choice. The $m$ folded pieces of paper are brought together then publicly unfolded, revealing the $x_j$. The outcome of the protocol is $x ...

What it sounds like you are looking for is a Commitment Scheme; that is, a way for Alice to compute a 'Commitment' based on a 'value', and publish the 'Commitment' to Bob (or a group of Bobs). Just from the tag, Bob cannot deduce the value (even if he know it's one of a small set of values). However, Alice at some point can 'open' the commitment, revealing ...

It sounds like you are thinking about this the wrong way. Verifying a commitment is very fast, if you choose the commitment scheme properly. In particular, I recommend that you use a hash-function-based commitment scheme: C(i) = Hash(x(i) || open(i)). Then verifying an opened commitment requires just one hash evaluation, which is very fast. Based on my ...

As you noticed correctly, a hash function is kind-of computationally binding if you assume collision resistance. However, it is impossible to achieve perfect hiding property for hash functions, due to the potential loss of information. Perfect hiding means, that a computationally unbound Alice COULD decomit any value: I.e. Pedersen commitments $c = g^xh^r$ ...

r can only be reused by coincidence (i.e., it must be selected independently each time). There is not problem with giving multiple commitments to the same x. In the following, p will be the modulus and q will be the order of the group. Definition: $\:$ range(n) is the set of non-negative integers that are less than n The following conditions guarantee ...

Putting ponchos comment aside for the moment: What if Alice were to ask all parties to hash their commitments in a deterministic way (no padding, no salt, etc.) and then send it to her. She would be able to tally the majority and know who took part in it. There would only be a problem if the set or size of commitments were so small that Alice would be able ...

Here is one difficultly such a protocol can have: say we do have a joint computation protocol that takes $N+1$ parties (Alice and her $n$ people); at the end of the protocol, Alice gets a list of the parties in the majority without learning their secret. Here is how Alice can attempt to cheat: extend the protocol to $N+3$ parties, and have the extra two ...

One approach that may work is the following. You can represent the accumulated values as a polynomial, where the roots are equal to the messages: User $1$ creates a representation of $P_1(x)=(x-C(1))$ User $i$ creates a representation of $P_i(x)=(x-C(i))P_{i-1}$ A commitment scheme with properties very close to what you want is PolyCommit. It allows any ...