Paper 2010/302

Using the Inhomogeneous Simultaneous Approximation Problem for Cryptographic Design

Frederik Armknecht, 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).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Simultaneous Approximation ProblemAnalytic Number TheoryDiophantine ApproximationProvable SecurityCommitment Scheme
Contact author(s)
mschmidt @ ifam uni-hannover de
History
2010-10-15: last of 2 revisions
2010-05-25: received
See all versions
Short URL
https://ia.cr/2010/302
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/302,
      author = {Frederik Armknecht and Carsten Elsner and Martin Schmidt},
      title = {Using the Inhomogeneous Simultaneous Approximation Problem for Cryptographic Design},
      howpublished = {Cryptology ePrint Archive, Paper 2010/302},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/302}},
      url = {https://eprint.iacr.org/2010/302}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.