已知秘密界的隐藏数问题

摘要

经典隐藏数问题方法(Hidden Number Problem,HNP)可用于实现密码系统安全性到相关秘密(隐藏数)的比特预测的有效概率归约.但是其效率及成功概率均与对Oracle询问次数、Oracle回答的信息量等紧密相关.本文在已知隐藏数x的一个界X的前提下,研究有d次询问Oracle回答的HNP,将HNP问题转化为基于格求解单变元模不等式(tx-u)modN＜δ的问题,证明在经过d次Oracle询问后,可以很大概率成功恢复出秘密,这里成功概率和效率紧密依赖于X及δ;同时给出了该算法中X和δ的制约关系,改进了Rosa的方法.进而,作为应用,在随机预言模型下分析了Schnorr签名安全性,给出该签名的安全性到其临时随机数的比特预测性的有效归约.