constant-time directory lookup

[davidsarah]

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.

[davidsarah]

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]

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]

... 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]

Reminder to self: try a pairing-based cryptosystem.

[daira]

We resolved to brainstorm about this in a Tahoe Dev Chat soon.