lets say we have a countable message space for example set of natural numbers then can we have a cryptography system that information-theoretically (Shannon or other equivalence definition) be Perfectly-secret ? if yes please give example if not an intuitionistic or mathematical proof would be great

  • 2
    $\begingroup$ Welcome to crypto.SE. You need to define "symmetric crypto system" very carefully for this to have a precise answer. If the One Time Pad with pad/key as long as the message (thus, countably infinite) and never reused fits that definition, the answer is: demonstraly yes. If the key is finite, the answer is: demonstrably no. $\endgroup$ – fgrieu Mar 3 at 13:56
  • 2
    $\begingroup$ @fgrieu: actually, by the definition assumed by the above question, OTP is not perfectly secret; if you see an OTP-encrypted message of 100 bits, you know that the plaintext cannot be 200 bits... $\endgroup$ – poncho Mar 3 at 14:22
  • $\begingroup$ @Poncho True, but codewords could be present in the OTP-encrypted message (think STASI and the TAPIR). Then the length of the ciphertext does the eavesdropper little good for getting the meaning, of course. Looks perfect to me. If we are going to share and secure symmetric keys, let's share some code too. $\endgroup$ – Patriot Mar 4 at 13:59

The answer is "no, it's not possible"

Since this is likely homework, I won't fill in all the details. I will point you to these ideas:

  • What is the definition of "perfect secrecy". Isn't that the concept that, for a specific ciphertext, each possible plaintext is equiprobable?

  • It turns that that no probability distribution over a countably infinite set is equidistributed - that there will always be some elements more probable than others.

| improve this answer | |
  • $\begingroup$ i think what you mentioned and Shannon theorem implies the answer is no , thanks for help , if you could add more detail to your answer for sake of other people may see this question later i could accept you question as right answer . $\endgroup$ – mike Mar 5 at 8:48
  • $\begingroup$ @mamad: is the question, in fact, homework? If it is, well, I'd rather let you complete your own homework. $\endgroup$ – poncho Mar 5 at 13:23
  • $\begingroup$ @pancho it was a homework and due date is finished . anyway it you choice $\endgroup$ – mike Mar 5 at 14:30
  • $\begingroup$ @mamad: have you figured it out? The main reason for doing homework is not the grade, but instead what learning you get out of it. $\endgroup$ – poncho Mar 5 at 14:31

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.