Armknecht F, Elsner C, Schmidt M (2011)
Publication Type: Book chapter / Article in edited volumes
Publication year: 2011
Publisher: Springer Berlin / Heidelberg
Edited Volumes: Progress in Cryptology – AFRICACRYPT 2011
Series: Lecture Notes in Computer Science
Book Volume: 6737
Pages Range: 242-259
ISBN: 978-3-642-21968-9
DOI: 10.1007/978-3-642-21969-6_15
We introduce the Inhomogeneous Simultaneous Approximation Problem (ISAP), an old problem from the field of analytic number theory. 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 solving related problems 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 6273 bits and execution time is in the milliseconds).
APA:
Armknecht, F., Elsner, C., & Schmidt, M. (2011). Using the Inhomogeneous Simultaneous Approximation Problem for Cryptographic Design. In Nitaj A, Pointcheval D (Eds.), Progress in Cryptology – AFRICACRYPT 2011. (pp. 242-259). Springer Berlin / Heidelberg.
MLA:
Armknecht, Frederik, Carsten Elsner, and Martin Schmidt. "Using the Inhomogeneous Simultaneous Approximation Problem for Cryptographic Design." Progress in Cryptology – AFRICACRYPT 2011. Ed. Nitaj A, Pointcheval D, Springer Berlin / Heidelberg, 2011. 242-259.
BibTeX: Download