Large Vector Problem (LVP)

Propose Edit

Updated:

The Large Vector Problem (LVP) was proposed by Cong, Cozzo, Maram, and Smart in 2021 [1] to propose a hybrid public-key encryption scheme. The problem requires an adversary to find a short vector, which multiplied by a (LWE-style) hidden matrix drawn from a discrete Gaussian distribution has large (infinity) norm.

Definition

LVP\(_{n,q,\sigma,c}\)

Sample \(\mat{A}_0 \sample \ZZ_q^{n \times n}\) and \(\mat{R}_0, \mat{R}_1 \sample D_{\ZZ,\sigma}^{n \times n}\). Define \(\mat{A}_1 = \mat{A}_0 \cdot \mat{R}_0 + \mat{R}_1 \bmod q\). Given \(\mat{A}_0\), \(\mat{A}_1\), an adverary is asked to find a short vector \(\vec{m} \in [-1/2,1/2]^n\) s.t.

\[\norm{\mat{R}_0 \cdot \vec{m}}_\infty \geq c \cdot \sigma \cdot \sqrt{n}/2.\]

Intuitively, the LPV assumption states that for a given LWE key \((\mat{A}, \mat{A} \cdot \mat{R}_0 + \mat{R}_1)\), it is hard to find a small vector \(\vec{m}\) such that \(\mat{R}_0 \cdot \vec{m}\) is relatively big.

Hardness

The following summarises the discussion of LVP in Section 5 of [1].

The probability that there are no solutions at all to the problem is roughly \(1 - n \cdot \mathsf{erfc}(c)\), where \(\mathsf{erfc}(c) \approx 2^{-\epsilon}\) and \(\epsilon = 128\) for \(c = 9.3\). Thus, the probability that there are any solutions (information theoretically) is very small for large enough \(c\).

If Search-LWE could be solved efficiently for the pair \((\mat{A}_0, \mat{A}_1)\) then finding a solution vector \(\vec{m}\) could potentially be trivial (if such a solution exists). If Search-LWE is hard then \(\mat{R}_0\) is hidden and thus, the adversary can only guess a message.

Based on this assumption, Cong et al. [1] analyse the problem assuming that \(\mat{R}_1\) is hidden and its variance to conclude that an adversary should not be able to exceed the advantage \(n \cdot \mathsf{erfc}(c)^2\), which they formalise in Conjecture 5.1.

Constructions built from LVP

  • Hybrid Public-Key Encryption [1]
  • LWE provides similar information to the adversary but asks for some output satisfying a different condition.

References

  • [1]Kelong Cong, Daniele Cozzo, Varun Maram, and Nigel P. Smart. 2021. Gladius: LWR Based Efficient Hybrid Public Key Encryption with Distributed Decryption. In Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6-10, 2021, Proceedings, Part IV (Lecture Notes in Computer Science), 2021. Springer, 125–155. Retrieved from https://ia.cr/2021/096