Abstract. In this work, we construct the first digital signature (SIG)
and public-key encryption (PKE) schemes with almost tight multi-user
security under adaptive corruptions based on the learning-with-errors
(LWE) assumption in the standard model. Our PKE scheme achieves almost tight IND-CCA security and our SIG scheme achieves almost tight
strong EUF-CMA security, both in the multi-user setting with adaptive
corruptions. The security loss is quadratic in the security parameter λ,
and independent of the number of users, signatures or ciphertexts. Previously, such schemes were only known to exist under number-theoretic assumptions or in classical random oracle model, thus vulnerable to quantum adversaries.
To obtain our schemes from LWE, we propose new frameworks for
constructing SIG and PKE with a core technical tool named probabilistic quasi-adaptive hash proof system (pr-QA-HPS). As a new variant of
HPS, our pr-QA-HPS provides probabilistic public and private evaluation
modes that may toss coins. This is in stark contrast to the traditional
HPS [Cramer and Shoup, Eurocrypt 2002] and existing variants like approximate HPS [Katz and Vaikuntanathan, Asiacrypt 2009], whose public and private evaluations are deterministic in their inputs. Moreover,
we formalize a new property called evaluation indistinguishability by requiring statistical indistinguishability of the two probabilistic evaluation
modes, even in the presence of the secret key. The evaluation indistinguishability, as well as other nice properties resulting from the probabilistic features of pr-QA-HPS, are crucial for the multi-user security proof
of our frameworks under adaptive corruptions.
As for instantiations, we construct pr-QA-HPS from the LWE assumption and prove its properties with almost tight reductions, which
admit almost tightly secure LWE-based SIG and PKE schemes under our
frameworks. Along the way, we also provide new almost-tight reductions
from LWE to multi-secret LWE, which may be of independent interest.
标签：Multi,Almost,almost,HPS,under,our,Model,security,LWE From： https://blog.51cto.com/u_14897897/7992966