# Tag Info

16

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

9

You could use HMAC for this. HMAC is available in pretty much every crypto library out there. The process would work like this. Randomly pick A and C. For simplicity, let's assume they are strings (of any length). Compute $B=HMAC(A,C)$. Publish $B$. Once someone guesses $A$, you publish $C$. Anyone can then verify that $B=HMAC(A,C)$. As long as a good hash ...

8

The misunderstanding you have is with the sentence "the sender is able to compute an $r'$..." Actually, that's not true, and the information theoretically hiding" bullet point does not state that. What it does state is that, for every $m'$, there exists an $r'$ that satisfies the relation; however it does not imply that a real sender can find such a value. ...

7

By Theorem 3 on page 15 of this paper, no secure-with-abort protocol for equality of long strings can be within 1/5 of fair. If there is a protocol for equality on a domain of size at least 3 which is secure against honest-but-curious adversaries, then oblivious transfer protocols exist. If oblivious transfer protocols exist, then there are protocols for ...

6

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

6

The main difference is that Pedersen commitments are unconditionally hiding, as given $g^mh^r$ represents an information theoretic hiding commitment, i.e., even an unbounded adversary will not be able to figure out $m$. In exponential ElGamal encryption, since you publish $(g^r,g^mh^r)$, this so obtained commitment is no longer unconditionally hiding, but ...

6

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

5

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 =... 4 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 ... 4 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 ... 4 One could split both secrets into smaller parts, commit to parts and "gradually" open that commitments to each other, so that no party is better than (ahead of the other) one such part. For example, let secret be a big number split into bits. With an additively homomorphic bit commitment scheme, the other party could verify that bit commitments correspond ... 4 This cannot be done. It is provably impossible. In order to explain this in technical terms, what you are looking for is a FAIR protocol to compute equality of long random strings (I added the latter since it adds a constraint and so in theory could make it easier). In any case, if I had such a protocol, then I could toss a fair unbiased coin. Here is the ... 3 If they don't trust the server they sure shouldn't send any money. The "trusted" third party is used to solve the problem of participants who don't trust each other. So by definition, your problem can only be somewhat mitigated, not solved completely. I'm not sure what you mean by "provably fair". If the server can't prove he cannot cheat, it's not provably ... 3 You're close with the idea of using an envelope; the standard answer is to use a commitment scheme; this is a scheme where someone can publish a 'commitment' to a value, and then later revealing what that value was. The two essential properties of commitments are: Someone just looking at the commitment cannot tell what the secret was Someone with the ... 3 Let$q$be given by$\:$for all$n$,$\: q(n) = 1 \;\;$.$\;\;\;\;\;$For every$P^*\hspace{-0.05 in}$, every$\: x\in L_R \:$,$\frac{p-\kappa(|x|)}{q(|x|)} = \frac{p-\kappa(|x|)}1 = \:p\hspace{-0.04 in}-\hspace{-0.04 in}\kappa(|x|) \: \leq \: p\hspace{-0.04 in}-\hspace{-0.04 in}0 \: = \: p \: \leq \: 1 \;\;$. For every$P^*\hspace{-0.05 in}$, every$\: ...

3

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

3

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

3

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

3

If $(G,q)$ are public authentic parameters and Alice publishes $(h,R,S)$, then if Alice later publishes $r$, Bob needs to check if $g^r=R$, which fixes $r$. Consequently, when computing $\log_g S/h^r$ also fixes $h$ and the exponent of $S$ is fixed. Changing $m$ to $m'$ would require to solve $m+rx\equiv m'+r'x \pmod{q}$ for $r'$. However, since $r$ is fixed ...

3

There is one subtle problem with your proposed protocol: unless $f$ is restricted to commutative functions, the lottery can choose to reveal one of two values. Here's how he does it: the lottery selects $p1$ and $p2$ as per the protocol, and publishes $p1\times p2, f$. However, when it comes time to reveal the committed value, and the lottery sees that the ...

3

Give a zero-knowledge proof that $y_1 \times y_2$ is a Quadratic Residue. [Extra verbage included because a one line answer feels too brief] If we have $y_1 = x_1^2 t^{b_1}$ and $y_2 = x_2^2 t^{b_2}$, then $y_1 y_2 = (x_1x_2)^2 t^{b_1 + b_2}$. If $b_1 = b_2$, this product is either $(x_1x_2)^2$ (if $b_1 = b_2 = 0$), or $(x_1x_2t)^2$ (if $b_1 = b_2 = 1$), ...

3

If you mean a prime in the neighborhood of $2^{80}$, well, that is incorrect. A prime that small will allow someone to commit to a value, and then reveal another one. A Pederson commitment is a value $g^x h^r \bmod p$, where $g$, $h$ and $p$ are public values, $x$ is the value being committed to, and $r$ is a random value. To reveal the commitment, you ...

3

If you can select the distinct secret primes $p$ and $q$ such that $(p-1)/2$ and $(q-1)/2$ are also prime, then it becomes easy. For a random value $r$, $g = r^2$ will have order precisely $(p-1)(q-1)/4 \approx n/4$ unless $r, r-1$ or $r+1$ happens to not be relatively prime to $n$ (which, if you select $r$ randomly in the range $[2, n-2]$, happens with ...

2

The published ciphertext is $(R,S) = (g^r,h^r g^m)$. Now Alice publishes $r$. But since Bob can check if $g^r=R$ holds, she cannot cheat at this point. If the public key $h$ is fixed and known, the message can be decrypted: $m=log (S/h^r)$. So concerning your questions: Yes, it's enough if Alice publishes $r$ and she can not cheat. The difference to ...

2

Proving uniqueness You can prove that the elements are unique in $O(m)$ time and space by pre-sorting them and then giving a zero-knowledge proof that they are in sorted order. Details follow. Assume the elements of $\Sigma$ are integers in the range $[0,K-1]$, where $K$ is a constant chosen in advance and made public. Pick a large prime $p$ and a group ...

2

You can use the techniques in the paper you have linked to show that a list of commitments $C_1,\ldots,C_m$ to the elements in $\Sigma$ are elements in $\Psi$ (the commitment scheme of choice are information-theoretically hiding Pedersen commitments, which are also used in the linked paper) . Basically, this works by the "owner" of the set $\Psi$ publishing ...

2

You are looking for secure coin flipping protocols. See the following: How to fairly select a random number for a game without trusting a third party? Verify product without revealing multipliers Proof that lottery does not know outcome of draw A fair peer-based coin-flipping protocol? Is this scheme a provably fair random number generation?

2

The commitment is the receiver's output from the protocol's initial phase, and the opening value is a witness that the commitment is to whatever it's to. The 'Binding' and 'Hiding' properties are defined w.r.t. the commitment scheme.

2

My preference would be to use hash for this purpose. Cons of using symmetric cipher include: Symmetric cipher keys are shorter than hashes (128-256 bits), where as hashes are longer (160-512 bits). When considering the length of symmetric cipher output, it is commonly short (like 128 bits). This length is often inadequate to protect against birthday attack ...

2

No. Yes, by choosing an authenticated encryption scheme with a known $\:I\hspace{.03 in}V\hspace{.04 in}||\hspace{.04 in}C\hspace{.04 in}||\hspace{.04 in}tag\:$ and $k_{\hspace{.02 in}0}$ and $k_1$ such that decrypting $\:I\hspace{.03 in}V\hspace{.04 in}||\hspace{.04 in}C\hspace{.04 in}||\hspace{.04 in}tag\:$ with $k_{\hspace{.02 in}0}$ and $k_1$ yields ...

Only top voted, non community-wiki answers of a minimum length are eligible