On the Higher-Bit Version of Approximate Inhomogeneous Short Integer Solution Problem

Anaëlle Le Dévéhat, Hiroki Shizuya, Shingo Hasegawa

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    1 Citation (Scopus)


    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.

    Original languageEnglish
    Title of host publicationCryptology and Network Security - 20th International Conference, CANS 2021, Proceedings
    EditorsMauro Conti, Marc Stevens, Stephan Krenn
    PublisherSpringer Science and Business Media Deutschland GmbH
    Number of pages20
    ISBN (Print)9783030925475
    Publication statusPublished - 2021
    Event20th International Conference on Cryptology and Network Security, CANS 2021 - Virtual, Online
    Duration: 2021 Dec 132021 Dec 15

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume13099 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference20th International Conference on Cryptology and Network Security, CANS 2021
    CityVirtual, Online

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)


    Dive into the research topics of 'On the Higher-Bit Version of Approximate Inhomogeneous Short Integer Solution Problem'. Together they form a unique fingerprint.

    Cite this