It is related to my earlier question:
Are there any algorithms for which generating zero-knowledge proof is so computationally complicated that they cannot be generated in any practical time, by mainstream devices (PCs, smartphones)?
I am interested mostly in encryption algorithms, but any examples would be great.
The following is a fairly "boring" example, but likely works (I'll point out the specific assumption I'm making later). If you also feel its boring, it might help you refine your question so that the answer is more interesting.
Say you have some encryption scheme with security parameter $n$ (We may as well think of $n$-bit RSA, any example works). Say that encryption takes $T_E = O(f(n))$ time for some function $f(n)$. Now consider some ZK proof of the statement you're interested in. Say that it takes $T_P = O(g(n))$ time to prove the statement, where the complexity depends on the security parameter chosen for encryption.
I'm going to assume that encryption is easier than proof generation, or formally $f(n) = o(g(n))$. This seems fairly natural, but I'm not familiar enough with the particulars to know if it holds for all pairs of encryption schemes/proofs (although if it doesn't, one gets proofs 'for free' asymptotically for a particular encryption scheme, which seems odd).
We can then consider introducing another parameter $k$ (which is small compared to $n$), and look at the encryption scheme/proof system with security parameter $kn$. I claim that the following two things should hold:
So if we take $k$ large enough, we expect both encryption and proof generation to become infeasible. But as the asymptotic complexity of the two differ, we expect proof generation to grow infeasible first, so there should be some "intermediate values" of $k$ such that one can still encrypt, but cannot generate proofs.
