Using the Inhomogeneous Simultaneous Approximation Problem for Cryptographic Design
Using the Inhomogeneous Simultaneous Approximation Problem for Cryptographic Design
复制标题
利用非齐次联立逼近问题进行密码设计
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Martin Schmidt
中科院分区：
文献类型：
--
作者：
Frederik Armknecht;C. Elsner;Martin Schmidt
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).
