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