Secure group key establishment revisited

We examine the popular proof models for group key establishment of Bresson et al. (LNCS 2248: 290–309, 2001; Proceedings of the 8th ACM conference on computer and communications security (CCS-8), 2001) and point out missing security properties addressing malicious protocol participants. We show that established group key establishment schemes from CRYPTO 2003 and ASIACRYPT 2004 do not fully meet these new requirements. Next to giving a formal definition of these extended security properties, we prove a variant of the explored proposal from ASIACRYPT 2004 secure in this stricter sense. Our proof builds on the Computational Diffie Hellman (CDH) assumption and the random oracle model.     

Solving Failing Queries through Cooperation and Collaboration

Sometime Query Answering Systems (QAS) for a Distributed Autonomous Information System (DAIS) may fail by returning the empty set of objects as an answer for a query q. Systems in DAIS can be incomplete, have hierarchical attributes, and the semantics of attributes and their values may differ between sites. Also, if there are no objects in S matching q, the query may fail when submitted to S. Alternatively, QAS for S may try to relax the query q as it was proposed in T. Gaasterland (IEEE Expert, 12(5), 1997, 48–59), P. Godfrey (International Journal of Cooperative Information Systems, 6(2), 1997, 95–149) and W. Chu et al. (Journal of Intelligent Information Systems, 6(2/3), 1996, 223–259). It means that q can be replaced by a new more general query. Clearly, the goal is to find possibly the smallest generalization of q which will not fail in S. Smaller generalizations guarantee higher confidence in objects returned by QAS. Such QAS is called cooperative (only one site is involved). Queries may also fail in S when some of the attributes listed in q are outside the domain of S. To resolve this type of queries, assuming that S is a part of DAIS, we may extract definitions of such attributes from information systems residing at some of the remote sites for S and next use them to approximate q in S. In order to do that successfully, we assume that all involved systems have to agree on the ontology of some of their common attributes Z.W. Raś and A. Dardzińska (Information Systems International Journal, 29(1), 2004, 47–58; Proceedings of FQAS 2004 Conference, LNCS/LNAI No. 3055, 2004, pp. 125–136); Z.W. Raś and S. Joshi, Fundamenta Informaticae Journal, 30(3/4), 1997, 313–324. QAS based on the above strategy is called collaborative (minimum two sites are involved). Similarly, a query may fail in S when the granularity of an attribute used in q is finer than the granularity of the same attribute in S. This paper shows how to use collaboration and cooperation approach to solve failing queries in DAIS assuming that attributes are hierarchical. Some aspects of a collaboration strategy dealing with failing query problem for non-hierarchical attributes have been presented in Z.W. Raś and A. Dardzińska (Information Systems International Journal, 29(1), 2004, 47–58; Proceedings of FQAS 2004 Conference, LNCS/LNAI No. 3055, 2004, pp. 125–136).     

A typed encoding of boxed into safe ambients

We present: (i) an encoding of Boxed Ambients into a variant of Safe Ambients; and (ii) a new type system for multi-level security of Safe Ambients in the style of Cardelli et al. (Information and Computation 177(2), 160–194 (2002)) and Dezani-Ciancaglini and Salvo (Security types for mobile safe ambients. In: Proceedings of ASIAN '00, LNCS 1961, pp. 215–236. Springer Verlag (2000)). Then, we show that the types, when applied to the encoded BA proceses, permits to accurately verify Mandatory Access Control policies of the source processes.     

Contention-free MAC protocols for asynchronous wireless sensor networks

A MAC protocol specifies how nodes in a sensor network access a shared communication channel. Desired properties of a MAC protocol are: it should be contention-free (avoid collisions); it should be distributed and self-stabilize to topological changes in the network; topological changes should be contained, namely, affect only the nodes in the vicinity of the change; it should not assume that nodes have a global time reference, that is, nodes may not be time-synchronized. We give a set of TDMA-based MAC protocols for asynchronous wireless sensor networks satisfying all of these requirements. The communication complexity, number and size of messages, for the protocols to stabilize is small, poly-logarithmic in the network size. A preliminary version of the paper appears in the Proceedings of the 18th Annual Conference on Distributed Computing (DISC 2004), LNCS 3704, pp 245–259, Trippenhuis, Amsterdam, The Netherlands, October 2004.     

Model Checking Weighted Integer Reset Timed Automata

Weighted timed automata (WTA), introduced in Alur et al. (Proceedings of HSCC’01, LNCS, vol. 2034, pp. 49–62, Springer, Berlin, 2001), Behrmann et al. (Proceedings of HSCC’01, LNCS, vol. 2034, pp. 147–161, Springer, Berlin, 2001) are an extension of Alur and Dill (Theor. Comput. Sci. 126(2):183–235, 1994) timed automata, a widely accepted formalism for the modelling and verification of real time systems. Weighted timed automata extend timed automata by allowing costs on the locations and edges. There has been a lot of interest Bouyer et al. (Inf. Process. Lett. 98(5):188–194, 2006), Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, 2008), Brihaye et al. (Proceedings of FORMATS/FTRTFT’04, LNCS, vol. 3253, pp. 277–292, Springer, Berlin, 2004), Brihaye et al. (Inf. Comput. 204(3):408–433, 2006) in studying the model checking problem of weighted timed automata. The properties of interest are written using logic weighted CTL (WCTL), an extension of CTL with costs. It has been shown Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, 2008) that the problem of model checking WTAs with a single clock using WCTL with no external cost variables is decidable, while 3 clocks render the problem undecidable Bouyer et al. (Inf. Process. Lett. 98(5):188–194, 2006). The question of 2 clocks is open. In this paper, we introduce a subclass of weighted timed automata called weighted integer reset timed automata (WIRTA) and study the model checking problem. We give a clock reduction technique for WIRTA. Given a WIRTA A\mathcal{A} with n≥1 clocks, we show that a single clock WIRTA A￠\mathcal{A}' preserving the paths and costs of A\mathcal{A} can be obtained. This gives us the decidability of model checking WIRTA with n≥1 clocks and m≥1 costs using WCTL with no external cost variables. We then show that for a restricted version of WCTL with external cost variables, the model checking problem is undecidable for WIRTA with 3 stopwatch costs and 1 clock. Finally, we show that model checking WTA with 2 clocks and 1 stopwatch cost against WCTL with no external cost variables is undecidable, thereby answering a question that has remained long open.     

A general scheme for formalizing defaults using the predicateab(I, S)

In common sense reasoning two typical types of defaults are encountered.One is of the form “all birds can fly excepts b1,b2,…,and bm(m≥1)”,and the other “All birds can fly,but there exist exceptions”.The type of defaults is readily formalized but the other,as some researchers have noticad,is difficult to deal with.This paper establishes a general scheme for formalizing defaults of the two types,the key to which is the introduction of a two-argument predicate ab(I,S) to represent exceptional objects.     

Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas

DPLL (for Davis, Putnam, Logemann, and Loveland) algorithms form the largest family of contemporary algorithms for SAT (the propositional satisfiability problem) and are widely used in applications. The recursion trees of DPLL algorithm executions on unsatisfiable formulas are equivalent to treelike resolution proofs. Therefore, lower bounds for treelike resolution (known since the 1960s) apply to them. However, these lower bounds say nothing about the behavior of such algorithms on satisfiable formulas. Proving exponential lower bounds for them in the most general setting is impossible without proving P ≠ NP; therefore, to prove lower bounds, one has to restrict the power of branching heuristics. In this paper, we give exponential lower bounds for two families of DPLL algorithms: generalized myopic algorithms, which read up to n ^1−ε of clauses at each step and see the remaining part of the formula without negations, and drunk algorithms, which choose a variable using any complicated rule and then pick its value at random. ^★Extended abstract of this paper appeared in Proceedings of ICALP 2004, LNCS 3142, Springer, 2004, pp. 84–96. ^†Supported by CCR grant CCR-0324906. ^‡Supported in part by Russian Science Support Foundation, RAS program of fundamental research “Research in principal areas of contemporary mathematics,” and INTAS grant 04-77-7173. ^§Supported in part by INTAS grant 04-77-7173.     

Simplified security notions of direct anonymous attestation and a concrete scheme from pairings

Direct Anonymous Attestation (DAA) is a cryptographic mechanism that enables remote authentication of a user while preserving privacy under the user’s control. The DAA scheme developed by Brickell, Camenisch, and Chen has been adopted by the Trust Computing Group for remote anonymous attestation of Trusted Platform Module, which is a small hardware device with limited storage space and communication capability. In this paper, we provide two contributions to DAA. We first introduce simplified security notions of DAA including the formal definitions of user controlled anonymity and traceability. We then propose a new DAA scheme from elliptic curve cryptography and bilinear maps. The lengths of private keys and signatures in our scheme are much shorter than the lengths in the original DAA scheme, with a similar level of security and computational complexity. Our scheme builds upon the Camenisch–Lysyanskaya signature scheme and is efficient and provably secure in the random oracle model under the LRSW (stands for Lysyanskaya, Rivest, Sahai and Wolf) assumption and the decisional Bilinear Diffie–Hellman assumption.     

Non-Linear Filtering and Limiting in High Order Methods for Ideal and Non-Ideal MHD

The adaptive nonlinear filtering and limiting in spatially high order schemes (Yee et al. J. Comput. Phys. 150, 199–238, (1999), Sjögreen and Yee, J. Scient. Comput. 20, 211–255, (2004)) for the compressible Euler and Navier–Stokes equations have been recently extended to the ideal and non-ideal magnetohydrodynamics (MHD) equations, (Sjögreen and Yee, (2003), Proceedings of the 16th AIAA/CFD conference, June 23–26, Orlando F1; Yee and Sjögreen (2003), Proceedings of the International Conference on High Performance Scientific Computing, March, 10–14, Honai, Vietnam; Yee and Sjögreen (2003), RIACS Technical Report TR03. 10, July, NASA Ames Research Center; Yee and Sjögreen (2004), Proceedings of the ICCF03, July 12–16, Toronto, Canada). The numerical dissipation control in these adaptive filter schemes consists of automatic detection of different flow features as distinct sensors to signal the appropriate type and amount of numerical dissipation/filter where needed and leave the rest of the region free from numerical dissipation contamination. The numerical dissipation considered consists of high order linear dissipation for the suppression of high frequency oscillation and the nonlinear dissipative portion of high-resolution shock-capturing methods for discontinuity capturing. The applicable nonlinear dissipative portion of high-resolution shock-capturing methods is very general. The objective of this paper is to investigate the performance of three commonly used types of discontinuity capturing nonlinear numerical dissipation for both the ideal and non-ideal MHD.     

Solutions of Multi-dimensional Hyperbolic Systems of Conservation Laws by Square Entropy Condition Satisfying Discontinuous Galerkin Method

In this paper, we study formally high-order accurate discontinuous Galerkin methods on general arbitrary grid for multi-dimensional hyperbolic systems of conservation laws [Cockburn, B., and Shu, C.-W. (1989, Math. Comput. 52, 411–435, 1998, J. Comput. Phys. 141, 199–224); Cockburn et al. (1989, J. Comput. Phys. 84, 90–113; 1990, Math. Comput. 54, 545–581). We extend the notion of E-flux [Osher (1985) SIAM J. Numer. Anal. 22, 947–961] from scalar to system, and found that after flux splitting upwind flux [Cockburn et al. (1989) J. Comput. Phys. 84, 90–113] is a Riemann solver free E-flux for systems. Therefore, we are able to show that the discontinuous Galerkin methods satisfy a cell entropy inequality for square entropy (in semidiscrete sense) if the multi-dimensional systems are symmetric. Similar result [Jiang and Shu (1994) Math. Comput. 62, 531–538] was obtained for scalar equations in multi-dimensions. We also developed a second-order finite difference version of the discontinuous Galerkin methods. Numerical experiments have been obtained with excellent results.      

Capabilities and Limits of Compact Error Resilience Methods for Algorithmic Self-Assembly

Winfree’s pioneering work led the foundations in the area of error-reduction in algorithmic self-assembly (Winfree and Bekbolatov in DNA Based Computers 9, LNCS, vol. 2943, pp. 126–144, [2004]), but the construction resulted in increase of the size of assembly. Reif et al. (Nanotechnol. Sci. Comput. 79–103, [2006]) contributed further in this area with compact error-resilient schemes that maintained the original size of the assemblies, but required certain restrictions on the Boolean functions to be used in the algorithmic self-assembly. It is a critical challenge to improve these compact error resilient schemes to incorporate arbitrary Boolean functions, and to determine how far these prior results can be extended under different degrees of restrictions on the Boolean functions. In this work we present a considerably more complete theory of compact error-resilient schemes for algorithmic self-assembly in two and three dimensions. In our error model, ε is defined to be the probability that there is a mismatch between the neighboring sides of two juxtaposed tiles and they still stay together in the equilibrium. This probability is independent of any other match or mismatch and hence we term this probabilistic model as the independent error model. In our model all the error analysis is performed under the assumption of kinetic equilibrium. First we consider two-dimensional algorithmic self-assembly. We present an error correction scheme for reduction of errors from ε to ε ² for arbitrary Boolean functions in two dimensional algorithmic self-assembly. Then we characterize the class of Boolean functions for which the error can be reduced from ε to ε ³, and present an error correction scheme that achieves this reduction. Then we prove ultimate limits on certain classes of compact error resilient schemes: in particular we show that they can not provide reduction of errors from ε to ε ⁴ is for any Boolean functions. Further, we develop the first provable compact error resilience schemes for three dimensional tiling self-assemblies. We also extend the work of Winfree on self-healing in two-dimensional self-assembly (Winfree in Nanotechnol. Sci. Comput. 55–78, [2006]) to obtain a self-healing tile set for three-dimensional self-assembly.     

Improved Distributed Algorithms for SCC Decomposition

We study and improve the OBF technique [Barnat, J. and P.Moravec, Parallel algorithms for finding SCCs in implicitly given graphs, in: Proceedings of the 5th International Workshop on Parallel and Distributed Methods in Verification (PDMC 2006), LNCS (2007)], which was used in distributed algorithms for the decomposition of a partitioned graph into its strongly connected components. In particular, we introduce a recursive variant of OBF and experimentally evaluate several different implementations of it that vary in the degree of parallelism. For the evaluation we used synthetic graphs with a few large components and graphs with many small components. We also experimented with graphs that arise as state spaces in real model checking applications. The experimental results are compared with that of other successful SCC decomposition techniques [Orzan, S., “On Distributed Verification and Verified Distribution,” Ph.D. thesis, Free University of Amsterdam (2004); Fleischer, L.K., B. Hendrickson and A. Pinar, On identifying strongly connected components in parallel, in: Parallel and Distributed Processing, IPDPS Workshops, Lecture Notes in Computer Science 1800, 2000, pp. 505–511].     

On Total Variation Minimization and Surface Evolution Using Parametric Maximum Flows

In a recent paper Boykov et al. (LNCS, Vol. 3953, pp. 409–422, 2006) propose an approach for computing curve and surface evolution using a variational approach and the geo-cuts method of Boykov and Kolmogorov (International conference on computer vision, pp. 26–33, 2003). We recall in this paper how this is related to well-known approaches for mean curvature motion, introduced by Almgren et al. (SIAM Journal on Control and Optimization 31(2):387–438, 1993) and Luckhaus and Sturzenhecker (Calculus of Variations and Partial Differential Equations 3(2):253–271, 1995), and show how the corresponding problems can be solved with sub-pixel accuracy using Parametric Maximum Flow techniques. This provides interesting algorithms for computing crystalline curvature motion, possibly with a forcing term. A. Chambolle’s research supported by ANR project “MICA”, grant ANR-08-BLAN-0082. J. Darbon’s research supported by ONR grant N000140710810.     

Finite Volume Discretization and Multilevel Methods in Flow Problems

This article is intended as a preliminary report on the implementation of a finite volume multilevel scheme for the discretization of the incompressible Navier–Stokes equations. As is well known the use of staggered grids (e.g. MAC grids, Perić et al. Comput. Fluids, 16(4), 389–403, (1988)) is a serious impediment for the implementation of multilevel schemes in the context of finite differences. This difficulty is circumvented here by the use of a colocated finite volume discretization (Faure et al. (2004a) Submitted, Perić et al. Comput. Fluids, 16(4), 389–403, (1988)), for which the algebra of multilevel methods is much simpler than in the context of MAC type finite differences. The general ideas and the numerical simulations are presented in this article in the simplified context of a two-dimensional Burgers equations; the two-, and three-dimensional Navier–Stokes equations introducing new difficulties related to the incompressibility condition and the time discretization, will be considered elsewhere (see Faure et al. (2004a) Submitted and Faure et al. (2004b), in preparation).     

Reversibility and Models for Concurrency

There is a growing interest in models of reversible computation driven by exciting application areas such as bio-systems and quantum computing. Reversible process algebras RCCS [Danos, V. and J. Krivine, Reversible communicating systems, in: P. Gardner and N. Yoshida, editors, Proceedings of the 15th International Conference on Concurrency Theory CONCUR 2004, LNCS 3170 (2004), pp. 292–307] and CCSK [Phillips, I.C.C. and I. Ulidowski, Reversing algebraic process calculi, in: Proceedings of 9th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2006, LNCS 3921 (2006), pp. 246–260. Extended version accepted by Journal of Logic and Algebraic Programming] were developed and general techniques for reversing other process operators were proposed. The paper shows that the notion of reversibility can bridge the gap between some interleaving models and non-interleaving models of concurrency, and makes them interchangeable. We prove that transition systems associated with reversible process algebras are equivalent as models to labelled prime event structures. Furthermore, we show that forward-reverse bisimulation corresponds to hereditary history-preserving bisimulation in the setting with no auto-concurrency and no auto-causation.     

Computation of Singular Integral Operators in Wavelet Coordinates

With respect to a wavelet basis, singular integral operators can be well approximated by sparse matrices, and in Found. Comput. Math. 2: 203–245 (2002) and SIAM J. Math. Anal. 35: 1110–1132 (2004), this property was used to prove certain optimal complexity results in the context of adaptive wavelet methods. These results, however, were based upon the assumption that, on average, each entry of the approximating sparse matrices can be computed at unit cost. In this paper, we confirm this assumption by carefully distributing computational costs over the matrix entries in combination with choosing efficient quadrature schemes.     

Weakly distributive domains(Ⅱ)

In our previous work (Inform. and Comput., 2005, 202: 87–103), we have shown that for any ω-algebraic meet-cpo D, if all higher-order stable function spaces built from D are ω-algebraic, then D is finitary. This accomplishes the first of a possible, two-step process in solving the problem raised (LNCS, 1991, 530: 16–33; Domains and lambda-calculi, Cambridge Univ. Press, 1998) whether the category of stable bifinite domains of Amadio-Droste-G?bel (LNCS, 1991, 530: 16–33; Theor. Comput. Sci., 1993, 111: 89–101) is the largest cartesian closed full subcategory within the category of ω-algebraic meet-cpos with stable functions. This paper presents the results of the second step, which is to show that for any ω-algebraic meet-cpo D satisfying axioms M and I to be contained in a cartesian closed full sub-category using ω-algebraic meet-cpos with stable functions, it must not violate MI^∞. We introduce a new class of domains called weakly distributive domains and show that for these domains to be in a cartesian closed category using ω-algebraic meet-cpos, property MI^∞ must not be violated. Further, we demonstrate that principally distributive domains (those for which each principle ideal is distributive) form a proper subclass of weakly distributive domains, and Birkhoff’s M ₃ and N ₅ (Introduction to Lattices and order, Cambridge Univ. Press, 2002) are weakly distributive (but non-distributive). Then, we establish characterization results for weakly distributive domains. We also introduce the notion of meet-generators in constructing stable functions and show that if an ω-algebraic meet-cpo D contains an infinite number of meet-generators, then [D → D] fails I. However, the original problem of Amadio and Curien remains open.     

Enabling e-business tools and robotics technology for teleconstruction

This paper proposes a comprehensive approach to the development of technology infrastructure for the application of information techology (IT) based solutions in teleconstruction—the performance of on-site construction and related tasks through the use of IT and robotics by a remotely located team of project participants: general contractor, subcontractors, equipment operators, materials suppliers, and project office professionals. The paper proposes that technologies exist that enable both terrestrial and extraterrestrial teleconstruction. Thomas Bock: German-American “Frontiers of Engineering” Symposium Participant, Essen 2001, Alexander von Humboldt Foundation 2004 “CONNECT” Award Recipient Mirosław Skibniewski: German-American “Frontiers of Engineering” Symposium Participant and Member of the Organizing Committee, Essen 2001, Alexander von Humboldt Foundation 2004 “CONNECT” Award Recipient 2–6: Photos copyright, Thomas Bock, TU Munich, Germany. 7–8: Photos and figure copyright, Prof. Masahiru Nohmi, Kagawa University, Japan.     

NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow

We consider the version of broadcast scheduling where a server can transmit W messages of a given set at each time-step, answering previously made requests for these messages. The goal is to minimize the average response time (ART) if the amount of requests is known in advance for each time-step and message. We prove that this problem is NP-hard, thus answering an open question stated by Kalyanasundaram, Pruhs and Velauthapillai (Proceedings of ESA 2000, LNCS 1879, 2000, pp. 290–301). Furthermore, we present an approximation algorithm that is allowed to send several messages at once. Using six channels for transmissions, the algorithm achieves an ART that is at least as good as the optimal solution using one channel. From the NP-hardness of broadcast scheduling we derive a new inapproximability result of (2 − ε, 1) for the (congestion, cost) bicriteria version of the single source unsplittable min-cost flow problem, for arbitrary ε > 0. The result holds even in the often considered case where the maximum demand is less than or equal to the minimum edge capacity (d _max ≤ u _min), a case for which an algorithm with ratio (3, 1) was presented by Skutella.     

Performance Evaluation of GAP-RBF Network in Channel Equalization

A Growing and Pruning Radial Basis Function (GAP-RBF) network has been recently proposed by Huang et al. [IEEE Transactions on Systems, Man and Cybernetics-Part B: Cybernetics, 34(6) (2004), 2284–2292]. However, its performance in signal processing areas is not clear yet. In this paper, GAP-RBF network is used for solving the communication channel equalization problem. The simulation results demonstrate that GAP-RBF equalizer outperforms other equalizers such as recurrent neural network and MRAN on linear and nonlinear channel model in terms of bit error rate.