Perfect secrecy with some considerartion According to eavesdropping indistinguishability experiment $PrivK_{A,\Pi}^{eav}$ from page 34 of this book, I define $\varepsilon$-perfect secrecy as this($\varepsilon&gt;0)$: For every adversary $A$ We have: $Pr[PrivK_{A,\Pi}^{eav}=1]≤\frac12+\varepsilon$. I want to prove that $\varepsilon$-perfect secrecy holds, when $|K|&lt;|M|$. Can anybody guide me? ($|K|$ and $|M|$ are the number of keys and messages in our schema respectively).
I want to prove that $\epsilon$-perfect secrecy holds, when $|K|&lt;|M|$.


I think you are misunderstanding something here. For perfect secrecy as defined, $|K| \geq |M|$ does not imply perfect secrecy. It is the other way around: If perfect secrecy is given, this implies $|K| \geq |M|$.

The implication the other way is impossible to show: Consider $E(m,k) = m$, with some keyspace $K$ larger than the message space $M$ (no need to be more specific). In this case we have $|K| \geq |M|$, but obviously it's not perfectly secret. 

And the same goes for your idea: You can not show that something has any kind of secrecy definition, when just the size of the messagespace and keyspace fullfill some equation or inequality. The (almost trivial) counterexample $E(m,k) = m$ with matching key- and message spaces works there as well.