Cryptology ePrint Archive: Report 2010/302

Using the Inhomogeneous Simultaneous Approximation Problem for Cryptographic Design

Frederik Armknecht and Carsten Elsner and Martin Schmidt

Abstract: 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 be open and investigated for a long time to make its hardness assumption plausible. Second, it should be easy to construct hard problem instances. Third, it should allow to build cryptographic applications on top of them. 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 introduce another candidate: the Inhomogeneous Simultaneous Approximation Problem (ISAP), an old problem from the field of analytic number theory that dates back to the 19th century. Although the Simultaneous Approximation Problem (SAP) is already known in cryptography, it has mainly been considered in its homogeneous instantiation for attacking schemes. We take a look at the hardness and applicability of ISAP, i.e., the inhomogeneous variant, for designing schemes.

More precisely, we define a decisional problem related to ISAP, called DISAP, and show that it is NP-complete. With respect to its hardness, we review existing approaches for computing a solution and give suggestions for the efficient generation of hard instances. 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).

Category / Keywords: foundations / Simultaneous Approximation Problem, Analytic Number Theory, Diophantine Approximation, Provable Security, Commitment Scheme

Date: received 20 May 2010, last revised 15 Oct 2010

Contact author: mschmidt at ifam uni-hannover de

Available formats: PDF | BibTeX Citation

Version: 20101015:100114 (All versions of this report)

Discussion forum: Show discussion | Start new discussion