环上的隐藏数问题的研究

In this proposal, we study hidden number problems(HNP, for brevity) over ring, extend the classic HNP to residue ring modulo a composite integer and polynomial domain, and try to solve some instances in HNP. Our work involves the following three aspects:.1）We try to extend the classic HNP to residue ring modulo a composite integer, study the existence and uniqueness of solutions of HNP and construct its solutions. Furthermore, we study HNP over a polynomial domain..2) Over a residue ring modulo a composite integer and a polynomial domain respectively, we study some instances of HNP: T-HNP, EC-HNP, and poly-ring-HNP for the cases of nonlinear hidden information and sparse polynomial..3) For application, we use the results in HNP over ring to analyze the security of cryptosystems and the reduction between the hardness of functions，for instance, computational N-th residuosity problem modulo a composite N, denoted Class[N,N], N-th roots modulo N, denoted RSA[N,N],Paillier cryptosystem, computation of elliptic curve and some trapdoor functions over elliptic curves, etc..These researches will contribute immensely to provide methodological and theoretical support for cryptographic test and analysis under outsourcing services with side channel and energy attacks, which make up a margin of studies in cryptography in our country.

本课题试图探索环上的隐藏数问题（HNP）的一般理论，将经典的HNP研究推广到模合数剩余类环和多项式整环，解决具体的HNP实例。具体内容包括：①将经典的HNP研究推广到模合数剩余类环，研究模合数隐藏数问题解的存在性、唯一性和解的构造。此外,尝试在多项式环上研究隐藏数问题。②研究模合数剩余类环和多项式环上HNP具体实例T-HNP问题、EC-HNP问题以及ploy-环-HNP问题的非线性隐藏信息情形和稀疏多项式或噪声多项式隐藏信息情形。③作为应用，利用模合数剩余类环和多项式整环上HNP结果分析密码系统的安全性和函数困难性归约关系，如，计算模合数N-次剩余类问题Class[N,g]、模合数N时开N-次根问题RSA[N,N]、Pilliar密码系统、椭圆曲线计算以及曲线上的陷门函数等等。.这些研究将为基于侧信道等外援攻击的密码系统分析提供理论基础，填补了国内空白。

本课题研究环上隐藏数问题（HNP）一般理论、格复杂性研究以及离散对数计算等，取得一系列具有很强的理论意义和应用价值成果：1).用分数2-adic展式与MSB、LSB的关系，给出HNP的确定求解方法，并开发成公钥密码的安全检测系统；提出变形隐藏数问题，实现LSB情形隐藏数问题中到经典HNP转化，这丰富HNP理论。2).研究Rabin /RSA-Paillier等具体实例的比特安全性。3). 研究LUC、XTR和RSA模指数函数的hardcore谓词。4).给出区间离散对数（DLP）的计算新算法，并对≦37比特素数试验验证。5).研究格覆盖半径近似计算，给出变体远距离集合问题 (V-RSP)的近似解算法，并分析其计算复杂性。