# MACing from an arbitrary high min-entropy shared secret

Let $\gamma$ be such that $\, 0<\gamma \,$. $\hspace{.1 in}$ Define $H_{\infty}$ to be min-entropy.

If $S_n$ is a shared secret between Alice and Bob such that $\, n^{\frac12+\gamma} \leq H_{\infty}(S_n) \,$,
then Alice can use that to securely encrypt a message for Bob.
(Alice uses a strong extractor, such as in either of Theorem 2/3,
to get the key, and sends the seed along with the ciphertext.)

This idea does not obviously suffice for Alice to authenticate a message to Bob, since a false
acceptance could be caused by someone changing both the message and the reported seed.

Is there a way for Alice to authenticate a message to
Bob from an arbitrary high min-entropy shared secret?

Potential Clarifications:

a. $\,$ I am fine with "high" meaning something much closer
$\hspace{.24 in}$to $n$ than I used in the encryption construction.

b. $\,$ I really do mean "Alice to authenticate a message to Bob"; that is,
$\hspace{.24 in}$it does not need to work from Bob to Alice or for more than one message.

c. $\,$ I would nonetheless be interested in whether or not
$\hspace{.24 in}$the restrictions described in (b) could be relaxed.

• What do you mean by "min-entropy 1/2"? $\,$ The definition I'm using would make that trivially a requirement. $\;$ – user6973 Dec 1 '11 at 5:42