2
$\begingroup$

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?

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
0
-3
$\begingroup$

Apologies for the delay in responding... 6 years...lol. Firstly, allow me to suggest that you have a problem with your security/(in)security definitions. There are only 2 real security categories:

  • Information Theoretical Security - For a closed pure secrecy system producing a ciphertext C to be considered information theoretically secure the conditional entropy of Message M (He(M)) and the conditional entropy of key K (He(K)) MUST be >= 1. Perfect Secrecy requires all possible messages and associated keys after a brute force attack, and Ideal Secrecy requires 2 or more possible messages and keys AFTER a brute force attack by an assailant with unlimited time and resources. It is these additional "possible" but wrong messages or keys that provide the security. You can also rely on Practical Secrecy - use of a mathematical problem to create workload, but that is not technically "info-theoretic security". In any event, it requires a proof that no fast solution to your mathematical problem exists. None has ever been provided for the systems we use now.
  • Computational Security? - Sorry, but that is just a made up pseudo-security term to justify not providing the proof of no fast solution to the maths problem. It's got no mathematical basis for security. And in any event, no time based security system can be info-theoretically secure - Using time merely indicates "it's just a matter of time before its broken".
  • Cryptographic Security? That's a security double standard, to give the illusion that insecure systems are "secure". The Enigma machine was "Cryptographically secure". You cannot use opinion to imply info-theoretic security, you must plot a conditional entropy graph, showing the conditional entropy of various message redundancy types to see whether it is secure or not. Again, this is the use of time based complexity theory to imply an assumed security state, when the onus is really to provide proof that such a system does not have a fast solution to the maths problem used.

As for P=NP, or P=!NP, from a cryptographic risk perspective, it should be assumed that P=NP until proven otherwise (which it is on the cryptographic level that you are working on). If you don't, then all you are doing is providing the illusion of security and putting peoples lives and finances at risk (which current solutions do). Worse still, you'll never know that you have been breached, because you cannot detect the passive compromise of your systems.

The problem is that info-theoretic systems exist, but are not taught in academia. If you set your sights REALLY high and focus on how you can prevent the attacker's elimination of keys and messages from reducing entropy to a single result, then you will attain the standard required for info-theoretic security. Anything else is just mathematical masturbation.

Please note that all current asymmetric solutions are NOT info-theoretically secure, as the key conditional entropy is GUARANTEED to be resolved to a single solution under a brute force attack. Its a great use of mathematics, but is doesn't work. Just because you are not aware of a fast solution to RSA, does not mean tat one is not available. I would recommend that you assume that the assailant can break such systems within a second. It is the solutions to breaking RSA/DH/EC that allows for future info-theoretically secure systems to be created.

Lastly. I.m sorry, but I cannot see how your system can be information theoretically secure, unless you use "augmented digital" one time pads to send P and Q to party 3. There are at least 2 hardware quantum based solutions on the market which you can use.

Your problem is an authentication and trust problem. You must first establish authentication for P3 (so its the right party), then implement a means to detect that P3 violates integrity, then have a means to revoke P3s authentication if trust is violated.

If you get rid of the idea that time provides any security, then you will be closer to creating an information-theoretic asymmetric solution.

Two information-theoretically secure systems (one symmetric and other asymmetric), secure against an unbounded assailant, will be revealed in the next 3 months. Analyse them extremely critically, and then you'll get to understand what is required to create your own.

Many will object to my answer, but if we don't raise our security standards just beyond impossible, we'll always be insecure.

$\endgroup$
1
  • 2
    $\begingroup$ This post doesn't directly seem to address the question given and seems to make unsubstantiated claims. Please edit it so that these issues are resolved. $\endgroup$
    – Maarten Bodewes
    Commented Oct 29, 2022 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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