Perfect Deniability of a MAC Protocol
Does this satisfy the properties of a MAC?


No, it doesn't, however a tweak to it does.

The issue is that flipping a single bit of $m$ always changes either every bit of the MAC (if $n$ is odd), or none of the bits (if $n$ is even); hence it is trivial for the attacker to modify the message, and adjust the MAC.

What you really meant is $b_i = \bigoplus_{j=1}^{n}(m \wedge k_i)$ (where $\wedge$ is the bit-wise and operation.  This still needs a bit of tweaking (because of the all-0 message; either include an artificial 1 bit in the message, or cheaper, do a final xor of yet another $k$ vector into the final $b$ result).

This method is equivalent to selecting a random $(n \times n)$ matrix in $GF(2)$, and then doing a matrix multiplication of the message to form the output; this is a well-known universal hash method.


  Does this satisfy this definition?


With the above tweaks, yes.


  Could this be done with a smaller key?


Of course.  I suspect that most universal hash methods could be made to do this; here's one approach (polynomial hashing) that uses quite a small key.

Lets pick an integer $z$, and a field representation of $GF(2^z)$ (actually, any field of about this size can be made to work).

Then, for our one-time keys key, we pick two random $z$-bit values $h$ and $c$.

Then, we divide our $n$-bit message $m$ into $z$-bit sized chunks $m_{i-1}, m_{i-2}, ..., m_0$ (where $i = \lceil( n / z ) \rceil$, and we compute:

$$MAC = m_{i-1} h^{i+1} + m_{i-2} h^{i} + ... + m_0 h^2 + i h + c$$

The above computation is done in $GF(2^z)$

This is also a secure MAC (any modification to the message and tag will pass the checks with probability at most $(i+1)2^{-z}$; we can select $z$ to make this arbitrarily small), and it also meets your requirements (to fake a MAC, we can select an arbitrary $h$ and compute what the $c$ value had to be); using a total of $2z$ OTS bits per message.