[wjn0]

Without some form of compression, I don't think it is.

In particular, consider your example (5 horcruxes with 3 needed to reconstruct). View the original file as the interval (0, N) and view it as a set covering problem. If each horcrux covers an interval of size N/3, then if any pair overlaps, there is no third horcrux that can complete the covering. This is a contradiction because 5 horcruxes of size N/3 must overlap somewhere.