在大数据环境中,云存储和云计算以低成本、高效率和高可扩展性等优势,已经成为了现实生活中不可或缺的重要组成部分。越来越多的企业、政府机关和个人使用云存储服务将数据外包存储至云服务器,以降低对本地硬件资源的需求,以及减少对数据进行维护与管理的压力。同时,云计算向用户提供按需付费的弹性计算服务,能够有效地降低本地的计算成本。另外,随着互联网信息产业的快速发展,数据的种类越来越丰富、结构越来越复杂。为了实现对复杂的数据进行灵活使用的需求,可以利用图结构对数据进行存储。图结构是由点和边组成的数据结构,并且可以借助丰富的图论算法实现多样化的搜索和计算。然而,云存储和云计算在提供优质服务体验的同时,也带来了安全问题。在数据安全方面,云服务使用户失去了对数据的物理控制,外包存储的数据和委托给云服务器的相关搜索与计算任务面临着严重的隐私泄露风险。因此,近年来面向云环境的隐私保护技术成为了学术界和工业界的研究热点,越来越多地受到了国内外学者的关注。为了满足在云环境中对密态图结构进行全路径搜索、邻接关系查询、交集/并集计算和子图匹配计算的需求,本文对基于图结构的可搜索加密和隐私保护关键技术展开研究,主要研究工作与成果如下:（1）针对密态图结构的全路径搜索问题,提出了一种基于图结构的全路径可搜索加密方案（GSE-APS）。该方案能够允许数据拥有者使用起点和终点在外包存储的密态图结构中搜索所有连接的路径。文中给出了方案的模型,并结合链式结构的思想设计了加密索引。详细描述了方案的具体构建,并在半诚实的威胁模型下对方案进行了安全性证明。从存储、计算和通信三个方面分析了方案的代价,并使用真实的图结构数据集进行了仿真实验。实验结果表明方案的搜索时间与图结构的大小无关,实现了高效的全路径搜索。（2）针对密态图结构的邻接关系查询问题,提出了一种支持邻接关系查询的图结构可搜索加密方案（GSE-AQ）。该方案能够允许数据拥有者在密态图结构中查询两个点之间的邻接关系。本文给出了出方案的形式化定义和安全性定义,并结合字典结构和矩阵结构的思想设计了加密索引。对方案的构建进行了详细的描述,并在半诚实的威胁模型下证明了方案满足自适应选择查询攻击安全性。代价分析和仿真实验表明,该方案具有常数阶的计算代价和通信代价,能够满足实际应用的高效性需求。（3）针对图结构的交集/并集计算问题,提出了一种基于图结构的交集/并集计算隐私保护协议（GPI/U）。该协议允许两个参与者使用各自的图结构共同进行交集/并集计算,同时在计算过程中保护图结构的隐私。本文给出了协议的模型,详细描述了协议的计算和交互流程,同时分析了协议的计算代价和通信代价。安全性证明和仿真实验表明,该协议实现了交集/并集计算的隐私保护性,参与协议的双方都无法获得对方图结构的相关信息。（4）针对子图匹配问题,利用同态加密和不经意多项式求值提出了一种基于图结构的子图匹配隐私保护协议（GPSM）。该协议可以让两个参与者在隐私保护的前提下共同计算图结构之间的子图包含关系。在协议中,参与计算的双方不需要互相发送关于各自图结构的明文信息,实现了图结构的隐私保护性。本文给出了协议的正确性定义和安全性定义,并详细描述了协议的构建过程。在半诚实的威胁模型下证明了方案的安全性,并使用仿真实验对协议的正确性和性能进行了验证。