云存储中的数据完整性证明研究及进展

随着云存储模式的出现,越来越多的用户选择将应用和数据移植到云中,但他们在本地可能并没有保存任何数据副本,无法确保存储在云中的数据是完整的.如何确保云存储环境下用户数据的完整性,成为近来学术界研究的一个热点.数据完整性证明(Provable Data Integrity,PDI)被认为是解决这一问题的重要手段,该文对此进行了综述.首先,给出了数据完整性证明机制的协议框架,分析了云存储环境下数据完整性证明所具备的特征;其次,对各种数据完整性证明机制加以分类,在此分类基础上,介绍了各种典型的数据完整性验证机制并进行了对比;最后,指出了云存储中数据完整性验证面临的挑战及发展趋势.     

A ground-complete axiomatization of stateless bisimilarity over Linda

This paper offers a finite, ground-complete axiomatization of stateless bisimilarity over the tuple-space-based coordination language Linda. As stepping stones towards that result, axiomatizations of stateless bisimilarity over the sequential fragment of Linda without the nask primitive, and over the full sequential sub-language are given. It is also shown that stateless bisimilarity coincides with standard bisimilarity over the sequential fragment of Linda without the nask primitive.     

Round-optimal zero-knowledge proofs of knowledge for NP

It is well known that all the known black-box zero-knowledge proofs of knowledge for NP are nonconstant-round.Whether there exit constant-round black-box zero-knowledge proofs of knowledge for all NP languages under certain standard assumptions is an open problem.This paper focuses on the problem and gives a positive answer by presenting two constructions of constant-round(black-box) zero-knowledge proofs of knowledge for the HC(hamiltonian cycle) problem.By the recent result of Katz,our second construction which relies on the existence of claw-free functions has optimal round complexity(5-round) assuming the polynomial hierarchy does not collapse.     

Unification under associativity and idempotence is of type nullary

It is shown, that there exist a unification problem〈s=t〉 _AI , for which the set of solutions under associativity and idempotence is not empty. But , the complete and minimal subset of this set of solutions does not exist, i.e.A+I is of type nullary. This is the first known standard first order theory with this unpleasant feature. This work is supported by the Deutsche Forschungsgemeinschaft, National Research Schema ‘Artificial Intelligence and Knowledge Based Systems’, SFB 314.     

Termination Proofs for Ground Rewrite Systems – Interpretations and Derivational Complexity

It is shown that finite terminating ground term rewrite systems have linearly bounded derivational complexity. This is proven via some suitable interpretation into the natural numbers. Terminating ground systems are not necessarily totally terminating, i.e., a strictly monotone interpretation into a well-order might not exist. We show, however, that those systems are almostω-terminating in the sense that such an interpretation into the sum of a finite partial order and the natural numbers always effectively exists. Finally, we show that for ground systems total termination is equivalent to ω-termination, and that this is a decidable property. Received: December 8, 1999     

Recursive Program Optimization through Inductive Synthesis Proof Transformation

The research described in this paper involved developing transformation techniques that increase the efficiency of the original program, the source, by transforming its synthesis proof into one, the target, which yields a computationally more efficient algorithm. We describe a working proof transformation system that, by exploiting the duality between mathematical induction and recursion, employs the novel strategy of optimizing recursive programs by transforming inductive proofs. We compare and contrast this approach with the more traditional approaches to program transformation and highlight the benefits of proof transformation with regards to search, correctness, automatability, and generality.     

Recursive 4SID algorithms using gradient type subspace tracking

Sometimes we obtain some prior information about a system to be identified, e.g., the order, model structure etc. In this paper, we consider the case where the order of a MIMO system to be identified is a priori known. Recursive subspace state-space system identification algorithms presented here are based on the gradient type subspace tracking method used in the array signal processing. The algorithms enable us to estimate directly the subspace spanned by the column vectors of the extended observability matrix of the system to be identified without performing the singular value decomposition. Also, a new convergence proof of the gradient type subspace tracking is given in this paper. Under the condition of a step size between 0 and 1, we prove the convergence property of the recursive equation of the gradient type subspace tracking. A numerical example illustrates that our algorithm is more robust with respect to the choice of the initial values than the corresponding PAST one.     

A note on equations for commutative regular languages

In this note we prove that the equations satisfied by one-letter regular languages are exactly those satisfied by commutative regular languages. This answers a problem raised by Arto Salomaa.     

Anti-patterns for rule-based languages

Negation is intrinsic to human thinking and most of the time when searching for something, we base our patterns on both positive and negative conditions. This should be naturally reflected in software that provide pattern-based searches. We would like for example to specify that we search for white cars that are not station wagons, or that we search for a list of objects that does not contain two identical elements.     

Complexity of Positivstellensatz proofs for the knapsack

A lower bound is established on degrees of Positivstellensatz calculus refutations (over a real field) introduced in (Grigoriev & Vorobjov 2001; Grigoriev 2001) for the knapsack problem. The bound depends on the values of coefficients of an instance of the knapsack problem: for certain values the lower bound is linear and for certain values the upper bound is constant, while in the polynomial calculus the degree is always linear (regardless of the values of coefficients) (Impagliazzo et al. 1999). This shows that the Positivstellensatz calculus can be strictly stronger than the polynomial calculus from the point of view of the complexity of the proofs. Received: February 9, 2000.