Re: Is this the first ever practically-deployed use of a threshold scheme?
> There is more than the UI at stake here, i.e. the basic functionality of > the scheme. Say you distribute shares in a 4 out of 7 scheme (ABCDEF) > and share A is published on the web. How do you recover from the > remaining 3 out of 6 scheme into a 4 out of 6 scheme without having a > key ceremony? In an ad-hoc multi-party scheme, you request 4 of the > remaining compliant parties to destroy key material allowing them to > participate in a group with the traitor A, but no other key material. No > system UI, but admittedly a coordination nightmare! > If the system is built to allow resharing then this is no problem. Resharing from a t-out-of-n scheme to an r-out-of-m scheme works as follows: If the secret s is shared using the (otherwise random) polynomial f of degree t then a share consists of (i,f(i)). To reshare, at least t or the original shareholders issue shares of f(i) in an r-out-of-m manner, i.e. take a polynomial gi of degree r and compute m shares (i,j,gi(j)). When these are distributed to the new users, the new users should end up with matching j's. The old shares (i,f(i)) are deleted. Each of the m new users now has t shares (i1,j,gi1(j)), (i2,j,gi2(j)), ... ,(it,j,git(j)). This information can be combined into a single share (j,G(j)) of s by using the Lagrange coefficients of the first scheme. All of this can be decorated with zero knowledge proofs to prove correctness of the shares etc. Note that there is no interaction of the t shareholders and everthing can be done remotely. In the scenario that one share A is published it's enough to have t-1 users help in the resharing since every new user can use the public information. On the other hand that's a mess to program, so it's more resonable to ask t of the remaining shareholders to help. Doesn't sound like a coordination nightmare to me. For all this in a more general setting see e.g. "Redistributing Secret Shares to New Access Structures and Its Applications" by Yvo Desmedt and Sushil Jajodia (1997) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.3353 Does this answer the question? Tanja - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: 112-bit prime ECDLP solved
> >So with about 1 000 000 USD and a full year you would get 122 bits > >already now and agencies have a bit more budget than this! Furthermore, > >the algorithm parallelizes extremely well and can handle a batch of 100 > >targets at only 10 times the cost. > > No it cannot handle a bunch of a hundred targets at only ten times the > cost. It is already parallelized. A hundred targets is a hundred times > the cost. > NO. Read Fabian Kuhn, René Struik: Random Walks Revisited: Extensions of Pollard's Rho Algorithm for Computing Multiple Discrete Logarithms. Selected Areas in Cryptography 2001: 212-229 Section 4. Besides, the estimates assume only playstations and the EPFL code instead of special purpose hardware which would give an extra speed up. And, no, I'm not suggesting to use the entire US gross national product for a year to break your key but given that that breaks 172 bits (SHARCS 2006 estimates for ECC-163 and 9 bits to scale from USD 5.8*10^11 to the GDP 1.4*10^13) I'm not comfortable with 160 bits, let alone 144. All the best Tanja - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: 112-bit prime ECDLP solved
> >We are pleased to announce that we have set a new record for the elliptic > >curve discrete logarithm problem (ECDLP) by solving it over a 112-bit > >finite field. The previous record was for a 109-bit prime field and > >dates back from October 2002. > First of all congratulations to the team at EPFL! > Which suggests that existing deployments should default to 128 bits. > with 160 bits being overkill. Of course overkill does not cost much. > If one shoots someone the head, it is wise to follow up with a second > shot through the head at very short range just to be on the safe side. > James, do I really have to point out the obvious that just because 112 bits is a new record this does not mean that 113 is undoable today. The coolness of this result is that a smallish cluster of low cost machines could do this computation in only half a year. 200 PS3s cost you no more than 200 x 400 USD at published prices - and less if you buy that many at once. So with about 1 000 000 USD and a full year you would get 122 bits already now and agencies have a bit more budget than this! Furthermore, the algorithm parallelizes extremely well and can handle a batch of 100 targets at only 10 times the cost. So, yes, we sure will be able to break 130 bits in 2033 - but certainly much sooner if anyone tries. Tanja - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: Who cares about side-channel attacks?
> Examples of side channel analysis on real systems I however have never > seen in the field. Any rumors would be highly appreciated. > At Crypto'08 a team from Bochum demonstrated their side-channel attack on KeeLoq. There were some theoretical attacks before but the SCA really broke it. KeeLoq is being used by some car manufacturers and by most garage door manufacturers. Regards Tanja - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
