Title: On the Higher bit Version of Approximate
Inhomogeneous Short Integer Solution Problem
Resume: We explore a bitwise modification in
Ajtai’s one-way function. Our main contribution
is to define the higher-bit approximate
inhomogeneous short integer solution (ISIS)
problem and prove its reduction to the ISIS
problem. In this new instance, our main idea
is to discard low-weighted bits to gain compactness.
As an application, we construct a bitwise version
of a hash-and-sign signature in the random oracle
model whose security relies on the (Ring)-LWE and
(Ring)-ISIS assumptions. Our scheme is built from
the hash-and-sign digital signature scheme based
on the relaxed notion of approximate trapdoors
introduced by Chen, Genise and Mukherjee (2019).
Their work can be interpreted as a bitwise optimization
of the work of Micciancio and Peikert (2012).
We extend this idea and apply our technique to
the scheme by discarding low-weighted bits in
the public key. Our modification brings improvement
in the public key size but also in the signature size when
used in the right setting. However, constructions based
on the higher-bit approximate ISIS save memory space
at the expense of loosening security. Parameters must
be set in regards with this trade-off. Finally, we combine
the higher bit approximate setting with the use of a
non-spherical Gaussian sampler as suggested by Jia,
Hu and Tang (2021) to construct a hash-and-sign signature
in the random oracle model whose security relies on the
(Ring)-LWE and (Ring)-ISIS assumptions. This helps us
understand better the higher-bit approximate setting.
