MACing from an arbitrary high min-entropy shared secret

Question

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.

Answer 1

As you may know, the problem of taking a weak shared key, about which the adversary knows some information, and extracting from it a key about which the adversary has essentially no information, is often referred to as privacy amplification. Once this is done, we can use the new strong key for authentication, encryption, etc.

If interaction is allowed, Alice and Bob can extract a strong key over an inauthentic channel very efficiently, in particular there is no requirement that the min-entropy rate be at least 1/2. See "Privacy Amplification with Asymptotically Optimal Entropy Loss" by Chandran, Kanukurthi, Ostrovsky, Reyzin, and references therein.

Their introduction mentions that non-interactive solutions (one message from Alice to Bob) exist as well (references 5, 10, 15), but these do require min-entropy rate 1/2. Depending on the application, another possibility for a one-message solution would be to use deterministic (aka seedless) extractors, which work only for certain classes of sources with some restricted structure. For instance, the adversary knows some fraction of the key's bits, but the remainder are uniformly random to him. See for example Kamp and Zuckerman, "Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography" or Kamp, Rao, Vadhan, Zuckerman, "Deterministic Extractors for Small-Space Sources"