As far as I understand, a property is computational if it holds in a computationally-bounded context, so for ANY computationally-bounded involved entity (even if an unbounded one could discover the property is actually missing): e.g. any computationally-bounded distinguisher evaluating two transcripts to check CZK, or computationally-bounded provers of an argument.

I guess that explicitly capturing the concept of "any computationally-bounded entity" in a proof isn't easy, so I think that's the reason I have met (at least dealing with ZKPs) computational properties proved by reduction to computationally-hard problems, like second preimage resistance of hashes or DLP (because their hardness relies on ALL entities being computationally-bounded, so if we prove that their hardness implies our property, we win)

I wonder if are out there examples of computational properties proved by means of different stategies; and if proving by reduction to hard problems isn't someway a "weak" proof, being based on an hardness assumption not guaranteed to last forever even if definitely accepted (I understand whole cryptography is a huge computational lie ;-) but let's say my doubt is theoretically-biased)



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.