1.12: An encryption scheme where the number of keys is smaller than the number of plaintexts corresponds to a bipartite graph where the degree is smaller than the number of vertices on the left side. Together with the validity condition this implies that there will be two left vertices x,x' with non-identical neighborhoods, and hence the scheme does not satisfy perfect secrecy.
{}