保障信息高效安全传输的密码学在信息安全、网络空间安全等领域起着基础核心的作用。由于量子计算技术的快速发展,基于经典数论困难问题的传统密码方案将面临极大的威胁。作为后量子密码体制的典型代表,格基密码学近些年来已经受到成为国内外学者密切的关注。作为密码学的重要组成部分,数字签名技术能够满足网络环境中的身份认证、数据完整性以及不可否认性等需求。大多数格基签名方案均基于随机格上小整数解(Small Integer Solution, SIS)问题或非齐次小整数解问题。从线性代数的观点来看,此两个问题可以看成求欠定线性方程组的短整数向量解。若将此离散空间欠定线性方程组求解问题扩展到实数域或者复数域上,则其与压缩感知模型极为相似。压缩感知理论蕴藏了天然的加密属性且无需额外的随机编码过程,已被广泛地应用于图像加密、身份认证以及秘密共享等密码方案中。本文从格与压缩感知底层不同类型的欠定线性系统出发,在熟悉相关理论的基础上,提出了若干个基于格与压缩感知的密码方案,目标是为寻找格与压缩感知理论的共同优势奠定一定的基础。从安全与效率的角度,本文首先提出了三个标准模型下基于格的签名方案,包含常数公钥大小的短格基签名方案、格基线性同态签名方案以及格基层级全同态签名方案。此外,基于压缩感知的压缩与加密特性,构建了一个基于压缩感知的图像秘密共享方案,且提出了一种基于压缩感知的耦合映像格子密码系统参数分析方案。本文主要的研究成果与创新点描述如下:(1)提出一个标准模型下具有常数公钥大小的短格基签名方案。在本方案中,每个签名只包含一个低维格向量,公钥只包含三个矩阵与一个向量。为了证明其安全性,提出了一个新的格困难问题:变体SIS问题,并给出了从SIS问题到变体SIS问题的安全性归约。基于此,定义了一类哈希函数且证明了其单向性与抗碰撞性。与先前的格基签名方案相比,本方案的通信负担及计算复杂性较低;(2)提出一个标准模型下高效的格基线性同态签名方案,此方案可为多源网络编码机制提供安全性保护。为了证明其安全性,提出了一个能产生随机格与其对应陷门短基的陷门抽样算法ProductSamp,且证明了该方案在选择文件攻击模型下的存在不可伪造性。所提的线性同态签名方案具有众多优势,如支持多源网络编码、较低计算复杂性以及较低的低通信代价;(3)提出一个基于同态Chameleon哈希函数的标准模型下层级全同态签名方案。首先给出同态Chameleon哈希函数的定义以及一个具体的构造方法,然后基于此哈希函数的抗碰撞特性,构造了可支持多项式深度电路计算的层级全同态签名方案。在此方案中,计算产生的同态签名的大小随着电路深度的增加而呈现多项式的增长;(4)提出一个基于压缩感知的可伸缩(k,n)图像秘密共享方案。可伸缩性意味着重构图像中包含的信息数量与参与者的数目成正比。由于自然图像在合适的基或字典下可以被少量的非零系数表示,该方案充分利用此特性来减小影子图像的大小。此方案具有较强的灵活性,即秘密分发者可以根据不同的应用需求来权衡影子大小与重构效果。此外,该方案具有平滑可伸缩性与抗噪性。与已有方案的分析比较和实验对比结果表明本方案具有可行性与优越性;(5)提出一种基于压缩感知的耦合映像格子混沌系统参数分析方案。耦合映像格子混沌系统经常被用来构造图像加密、哈希函数等密码方案,而其系统参数往往在密码方案中起着非常关键的作用。具体地,首先将耦合映像格子的参数分析问题转化为欠定线性系统的求解问题。然后从理论上证明了当权重矩阵稀疏时,由耦合映像格子混沌系统产生的系数矩阵满足限制性等距条件。因此准确地分析了所需的观测次数要远少于耦合映像格子系统中格元素的个数。实验中还考虑了稀疏度、采样次数以及耦合参数对重构率的影响。该方案另外一个重要的优势是,若观测值带有噪音,则提出的分析方案仍然有效。