负数据库是一种新兴的数据保护方法,其存储原始数据的补集信息。关于负数据库的研究主要集中在两个方面:负数据库的生成算法研究和负数据库的应用研究。基于负数据库的不可逆性和多样性等性质,负数据库可以被用来保护原始数据。负数据库已被应用到很多领域,如安全生物识别,安全多方计算,和一次性口令认证。为了进一步扩展负数据库的生成算法研究和负数据库的应用研究,本文开展单串负数据库(对应的原数据库包含一条记录)的相关问题研究,分为以下两个部分。(1)提出了一个含预定义解和社区结构的SAT(布尔可满足问题)实例生成算法。SAT实例与负数据库一一对应,因此,SAT实例生成算法可以用于生成负数据库。本文首先分析了现有的负数据库生成算法和SAT实例生成算法的特点。然后,通过结合具有不同性质的两类生成算法,提出了一个SAT实例生成算法。该算法不仅可以保证生成的SAT实例含有一个预定义解,而且对SAT实例对应的社区结构具有细粒度的控制。最后,研究了本算法的不同参数设置对SAT实例难解度(通过两类求解器的求解时间衡量:基于随机局部搜索策略的求解器,和基于冲突驱动子句学习策略的求解器)的影响。(2)提出了一个基于单串负数据库的口令认证框架。本文首先分析了典型的口令存储方案(散列口令,加盐散列口令,和密钥延展口令)存在的一些问题。然后,提出了基于单串负数据库的口令认证框架。在本框架中,认证数据表通过存储加密负口令,来实现口令的安全存储。加密负口令利用了单串负数据库的可逆性和多样性,并结合了密码散列函数和对称密钥算法的优势。接着,提出了加密负口令的两个实现。最后,分析了加密负口令和典型的口令存储方案的攻击复杂性。分析结果表明,加密负口令可以抵抗查找表攻击;在字典攻击下,加密负口令依然可以较安全地存储口令。本文主要研究了单串负数据库的生成算法,和单串负数据库在口令认证方面的应用。分析和实验结果表明,本文提出的算法是有效的,对负数据库的研究起到了一定的扩展作用。