Does there exist a protocol $\pi$ for some functionality $F$ which is information theoretically secure protocol that is not cryptographically secure for some threshold number of corrupt parties? Intuitively, such a protocol cannot exist, because if a protocol is not secure in the presence of a poly time adversary, then it must be insecure even in the presence of an adversary with unbounded computational power. However, I have constructed a protocol $\pi$ for a functionality $F$, which seems to be information theoretically secure protocol but not cryptographically secure.

Consider three parties $P_1, P_2,P_3$ with private inputs $p,q$ and $\phi$ respectively, where $p$ and $q$ are prime numbers. They wish to compute the functionality $F(p,q,\phi) = (\phi,\phi,p*q)$ i.e. party $P_3$ must receive the product of the two prime numbers as the output.

I design the following protocol to achieve the functionality: Party $P_1$ sends $p$ to party $P_3$ and party $P_2$ sends $q$ to party $P_3$. Party $P_3$ computes the product $p*q$.

The view of party $P_3$ in this protocol is $(p,q,p*q)$, where as its view is only (p*q) in an ideal implementation of the functionality $F$. Let consider the case where $P_3$ is an adversary (with no coalitions). If $P_3$ has unbounded computational power, then the two views are equivalent, and hence the protocol is information theoretically secure. Whereas, if the adversary can run only efficient algorithms (polynomial time algorithms), then the view of out protocol $\pi$ given more information that the ideal implementation of $F$, assuming factoring to be a hard problem.

My doubts are the following:

(1) Am I right to conclude that the protocol $\pi$ described above is information theoretically secure but not computationally secure, in the presence of one corrupt party.

(2) Does the simulator $S$ designed for showing the equivalence of an ideal implementation and a proposed implementation always need to be efficient? Is it dependent on the adversary's computational capabilities?


In order for information-theoretic security to imply computational security, you need to require that the simulator run in time that is polynomial in the running time of the real adversary. This is the standard definition, specifically to avoid protocols such as you presented in your question.

So, the answer is:

  1. If you allow the simulator to be unbounded in running time (and irrespective of the running time of the real adversary) then information-theoretic security does not necessarily imply computational security.
  2. If you restrict the simulator as I described, then information-theoretic security does imply computational security.

In my opinion, it makes no sense to allow the simulator to be unbounded if the real world party is (and this is the case in the real world). Therefore, I strongly argue that you must restrict the simulator as described.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.