**The LPN Problem with Auxiliary Input**

*Yu Yu*

**Abstract: **This paper investigates the Learning from Parity with Noise (LPN)
problem under the scenario that the unknowns (secret keys) are only
unpredictable instead of being uniformly random to the adversaries.
In practice, this corresponds to the case where an adversary already
possesses some additional knowledge about the secret key. In the
information-theoretic setting, we show that the problem is robust
against arbitrary leakages as long as the unknowns remain some
sufficient amount of min-entropy. In the computational setting, we
prove Dodis et al.'s [STOC'09] conjecture that the auxiliary-input
LPN assumption is implied by the standard LPN assumption,
i.e., encryption schemes based on the standard LPN
assumption is secure against any exponentially hard-to-invert
auxiliary input.

\medskip Our setting is more general than the traditional model of auxiliary input which deals with secret keys of sufficient min-entropy, in particular, we allow leakages that information-theoretically determine their secret keys as long as the keys remain a linear amount of unpredictability pseudoentropy. Further, unlike most other schemes, our result is reducible to a well-known hardness problem and does not quantify over all hard-to-invert auxiliary functions.

**Category / Keywords: **hard learning problem, cryptography with auxiliary input

**Publication Info: **n.a.

**Date: **received 23 Sep 2009, last revised 28 Sep 2009, withdrawn 29 Sep 2009

**Contact author: **yu yu at uclouvain be

**Available format(s): **(-- withdrawn --)

**Version: **20090929:071544 (All versions of this report)

**Short URL: **ia.cr/2009/467

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]