Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Can a monoalphabetic substitution cipher attain perfect secrecy?

Definition of perfect secrecy:

$${\rm Pr}[\,{\rm Enc}_k(m_1) = c\,] = {\rm Pr}[\,{\rm Enc}_k(m_2) = c\,]$$

share|improve this question
2  
yes if the plaintext space is restricted to one character and the substitution mapping is truly random. –  mikeazo Mar 13 at 14:08
1  
Firstly, is this a H/W question? If so we can give you some hints but probably shouldn't tell you the answer... Secondly: Following from Mike's point, think carefully what you mean by 'alphabet'. With a suitably large alphabet and sufficiently large keyspace clearly yes (eg I could use a complete English dictionary as my alphabet if i wanted) –  figlesquidge Mar 13 at 14:10
    
@figlesquidge, right. In some sense the OTP is a monoalphabetic substitution cipher where the alphabet is all strings of a specific length. –  mikeazo Mar 13 at 14:29
    
yes , it is a part of H/W. @figlesquidge do you say that if the plaintext space is larger than one charachter then it is possible to have perfect secrecy? you said that you could use a complete English dictionary as an alphabet, does it mean to match each character to a word in a dictionary? –  abdolahS Mar 13 at 14:34
    
An "Alphabet" is just a collection of symbols. I can choose whatever set of symbols I like and as many as I want. Just because we traditionally denote alphabet symbols by a single character doesn't mean we have to. That said, this is probably not what your H/W is looking for. Mike's answer is more likely to be relevant to what your class is after –  figlesquidge Mar 13 at 15:31
add comment

1 Answer 1

Since this is homework, let me just give you a hint: consider the two-character messages $m_1 = \text{"aa"}$ and $m_2 = \text{"ab"}$.

Given a ciphertext $c$ encrypted with a monoalphabetic substitution cipher, can you tell which of $m_1$ or $m_2$ it corresponds to, even without knowing the key? Why (not)? What does this imply about perfect secrecy?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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