Re: Is this the first ever practically-deployed use of a threshold scheme?

2010-08-04 Thread Tanja Lange
 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

2009-07-17 Thread Tanja Lange
 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

2009-07-14 Thread Tanja Lange
 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?

2008-11-03 Thread Tanja Lange
 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]