环上的隐藏数问题的研究

项目名称： 环上的隐藏数问题的研究

项目编号： No.61272039

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 自动化技术、计算机技术

项目作者： 吕克伟

作者单位： 中国科学院信息工程研究所

项目金额： 60万元

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

中文关键词： 隐藏数问题；环；密码系统；单向函数；格

英文摘要： 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

英文关键词： Hidden number problem；Ring；Cryptosystem；Oneway function；Lattice