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
AIM` has quit []
slivera has quit [Quit: Leaving]
Chris_Stewart_5 has quit [Ping timeout: 258 seconds]
head_victim has joined #bitcoin-wizards
ddustin has joined #bitcoin-wizards
ddustin has quit [Ping timeout: 268 seconds]
ddustin has joined #bitcoin-wizards
ddustin has quit [Read error: Connection reset by peer]
ddustin has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
dr-orlovsky has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
dr-orlovsky has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
slivera has joined #bitcoin-wizards
kabaum has quit [Ping timeout: 248 seconds]
hardaker has quit []
ksamak has joined #bitcoin-wizards
TheoStorm has joined #bitcoin-wizards
<sipa>
waxwing: in https://joinmarket.me/blog/blog/avoiding-wagnerian-tragedies/ you mention using XOR as a way to combine the results of hash functions... if yiu actually use xor you can do much better than wagner's algorithm by treating the system as a set of linear equations over GF(2)
<sipa>
so it's just a matrix inversion with O(n) hashes
<sipa>
waxwing: basically if you want to solve the generalized birthday problem, and the operation you use to combime hashes is bitwise xor
<sipa>
you can just generate a random 256 bit hashes
<sipa>
make them the rows of a GF(2) 256*256 matrix
<waxwing>
"MuHash" .. get your lawyers on them :)
<sipa>
invert that matrix, and multiply it with your desired hash sum vector
<sipa>
this gives you a bit vector that identifes the subset of hashes to combine
<sipa>
you can use wagner's algorithm too of course, but in this case there is a much more efficient algorithm for solving the problem
<waxwing>
this paper is interesting, i like these points about homomorphic hashes
<waxwing>
so thanks. i'll have a read and ask you if i still don't get it (though it sounds intuitively like it makes sense).
<sipa>
so wagner's algorithm is really only optimal when your hash combination function defines a group that doesn't split into many tiny subgroups
<sipa>
which is the case when you're working over GF(p)
ksamak has quit []
<sipa>
waxwing: there is a lot of interesting stuff in that paper
<sipa>
i hope i'm not misremembering that it's there that i read about xhash (xor of set hashes) being so trivial to break
<waxwing>
it doesn't kind of violate the thread of my blog post, i was mainly trying to reach an understanding of the inapplicability of this attack to discrete-log-hard groups, it seemed like a really interesting thing to investigate.
<waxwing>
that there's a substantially better way to do it in certain cases is definitely interesting though.
<sipa>
yeah, agree - it's not wrong, just not a perfect example
<gmaxwell>
it's a reason though perhaps to just avoid using xor as your leading example. :P
<gmaxwell>
if you were to do a revision
<waxwing>
gmaxwell, sure. but i was literally following the paper.
<sipa>
random vaguely related fact: did you know that the probability that a GF(2) n*n matrix is invertible comverges rapidly to a constant 0.288788... as n grows?
<waxwing>
thanks for the comments though, it's great to get some input on it.
<gmaxwell>
sipa: I seem to recall discussing with you the more general case of other fields before.
<gmaxwell>
prod(1-0.5^n,1,inf) might be more informative than the constant. :P
<waxwing>
lol yeah i just found the proof. it's irritatingly simple.
<waxwing>
found as in found on web, not worked it out :)
<sipa>
yeah
<sipa>
but this means that to solve generalized birthday for xhash you literally just need 3.5 ish iterations, independently of how large the hash is
<gmaxwell>
it's not as simple to figure out how many additional you need to draw before you can find a subset thats invertable.
<sipa>
yeah, just replace all of them
<gmaxwell>
lame upper bound. :P
<sipa>
you can do it row by row
<gmaxwell>
usually you'll only fail by a single linear dependance, and can fix just that one.
<sipa>
every new hash you add has to be linearly independent of the ones you have before
<sipa>
if it isn't, replace just the last one
<sipa>
and then continue
<gmaxwell>
the same inversion trick should work for arbritary fields so long as you can include an entry an arbritary (potentially very large) number of times.
slivera has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
<sipa>
gmaxwell: invertibility for matrices over fields larger than gf(2) is harder as you need to account for linear combinations over all vectors
<gmaxwell>
Yes, but they are invertable even more often than GF(2).