当今社会中,网络交流在日常生活中占据着重要地位,同时也带来了一系列的信息安全问题。为了防止网络中的恶意第三方假冒正常用户,通常需要进行身份认证,即通过一定的技术手段,对网络中的用户身份进行确认。身份认证方案的构造方法也很多,比如基于密码学知识的认证,基于生物学特征的认证等等,相比较而言,基于密码学上的困难问题构造身份认证方案的应用更加广泛。目前,大量身份认证方案的构建基于密码学里传统的困难问题,例如大整数因子分解问题,有限域上的离散对数问题等,但是此类身份认证方案是存在不足的:一方面,密钥的增长速度随着系统的安全要求增加而增长,导致方案的计算开销越来越大;另一方面,传统的困难问题难以抵抗量子计算机攻击,致使身份认证方案的安全性容易被破坏。针对现有身份认证方案的不足,本文基于编码困难问题去构建安全高效,开销较小的零知识身份认证协议。针对一些交互式身份认证方案存在合理性欺骗概率较大的问题,本文提出来一种基于矩阵填充困难问题的零知识MCZK身份认证方案。本文基于低秩矩阵填充困难问题,构建了一种五轮交互式的身份认证协议,在验证者和证明者之间增加了随机数和随机矩阵的传递,把原来的攻击者成功假冒证明者的概率从2/3降低为1/2,减少了达到同样要求的系统安全性的协议执行次数,本文同样证明了MCZK方案作为一个零知识证明协议,满足完备性,合理性,零知识性。通过实验仿真分析可知,本文MCZK方案在选取11×11维矩阵时,具有通信开销较小,总协议次数较少,抵抗量子攻击的优点。针对一些基于汉明编码困难问题的身份认证方案中存在通信开销较大,效率较低的问题,本文又提出来一种基于秩校验子译码的零知识RSDZK身份认证方案。本文设计一个承诺算法,通过两个随机向量掩盖证明者的私钥,协助构建了一个交互式的零知识证明方案,并证明方案满足三个性质:完备性,合法性和零知识性。在实验仿真中,本文分别在秩度量和汉明度量上实现了RSDZK方案以及对比方案,并比较了它们在不同安全参数下的秘密值长度,平均通信开销等,结果显示本文方案的平均通信开销降低了约58%,同时在选取公共参数上具有明显的优势。此外,本文测试了两个方案在一次协议中各个交互阶段的运行时间,验证了本文RSDZK方案在时间效率上的优越性。最后,本文结合理论分析和仿真实验,验证了两个交互式零知识身份认证方案的安全性和高效率,并对基于编码困难问题构建身份认证方案的研究方向作出展望。