Solving `Ax=b` is easy if `x` can be any value. But if you bound `x` such that all entries must be small (e.g. only zeroes and ones) then the problem is hard: h

Solving `Ax=b` is easy if `x` can be any value. But if you bound `x` such that all entries must be small (e.g. only zeroes and ones) then the problem is hard: https://en.wikipedia.org/wiki/Short_integer_solution_problem https://en.wikipedia.org/wiki/Short_integer_solution_problem What you described would be closer to learning with errors (https://en.m.wikipedia.org/wiki/Learning_with_errors https://en.m.wikipedia.org/wiki/Learning_with_errors) combined with SIS/SVP. Learning with errors is based on the parity learning problem (https://en.m.wikipedia.org/wiki/Parity_learning https://en.m.wikipedia.org/wiki/Parity_learning) in machine learning, which I take as a positive sign of security. Interestingly you can get information theoretically secure constructions using lattices by tuning the parameters. For example, if you make the `A` matrix large enough it becomes statistically unlikely that more than 1 solution exists (e.g. generate a random binary vector `x` and it's unlikely that an `x'` exists that solves for `b`).