Using the Inhomogeneous Simultaneous Approximation Problem for Cryptographic Design

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

Abstract

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).

Authors with CRIS profile

Martin Schmidt Juniorprofessur für Optimierung von Energiesystemen

Involved external institutions

Universität Mannheim DE Germany (DE) Fachhochschule für die Wirtschaft Hannover (FHDW) DE Germany (DE)

How to cite

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