Stronger Security Margins on Private FS Names

[matheus23]

Summary

Switch out the cryptographic accumulator used for private file system paths for bigger security margins.

Problem / Need / Opportunity

At the moment the write access & path obfuscation mechanisms in the private file system are built on bloom filters. These have a false-positive rate of 1 in a billion and a depth limit of 47 path elements.
Also, a path segment membership witness for a single file system block leaks information about which other private file system blocks also contain this path segment.
It's possible to improve this when switching to another accumulator scheme.

Success Scenario

There is no depth limit for paths. The security margin for brute-forcing is 2^112 or bigger. There is no correlation possible between labels of private file system blocks, membership witnesses leak no information about unrelated private file system blocks.

Notes

A possible solution could be RSA accumulators.

ETA: 2023-09-30

[jeffgca]

Use case: Filecoin Private Data adoption.

TODO: need more detail on what exactly were the downstream needs related to this requirement @expede

Additionally: a new accumulator needs be at least as performant as the existing one.

[expede]

@therealjeffg we need to actually try it to know where the sharp edges are and optimizations that we can make, but in theory the first version looks something like this:

1. Put your data in the private side of WNFS
2. Persist that WNFS (via it's top CID) to Filecoin
3. Party

[expede]

From a product requirements level, my understanding is that people want data that the storage provider can't read. As a stretch goal: only retrieve subsets of that data (e.g. a single directory) or do key rotation (update keys over time)

[expede]

@therealjeffg I got some extra context on this from @matheus23:

The core issue is that if we say that we scramble the tree structure, we should do so in a way that has sufficient entropy that it would be impractical to reverse for a motivated attacker. This came up at IPFS Thing when chatting with a bunch of the PL folks, who want this property, but the namefilter strategy as it stands would need to be quite a bit larger and add some tweaks to make them have that level of entropy. We knew that we'd need to revisit this at some stage, and had some theories going back to the initial design with Daniel.

Philipp & I went back to the drawing board, and RSA Accumulators are the best of the tradeoffs. All accumulators today leave something to be desired, but this strategy is uses a technique that puts the concerns cited above at ease.

[jeffgca]

That's great context. I think I am mostly thinking about this in terms of:

1/ how much entropy is enough for the use case? Sounds like we have a good idea.

2/ what's the impact on performance? As file paths get longer is there a linear degradation or some sort of cliff we fall off of?

[matheus23]

This has been completed with the work in wnfs-wg/rs-wnfs#247 and wnfs-wg/spec#65