Identity-based encryption with wildcards in the standard model

In this article, based on Chatterjee-Sarkar＇ hierarchical identity-based encryption （HIBE）, a novel identity-based encryption with wildcards （WIBE） scheme is proposed and is proven secure in the standard model （without random oracle）. The proposed scheme is proven to be secure assuming that the decisional Bilinear Diffie-Hellman （DBDH） problem is hard. Compared with the Wa-WIBE scheme that is secure in the standard model, our scheme has shorter common parameters and ciphertext length.

Pattern Matching with Flexible Wildcards

Pattern matching with wildcards（PMW） has great theoretical and practical significance in bioinformatics,information retrieval, and pattern mining. Due to the uncertainty of wildcards, not only is the number of all matches exponential with respect to the maximal gap flexibility and the pattern length, but the matching positions in PMW are also hard to choose. The objective to count the maximal number of matches one by one is computationally infeasible. Therefore,rather than solving the generic PMW problem, many research efforts have further defined new problems within PMW according to different application backgrounds. To break through the limitations of either fixing the number or allowing an unbounded number of wildcards, pattern matching with flexible wildcards（PMFW） allows the users to control the ranges of wildcards. In this paper, we provide a survey on the state-of-the-art algorithms for PMFW, with detailed analyses and comparisons, and discuss challenges and opportunities in PMFW research and applications.

Multi-Pattern Matching Algorithm with Wildcards Based on Bit-Parallelism

Multi-pattern matching with wildcards is a problem of finding the occurrence of all patterns in a pattern set {p^1,… ,p^k} in a given text t. If the percentage of wildcards in pattern set is not high, this problem can be solved using finite automata. We introduce a multi-pattern matching algorithm with a fixed number of wildcards to overcome the high percentage of the occurrence of wildcards in patterns. In our proposed method, patterns are matched as bit patterns using a sliding window approach. The window is a bit window that slides along the given text, matching against stored bit patterns. Matching process is executed using bit wise operations. The experimental results demonstrate that the percentage of wildcard occurrence does not affect the proposed algorithm＇s performance and the proposed algorithm is more efficient than the algorithms based on the fast Fourier transform. The proposed algorithm is simple to implement and runs efficiently in O（n ＋ d（n/σ ）（m/w）） time, where n is text length, d is symbol distribution over k patterns, m is pattern length, and σ is alphabet size.

新型油膜轴承端罩箱盖试制试验研究

端罩箱盖使油膜轴承与外界隔离,形成相对封闭的润滑体系,避免杂质进入轴承内部,保护轴承和润滑油的清洁度,延长了轴承的使用寿命。现有钢端罩箱盖存在因自重下沉,变形,导致30%端罩漏油,密封失效,造成润滑油严重经济损失。端罩箱盖为单配加工,用户更换成本大。为此,本文试制一种新型油膜轴承端罩,采用玻璃钢代替普通碳钢,满足设计要求;采用通配工艺方法,满足端罩箱盖互换性需求;建立端罩有限元模型,校核端罩刚度;通过铸造、加工、安装透视窗、安装铜套、通配、把合等全部工序,完成玻璃钢端罩箱盖试制试验。结果表明:采用玻璃钢端罩,减小自重60%,降低生产成本20%,解决了端罩下沉、变形等故障,实现零件轻量化设计。采用通配工艺,提高端罩箱盖成品批量合格率,降低用户维修成本,实现产品尺寸标准化,满足工艺要求和现场装配互换性需求。

带通配符和One-Off条件的序列模式挖掘

很多应用领域产生大量的序列数据.如何从这些序列数据中挖掘具有重要价值的模式,已成为序列模式挖掘研究的主要任务.研究这样一个问题:给定序列S、支持度阈值和间隔约束,从序列S中挖掘所有出现次数不小于给定支持度阈值的频繁序列模式,并且要求模式中任意两个相邻元素在序列中的出现位置满足用户定义的间隔约束.设计了一种有效的带有通配符的模式挖掘算法One-Off Mining,模式在序列中的出现满足One-Off条件,即模式的任意两次出现都不共享序列中同一位置的字符.在生物DNA序列上的实验结果表明,One-Off Mining比相关的序列模式挖掘算法具有更好的时间性能和完备性.

一种求解MPMGOOC问题的启发式算法

具有间隙约束和一次性条件的最大模式匹配(Maximum Pattern Matching with Gaps and One-Off Condition,MPMGOOC)是一种具有通配符长度约束的模式匹配问题,其任务是寻找彼此互不相关的最多出现.文中基于一种新的非线性数据结构——网树,提出了一种解决MPMGOOC问题的启发式算法.与树结构不同之处在于,除根结点外,网树中任何结点可以多于1个双亲结点.文中给出了网树的定义及其相关的概念和性质.基于这些概念和性质,提出了一种选择较优出现(Selecting Better Occurrence,SBO)的启发式算法.该算法在搜索一个出现的循环中,采用了贪婪搜索双亲策略(Strategy of Greedy-Search Parent,SGSP)和最右双亲策略(Strategy of RightMostParent,SRMP)寻找相同叶子的两个出现并选择其中较好的出现作为SBO算法的结果.SGSP策略的核心思想是每一步都寻找当前结点的一个近似最优双亲(Approximately Optimimal Parent,AOP);SRMP策略的核心思想是每一步都寻找当前结点的最右双亲结点.实验结果表明,在多数情况下SBO算法可以获得更好的解且解的质量较其它算法有显著的提高.文中不但提供了一个解决MPMGOOC问题的启发式算法,更重要的是对于求解其它复杂问题具有一定的参考价值.

提高文献查全率和查准率的有效途径——逻辑运算符、位置算符和通配符的灵活运用

逻辑运算符、位置算符和通配符是文献检索中经常使用的检索手段,本文首先概述了它们的使用原理,然后详细介绍了在几个常用数据库中的使用技巧,最后通过具体实例解析了在数据库中的应用,以便为广大的科技工作者和情报检索人员提供有益的参考。

Estimating ancestral distributions of lineages with uncertain sister groups:a statistical approach to Dispersal-Vicariance Analysis and a case using Aesculus L.(Sapindaceae) including fossils

We propose a simple statistical approach for using Dispersal-Vicariance Analysis （DIVA） software to infer biogeographic histories without fully bifurcating trees. In this approach, ancestral ranges are first optimized for a sample of Bayesian trees. The probability P of an ancestral range r at a node is then calculated as P（rY） = ∑t^n=1 F（rY）t Pt where Y is a node, and F（rY） is the frequency of range r among all the optimal solutions resulting from DIVA optimization at node Y, t is one of n topologies optimized, and Pt is the probability of topology t. Node Y is a hypothesized ancestor shared by a specific crown lineage and the sister of that lineage ＂x＂, where x may vary due to phylogenetic uncertainty （polytomies and nodes with posterior probability 〈 100%）. Using this method, the ancestral distribution at Y can be estimated to provide inference of the geographic origins of the specific crown group of interest. This approach takes into account phylogenetic uncertainty as well as uncertainty from DIVA optimization. It is an extension of the previously described method called Bayes-DIVA, which pairs Bayesian phylogenetic analysis with biogeographic analysis using DIVA. Further, we show that the probability P of an ancestral range at Y calculated using this method does not equate to pp＊F（rY） on the Bayesian consensus tree when both variables are 〈 100%, where pp is the posterior probability and F（rY） is the frequency of range r for the node containing the specific crown group. We tested our DIVA-Bayes approach using Aesculus L., which has major lineages unresolved as a polytomy. We inferred the most probable geographic origins of the five traditional sections of Aesculus and ofAesculus californica Nutt. and examined range subdivisions at parental nodes of these lineages. Additionally, we used the DIVA-Bayes data from Aesculus to quantify the effects on biogeographic inference of including two wildcard fossil taxa in phylogenetic analysis. Our analysis resolved the geographic ranges of the parental nodes of the lineages of Aesculus with moderate to high probabilities. The probabilities were greater than those estimated using the simple calculation ofpp＊F（rY） at a statistically significant level for two of the six lineages. We also found that adding fossil wildcard taxa in phylogenetic analysis generally increased P for ancestral ranges including the fossil＇s distribution area. The AP was more dramatic for ranges that include the area of a wildcard fossil with a distribution area underrepresented among extant taxa. This indicates the importance of including fossils in biogeographic analysis. Exmination of range subdivision at the parental nodes revealed potential range evolution （extinction and dispersal events） along the stems ofA. californica and sect. Parryana.

标准模型下可证安全的通配符基于身份加密方案

针对通配符基于身份加密方案中安全归约不紧密以及运算量大的缺陷,利用双线性对和分级基于身份加密的思想提出标准模型下可证安全的通配符基于身份加密方案.新方案取得紧密的安全归约,同时加密算法不需要对运算,解密算法仅仅需要2个对运算.安全性分析表明,基于改进判定双线性Diffie-Hellman指数假设下。

一种带有通配符和长度约束模式匹配问题的动态剪枝算法

近年来,随着生物信息学、信息检索等领域的发展,串模式匹配问题被不断扩展。其中,具有代表性的是在模式中引入可变长度的通配符而形成带有通配符的模式匹配(PMWL)。该问题定义的灵活性给用户提供了方便,却也造成了求解上的困难。因此,如何在多项式时间内得到更好的匹配解成为研究的焦点。提出了一种启发式的小兵算法。小兵算法通过将PMWL问题转化为路径搜索问题,并借鉴动态剪枝思想,在算法搜索的过程中动态地将不可能的匹配位置剪枝,从而提高解的质量。实验在真实DNA序列上进行,并人工生成了196个模式。结果表明,相比于目前最有效的SAIL算法,小兵算法在绝大多数的尾部有重复字符的模式中可以获得更好的匹配解。

高性能文本索引系统的设计与实现

针对传统文本索引技术空间消耗大、分词不准确等问题,设计并实现了高性能文本索引系统。该系统采用压缩的全文自索引算法,节省了空间开销,避免了自然语言分词方法的影响,配合通配符搜索算法扩展了模糊搜索的功能,在众核CPU高性能处理器上可实现多线程并行处理,提高了处理速度,整个系统的实现是基于Web方式的,可以跨平台运行。实验结果表明,该系统将文本索引的空间消耗降为原文本的50%左右,具有较高的实用价值。

密钥弹性泄漏安全的通配模板层次委托加密机制

传统的密码方案假定密钥对可能的攻击者来说是完全隐藏的(只有算法是公开的),敌手无法获得有关密钥的任何信息.但在实际系统中,攻击者可在噪声信道或由侧信道攻击获得有关密钥的部分信息.密钥弹性泄漏安全的加密方案通过改进密码算法达到在密钥存在可能部分泄漏情况下的语义安全性.设计了一个抗密钥弹性泄漏的可委托层次模板加密方案.在该方案中,用户身份关联到含有通配符的身份模板,并可以实现再次密钥委托.该方案是抗泄漏的层次身份加密方案(hierarchical identity-based encryption,简称HIBE)和隐藏向量加密方案(hidden vector encryption,简称HVE)的一般扩展,可有效地抵抗密钥弹性泄漏,并达到自适应语义安全性.同时给出该方案的安全性证明和系统抗泄漏性能,分析显示,该方案具有较好的密钥泄漏容忍性.

SQL数据库管理系统中的模糊查询技术

介绍了数据库管理系统SQL server 2000中的模糊查询方法及基于模糊理论的模糊查询的实现,并借助语言工具Visual Basic做出了一个良好的模糊信息转换工具,将自然语言中的模糊信息通过计算生成精确的SQL语句,实现从模糊查询转换为精确查询.

满足非重叠条件的带有通配符序列模式挖掘

很多应用领域产生大量的序列数据,例如:基因序列,超市购买记录,股市交易数据,文本序列等.如何从这些序列数据中挖掘具有重要价值的模式已成为序列模式挖掘研究的主要任务.本文研究带有通配符的序列模式挖掘问题,给定支持度阈值和间隔约束,从序列数据库中挖掘所有出现次数不小于给定支持度阈值的频繁序列模式,模式中任意两个相邻元素在序列中的出现位置满足用户定义的间隔约束.本文设计一种基于层次图的带有通配符序列模式挖掘算法PMLG,利用层次图结构在多项式时间和空间复杂度内构建和存储模式在序列中满足间隔约束的所有出现位置,采用深度优先搜索策略对图进行遍历,计算模式的支持度,其中模式的任意两次出现的相同位置都不共享序列中同一位置的字符,即满足非重叠出现.在生物DNA序列上的实验表明,PMLG比相关的序列模式挖掘算法具有更好的时间性能和完备性.

基于LSPI索引的不确定XML查询处理算法

针对目前已有XML通配符查询处理需将文档中所有元素标签读入内存中,匹配效率低的问题,提出一种新的基于LSPI(leaf sibling of path information)索引的不确定XML包含通配符和复杂谓词的查询处理算法Prob-BooleanStarTwig。算法基于有效过滤策略自底向上进行模式匹配,将通配符转换成A-D关系和层次信息约束,解决传统通配符匹配问题,避免多次扫描查询模式,提高查询速度。理论分析和实验结果表明,算法的查询效率明显优于已有的算法。

带弱通配符的模式匹配及其在时序分析中的应用

针对模式匹配的准确性和灵活性问题,提出了一种基于弱通配符的匹配算法,以快速定位重要的时间点,辅助用户决策。首先通过数据预处理得到编码字符串序列,然后定义具有特殊语义的弱通配符及区间长度,最后设计一种高效的模式匹配算法。在时序分析中,模式反映了数据的变化趋势,预示着事件的发生。传统的精确匹配受噪声的影响比较大,匹配的灵活性低。通过添加弱通配符可以兼顾匹配过程的灵活性和准确性。油田产量与股票交易数据实验表明,所提方法较精确匹配而言,能够更有效地找到符合用户要求的模式。

中国生物医学文献服务系统(SinoMed)截词检索功能分析

通过大量的文献检索试验,探讨了网络版Sino Med平台的中国生物医学文献数据库在截词检索方面存在的主要问题,包括省略通配符检索存在的问题及任意通配符"%"和单字通配符"?"用于截词检索的主要问题,并就检索效率及数据库功能的进一步完善提出了建议。

图算法求解带有限长空位和one-off约束的模式匹配问题

讨论带有限长空位和one-off约束条件的模式匹配问题,其中限长空位改变单个匹配解结构,one-off条件约束匹配解之间的关系,从而形成规模较大且稀疏的解空间.借鉴约束可满足性问题框架,将PMGO问题转化为图结构下的路径搜索问题,并证明转化的等价性.然后提出图结构下的剪枝和匹配算法(GPM),根据one-off约束得到节点之间的约束关系,再迭代交互地进行剪枝与搜索.实验中使用匹配解丢失率度量已有启发式算法和GPM的完备性,证明GPM可与已有启发式算法形成互补,有效降低匹配解丢失率.

基于遗传算法的系统调用序列审计研究

在分析已有通过系统序列调用分析入侵行为的基础上,提出了一种基于遗传算法的系统调用序列审计算法。该算法首先从系统运行的进程中截获并生成系统调用序列,并通过遗传算法对其进行演化,来达到对未知攻击调用序列审计的目的。算法的规则中使用通配符可以大大减少审计规则的数量,从而提高审计系统的运行效率,最后分析了通配符个数以及信任度对规则数量和准确率的影响。

字符分布特征对带有通配符串匹配问题的影响

近年来，字符串匹配问题被不断扩展。其中，具有代表性的是在模式中引入可变长度的通配符，称之为PMWL问题。针对此问题，已有工作分析了在不同的模式特征下，匹配数卵随文本长度增加呈指数级增长。同时考虑文本分布特征和模式特征，建立了期望模型E（Ω）=nDπ（P），其中n为文本长度，D为模式中各通配符跨度的乘积，π（P）为基于字符分布的模式出现概率。实验部分，在人工随机数据和DNA真实数据上验证了E（Ω）的准确性，得到预测误差率分别为1．8％-3．2％和4．7％～7．8％；在不同字符分布中，分析了模式模长和通配符跨度对匹配数n的影响。E（Ω）模型揭示了n的增长趋势不一定呈指数级，而取决于π（P）和D的共同影响，且E（Ω）模型能够在线性时间内得到近似完备解。