TPTB_need_war


November 20, 2015, 11:57:39 PM Last edit: November 21, 2015, 12:48:56 AM by TPTB_need_war 

Does this apply because of the two base points G and E introduced when you switched to the proofofsquare?
In other words, does the original proofofsmallness (that did not employ H, the decomposed hash of G) have this assumption if E is not employed (i.e. before you added proofofsquare 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 proofofsquare.
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/52theellipticcurvediscretelogarithmproblemWhere I have seen the decomposition from a Hash function as the base point for breaking the factorability between commitment sets such as in ShenNoether'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 FiatShamir in between any such factorizations? When T > x > T, then the prover's guess has to be exactly 1 of the 2 ^{t} 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?





Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.



ssff
Newbie
Offline
Activity: 1
Merit: 0


November 21, 2015, 12:12:25 AM 





Mixles
Member
Offline
Activity: 63
Merit: 10


November 21, 2015, 06:37:30 PM Last edit: November 21, 2015, 07:18:19 PM by Mixles 

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 (FujisakiOkamoto): http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=2B21218DC3B721C6834211C3DFEE544D?doi=10.1.1.79.5740&rep=rep1&type=pdfApparently, "if the order of the group is known, the [widenedinterval] 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 nonprime 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.

Donations to 1SumKArxoEJ1HoGibmj8ygw1DZWYBvjmM



letsplayagame


November 21, 2015, 09:13:50 PM 

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 (FujisakiOkamoto): http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=2B21218DC3B721C6834211C3DFEE544D?doi=10.1.1.79.5740&rep=rep1&type=pdfApparently, "if the order of the group is known, the [widenedinterval] 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 nonprime 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.

Chess, Bitcoin, Privacy and Freedom Make BTC Donations via XMR.TO or Shapeshift XMR: 47nMGDMQxEB8CWpWT7QgBLDmTSxgjm9831dVeu24ebCeH8gNPG9RvZAYoPxW2JniKjeq5LXZafwdPWH7AmX2NVji3yYKy76



TPTB_need_war


November 22, 2015, 09:58:10 AM Last edit: November 22, 2015, 11:01:17 AM by TPTB_need_war 

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 (FujisakiOkamoto): http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=2B21218DC3B721C6834211C3DFEE544D?doi=10.1.1.79.5740&rep=rep1&type=pdfApparently, "if the order of the group is known, the [widenedinterval] 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 nonprime 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: 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. A residue class in this context would be a functional relationship between the commited values D and the commitment values g^{D} 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 g^{D} mod n. Thus when −2^{t+l}b > x > 2^{t+l}b, 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 informationtheoretic 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/eddsa20150704.pdfSo problem solved and efficiency maintained. Again I am not a mathematician and my training in this area of algebraic geometry is nonexistent, 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/arelativelyeasytounderstandprimeronellipticcurvecryptography/https://bithin.wordpress.com/2012/02/22/simpleexplanationforellipticcurvecryptographyecc/https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Example




Mixles
Member
Offline
Activity: 63
Merit: 10


November 22, 2015, 05:54:20 PM Last edit: November 25, 2015, 11:17:32 AM by Mixles 

There is something else.
Knowing the prime curve order n, the Prover can cheat widenedinterval protocols (CFT and Warren) by setting x=(n1)/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 coprime 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 coprime curves in June more directly, but that particular approach could not prevent negative numbers.

Donations to 1SumKArxoEJ1HoGibmj8ygw1DZWYBvjmM



Mixles
Member
Offline
Activity: 63
Merit: 10


December 04, 2015, 12:59:47 PM Last edit: December 05, 2015, 09:42:07 AM by Mixles 

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

Donations to 1SumKArxoEJ1HoGibmj8ygw1DZWYBvjmM



johoe


December 05, 2015, 04:58:10 AM 

There is something else.
Knowing the prime curve order n, the Prover can cheat widenedinterval protocols (CFT and Warren) by setting x=(n1)/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 coprime 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 coprime 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 = (m1)/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).

Donations to 1CF62UFWXiKqFUmgQMUby9DpEW5LXjypU3



Mixles
Member
Offline
Activity: 63
Merit: 10


December 05, 2015, 07:50:32 AM Last edit: December 05, 2015, 10:30:48 AM by Mixles 

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 misverifying miner would get overpowered. Paper updated. Will think it through further.

Donations to 1SumKArxoEJ1HoGibmj8ygw1DZWYBvjmM



Mixles
Member
Offline
Activity: 63
Merit: 10


December 09, 2015, 11:02:36 PM Last edit: December 10, 2015, 12:35:21 PM by Mixles 

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 misverifying 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 (c1) 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).

Donations to 1SumKArxoEJ1HoGibmj8ygw1DZWYBvjmM



johoe


December 10, 2015, 10:11:51 AM 

Someone has emailed me, demonstrating that a prime c still allows cheating. With odd c, prover can use (c1) 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.

Donations to 1CF62UFWXiKqFUmgQMUby9DpEW5LXjypU3



Mixles
Member
Offline
Activity: 63
Merit: 10


December 10, 2015, 12:34:49 PM Last edit: December 11, 2015, 10:14:15 AM by Mixles 

Someone has emailed me, demonstrating that a prime c still allows cheating. With odd c, prover can use (c1) 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. Let x = (N+1) / 2 Let r = 2^{381}  x (mod N) Now, observe that m = r + cx = (r + x) + (c1) x. As 2x = N+1 = 1 mod N, for oddvalued c, m = 2^{381} + ((c1)/2) (2x) = 2^{381} + (c1) / 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=(n1)/2 and it verified). So... I can try prime c in Warren and then it's back to the drawing board.

Donations to 1SumKArxoEJ1HoGibmj8ygw1DZWYBvjmM



gbrs
Newbie
Offline
Activity: 43
Merit: 0


December 15, 2015, 01:57:16 PM 

I have had a little bit of time, so I can present an uptodate applestooranges 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?




Mixles
Member
Offline
Activity: 63
Merit: 10


December 16, 2015, 01:59:48 PM Last edit: December 17, 2015, 11:08:34 PM by Mixles 

I have had a little bit of time, so I can present an uptodate applestooranges 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 setup.

Donations to 1SumKArxoEJ1HoGibmj8ygw1DZWYBvjmM



Mixles
Member
Offline
Activity: 63
Merit: 10


December 22, 2015, 05:41:02 PM 

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

Donations to 1SumKArxoEJ1HoGibmj8ygw1DZWYBvjmM



Mixles
Member
Offline
Activity: 63
Merit: 10


February 02, 2016, 12:13:19 PM Last edit: February 02, 2016, 12:34:32 PM by Mixles 

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

Donations to 1SumKArxoEJ1HoGibmj8ygw1DZWYBvjmM



iCEBREAKER
Legendary
Offline
Activity: 2156
Merit: 1070
Crypto is the separation of Power and State.


February 02, 2016, 01:52:08 PM 

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

██████████ ██████████████████ ██████████████████████ ██████████████████████████ ████████████████████████████ ██████████████████████████████ ████████████████████████████████ ████████████████████████████████ ██████████████████████████████████ ██████████████████████████████████ ██████████████████████████████████ ██████████████████████████████████ ██████████████████████████████████ ████████████████████████████████ ██████████████ ██████████████ ████████████████████████████ ██████████████████████████ ██████████████████████ ██████████████████ ██████████ Monero

 "The difference between bad and welldeveloped digital cash will determine whether we have a dictatorship or a real democracy." David Chaum 1996 "Fungibility provides privacy as a side effect." Adam Back 2014

  



Preclus


February 03, 2016, 07:51:05 AM 

My comment: that's a wonderfully written paper, really well done.




Poloniex Matthew
Newbie
Offline
Activity: 26
Merit: 0


February 03, 2016, 04:31:16 PM 

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.




Poloniex Matthew
Newbie
Offline
Activity: 26
Merit: 0


February 03, 2016, 05:21:50 PM 

Unfortunately, Andrew Poelstra was able to break the cryptosystem for this scheme's rangeproofs. 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.




