公钥基础设施(PKI)利用数字证书为网络安全交易提供保障。PKI服务的终端实体之间进行交易之前首先要确定通信双方身份的真实性,为此需要验证通信方数字证书的可信性。在验证数字证书是否可信的过程中,需要构造一条连接通信双方的证书路径,通过验证证书路径中所有证书的可信性,最终确定通信双方证书的可信性。证书路径的构造与终端实体所处信任模型是密不可分的,本文在深入研究了PKI中典型的信任模型的基础上,指出了各个模型的优缺点及其证书路径构造方法。研究侧重于通过改变PKI的体系结构来提高证书路径构造效率,提出了一个新的信任模型——依赖图结构模型。同时给出了该模型下的证书路径构造方案。在依赖图信任模型中,各CA之间信任关系平等,新加入的CA只需与已在信任关系中的K个满足条件的CA相互认证,就能加入到信任体系中,方便了信任域的扩展,同时也减轻了单个CA的证书管理负担。依赖图信任模型具有很好的冗余性,单个CA安全性的削弱对整个信任体系不会造成很大影响。本文对现有信任模型下的证书路径构造方法进行了深入研究,结合所提出的依赖图信任模型,给出了相应的证书路径构造方法。在证书路径构造过程中,采用图的广度优先搜索,同时充分利用依赖图的结构特点,消除了一些无效路径和证书路径回路,提高了证书路径构造效率。