sipa changed the topic of #bitcoin-wizards to: This channel is for discussing theoretical ideas with regard to cryptocurrencies, not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja
Hexxeh has quit []
justanotheruser has joined #bitcoin-wizards
shush has quit [Remote host closed the connection]
shush has joined #bitcoin-wizards
justanotheruser has quit [Ping timeout: 246 seconds]
TurquoiseEvents has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
shush has quit [Remote host closed the connection]
shush has joined #bitcoin-wizards
shush has quit [Ping timeout: 246 seconds]
marcoagner has quit [Ping timeout: 250 seconds]
TurquoiseEvents has joined #bitcoin-wizards
justanotheruser has joined #bitcoin-wizards
shush has joined #bitcoin-wizards
gleb has joined #bitcoin-wizards
Implant1 has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
ddustin has quit [Ping timeout: 246 seconds]
TheoStorm has quit [Remote host closed the connection]
shush has quit [Remote host closed the connection]
shush has joined #bitcoin-wizards
chendo_ has joined #bitcoin-wizards
shush has quit [Remote host closed the connection]
justanotheruser has quit [Ping timeout: 246 seconds]
shush has joined #bitcoin-wizards
berndj has quit [Ping timeout: 256 seconds]
berndj has joined #bitcoin-wizards
AaronvanW has quit [Remote host closed the connection]
captjakk has joined #bitcoin-wizards
Kiminuo has quit [Ping timeout: 265 seconds]
justanotheruser has joined #bitcoin-wizards
<bsm117532>
^^^ That paper has a hole: their Pedersen commitments omit the "hiding" element.
<bsm117532>
But I still think it's a nice demonstration of how redistributable, verifiable secret sharing can work.
<bsm117532>
The consequence of omitting hiding is that if you know (or can guess) a few bits of the secret, you can derive some bits of the polynomial coefficients.
<bsm117532>
See CHURP instead if you're interested in this idea: https://eprint.iacr.org/2019/017, or encrypt your secret so that it is uniformly random (adding a hiding element).
captjakk has quit [Read error: Connection reset by peer]
captjakk has joined #bitcoin-wizards
<bsm117532>
Is Z_{4p+1} an appropriate ring for committing to values in Z_p? (bitcoin private keys, where p = bitcoin's prime).
roconnor has quit [Quit: Konversation terminated!]
shesek has joined #bitcoin-wizards
shesek has quit [Client Quit]
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
shesek has joined #bitcoin-wizards
shesek has quit [Client Quit]
jungly has quit [Remote host closed the connection]
<sipa>
bsm117532: what does that mean?
AaronvanW has joined #bitcoin-wizards
captjakk has quit [Remote host closed the connection]
captjakk has joined #bitcoin-wizards
<bsm117532>
The above paper requires Pedersen commitments to the secret values. I'm wondering if the prime 4p+1 is generally appropriate for commitments to bitcoin private keys. (independent of that paper -- might be used in other ways)
<sipa>
is that a multiplication-mod-prime group? i haven't read the paper
<bsm117532>
Such things require a prime 2*p+1, but for the bitcoin prime, 2*p+1 isn't prime, but 4*p+1 is.
<sipa>
oh that's a simplification
<sipa>
in reality you will always use EC groups
<sipa>
instead of DSA-style group
captjakk has quit [Ping timeout: 250 seconds]
<bsm117532>
Sure. The only reason I ask is the above paper uses exponentiated Pedersen commitments, not EC commitments.
<bsm117532>
I was fooling with this years ago, have been wondering about 4p+1 ever since, but never satisfied myself that 4p+1 was secure. Yes it's small. r=(4p+1)+1 has a 133-bit factor. I'm not sure how to use that though...
<sipa>
you need a 3000-bit group for 12i-bit sexurity
<sipa>
you need a 3000-bit group for 128-bit security
AaronvanW has quit [Remote host closed the connection]
<bsm117532>
But this is just a Pedersen commitment, not RSA. how would you use a too-small prime to break a Pedersen commitment?
<sipa>
DL happens to be exactly as hard as factorization
aupiff has joined #bitcoin-wizards
<bsm117532>
Ok, but how ;-)
<sipa>
if DL is broken, the commitment is broken, no?
<sipa>
otherwise, you could just a much simpler group if DL hardness was not required
<bsm117532>
I accept your argument, but I'm looking for a procedure to extract the committed value, just to help me understand. ;-)
<sipa>
pedersen commitments are information theoretically hiding (if the blinding factor is random), there is no way to.extract
<sipa>
but if DL is brokem you can open them to whatever value you like
<sipa>
if that's ok to you, you could use a+r as a commitment to a :p
<sipa>
or the constant 11
captjakk has joined #bitcoin-wizards
mdunnio has quit [Remote host closed the connection]
mdunnio has joined #bitcoin-wizards
mdunnio has quit [Remote host closed the connection]
mdunnio has joined #bitcoin-wizards
shush has quit [Remote host closed the connection]
mdunnio has quit [Ping timeout: 256 seconds]
shush has joined #bitcoin-wizards
jungly has joined #bitcoin-wizards
captjakk has quit [Ping timeout: 256 seconds]
captjakk has joined #bitcoin-wizards
captjakk has quit [Client Quit]
AaronvanW has joined #bitcoin-wizards
Kiminuo has joined #bitcoin-wizards
* bsm117532
scurries off to figure out how to break discrete log commitments...
<sipa>
say you commit to a using an EC commitment with generators G and H, in a group in which DL is easy
<sipa>
your commitment is aG+rH
<sipa>
you'd like to open it to value c instead
<sipa>
so you're trying to find s such that cG+sH = aG+bH
<sipa>
s = (aG+bH-cG)/H
<sipa>
where / is your DL algorithm
captjakk has joined #bitcoin-wizards
jungly_ has joined #bitcoin-wizards
Krellan_ has quit [Remote host closed the connection]
Krellan_ has joined #bitcoin-wizards
jungly has quit [Ping timeout: 256 seconds]
captjakk has quit [Client Quit]
mdunnio has joined #bitcoin-wizards
Krellan_ has quit [Ping timeout: 246 seconds]
mdunnio has quit [Ping timeout: 240 seconds]
mdunnio has joined #bitcoin-wizards
dr-orlovsky has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
captjakk has joined #bitcoin-wizards
chendo_ has quit []
jungly_ has quit [Remote host closed the connection]
jungly has joined #bitcoin-wizards
ski1 has joined #bitcoin-wizards
jungly has quit [Ping timeout: 250 seconds]
shush has quit []
Krellan_ has joined #bitcoin-wizards
Krellan_ has quit [Ping timeout: 246 seconds]
dr-orlovsky has joined #bitcoin-wizards
<bsm117532>
sipa: (segue from Twitter) The bad idea in my head is to do a multisignature with (e.g. 2-of-3) P = P_1 P_2 + P_2 P_3 + P_1 P_3. This is a monotone boolean function on the pubkeys with + as an OR operation and * as an AND operation.
<bsm117532>
(Insert hashes in front of the terms as necessary to commit to this combination being allowed)
<bsm117532>
Parties 1 and 2 could then construct a signature by using the ideas from 2p-ECDSA (multiplicative aggregate keys), and possibly abusing the Schnorr related key attack to remove the extra terms.
<bsm117532>
Is something along these lines impossible? Or is it just that no one has described how to do it?
<sipa>
well that depends on what your OR operation is
<sipa>
if it's a Merkle tree, that's certainly been described before
<sipa>
if it's SSS, that's verifiable secret sharing based threshold crypto
<sipa>
well, not really; the SSS is doing both the ANDs and ORs
<sipa>
but there are schemes (somewhat related to VSS) that can translate any monotone boolean function over keys to a setup for that policy
<bsm117532>
I'm familiar with all the SSS stuff, I'm trying to find a non-SSS way to do it. ;-)
<bsm117532>
OR operation is using (abusing) related key attacks in some way.
<sipa>
make a Merkle tree where every leaf is a MuSig of some subset of the keys; and you have one leaf for each of the (n choose k) combinations
<sipa>
done
<sipa>
i don't understand the relation with related key attacks
<bsm117532>
Yep, that Merkle construction certainly works...
<sipa>
this of course has signatures that scale with O(log(n choose k))
<bsm117532>
related key: just saying it's in general possible to sign for P+a if you have the private keys for P. (you called it a "related key attack" in bip-schnorr) Or pubkey tweak, or whatever.
<sipa>
bsm117532: that's VSS; the signers effectively use shamir shares to reconstruct the (partial signature for) the secret keys they are missing; the linearity of the keys and signatures means that's enough
<bsm117532>
Sure you can do that with VSS, I know.
<sipa>
then i don't know what you're asking for
<bsm117532>
I'm asking for an algorithm for 2-of-3 parties to construct a signature for the aggregate pubkey P = P_1 P_2 + P_2 P_3 + P_1 P_3, without using Shamir sharing.
<bsm117532>
(and I don't think one exists, probably because no one has tried?)
<bsm117532>
Or, some reason this is a terrible idea...
<sipa>
what does the multiplication even mean?
<sipa>
you can't multiply keys
<sipa>
i know you mean "something representing and", but if you're not concrete then the question is meaningless
<bsm117532>
I mean P = p_1 p_2 G + p_2 p_3 G + p_1 p_3 G for lower case p being private keys
<sipa>
ah!
<bsm117532>
Sorry, I was sloppy
<sipa>
so your multiplication is effectively DH
<bsm117532>
Yes.
<sipa>
now you're going to need proofs of DLEQ
<sipa>
to compute the aggregate
<sipa>
how would what you're trying to build be better than VSS?
<bsm117532>
It probably wouldn't because of the factorial number of terms involved. I'm just curious...since this is what was in my head naively as "native threshold Schnorr".
CryptoDavid has joined #bitcoin-wizards
Krellan_ has joined #bitcoin-wizards
nick_freeman has joined #bitcoin-wizards
<bsm117532>
I also know some optimizations for polynomial representation that I might dig in to to reduce that factorial complexity, if I thought the idea in general was workable...
<yanmaani>
\
<yanmaani>
oops
Krellan_ has quit [Ping timeout: 246 seconds]
captjakk has quit [Remote host closed the connection]
captjakk has joined #bitcoin-wizards
jungly has joined #bitcoin-wizards
sonofhan has joined #bitcoin-wizards
Krellan_ has joined #bitcoin-wizards
jungly has quit [Remote host closed the connection]
jungly has joined #bitcoin-wizards
Krellan_ has quit [Ping timeout: 260 seconds]
jungly has quit [Ping timeout: 250 seconds]
roconnor has joined #bitcoin-wizards
roconnor has quit [Ping timeout: 256 seconds]
jungly has joined #bitcoin-wizards
roconnor has joined #bitcoin-wizards
ski1 has quit []
ddustin has joined #bitcoin-wizards
ddustin has quit [Ping timeout: 246 seconds]
slivera has joined #bitcoin-wizards
TurquoiseEvents has joined #bitcoin-wizards
Krellan_ has joined #bitcoin-wizards
orion`1 has joined #bitcoin-wizards
captjakk has quit [Remote host closed the connection]
captjakk has joined #bitcoin-wizards
TurquoiseEvents has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
Krellan_ has quit [Ping timeout: 240 seconds]
TheoStorm has quit [Quit: Leaving]
captjakk has quit [Remote host closed the connection]
TurquoiseEvents has joined #bitcoin-wizards
aupiff has quit [Ping timeout: 256 seconds]
captjakk has joined #bitcoin-wizards
Guyver2 has quit [Remote host closed the connection]
TheoStorm has joined #bitcoin-wizards
TurquoiseEvents has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
dr-orlovsky has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
TurquoiseEvents has joined #bitcoin-wizards
mdunnio has quit [Remote host closed the connection]
mdunnio has joined #bitcoin-wizards
mdunnio has quit [Ping timeout: 250 seconds]
sonofhan has quit [Quit: Leaving...]
jungly has quit [Remote host closed the connection]
TurquoiseEvents has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
TurquoiseEvents has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
justanotheruser has quit [Ping timeout: 250 seconds]
lukedashjr has joined #bitcoin-wizards
luke-jr has quit [Ping timeout: 240 seconds]
nick_freeman has quit []
lukedashjr is now known as luke-jr
luke-jr has quit [Ping timeout: 256 seconds]
luke-jr has joined #bitcoin-wizards
mdunnio has joined #bitcoin-wizards
justanotheruser has joined #bitcoin-wizards
mdunnio has quit [Ping timeout: 264 seconds]
lukedashjr has joined #bitcoin-wizards
luke-jr has quit [Ping timeout: 256 seconds]
luke-jr has joined #bitcoin-wizards
bildramer has quit [Remote host closed the connection]
bildramer has joined #bitcoin-wizards
lukedashjr has quit [Ping timeout: 240 seconds]
lukedashjr has joined #bitcoin-wizards
TurquoiseEvents has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
luke-jr- has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 250 seconds]