Traditional data authentication systems are sensitive to single bit changes and so are unsuitable for message spaces that are naturally "fuzzy" where "similar" messages are considered "the same" or indistinguishable. In this paper, we study unconditionally secure approximate authentication. We generalize traditional universal hashing to fuzzy universal hashing and use it to construct secure approximate authentication for multiple messages.