[chrislipa]

Maybe there's still a way to use homomorphic encryption. gwern rightly suggests that it causes a big problem if the recipient must decrypt the result of an encrypted computation. However, what if the decrypted result of the computation is never known to the recipient and instead the recipient must use the still-encrypted result of the encrypted homomorphic computation?

It would work like this:

The secret sharer creates some random string called 'a' and some computable function 'f'. The secret sharer also creates an encryption function 'e', and a homomorphic equivalent to 'f', called 'F' so that the following commutes: e(f(x)) = F(e(x)). F acts on encrypted data and gives encrypted results, but is much slower than f.

The secret sharer can comparatively quickly compute e(f(x)), which he or she uses as a key to encrypt a message. However the recipient is only given the values e(x) and F and must use exponentially more computational time to go the more laborious route, computing F(e(x)).

[dsl]

That is effectively a proof of work scheme, which is what most time lock systems are based on. The fundamental problem is that people with more resources can decrypt faster than people with less resources, and you're generally wanting to share with someone who has less not more.

[chrislipa]

You make a good point, but that's also a shortcoming of all of the purely computational techniques. I think the most you can hope for is 'democratizing' the computational methods, i.e. making them non-parallelizable.

Taking gwern's idea, what if the homomorphic computation is just incrementing your input repeatedly inside of a loop? It seems like that might be hard to parallelize. Or at least, I don't know enough to assume otherwise.