International Association for Cryptologic Research

International Association
for Cryptologic Research


Martin Schmidt


Using the Inhomogeneous Simultaneous Approximation Problem for Cryptographic Design
Since the introduction of the concept of provable security, there has been the steady search for suitable problems that can be used as a foundation for cryptographic schemes. Indeed, identifying such problems is a challenging task. First, it should allow to build cryptographic applications on top of them. Second, it should be open and investigated for a long time to make its hardness assumption plausible. Third, it should be easy to construct hard problem instances. Not surprisingly, only a few problems are known today that satisfy all conditions, e.g., factorization, discrete logarithm, and lattice problems. In this work, we investigate another candidate: the Inhomogeneous Simultaneous Approximation Problem (ISAP), an old problem from the field of analytic number theory. Although this problem is already known in cryptography, it has mainly been considered for attacks while we take a look at its hardness and applicability for cryptographic design. More precisely, we define a decisional problem related to ISAP, called DISAP, and show that it is NP-complete. As a starting point for concrete parameter ranges, we review the hardness of a related problem, being a computational and homogeneous variant of DISAP. Regarding the applicability, we describe as a proof of concept a bit commitment scheme where the hiding property is directly reducible to DISAP. An implementation confirms its usability in principle (e.g., size of one commitment is slightly more than 6 KB and execution time is in the milliseconds). From our point of view, DISAP is an interesting problem that can be used for cryptographic designs. We hope to encourage further research on (D)ISAP in particular and possibly other problems from analytic number theory in general.