Topic: [Crypto] Compact Confidential Transactions for Bitcoin (Read 18446 times)
Unfortunately, Andrew Poelstra was able to break the cryptosystem for this scheme's range-proofs. The author is working on fixing it, and I'm hopeful for progress there. This may take a bit of time, so if you're looking for something to test right now the CT feature in the Elements/Alpha is the best that is out there at the moment.
The problem was with an invalid assumption that two curves of different orders would not be able to generate proof of same negative value, as long as the negative value is in the small range being proved. They clearly can, because "m = r + c*x" allows a negative x to leak into the negative cx and then offset against the positive random r, and the resulting m is then used for both curves.
That assumption is no longer present in the current version of paper (now with:.. diagrams!), but the resulting proofs are not as compact as initially hoped.
My comment: that's a wonderfully written paper, really well done.
Quick paper update, we have 4 cases to consider with (2) and (4) being interesting options.
1) Trusted, unknown group order:
Trusted party generates p*q factors
Use Paillier or additive ElGammal cryptosystem.
2) Trusted, known group order (elliptic curves):
Trusted party generates r in the correct range, and hands out batches of r to participants on request.
We can then use the super-efficient CFT proof on a large curve.
It is compact (0.4KB) for private blockchains, but is not suitable for Bitcoin.
3) Trustless, unknown group order:
Generate a UFO (UnFactorable Object) like ZeroCash.
Use Paillier or additive ElGammal cryptosystem.
4) Trustless, known group order (elliptic curves):
I have managed to make BCDG proof more compact (2.5KB) than the original paper.
As it can deal with 64 bit numbers, it is still more compact than CT, and is suitable for Bitcoin.
1) Trusted, unknown group order:
Trusted party generates p*q factors
Use Paillier or additive ElGammal cryptosystem.
2) Trusted, known group order (elliptic curves):
Trusted party generates r in the correct range, and hands out batches of r to participants on request.
We can then use the super-efficient CFT proof on a large curve.
It is compact (0.4KB) for private blockchains, but is not suitable for Bitcoin.
3) Trustless, unknown group order:
Generate a UFO (UnFactorable Object) like ZeroCash.
Use Paillier or additive ElGammal cryptosystem.
4) Trustless, known group order (elliptic curves):
I have managed to make BCDG proof more compact (2.5KB) than the original paper.
As it can deal with 64 bit numbers, it is still more compact than CT, and is suitable for Bitcoin.
Does RingCT fit into any of those categories?
I'm guessing 3 or 4 might apply, but my parser fails at "group order."
I am offering a prize pool of 10 Bitcoin (about 3,600 USD at time of writing) for any breaks, cryptanalysis, security proofs, analysis or improvements relating directly to the CCT protocol.
Some ideas in no particular order:
1) what is the most optimal attack on E, as it is known to be a square root?
2) other ways for prover to cheat
3) other ways for verifier to gain information
4) ways to make calculation go faster, and/or reduce curve size
5) out of the box thinking
Target for attack is section 3.5.2 on page 7
http://voxelsoft.com/dev/cct.pdf
Deadline for entry by posting to this thread, or PM/BM/email to me, is 20th of January UTC (but earlier is better). I have set a fixed date, and no escrow, to avoid creating an unclaimable fund. Awards to be made at my discretion. By default, the coins would be distributed to people who have made significant contributions previously. List of awards will be paid and publicly posted here by end of January.
If you're not into crypto, please pass on the message to a cryptanalyst who might be interested.
If you wish to contribute to the prize, my address is in the signature and QR code is in the whitepaper.
Some ideas in no particular order:
1) what is the most optimal attack on E, as it is known to be a square root?
2) other ways for prover to cheat
3) other ways for verifier to gain information
4) ways to make calculation go faster, and/or reduce curve size
5) out of the box thinking
Target for attack is section 3.5.2 on page 7
http://voxelsoft.com/dev/cct.pdf
Deadline for entry by posting to this thread, or PM/BM/email to me, is 20th of January UTC (but earlier is better). I have set a fixed date, and no escrow, to avoid creating an unclaimable fund. Awards to be made at my discretion. By default, the coins would be distributed to people who have made significant contributions previously. List of awards will be paid and publicly posted here by end of January.
If you're not into crypto, please pass on the message to a cryptanalyst who might be interested.
If you wish to contribute to the prize, my address is in the signature and QR code is in the whitepaper.
Thanks to everyone who helped to further my comprehension of the topic.
Awards have been sent:
elaine and andrew on behalf of IC3 (1C3rocKSh6sPPibn2jbMFBzcdvfGZySY6t): 6BTC
johoe in this thread (1K4b1MKUJ4mnsR4MMHBkL3Q55XP9YFZVjL): 2BTC
jonathan from UCL: 2BTC
Sorry this took a couple of days longer than expected. I haven't been able to sync a full node despite much effort, as bitcoind doesn't cope with the bitflips in my RAM.
Quick paper update, we have 4 cases to consider with (2) and (4) being interesting options.
1) Trusted, unknown group order:
Trusted party generates p*q factors
Use Paillier or additive ElGammal cryptosystem.
2) Trusted, known group order (elliptic curves):
Trusted party generates r in the correct range, and hands out batches of r to participants on request.
We can then use the super-efficient CFT proof on a large curve.
It is compact (0.4KB) for private blockchains, but is not suitable for Bitcoin.
3) Trustless, unknown group order:
Generate a UFO (UnFactorable Object) like ZeroCash.
Use Paillier or additive ElGammal cryptosystem.
4) Trustless, known group order (elliptic curves):
I have managed to make BCDG proof more compact (2.5KB) than the original paper.
As it can deal with 64 bit numbers, it is still more compact than CT, and is suitable for Bitcoin.
1) Trusted, unknown group order:
Trusted party generates p*q factors
Use Paillier or additive ElGammal cryptosystem.
2) Trusted, known group order (elliptic curves):
Trusted party generates r in the correct range, and hands out batches of r to participants on request.
We can then use the super-efficient CFT proof on a large curve.
It is compact (0.4KB) for private blockchains, but is not suitable for Bitcoin.
3) Trustless, unknown group order:
Generate a UFO (UnFactorable Object) like ZeroCash.
Use Paillier or additive ElGammal cryptosystem.
4) Trustless, known group order (elliptic curves):
I have managed to make BCDG proof more compact (2.5KB) than the original paper.
As it can deal with 64 bit numbers, it is still more compact than CT, and is suitable for Bitcoin.
I have had a little bit of time, so I can present an up-to-date apples-to-oranges comparison results from my most recent CCT test:
I'm missing the unit of measure here (and in the paper). I guess it is seconds?
Yes, "per sec" means seconds.
and then it's back to the drawing board
Edit: another attempt didn't work
If the problem is that prover is free to choose any x and r, including a multiplicative inverse, then the solution is to restrict that choice. There seems to be no good way to do that without initial trusted set-up.
I have had a little bit of time, so I can present an up-to-date apples-to-oranges comparison results from my most recent CCT test:
I'm missing the unit of measure here (and in the paper). I guess it is seconds?
Someone has emailed me, demonstrating that a prime c still allows cheating. With odd c, prover can use (c-1) to cancel an x in r. I've rebased the paper on Warren's version of the interval proof again (will test against these attacks when I get some spare time).
Can you give more details? Does the prover need to know c before choosing x? This would not be possible, since the prover needs to commit for x and c is the hash of the commitment.
I have tested the following, and it verifies. The prover is free to move multiples of x between r and cx, to increment/decrement c (for the purpose of calculating m), so we can't rely directly on the prime property of c.
Quote
Let x = (N+1) / 2
Let r = 2^{381} - x (mod N)
Now, observe that m = r + cx = (r + x) + (c-1) x. As 2x = N+1 = 1 mod N, for odd-valued c,
m = 2^{381} + ((c-1)/2) (2x) = 2^{381} + (c-1) / 2
When c = 1, we have:
m = r + cx = 2^{381}.
When c = 2^{128} - 1, we have:
m = 2^{381} + 2^{127} - 1.
For any odd c \in [0,2^{128}), therefore,
m \in [2^{381}, 2^{381} + 2^{127} - 1] = [A, B]
As cb <= 2^{128}2^{252} = 2^380, it follows that A > cb. As T = 2^{400}, we have B < T.
Therefore, for odd c, it is the case that c*b < m < T, and the Verifier will accept the proof. As c is prime, and 2 is the only even prime, the Verifier will accept with probability almost 1.
Let r = 2^{381} - x (mod N)
Now, observe that m = r + cx = (r + x) + (c-1) x. As 2x = N+1 = 1 mod N, for odd-valued c,
m = 2^{381} + ((c-1)/2) (2x) = 2^{381} + (c-1) / 2
When c = 1, we have:
m = r + cx = 2^{381}.
When c = 2^{128} - 1, we have:
m = 2^{381} + 2^{127} - 1.
For any odd c \in [0,2^{128}), therefore,
m \in [2^{381}, 2^{381} + 2^{127} - 1] = [A, B]
As cb <= 2^{128}2^{252} = 2^380, it follows that A > cb. As T = 2^{400}, we have B < T.
Therefore, for odd c, it is the case that c*b < m < T, and the Verifier will accept the proof. As c is prime, and 2 is the only even prime, the Verifier will accept with probability almost 1.
My new version based on Warren is also broken (I just tested x=(n-1)/2 and it verified).
So... I can try prime c in Warren and then it's back to the drawing board.
Someone has emailed me, demonstrating that a prime c still allows cheating. With odd c, prover can use (c-1) to cancel an x in r. I've rebased the paper on Warren's version of the interval proof again (will test against these attacks when I get some spare time).
Can you give more details? Does the prover need to know c before choosing x? This would not be possible, since the prover needs to commit for x and c is the hash of the commitment.
I think a better way to fix this is to require c to be a prime, instead of adding I, H and the second curve. This puts a bit more burden on the prover, as it has to restart if c is not prime. This extra burden is no problem for your scenario, right? The verifier would just have one additional step that checks that c is prime (e.g., using some probabilistic primality test, or requiring that the prover provides a primality certificate). I haven't completely checked this yet but I think it should work. If the verifier succeeds, it means that |c*x| is <= 2^t * T (or the prover had a very lucky guess of c). Moreover, since c is prime, this means that x < 2^t*T or x is a multiple of 1/c (which means that the prover guessed c).
This sounds excellent! Putting burden on Prover is the right way to go. In typical usage this seems to require a few, to a few hundred, restarts of the protocol. Probably need a couple more bits in c. Probabilistic primality test should be ultra fast and good enough (128 miller rabin steps are much faster than EC multiplication, gives 4**-128 ability to cheat), and a mis-verifying miner would get overpowered. Paper updated. Will think it through further.
Someone has emailed me, demonstrating that a prime c still allows cheating. With odd c, prover can use (c-1) to cancel an x in r. I've rebased the paper on Warren's version of the interval proof again (will test against these attacks when I get some spare time).
I think a better way to fix this is to require c to be a prime, instead of adding I, H and the second curve. This puts a bit more burden on the prover, as it has to restart if c is not prime. This extra burden is no problem for your scenario, right? The verifier would just have one additional step that checks that c is prime (e.g., using some probabilistic primality test, or requiring that the prover provides a primality certificate). I haven't completely checked this yet but I think it should work. If the verifier succeeds, it means that |c*x| is <= 2^t * T (or the prover had a very lucky guess of c). Moreover, since c is prime, this means that x < 2^t*T or x is a multiple of 1/c (which means that the prover guessed c).
This sounds excellent! Putting burden on Prover is the right way to go. In typical usage this seems to require a few, to a few hundred, restarts of the protocol. Probably need a couple more bits in c. Probabilistic primality test should be ultra fast and good enough (128 miller rabin steps are much faster than EC multiplication, gives 4**-128 ability to cheat), and a mis-verifying miner would get overpowered. Paper updated. Will think it through further.
There is something else.
Knowing the prime curve order n, the Prover can cheat widened-interval protocols (CFT and Warren) by setting x=(n-1)/2, thereby committing to the multiplicative inverse of -2 mod n. Thereafter she can use -c/2 as c*x. The Verifier is fooled because E is indeed the encryption of "divide by -2" and does produce something small when multiplied by an even challenge. This would work for other positive and negative multiplicative inverses too, with the appropriate challenges.
My initial thought is that we can require the proof on two curves of co-prime order. Paper updated to illustrate (section 3.5.2). While small numbers would produce the same exponentiations on both curves, multiplicative inverse of one curve will not work on the other. I actually started off with two co-prime curves in June more directly, but that particular approach could not prevent negative numbers.
Knowing the prime curve order n, the Prover can cheat widened-interval protocols (CFT and Warren) by setting x=(n-1)/2, thereby committing to the multiplicative inverse of -2 mod n. Thereafter she can use -c/2 as c*x. The Verifier is fooled because E is indeed the encryption of "divide by -2" and does produce something small when multiplied by an even challenge. This would work for other positive and negative multiplicative inverses too, with the appropriate challenges.
My initial thought is that we can require the proof on two curves of co-prime order. Paper updated to illustrate (section 3.5.2). While small numbers would produce the same exponentiations on both curves, multiplicative inverse of one curve will not work on the other. I actually started off with two co-prime curves in June more directly, but that particular approach could not prevent negative numbers.
I think your update won't prevent this scenario:
Prover sets x = -1/2 or another small fraction, E=x*G, F=x*E, I=x*H, where -1/2 is computed modulo the prime order of the respective curve, i.e. I = (m-1)/2 * H. Then if c is divisible by 2, c*x is a small number and m = r+c*x is in range. The verifier would still accept the proof.
I think a better way to fix this is to require c to be a prime, instead of adding I, H and the second curve. This puts a bit more burden on the prover, as it has to restart if c is not prime. This extra burden is no problem for your scenario, right? The verifier would just have one additional step that checks that c is prime (e.g., using some probabilistic primality test, or requiring that the prover provides a primality certificate). I haven't completely checked this yet but I think it should work. If the verifier succeeds, it means that |c*x| is <= 2^t * T (or the prover had a very lucky guess of c). Moreover, since c is prime, this means that x < 2^t*T or x is a multiple of 1/c (which means that the prover guessed c).
I am offering a prize pool of 10 Bitcoin (about 3,600 USD at time of writing) for any breaks, cryptanalysis, security proofs, analysis or improvements relating directly to the CCT protocol.
Some ideas in no particular order:
1) what is the most optimal attack on E, as it is known to be a square root?
2) other ways for prover to cheat
3) other ways for verifier to gain information
4) ways to make calculation go faster, and/or reduce curve size
5) out of the box thinking
Target for attack is section 3.5.2 on page 7
http://voxelsoft.com/dev/cct.pdf
Deadline for entry by posting to this thread, or PM/BM/email to me, is 20th of January UTC (but earlier is better). I have set a fixed date, and no escrow, to avoid creating an unclaimable fund. Awards to be made at my discretion. By default, the coins would be distributed to people who have made significant contributions previously. List of awards will be paid and publicly posted here by end of January.
If you're not into crypto, please pass on the message to a cryptanalyst who might be interested.
If you wish to contribute to the prize, my address is in the signature and QR code is in the whitepaper.
Some ideas in no particular order:
1) what is the most optimal attack on E, as it is known to be a square root?
2) other ways for prover to cheat
3) other ways for verifier to gain information
4) ways to make calculation go faster, and/or reduce curve size
5) out of the box thinking
Target for attack is section 3.5.2 on page 7
http://voxelsoft.com/dev/cct.pdf
Deadline for entry by posting to this thread, or PM/BM/email to me, is 20th of January UTC (but earlier is better). I have set a fixed date, and no escrow, to avoid creating an unclaimable fund. Awards to be made at my discretion. By default, the coins would be distributed to people who have made significant contributions previously. List of awards will be paid and publicly posted here by end of January.
If you're not into crypto, please pass on the message to a cryptanalyst who might be interested.
If you wish to contribute to the prize, my address is in the signature and QR code is in the whitepaper.
There is something else.
Knowing the prime curve order n, the Prover can cheat widened-interval protocols (CFT and Warren) by setting x=(n-1)/2, thereby committing to the multiplicative inverse of -2 mod n. Thereafter she can use -c/2 as c*x. The Verifier is fooled because E is indeed the encryption of "divide by -2" and does produce something small when multiplied by an even challenge. This would work for other positive and negative multiplicative inverses too, with the appropriate challenges.
My initial thought is that we can require the proof on two curves of co-prime order. Paper updated to illustrate (section 3.5.2). While small numbers would produce the same exponentiations on both curves, multiplicative inverse of one curve will not work on the other. I actually started off with two co-prime curves in June more directly, but that particular approach could not prevent negative numbers.
Knowing the prime curve order n, the Prover can cheat widened-interval protocols (CFT and Warren) by setting x=(n-1)/2, thereby committing to the multiplicative inverse of -2 mod n. Thereafter she can use -c/2 as c*x. The Verifier is fooled because E is indeed the encryption of "divide by -2" and does produce something small when multiplied by an even challenge. This would work for other positive and negative multiplicative inverses too, with the appropriate challenges.
My initial thought is that we can require the proof on two curves of co-prime order. Paper updated to illustrate (section 3.5.2). While small numbers would produce the same exponentiations on both curves, multiplicative inverse of one curve will not work on the other. I actually started off with two co-prime curves in June more directly, but that particular approach could not prevent negative numbers.
If you have the time and inclination, I would sure love to read a more elaborated (slightly more towards layman comprehension) explanation of what is subject to factorization and not related to the inability to find the multiple between two points given by ECLP
So would I.
Cao kept the unknown factorisation assumption even after reducing to a single base in modular DLP, so it has nothing to do with multiple base point commitment (Fujisaki-Okamoto):
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=2B21218DC3B721C6834211C3DFEE544D?doi=10.1.1.79.5740&rep=rep1&type=pdf
Apparently, "if the order of the group is known, the [widened-interval] protocol becomes easy to break". It will take some time for me to figure out whether this is true or not (or maybe only applies to non-prime curves and some types of commitments). I don't know the specific attack.
In short, it appears you can either employ a Hash on the relative base points or on the values committed to the base points. Afaics, your original proof in a large interval did the latter and thus was already immune to factorization of the committed values.
Possibly. Will take some time to figure out.
From section 4:
Quote from: Cao
Alice cannot cheat Bob even she knows the order of g.
The factorization of the modulus n is unknown by Alice, which implies that D = α + xc is just an integer (not a residue class).
The authors [6] gave the original presentation of CFT proof in ElGamal setting[12]. It’s corrected soon [7] because Alice can cheat Bob if the order of the cryptographic group is known by her.
The factorization of the modulus n is unknown by Alice, which implies that D = α + xc is just an integer (not a residue class).
The authors [6] gave the original presentation of CFT proof in ElGamal setting[12]. It’s corrected soon [7] because Alice can cheat Bob if the order of the cryptographic group is known by her.
A residue class in this context would be a functional relationship between the commited values D and the commitment values gD mod n w.r.t. to modulus n such that Alice (as an adversary) would know all values for D which produce the same commitment value gD mod n. Thus when −2t+lb > x > 2t+lb, Alice would not be limited to only one value for α which fulfills the proof. Thus the probability of Alice cheating would not be limited to 1/2t+lb[/sub]. The hash C = H(W) is secure only under the assumption that Alice can't factor the curve order so that D is just an integer to Alice and not a member of a residue class which Alice knows.
For ECC, the "n" is the order of the curve, i.e. the finite number of elements in the field which is the "modulus" where xG wraps around and repeats values that are obtained for other values of x.
Thus the simple solution to this problem is to make the curve order prime so that it can't be factored and thus a residual class can't be found (in the computationally conditional not information-theoretic security model) . In [7] two distinct finite fields were employed because it was constructed in the setting where one of the prime factors of the modulus was known (thus the modulus could be theoretically factored), but in our case only the curve order is known, so we merely have to make it prime to make it (theoretically assuming the proof of it being prime is sound) unfactorable.
Or you do what you proposed which is hash the mathematical relationship of the commitment values (not just hash the integer relationship, thus why two hashes are required) so that no such residue class can be found, but this makes your algorithm 50% slower. My way of thinking about this is that the committed values are a distinct field from the commitment values, thus the hash C = H(W) applies to the field of real numbers (stated as "integer" by Cao) and does not apply to the abelian group field of the commitment values.
Note that Berstein's curves have odd prime orders:
http://ed25519.cr.yp.to/eddsa-20150704.pdf
So problem solved and efficiency maintained.
Again I am not a mathematician and my training in this area of algebraic geometry is non-existent, so please do peer review of my statements.
For n00bs, remember it is the factorability of the RSA modulus (because it is composed of two prime factors) which makes it vulnerable (but this may not be the only vulnerability) and why it needs exponentially larger keys than ECDSA (or Berstein's EdDSA):
http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/
https://bithin.wordpress.com/2012/02/22/simple-explanation-for-elliptic-curve-cryptography-ecc/
https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Example
If you have the time and inclination, I would sure love to read a more elaborated (slightly more towards layman comprehension) explanation of what is subject to factorization and not related to the inability to find the multiple between two points given by ECLP
So would I.
Cao kept the unknown factorisation assumption even after reducing to a single base in modular DLP, so it has nothing to do with multiple base point commitment (Fujisaki-Okamoto):
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=2B21218DC3B721C6834211C3DFEE544D?doi=10.1.1.79.5740&rep=rep1&type=pdf
Apparently, "if the order of the group is known, the [widened-interval] protocol becomes easy to break". It will take some time for me to figure out whether this is true or not (or maybe only applies to non-prime curves and some types of commitments). I don't know the specific attack.
In short, it appears you can either employ a Hash on the relative base points or on the values committed to the base points. Afaics, your original proof in a large interval did the latter and thus was already immune to factorization of the committed values.
Possibly. Will take some time to figure out.
I wish I fully understood this. Its seems important so maybe I will devote some time to learn.
If you have the time and inclination, I would sure love to read a more elaborated (slightly more towards layman comprehension) explanation of what is subject to factorization and not related to the inability to find the multiple between two points given by ECLP
So would I.
Cao kept the unknown factorisation assumption even after reducing to a single base in modular DLP, so it has nothing to do with multiple base point commitment (Fujisaki-Okamoto):
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=2B21218DC3B721C6834211C3DFEE544D?doi=10.1.1.79.5740&rep=rep1&type=pdf
Apparently, "if the order of the group is known, the [widened-interval] protocol becomes easy to break". It will take some time for me to figure out whether this is true or not (or maybe only applies to non-prime curves and some types of commitments). I don't know the specific attack.
In short, it appears you can either employ a Hash on the relative base points or on the values committed to the base points. Afaics, your original proof in a large interval did the latter and thus was already immune to factorization of the committed values.
Possibly. Will take some time to figure out.
good
Does this apply because of the two base points G and E introduced when you switched to the proof-of-square?
In other words, does the original proof-of-smallness (that did not employ H, the decomposed hash of G) have this assumption if E is not employed (i.e. before you added proof-of-square to your white paper)? I think not (because the assumption of factorization is between G and E correct?). I ask because my version of your paper does not use a proof-of-square.
In other words, does the original proof-of-smallness (that did not employ H, the decomposed hash of G) have this assumption if E is not employed (i.e. before you added proof-of-square to your white paper)? I think not (because the assumption of factorization is between G and E correct?). I ask because my version of your paper does not use a proof-of-square.
No. It's because the original CFT widened interval proof depends on an unfactorable number (or as Boudot and Cao put it, "n is a large composite number whose factorisation is unknown [to the prover]").
If you have the time and inclination, I would sure love to read a more elaborated (slightly more towards layman comprehension) explanation of what is subject to factorization and not related to the inability to find the multiple between two points given by ECLP:
https://www.certicom.com/index.php/52-the-elliptic-curve-discrete-logarithm-problem
Where I have seen the decomposition from a Hash function as the base point for breaking the factorability between commitment sets such as in Shen-Noether's design for CT+ CN (where knowing the commitment point of H relative to G, would enable one to cheat). It seems factorability applies when there are two commitment base points involved. I am not readily seeing where such factorability can be employed by the prover to break the original proof in a large interval because afaics there was already a hash function for the Fiat-Shamir in between any such factorizations? When -T > x > T, then the prover's guess has to be exactly 1 of the 2t possibilities. How does factoring help avoid the security provided by the hash function?
In short, it appears you can either employ a Hash on the relative base points or on the values committed to the base points. Afaics, your original proof in a large interval did the latter and thus was already immune to factorization of the committed values. Now you've changed it to do hashing on both. What am I missing?
Jump to: