constant-time directory lookup #1906

New Issue

tahoe-lafs · 2013-01-23T16:42:11Z

davidsarah commented

2013-01-23 16:42:11 +00:00

Currently to look up an entry in a directory, it is necessary to download the whole file backing the directory, then decode it to find the correct child. This takes linear time in the number of entries.

Suppose that the secret cryptovalue of each child were derived from the cap of the parent directory and the child name. Then, provided that the metadata is not needed, it is possible to obtain the child directly rather than via the parent. (If that child does not exist, we can't distinguish that from missing shares, but that isn't necessarily a problem.)

Note that this makes directories more useful for some database-like applications, rather than just as filesystem directories per-se.

Currently to look up an entry in a directory, it is necessary to download the whole file backing the directory, then decode it to find the correct child. This takes linear time in the number of entries. Suppose that the secret cryptovalue of each child were derived from the cap of the parent directory and the child name. Then, provided that the metadata is not needed, it is possible to obtain the child directly rather than via the parent. (If that child does not exist, we can't distinguish that from missing shares, but that isn't necessarily a problem.) Note that this makes directories more useful for some database-like applications, rather than just as filesystem directories per-se.

tahoe-lafs added the

labels 2013-01-23 16:42:11 +00:00

tahoe-lafs added this to the undecided milestone 2013-01-23 16:42:11 +00:00

davidsarah commented

2013-02-03 21:20:43 +00:00

A complication is that it must be possible to derive both the child writecap from the parent writecap and childname, and the child readcap from the parent readcap and childname. This requires the following diagram to commute:

  Write_parent × childname -> Write_child
        |                          |
        v                          v
   Read_parent ● childname ->  Read_child

where the downward arrows, '×', and '●' are feasibly computable but one-way operations. This seems like some kind of homomorphic encryption, but the constructions I've tried so far don't quite work.

A complication is that it must be possible to derive both the child writecap from the parent writecap and childname, and the child readcap from the parent readcap and childname. This requires the following diagram to commute: ``` Write_parent × childname -> Write_child | | v v Read_parent ● childname -> Read_child ``` where the downward arrows, '×', and '●' are feasibly computable but one-way operations. This seems like some kind of homomorphic encryption, but the constructions I've tried so far don't quite work.

davidsarah commented

2013-03-03 00:36:51 +00:00

The nearest I got was this: if readcap = g^writecap^ in some cryptographic group, then × can be multiplication by H(childname) modulo the group order, and readcap ● childname can be readcap^H(childname)^. But then × is not one-way.

davidsarah commented

2013-03-03 00:52:12 +00:00

... and the same problem applies to attempts to use partially homomorphic encryption schemes - for all of the schemes I'm aware of, the operation to combine plaintexts is not one-way.

daira commented

2014-03-29 11:42:29 +00:00

Reminder to self: try a pairing-based cryptosystem.

daira commented

2014-04-14 23:14:59 +00:00

We resolved to brainstorm about this in a LAFS Tesla Coils and Corpses session soon.

Sign in to join this conversation.