对一种多重密钥共享认证方案的分析和改进

在(t,n)密钥共享方案中,密钥管理者将一个秘密密钥分成n个子密钥,然后让n个成员中的每个成员保存一个子密钥.当需要恢复秘密密钥时,任意t个成员拿出他们持有的子密钥后,就可以按既定的公开算法恢复出所需密钥.而多重密钥共享使得密钥管理者可以安全且有效地共享多个密钥.Shi给出了一种高效率的多重密钥共享认证方案.在其方案中,不仅成员持有的子密钥能够重复使用,而且管理者分发的子密钥和成员提供的影子子密钥也都是可认证的.对Shi方案的安全性进行了分析:首先指出该方案的一个设计错误;然后给出两个攻击,以表明该方案中的子密钥和影子子密钥认证方法实际上都是不安全的.准确地说,利用所提出的攻击,不诚实的管理者可以将假的子密钥分发给成员;而不良成员可以很容易地伪造假的但能满足认证等式的影子子密钥,从而欺骗诚实成员,使得诚实成员误以为他们恢复出的密钥是正确的.另外,还给出了改进方法,以避免上述设计错误和攻击.     

有Mate-Pairs的个体单体型MSR问题的参数化算法

个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2^kn²m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k₁-1)k₂2^2h+(k₁+1)^2h+nk₂+mk₁)的新算法,其中,k₁为一个片断覆盖的最大SNP位点数(不大于n),k₂为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k₂).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值.     

资源独立工作流可满足性的最小增量模式回溯

工作流可满足性是业务安全规划的基本问题, 正在面临高资源配比(资源数n显著大于步骤数k)造成的性能挑战. 在资源独立约束下, 其最高效求解途径是模式空间上的增量回溯法IPB. 为克服结点真实性验证的性能瓶颈, 它增量计算模式k指派(二部)图及其(左完备)匹配, 分别需要O(kn)和O(k²)时间. 利用父子模式的原子差异增量计算完全指派图, 只需O(n)时间, 特别是其实际性能, 将随模式块规模增长迅速提高. 但该图的O(kn)规模导致了同样的增量匹配时间. 进而引入完备k核心匹配概念, 证明其存在性等价于左完备匹配, 且其增量计算时间为O(k²). 由此, 建立了时间复杂度更低的最小增量模式回溯法. 在含互斥和两种全局值势约束而授权比例约为1/4的扩展公开实例集上进行实验, 结果表明: 当n/k=10(及n/k=100), 而k变化时, 该方法较IPB有平均超过2(及5)倍、最低1.5(及2.9)倍的性能优势; 当k=18(及k=36), 而n/k=2~4096(及n/k=2~2048)时, 该方法有平均超过2.6(及3.6)倍优势; 而较2021年Minizinc挑战赛的冠军求解器Google OR-Tools CP-SAT, 该方法最低有超过3倍优势.     

求解大规模谱聚类的近似加权核k-means算法

谱聚类将聚类问题转化成图划分问题,是一种基于代数图论的聚类方法.在求解图划分目标函数时,一般利用Rayleigh熵的性质,通过计算Laplacian矩阵的特征向量将原始数据点映射到一个低维的特征空间中,再进行聚类.然而在谱聚类过程中,存储相似矩阵的空间复杂度是O(n²),对Laplacian矩阵特征分解的时间复杂度一般为O(n³),这样的复杂度在处理大规模数据时是无法接受的.理论证明,Normalized Cut图聚类与加权核k-means都等价于矩阵迹的最大化问题.因此,可以用加权核k-means算法来优化Normalized Cut的目标函数,这就避免了对Laplacian矩阵特征分解.不过,加权核k-means算法需要计算核矩阵,其空间复杂度依然是O(n²).为了应对这一挑战,提出近似加权核k-means算法,仅使用核矩阵的一部分来求解大数据的谱聚类问题.理论分析和实验对比表明,近似加权核k-means的聚类表现与加权核k-means算法是相似的,但是极大地减小了时间和空间复杂性.     

结合可信度的km-means算法

以K-means为代表的聚类算法被广泛地应用在许多领域, 但是K-means不能直接处理不完整数据集. k_m-means是一种处理不完整数据集的聚类算法, 通过调整局部距离计算方式, 减少不完整数据对聚类过程的影响. 然而k_m-means初始化阶段选取的聚类中心存在较大的不可靠性, 容易陷入局部最优解. 针对此问题, 本文引入可信度, 提出了结合可信度的k_m-means聚类算法, 通过可信度调整距离计算, 增大初始化过程中选取聚类中心的可靠性, 提高聚类算法的准确度. 最后, 通过UCI和UCR数据集验证算法的有效性.     

数据仓库系统中层次式Cube存储结构

区域查询是数据仓库上支持联机分析处理(on-line analytical processing,简称OLAP)的重要操作.近几年,人们提出了一些支持区域查询和数据更新的Cube存储结构.然而这些存储结构的空间复杂性和时间复杂性都很高,难以在实际中使用.为此,提出了一种层次式Cube存储结构HDC(hierarchical data cube)及其上的相关算法.HDC上区域查询的代价和数据更新代价均为O(log^dn),综合性能为O((logn)^2d)(使用C_qC_u模型)或O(K(logn)^d)(使用C_qn_q+C_un_u模型).理论分析与实验表明,HDC的区域查询代价、数据更新代价、空间代价以及综合性能都优于目前所有的Cube存储结构.     

LRCRaft: 支持节点数据快速恢复的共识协议

在支持纠删码的分布式存储系统中, 最常用的编码是RS (Reed-Solomon)码. 对于一个RS(k, m)编码条带, 常见的配置是一个节点仅存储条带中的一个分片, 这导致在节点出现故障的情况下, 对其存储分片的恢复需要跨多个节点读取分片并重新编码生成恢复分片, 容易造成系统网络拥塞. 在需要恢复大量数据的场合, 系统在恢复期间会处于较长时间的脆弱期, 容错能力和吞吐量下降、读写时延升高时有发生. LRCRaft是一个基于LRC (local reconstruction code)的改进Raft共识协议, 通过在Raft中引入LRC码、动态日志增补、状态机删减和分片版本一致性等机制, 降低了Raft的读写时延, 缩短了节点故障恢复时间. 实验结果表明, 相较于Raft, LRCRaft在不同恢复模式中恢复一个单节点故障数据时, 恢复用时有着49.25%–74.97%的减少.     

多值Łukasiewicz逻辑公式的范式表示和计数问题

将符号化计算树逻辑中的Shannon展开式做了推广,在n值Łukasiewicz逻辑系统Łn中,研究了由逻辑公式导出的n值McNaughton函数的展开式,给出了m元n值McNaughton函数的准析取范式和准合取范式.在此基础上,给出了m元n值McNaughton函数的计数问题,并在n值Łukasiewicz逻辑系统Łn中,给出了m元逻辑公式的构造方法及其逻辑等价类的计数问题.     

Ball基的推广

构造了一系列次数为n且带有参数k(2(≤)k(≤)「n/2」+1)的新的广义Ball基,作为Wang-Ball基(k=2)到Said-Ball基(k=「n/2」+1)的过渡,并给出新基的一些性质.接着,由新基定义出新的广义Ball曲线,给出曲线的递归求值、升阶和降阶逼近算法.最后,提出相应的三角基,并给出三角曲面的递归求值和升阶算法.     

分布式无中心授权的属性基可变门限环签名

基于属性的环签名具有表达能力强、使用灵活、便于隐匿签名者身份等优点,因此逐渐成为相关领域的研究热点.分析结果表明,现有方案大多无法同时具备无条件强匿名性和抗合谋攻击性,并且存在属性密钥托管、签名门限固定、验证效率低下等问题.针对上述不足,首先给出分布式属性基门限环签名方案的形式化定义和安全模型,然后提出一个分布式无中心授权的属性基可变门限环签名方案.该方案采用分布式密钥生成协议,分散了属性授权机构权限,解决了属性密钥托管问题;通过在属性密钥中嵌入用户身份标识,在签名中引入用户身份模糊因子的方式,使该方案同时具备无条件强匿名性和抗合谋攻击性.另外,提出了一种适用于该方案的批验证算法,能够将验证计算量由nO（·）降为O（·）+n（其中,n为待验证签名的数量）,有效提高了验证效率.在随机预言机模型和CDH困难问题假设下,该方案被证明在适应性选择消息和断言攻击下是存在性不可伪造的,并且能够抵抗由拥有互补属性集合的恶意成员发动合谋攻击.     

云存储中基于MHT的动态数据完整性验证与恢复方案

针对云服务器上存储数据完整性验证过程中的高通信开销和动态数据验证问题,提出一种基于Merkle哈希树(MHT)的动态数据完整性验证与恢复方案。首先,基于MHT构建了一种新型分层认证数据结构,将数据块的每个副本块组织成副本子树,以此大幅降低多副本更新验证的通信开销。然后,在数据验证中,融入了对服务器安全索引信息的认证,以此避免服务器攻击。最后,当发现数据损坏时,通过二分查找和Shamir秘密共享机制来恢复数据。实验结果表明,该方案在验证过程中能有效降低计算和通讯开销,并能够很好地支持数据的动态操作。     

Greyscale-images-oriented progressive secret sharing based on the linear congruence equation

Secret image sharing (SIS) can be applied to protect a secret image when the secret is transmitted in public channels. However, classic SIS schemes, e.g., visual secret sharing (VSS) and Shamir’s polynomial-based scheme, are not suitable for progressive encryption of greyscale images, because they will lead to many problems, such as “All-or-Nothing”, lossy recovery, complex computations and so on. Based on the linear congruence equation, three novel progressive secret sharing (PSS) schemes are proposed to overcome these problems: (k, k) threshold LCSS and (k, n) threshold LCPSS aim to achieve general threshold progressive secret sharing with simple computations. Furthermore, extended LCPSS (ELCPSS) is developed to generate meaningful shadow images, which enable simple management and misleading the enemy. Both theoretical proofs and experimental results are given to demonstrate the validity of the proposed scheme.     

Cross-group secret sharing scheme for secure usage of cloud storage over different providers and regions

With the spread of the Internet, more and more data are being stored in the cloud. Here the technique of secret sharing can be naturally applied in order to provide both security and availability of the stored data, hereby reducing the risks of data leakage and data loss. The privacy property of secret sharing ensures protection against unauthorized access, while protection against data loss may be attained by distributing shares to the servers located in different regions. However, there is still a problem: If we naively employ the secret sharing technique without regarding to whom the cloud servers belong, a dishonest provider can obtain the secret data by collecting enough shares from its servers. In this scenario, there is a need to distribute shares over cloud services operated by different providers. In this paper, we propose a simple secret sharing technique, a cross-group secret sharing (CGSS), which is suitable for storing the data on cloud storage distributed over different groups—that is, different providers and regions. By combining an \(\ell \)-out-of-m threshold secret sharing scheme with a k-out-of-n threshold secret sharing scheme using a symmetric-key encryption scheme, we construct the CGSS scheme that forces k shares to be collected from \(\ell \) groups. Compared with the previous works, our scheme attains the functionality with reasonable computation. We also formalize the problem of allocating shares over different providers and regions as an optimization problem and show the design principles, which one must follow, when applying our proposal in practical settings. An experiment on real IaaS systems shows effectiveness of our proposed scheme, CGSS.     

工业互联网中增强安全的云存储数据访问控制方案

在工业互联网应用中,由于异构节点计算和存储能力的差异,通常采用云方案提供数据存储和数据访问服务.云存储中的访问控制如扩展多权限的云存储数据访问控制方案(NEDAC-MACS),是保证云存储中数据的安全和数据隐私的基石.给出了一种攻击方法来证明NEDAC_MACS中,被撤销的用户仍然可以解密NEDAC-MACS中的新密文;并提出了一种增强NEDAC-MACS安全性的方案,该方案可以抵抗云服务器和用户之间的合谋攻击;最后通过形式密码分析和性能分析表明,该方案能够抵抗未授权用户之间以及云服务器与用户之间的合谋攻击,保证前向安全性、后向安全性和数据保密性.     

增强安全的云存储数据访问控制方案

云存储带来了许多优势,例如,可节省用户的硬件购买成本,并提供实时在线数据存储服务。越来越多的人选择将数据存储在云上。为了提高数据安全性和数据隐私性,Wu等人在Yang的方案的基础上,给出了一种扩展的多权限云存储数据访问控制方案(NEDAC-MACS)。本文给出一种攻击方法,以证明被撤消的用户仍然可以解密NEDAC-MACS中的新密文,并提出一种增强NEDAC-MACS安全性的方案,该方案可以抵抗云服务器与用户之间的串通攻击。加密分析表明,该方案能够抵抗串通攻击并且是可行的。     

A novel (n,t, n) secret image sharing scheme without a trusted third party

Secret image sharing is a technique to share a secret image among a set of n participants. A trusted third party embeds the secret image into the cover image to generate shadow images such that at least t or more shadow images can reconstruct the secret image. In this paper, we consider an extreme and real-world situation, in which there is no one who is trusted by anyone else. In the proposed scheme, the participants can act as a dealer and communicate with each other in a secret channel. Each participant can generate her/his own shadow image independently, according to the cover image and the secret image. Experimental results are provided to show that the shadow images have satisfactory quality. In addition, our scheme has a large embedding capacity, and the secret image can be reconstructed losslessly.     

A high quality and small shadow size visual secret sharing scheme based on hybrid strategy for grayscale images

Many secret sharing schemes for digital images have been developed in recent decades. Traditional schemes typically must deal with the problem of computational complexity, and other visual secret sharing schemes come with a higher transmission cost and storage cost; that is, each shadow size is m times as big as the original secret image. The new (2,n) secret sharing scheme for grayscale images proposed in this paper is based a combination of acceptable image quality using block truncation coding (BTC), high compression ratio discrete wavelet transform (DWT) and good subjective performance of the vector quantization (VQ) technique. Experimental results confirm that our proposed scheme not only generates a high quality reconstructed original image but also generates small, random-like grayscale shadows.     

一种基于LT码的数据云存储方案

拜占庭失效或恶意攻击会降低云服务供应商的云存储服务可靠性,为此,提出一种基于云计算的安全可靠数据存储方案。通过LT编码增加分布式云服务器的数据冗余度,在保证性能全局准最优的同时,提升数据用户在数据检索阶段的解码效率。利用支持公共数据完整性检查和准确数据修复,避免数据拥有者长期保持在线状态,并设计数据修复解决方案,使服务运行期间无需产生元数据也能进行数据修复。实验结果表明,与基于网络编码和基于RS码的云存储方案相比,该方案的通信成本只增加了15%,但数据检索效率却提高了约1倍。     

基于云存储的多用户可搜索加密方案

云存储服务允许用户外包数据并以此来降低资源开销。针对云服务器不被完全信任的现状,文章研究如何在云环境下对数据进行安全存储和加密搜索。多用户的可搜索加密方案为用户提供了一种保密机制,使用户可以在不受信任的云存储环境下安全地共享信息。在现有的可搜索加密方案的基础上,文章提出了一种安全有效的带关键字搜索的加密方案,以及更加灵活的密钥管理机制,降低了云端数据处理的开销。     

一种采用签名与哈希技术的云存储去重方案

针对单一云存储服务提供商可能对数据进行垄断控制和现有云存储去重系统采用的收敛加密算法容易遭受暴力攻击等问题,提出了一种采用签名与哈希技术的云存储去重方案,通过在数据去重过程中采用双层校验机制对数据完整性进行审计,能够校验文件的完整性和精确地定位到损坏的数据块;同时构造Merkle哈希树来生成校验值,计算出去重标签,保证重复数据能够被检测;使用Mapbox和Lockbox结合的机制加密数据信息,保证非授权用户无法对文件进行访问。安全性分析及仿真实验结果表明,方案有效抵制暴力攻击,并能够降低去重标签的计算开销和减少存储空间。