[tahoe-dev] [tahoe-lafs] #217: DSA-based mutable files -- small URLs, fast file creation

[tahoe-lafs]

#217: DSA-based mutable files -- small URLs, fast file creation
----------------------------+-----------------------------------------------
 Reporter:  zooko           |           Owner:  zooko     
     Type:  enhancement     |          Status:  assigned  
 Priority:  major           |       Milestone:  eventually
Component:  code-mutable    |         Version:  0.7.0     
 Keywords:  mutable crypto  |   Launchpad_bug:            
----------------------------+-----------------------------------------------

Comment(by zooko):

 So up until the last bullet point concerning the storage-index, I think
 what you describe is what I diagrammed in Figure 3 of
 [http://allmydata.org/~zooko/lafs.pdf lafs.pdf].  Does that look right?

 I agree this scheme has many good properties.  I do still have a concern
 that 256-bit read-caps (e.g.
 {{{http://127.0.0.1:8234/c/r_FRPG24yB7Amho6NoWaaJlBrU7lON7AyiChWRcaQZ1pH}}}
 or
 {{{http://127.0.0.1:8234/c/D_FRPG24yB7Amho6NoWaaJlBrU7lON7AyiChWRcaQZ1pH/path/to/sub/file.txt}}})
 might be long enough to exclude Tahoe from some interesting uses where
 125-bit read-caps (e.g.
 {{{http://127.0.0.1:8234/c/r_FMK3eUypHbj6uLocF0496}}} or
 {{{http://127.0.0.1:8234/c/D_FMK3eUypHbj6uLocF0496/path/to/sub/file.txt}}}
 would fit.

 Have you ever looked at http://bench.cr.yp.to ?  In particular, this page
 -- http://bench.cr.yp.to/results-sign.html -- shows measurements of a
 bunch of digital signature schemes, including key-generation time, public-
 key size, and private-key size.  Compare "ecdonaldp256" (which is ecdsa
 with a 256-bit curve) with the one named "hector" (which is a
 hyperelliptic curve scheme).

 Hector has estimated 113-bit security (compared to ecdonaldp256's 128-bit
 security), verifies signatures in about half as many CPU cycles, generates
 signatures in about one eighth as many CPU cycles, generates key pairs in
 about one eighth as many CPU cycles.  In theory (I think) hyperelliptic
 curve public keys can be compressed down to the size of the curve, in this
 case 113 bits, just like elliptic curve pubkeys can be compressed down to
 the size of the curve, although implementations of both measured here
 don't do that sort of compression.

 Here's the source code of the hyperelliptic curve implementation:

 http://cryptojedi.org/crypto/index.shtml

 113 bits should be enough for now in my opinion.

 The fatal flaw of the hector algorithm is that it isn't mature.  The only
 known implementation is described as a "demo", it doesn't work at all
 unless your CPU has SSE2 instructions, and it doesn't compile out of the
 box on my Ubuntu Jaunty amd64.  Figuring out how to compress the public
 keys and finding or creating a portable implementation sounds like way too
 hard of a job for us.  Hopefully in a few years other people who know more
 about implementing such things than us will have done so and we can rely
 on their implementations, but for now I think we have to reluctantly pass
 up the opportunity to be the first ever serious users of hyperelliptic
 curve cryptography.  :-)

 Lacking hyperelliptic curve cryptography, we have to make a trade-off
 between the larger size of having a full elliptic curve point in the cap
 and the disadvantages of having the key stored on the servers instead of
 in the caps.

 I'm not entirely sure about those disadvantages.  We've previously talked
 about several, but on closer inspection I'm not sure if they are actual
 disadvantages.  You (Brian) nicely summarized some of those at the end of
 your note:

  * offline attenuation (By the way, let's call this action "diminishing" a
 capability.  "Attenuating" is something that you do to authority, and it
 is a very general and flexible notion -- you can imagine writing arbitrary
 code or even having a human in the loop making the decisions which result
 in the authority being attenuated.  "Diminishing" is something that you do
 to a capability, and it only goes from one specific thing to another
 specific thing.  I called this operation "diminishing" in lafs.pdf in
 order to follow the terminology of Jonathan Shapiro's thesis about EROS
 (http://www.eros-os.org/papers/shap-thesis.ps), where he defined the
 "Diminish-Take" access model as an extension of the standard "Take-Grant"
 access model.  The addition he added was an operation named "diminish",
 the effect of which was to produce a capability which offered transitive
 read-only access to whatever the original capability could access.  The
 first kind of "diminishing" that we wanted in Tahoe was for precisely this
 same purpose, so that's why I used that word.  Of course, the ''next''
 kind of diminishing that we wanted was for something else -- producing a
 verify cap from a read cap.  Oh well.  Anyway, since I've already
 committed to "diminish" in publishing lafs.pdf, and since it might be
 useful to have the word "attenuation" separately as being what you do to
 authority in general, let's call this operation "diminish".)

 Oh dear it is way past my bedtime.  I'll continue this tomorrow.

-- 
Ticket URL: <http://allmydata.org/trac/tahoe/ticket/217#comment:50>
tahoe-lafs <http://allmydata.org>
secure decentralized file storage grid