Tag Info

Hot answers tagged

13

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


7

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


6

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


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


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

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

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


3

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


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

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

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


2

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


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

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

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


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


1

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.


1

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


1

Your approach makes getting information other than count of cards in possession of each player at least as hard as breaking the PRFness of HMAC. To make it information-theoretically impossible "for all the ... each player", $\;\;$ if different card_values have different lengths then use $\;\;$ SHA256(commonly_agreed_public_salt:card_value) $\;\;$ ...


1

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?


1

Yes, this is doable. You can verify that $m=a \times b$, given El Gamal encryptions of $m,a,b$, since El Gamal is multiplicatively homomorphic. You can also prove that the El Gamal decryption of some ciphertext is in a given range (using a combination of Schnorr proofs). Putting those two together will give your first desired primitive. This requires you ...


1

Yes. $\:$ If one uses a secure symmetric cipher properly, then the commitment scheme will be unconditionally binding, length-revealing, otherwise computationally hiding, and produce commitments whose length is grows linearly with the length of the message. $\:$ If one uses a collision-resistant hash properly, then the commitment scheme will be ...


1

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


1

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


1

Two variations. If one of the "players" is going to generate the number for others to guess (lottery) then you could do it this way: Collect a token from each participant (a nonce, a random number, a favorite color, etc.) Generate or select the secret number. Hash the generated number with the tokens. Publish the hash and the tokens. Allow each other ...


1

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



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