Feasible Operations on Proofs: The Logic of Proofs for Bounded Arithmetic

This paper presents a semantics for the logic of proofs in which all the operations on proofs are realized by feasibly computable functions. More precisely, we will show that the completeness of for the semantics of proofs of Peano Arithmetic extends to the semantics of proofs in Buss’ bounded arithmetic . In view of applications in epistemology of in particular and justification logics in general this result shows that explicit knowledge in the propositional framework can be made computationally feasible. This research supported by CUNY Community College Collaborative Incentive Research Grant 91639-0001 “Mathematical Foundations of Knowledge Representation”.     

格上的简短可链接环签名

可链接环签名可防止区块链中的双花攻击,基于格的签名可抵抗量子攻击,但已有格基可链接环签名的大小随环成员的增多而增大。针对该问题,提出了一种格上的简短可链接环签名方案。该方案用队列实现了向量数制的特殊转换,利用格上的累加器对环成员的公钥进行累加,使得签名大小不会随环成员的增多而增大;利用拒绝采样定理,构造出格上的知识证明签名,在防止签名私钥泄露的同时,提高了计算效率。在随机预言机模型下,证明了方案具有不可伪造性、匿名性、可链接性。性能分析与实验评估表明,所提方案节省了时间开销和存储开销,且随着环成员的增多签名大小固定不变。     

PTT纤维长毛绒产品数字化测配色方法探讨

应用datacolor SF600分光光度计及datamatch3．5测色配色软件,采用条件等色的计算机配色方式,以CIE标准施照态D65和CIE标准观察者为基础,探讨了用于长毛绒产品的PTT纤维数字化测配色工艺路线与技术方法,分析了在可见光范嗣内PTT纤维染色过程中反射率R％、K／S值的变化规律．以R、Y、B色料三原素为基础建立了用于PTT纤维配色数据库,得到能在CIE标准施照态D65和CIE标准观察者2个条件下染得与产品标样相同色泽的染色处方,其方法可对纤维类产品的染色测色配色提供借鉴．     

启发式方法生成命题逻辑可读证明

探讨了自动生成命题逻辑系统R的可读证明.采用试探法和自然推理法分别从前推和后推模拟人类思维求证,试探法根据推理规则将待证公式反向分解,自然推理法从假设出发根据推理规则生成新的公式.两种方法都实现了相干命题逻辑系统R的可读证明,并结合实现了混合证明.试探法和自然推理法是生成可读证明的有效方法,前推和后推两种思维方法也适用于其他逻辑系统的自动证明.     

The Warshall Algorithm and Dickson's Lemma: Two Examples of Realistic Program Extraction

By means of two well-known examples it is demonstrated that the method of extracting programs from proofs is manageable in practice and may yield efficient programs. The Warshall algorithm computing the transitive closure of a relation is extracted from a constructive proof that repetitions in a path can always be avoided. Second, we extract a program from a classical (i.e., nonconstructive) proof of a special case of Dickson's lemma, by transforming the classical proof into a constructive one. These techniques (as well as the examples) are implemented in the interactive theorem prover MINLOG developed at the University of Munich.     

A Bayes-true data generator for evaluation of supervised and unsupervised learning methods

Benchmarking pattern recognition, machine learning and data mining methods commonly relies on real-world data sets. However, there are some disadvantages in using real-world data. On one hand collecting real-world data can become difficult or impossible for various reasons, on the other hand real-world variables are hard to control, even in the problem domain; in the feature domain, where most statistical learning methods operate, exercising control is even more difficult and hence rarely attempted. This is at odds with the scientific experimentation guidelines mandating the use of as directly controllable and as directly observable variables as possible. Because of this, synthetic data possesses certain advantages over real-world data sets. In this paper we propose a method that produces synthetic data with guaranteed global and class-specific statistical properties. This method is based on overlapping class densities placed on the corners of a regular k-simplex. This generator can be used for algorithm testing and fair performance evaluation of statistical learning methods. Because of the strong properties of this generator researchers can reproduce each others experiments by knowing the parameters used, instead of transmitting large data sets.     

Optimality of size-width tradeoffs for resolution

This paper is concerned with the complexity of proofs and of searching for proofs in resolution. We show that the recently proposed algorithm of Ben-Sasson & Wigderson for searching for proofs in resolution cannot give better than weakly exponential performance. This is a consequence of our main result: we show the optimality of the general relationship called size-width tradeoffs in Ben-Sasson & Wigderson. Moreover we obtain the optimality of the size-width tradeoffs for the widely used restrictions of resolution: regular, Davis-Putnam, negative, positive. Received: January 31, 2000.     

基于确定/概率性文件拥有证明的机密数据安全去重方案

为解决云存储系统中机密数据去重面临的密文重复性检测与拥有性证明、针对数据机密性的攻击等难题,提出了基于Merkle散列树的MHT-Dedup方案和基于同态MAC的hMAC-Dedup方案。两者均通过对密文文件的拥有证明进行跨用户文件级重复性检测,并通过检查数据块明文的摘要进行本地数据块级重复性检测,避免了跨用户文件级客户端重复性检测中hash-as-a-proof方法存在的安全缺陷。MHT-Dedup方案通过数据块密文的标签生成的验证二叉树提供确定性的文件拥有证明,具有较低的计算和传输开销,而hMAC-Dedup方案则通过对抽样数据块密文和其标签进行同态MAC运算提供概率性的文件拥有证明,具有较低的额外存储开销。分析与比较表明,本方案在同时支持两级客户端机密数据安全去重和抵抗对数据块的暴力搜索攻击方面具有明显优势。