Scholarlink

In this work, we investigate the landscape of emerging lattice-based assumptions tailored for anonymous credentials, focusing on variants of the Short Integer Solution (SIS) problem augmented with auxiliary hints. We provide a tight reduction from the Generalised ISIS \(_{f_\kappa }\) ( \(\text {GenISIS}_{f_\kappa }\) ) (Dubois et al., PKC 2025) assumption to its interactive variant \(\text {IntGenISIS}_{f_\kappa }\) , enabling the construction of proof-friendly signature schemes without incurring the significant efficiency loss observed in prior works. In particular, our results directly apply to the anonymous credential scheme proposed by Bootle et al. (CRYPTO 2023), and circumvent the 4X blow-up in the credential size due to their security loss. We also identify families of functions f for which \(\text {GenISIS}_{f_\kappa }\) is as hard as SIS, leading to the first (strongly) unforgeable standard-model signature scheme from SIS without relying on chameleon hash functions. Moreover, we analyse the “one-more”-type lattice assumptions, showing in particular that Randomised One-More-ISIS (Baldimtsi et al., ASIACRYPT 2024) is at least as hard as standard One-More-ISIS (Agrawal et al., ACM CCS 2022). Further, we inspect different, yet equivalent, variations of Randomised One-More-ISIS which could be of independent interest. Finally, we compare the structural properties of \(\text {GenISIS}_{f_\kappa }\) and One-More-ISIS, highlighting both shared techniques and fundamental differences. We believe our results contribute to a clearer understanding of the assumptions underpinning efficient, lattice-based anonymous credential systems.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Tight Reductions for SIS-with-Hints Assumptions with Applications to Anonymous Credentials

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Ngoc Khanh Nguyen,
  • Jan Niklas Siemer

摘要

In this work, we investigate the landscape of emerging lattice-based assumptions tailored for anonymous credentials, focusing on variants of the Short Integer Solution (SIS) problem augmented with auxiliary hints. We provide a tight reduction from the Generalised ISIS \(_{f_\kappa }\) ( \(\text {GenISIS}_{f_\kappa }\) ) (Dubois et al., PKC 2025) assumption to its interactive variant \(\text {IntGenISIS}_{f_\kappa }\) , enabling the construction of proof-friendly signature schemes without incurring the significant efficiency loss observed in prior works. In particular, our results directly apply to the anonymous credential scheme proposed by Bootle et al. (CRYPTO 2023), and circumvent the 4X blow-up in the credential size due to their security loss. We also identify families of functions f for which \(\text {GenISIS}_{f_\kappa }\) is as hard as SIS, leading to the first (strongly) unforgeable standard-model signature scheme from SIS without relying on chameleon hash functions. Moreover, we analyse the “one-more”-type lattice assumptions, showing in particular that Randomised One-More-ISIS (Baldimtsi et al., ASIACRYPT 2024) is at least as hard as standard One-More-ISIS (Agrawal et al., ACM CCS 2022). Further, we inspect different, yet equivalent, variations of Randomised One-More-ISIS which could be of independent interest. Finally, we compare the structural properties of \(\text {GenISIS}_{f_\kappa }\) and One-More-ISIS, highlighting both shared techniques and fundamental differences. We believe our results contribute to a clearer understanding of the assumptions underpinning efficient, lattice-based anonymous credential systems.