# Can a monoalphabetic substitution cipher attain perfect secrecy?

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\,]$$

-
yes if the plaintext space is restricted to one character and the substitution mapping is truly random. – mikeazo Mar 13 '14 at 14:08
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 '14 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 '14 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 '14 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 '14 at 15:31

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?