Search

This paper presents mcmas, a model checker for Multi-Agent Systems (MAS). Differently from traditional model checkers, mcmas permits the automatic verification of specifications that use epistemic, correctness, and cooperation modalities, in addition to the standard temporal modalities. These additional modalities are used to capture properties of various scenarios (including communication and security protocols, games, etc.) that may be difficult or unnatural to express with temporal operators only; a small number of applications are presented in Section[4]. Agents are described in mcmas by means of the dedicated programming language ISPL (Interpreted Systems Programming Language). The approach is symbolic and uses ordered binary decision diagrams (obdds), thereby extending standard techniques for temporal logic to other modalities distinctive of agents. mcmas and all the examples presented in this paper are available for download [14] under the terms of the GPL license. [ABSTRACT FROM AUTHOR]

In a seminal paper, Håstad, Impagliazzo, Levin, and Luby showed that pseudorandom generators exist if and only if one-way functions exist. The construction they propose to obtain a pseudorandom generator from an n-bit one-way function uses random bits in the input (which is the most important complexity measure of such a construction). In this work we study how much this can be reduced if the one-way function satisfies a stronger security requirement. For example, we show how to obtain a pseudorandom generator which satisfies a standard notion of security using only bits of randomness if a one-way function with exponential security is given, i.e., a one-way function for which no polynomial time algorithm has probability higher than 2-cn in inverting for some constant c. Using the uniform variant of Impagliazzo's hard-core lemma given in [7] our constructions and proofs are self-contained within this paper, and as a special case of our main theorem, we give the first explicit description of the most efficient construction from [6]. [ABSTRACT FROM AUTHOR]

This paper proposes a new efficient signature scheme from bilinear maps that is secure in the standard model (i.e., without the random oracle model). Our signature scheme is more effective in many applications (e.g., blind signatures, group signatures, anonymous credentials etc.) than the existing secure signature schemes in the standard model such as the Boneh-Boyen [6], Camenisch-Lysyanskaya [10], Cramer-Shoup [15] and Waters [33] schemes (and their variants). The security proof of our scheme requires a slightly stronger assumption, the 2SDH assumption, than the SDH assumption used by Boneh-Boyen. As typical applications of our signature scheme, this paper presents efficient blind signatures and partially blind signatures that are secure in the standard model. Here, partially blind signatures are a generalization of blind signatures (i.e., blind signatures are a special case of partially blind signatures) and have many applications including electronic cash and voting. Our blind signature scheme is much more efficient than the existing secure blind signature schemes in the standard model such as the Camenisch-Koprowski-Warinsch [8] and Juels-Luby-Ostrovsky [22] schemes, and is also almost as efficient as the most efficient blind signature schemes whose security has been analyzed heuristically or in the random oracle model. Our partially blind signature scheme is the first one that is secure in the standard model and it is very efficient (almost as efficient as our blind signatures). We also present a blind signature scheme based on the Waters signature scheme. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of counting models in integer linear programming (ILP) using Boolean Satisfiability (SAT) techniques, and proposes two approaches to solve this problem. The first approach consists of encoding ILP instances into pseudo-Boolean (PB) instances. Moreover, the paper introduces a model counter for PB constraints, which can be used for counting models in PB as well as in ILP. A second alternative approach consists of encoding instances of ILP into instances of SAT. A two-step procedure is proposed, consisting of first mapping the ILP instance into PB constraints and then encoding the PB constraints into SAT. One key observation is that not all existing PB to SAT encodings can be used for counting models. The paper provides conditions for PB to SAT encodings that can be safely used for model counting, and proves that some of the existing encodings are safe for model counting while others are not. Finally, the paper provides experimental results, comparing the PB and SAT approaches, as well as existing alternative solutions. [ABSTRACT FROM AUTHOR]

This paper is a contribution to the general investigation into how the complexity of constraint satisfaction problems (CSPs) is determined by the form of the constraints. Schaefer proved that the Boolean generalized CSP has the dichotomy property (i.e., all instances are either in P or are NP-complete), and gave a complete and simple classification of those instances which are in P (assuming $\mbox{P}\neq\mbox{NP}$) [20]. In this paper we consider a special subcase of the generalized CSP. For this CSP subcase, we require that the variables be drawn from disjoint Boolean domains. Our relation set contains only two elements: a monotone multiple-arity Boolean relation R and its complement $\overline{R}$. We prove a dichotomy theorem for these monotone function CSPs, and characterize those monotone functions such that the corresponding problem resides in P. [ABSTRACT FROM AUTHOR]

In this paper we present a new progressive cooperating simplifier for deciding the satisfiability of a quantifier-free formula in the first-order theory of integers involving combinations of sublogics, referred to as Satisfiability Modulo Theories (SMT). Our approach, given an SMT problem, replaces each non-propositional theory atom with a Boolean indicator variable yielding a purely propositional formula to be decided by a SAT solver. Starting with the most abstract representation (the Boolean formula), the solver gradually integrates more complex theory solvers into the working decision procedure. Additionally, we propose a method to simplify "expensive" atoms into suitable conjunctions of "cheaper" theory atoms when conflicts occur. This process considerably increases the efficiency of the overall procedure by reducing the number of calls to the slower theory solvers. This is made possible by adopting our novel inter-logic implication framework, as proposed in this paper. We have implemented these methods in our Ario SMT solver by combining three different theory solvers within a DPLL-style SAT solver: a Unit-Two-Variable-Per-Inequality (UTVPI) solver, an integer linear programming (ILP) solver, and a solver for systems of equalities with uninterpreted functions. The efficiencies of our proposed algorithms are demonstrated and exhaustively investigated on a wide range of benchmarks in hardware and software verification domain. Empirical results are also presented showing the advantages/limitations of our methods over other modern techniques for solving these SMT problems. [ABSTRACT FROM AUTHOR]

In this paper we present a review of SAT-based approaches for building scalable and efficient decision procedures for quantifier-free first-order logic formulas in one or more decidable theories, known as Satisfiability Modulo Theories (SMT) problems. As applied to different system verification problems, SMT problems comprise of different theories including fragments of elementary theory of numbers, the theory of arrays, the theory of list structures, etc. In this paper we focus on different DPLL-style satisfiability procedures for decidable fragments of the theory of integers. Leveraging the advances made in SAT solvers in the past decade, we introduce several SAT-based SMT solving methods that in many applications have outperformed classical decision methods. Aside from the classical method of translating the SMT formula to a purely Boolean problem, in recent methods, a SAT solver is utilized to serve as the "glue" that ties together the different theory atoms and forms the basis for reasoning and learning within and across them. Several methods have been developed to provide a combination framework for implications to flow through the theory solvers and to possibly activate other theory atoms based on the current assignments. Similarly, conflict-based learning is also extended to enable the creation of learned clauses comprising of the combination of theory atoms. Additional methods unique to one or more types of theory atoms have also been proposed that learn more expressive constraints and significantly increase the pruning power of these combination schemes. We will describe several combination strategies and their impact on scalability and performance of the overall solver in different settings and applications. [ABSTRACT FROM AUTHOR]

Many structures used in computer science and software can be represented by context-free languages. This paper discusses computable functions on such languages, which give a useful model for studies of computability and algorithms involving complex data structures. This paper further tackles some practical issues for using the functions. Some practical schemes of the functions are presented. A subclass of functions is provided, which can be implemented efficiently. Keywords: recursive function, context-free language, structured data, operator, computability. [ABSTRACT FROM AUTHOR]

This paper deals with secure computations in a minimal model, and gives a protocol which securely computes every function by means of the techniques of exclusive-or sum-of-products (ESOP) expressions. The communication complexity of our protocol is proportional to the size of an obtained multiple-valued-input ESOP expression. Since the historical research on minimizing ESOP expressions is now still active, our protocol will turn to an efficient one as this research progresses. Thus, this paper gives an application of ESOP expressions to designing cryptographic protocols, and we hope that it would motivate further research on minimizing ESOP expressions. [ABSTRACT FROM AUTHOR]

Although complexity theory already extensively studies path-cardinality-based restrictions on the power of nondeterminism, this paper is motivated by a more recent goal: To gain insight into how much of a restriction it is of nondeterminism to limit machines to have just one contiguous (with respect to some simple order) interval of accepting paths. In particular, we study the robustness—the invariance under definition changes—of the cluster class [8]. This class contains each function that is computed by a balanced Turing machine whose accepting paths always form a cluster with respect to some length-respecting total order with efficient adjacency checks. The definition of is heavily influenced by the defining paper's focus on (global) orders. In contrast, we define a cluster class, , to capture what seems to us a more natural model of cluster computing. We prove that the naturalness is costless: . Then we exploit the more natural, flexible features of to prove new robustness results for and to expand what is known about the closure properties of . The complexity of recognizing edges—of an ordered collection of computation paths or of a cluster of accepting computation paths—is central to this study. Most particularly, our proofs exploit the power of unique discovery of edges—the ability of nondeterministic functions to, in certain settings, discover on exactly one (in some cases, on at most one) computation path a critical piece of information regarding edges of orderings or clusters. [ABSTRACT FROM AUTHOR]

A semi-matching on a bipartite graph G=(U ∪ V, E) is a set of edges such that each vertex in U is incident to exactly one edge in X. The sum of the weights of the vertices from U that are assigned (semi-matched) to some vertex v ∈ V is referred to as the load of vertex v. In this paper, we consider the problem to finding a semi-matching that minimizes the maximum load among all vertices in V. This problem has been shown to be solvable in polynomial time by Harvey et. al [3] and Fakcharoenphol et. al [5] for unweighted graphs. However, the computational complexity for the weighted version of the problem was left as an open problem. In this paper, we prove that the problem of finding a semi-matching that minimizes the maximum load among all vertices in a weighted bipartite graph is NP-complete. A -approximation algorithm is proposed for this problem. Keywords: semi-matching, bipartite graphs, load balancing, NP-hard, approximation algorithm. [ABSTRACT FROM AUTHOR]

This expository paper describes some of the results of two recent research papers [GOP+05, GPSZ05]. The first of these papers proves that every NP-complete set is many-one autoreducible. The second paper proves that every many-one autoreducible set is many-one mitotic. It follows immediately that every NP-complete set is many-one mitotic. Hence, we have the compelling result that every NP-complete set A splits into two NP-complete sets A1 and A2. [ABSTRACT FROM AUTHOR]

This paper proposes a new metric that aims to express the cost of manufacturing large-scale, communication-intensive digital systems. These systems are modeled by networks with internal and external edges, where the latter are input/output edges connecting the system with the external world. A k-parceling of such a network is a partition of the network into components each having at most k non-internal edges. (Such a partition is of interest when the number of the external edges is much larger than k.) The k-parceling number of a network is the minimal number of components in a k-parceling. We argue that the parceling number of a large-scale, communication-intensive network expresses the cost of such a system better than the contemporary prevalent metrics and therefore it can guide the designers of such systems better than these metrics. The paper studies the parceling of two important networks, the Butterfly and the Batcher Bitonic sorting network. It establishes explicit (rather than asymptotic) lower and upper bounds on the parceling number of both networks. [ABSTRACT FROM AUTHOR]

A fundamental goal of Internet congestion control is to allocate limited bandwidth fairly to competing flows. Such flow control involves an interplay between the behavior of routers and the behavior of end hosts. Routers must decide which packets to drop when their output links become congested. End hosts must decide how to moderate their packet transmissions in response to feedback in the form of acknowledgements of packet delivery (acks). Typically this is done according to the TCP protocol, in which a host maintains a window (the number of packets that have been sent but not yet acknowledged) that is increased when an ack is received and decreased when a drop is detected. Often the selection of packets to be dropped at a router depends on the order of their arrivals at the router but not on the flows to which the packets belong. An exception occurs when packets are stratified according to their quality of service guarantee; in this case packets at higher strata are given priority, but within a stratum the packets from different flows receive the same treatment. A number of methods have been proposed to ensure fairness by selectively dropping packets from flows that are receiving more than their fair share of bandwidth. The most effective known algorithms for detecting and selectively dropping high-rate flows at a router are based on random hashing or random sampling of packets and give only probabilistic guarantees. The known deterministic algorithms either require excessive storage, require packets to carry accurate estimates of the rates of their flows, assume some special properties of the stream of arriving packets, or fail to guarantee fairness. In a simplified theoretical setting we show that the detection and selective dropping of high-rate flows can be accomplished deterministically without any of these defects. This result belies the conventional wisdom that per-flow state is required to guarantee fairness. Given an arriving stream of packets, each labeled with the name of its flow, our algorithm drops packets selectively upon arrival so as to guarantee that, in every consecutive subsequence of the stream of surviving packets, no flow has significantly more than its fair share of the packets. The main results of the paper are tight bounds on the worst-case storage requirement of this algorithm. The bounds demonstrate that the storage and computation required to guarantee fairness are easily within the capabilites of conventional routers. It is important to acknowedge the limitations of this work. We have formulated the achievement of fairness at a router in terms of local information on the stream of arriving packets at that router. The implications of such a locally optimal policy on the global stability of the Internet would require analyzing the Internet as a complex dynamical system involving interactions among routers and end hosts, of which some will be TCP-compliant and some will not. In work not reported here we have made an initial simulation study of this complex process, but such a study is outside the scope of the present paper. [ABSTRACT FROM AUTHOR]

The Minimum Energy Broadcast Routing problem was extensively studied during the last years. Given a sample space where wireless devices are distributed, the aim is to perform the broadcast pattern of communication from a given source while minimizing the total energy consumption. While many papers deal with the 2-dimensional case where the sample space is given by a flat area, few results are known about the more interesting and practical 3-dimensional case. In this paper we study such a case and we present a tighter analysis of the minimum spanning tree heuristic in order to considerably decrease its approximation factor from the known 26 to roughly 18.8. This decreases the gap with the known lower bound of 12 given by the so called kissing number. [ABSTRACT FROM AUTHOR]

The k-set agreement problem is a generalization of the consensus problem: considering a system made up of n processes where each process proposes a value, each non-faulty process has to decide a value such that a decided value is a proposed value, and no more than k different values are decided. It has recently be shown that, in the crash failure model, min$(\lfloor \frac{f}{k} \rfloor+2,\lfloor \frac{t}{k} \rfloor +1)$ is a lower bound on the number of rounds for the non-faulty processes to decide (where t is an upper bound on the number of process crashes, and f, 0 ≤f ≤t, the actual number of crashes). This paper considers the k-set agreement problem in synchronous systems where up to t < n /2 processes can experience general omission failures (i.e., a process can crash or omit sending or receiving messages). It first introduces a new property, called strong termination. This property is on the processes that decide. It is satisfied if, not only every non-faulty process, but any process that neither crashes nor commits receive omission failures decides. The paper then presents a k-set agreement protocol that enjoys the following features. First, it is strongly terminating (to our knowledge, it is the first agreement protocol to satisfy this property, whatever the failure model considered). Then, it is early deciding and stopping in the sense that a process that either is non-faulty or commits only send omission failures decides and halts by round min$(\lfloor \frac{f}{k} \rfloor+2,\lfloor \frac{t}{k} \rfloor +1)$. To our knowledge, this is the first early deciding k-set agreement protocol for the general omission failure model. Moreover, the protocol provides also the following additional early stopping property: a process that commits receive omission failures (and does not crash) executes at most min$(\lceil \frac{f}{k} \rceil +2,\lfloor \frac{t}{k} \rfloor +1)$ rounds. It is worth noticing that the protocol allows each property (strong termination vs early deciding/stopping vs early stopping) not to be obtained at the detriment of the two others. The combination of the fact that min$(\lfloor \frac{f}{k} \rfloor+2,\lfloor \frac{t}{k} \rfloor +1)$ is lower bound on the number of rounds in the crash failure model, and the very existence of the proposed protocol has two very interesting consequences. First, it shows that, although general omission failure model is more severe than the crash failure model, both models have the same lower bound for the non-faulty processes to decide. Second, it shows that, in the general omission failure model, that bound applies also the processes that commit only send omission failures. Keywords: Agreement problem, Crash failure, Strong Termination, Early decision, Early stopping, Efficiency, k-set agreement, Message-passing system, Receive omission failure, Round-based computation, Send omission failure, Synchronous system. [ABSTRACT FROM AUTHOR]

This paper studies local algorithms for autonomous robot systems, namely, algorithms that use only information of the positions of a bounded number of their nearest neighbors. The paper focuses on the spreading problem. It defines measures for the quality of spreading, presents a local algorithm for the one-dimensional spreading problem, prove its convergence to the equally spaced configuration and discusses its convergence rate in the synchronous and semi-synchronous settings. It then presents a local algorithm achieving the exact equally spaced configuration in finite time in the synchronous setting, and proves it is time optimal for local algorithms. Finally, the paper also proposes an algorithm for the two-dimensional case and presents simulation results of its effectiveness. [ABSTRACT FROM AUTHOR]

We study scheduling problems in battery-operated computing devices, aiming at schedules with low total energy consumption. While most of the previous work has focused on finding feasible schedules in deadline-based settings, in this paper we are interested in schedules that guarantee good response times. More specifically, our goal is to schedule a sequence of jobs on a variable speed processor so as to minimize the total cost consisting of the power consumption and the total flow time of all the jobs. We first show that when the amount of work, for any job, may take an arbitrary value, then no online algorithm can achieve a constant competitive ratio. Therefore, most of the paper is concerned with unit-size jobs. We devise a deterministic constant competitive online algorithm and show that the offline problem can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

We study route selection for packet switching in the competitive throughput model. In contrast to previous papers which considered competitive algorithms for packet scheduling, we consider the packet routing problem (output port selection in a node). We model the node routing problem as follows: a node has an arbitrary number of input ports and an arbitrary number of output queues. At each time unit, an arbitrary number of new packets may arrive, each packet is associated with a subset of the output ports (which correspond to the next edges on the allowed paths for the packet). Each output queue transmits packets in some arbitrary manner. Arrival and transmission are arbitrary and controlled by an adversary. The node routing algorithm has to route each packet to one of the allowed output ports, without exceeding the size of the queues. The goal is to maximize the number of the transmitted packets. In this paper, we show that all non-refusal algorithms are 2-competitive. Our main result is an almost optimal -competitive algorithm, for a large enough queue size. For packets with arbitrary values (allowing preemption) we present a 2-competitive algorithm for any queue size. [ABSTRACT FROM AUTHOR]

The common theoretical model adopted in recent studies on algorithms for systems of autonomous mobile robots assumes that the positional input of the robots is obtained by perfectly accurate visual sensors, that robot movements are accurate, and that internal calculations performed by the robots on (real) coordinates are perfectly accurate as well. The current paper concentrates on the effect of weakening this rather strong set of assumptions, and replacing it with the more realistic assumption that the robot sensors, movement and internal calculations may have slight inaccuracies. Specifically, the paper concentrates on the ability of robot systems with inaccurate sensors, movements and calculations to carry out the task of convergence. The paper presents several impossibility results, limiting the inaccuracy allowing convergence. The main positive result is an algorithm for convergence under bounded measurement, movement and calculation errors. [ABSTRACT FROM AUTHOR]

In order to efficiently perform scalar multiplications on elliptic Koblitz curves, expansions of the scalar to a complex base associated with the Frobenius endomorphism are commonly used. One such expansion is the τ-adic NAF, introduced by Solinas. Some properties of this expansion, such as the average weight, are well known, but in the literature there is no proof of its optimality, i.e. that it always has minimal weight. In this paper we provide the first proof of this fact. Point halving, being faster than doubling, is also used to perform fast scalar multiplications on generic elliptic curves over binary fields. Since its computation is more expensive than that of the Frobenius, halving was thought to be uninteresting for Koblitz curves. At PKC 2004, Avanzi, Ciet, and Sica combined Frobenius operations with one point halving to compute scalar multiplications on Koblitz curves using on average 14% less group additions than with the usual τ-and-add method without increasing memory usage. The second result of this paper is an improvement over their expansion. The new representation, called the wide-double-NAF, is not only simpler to compute, but it is also optimal in a suitable sense. In fact, it has minimal Hamming weight among all τ-adic expansions with digits {0,±1} that allow one halving to be inserted in the corresponding scalar multiplication algorithm. The resulting scalar multiplication requires on average 25% less group operations than the Frobenius method, and is thus 12.5% faster than the previously known combination. Keywords. Koblitz curves, scalar multiplication, point halving, τ-adic expansion, integer decomposition. [ABSTRACT FROM AUTHOR]

This paper introduces an architecture for generic constraint implementations based on variable views and range iterators. Views allow, for example, to scale, translate, and negate variables. The paper shows how to make constraint implementations generic and how to reuse a single generic implementation with different views for different constraints. A wide range of applications of views exemplifies their usefulness and their potential for simplifying constraint implementations. We introduce domain operations compatible with views based on range iterators. The paper evaluates the applicability of the approach as well as different implementation techniques for the presented architecture. [ABSTRACT FROM AUTHOR]

In 2006, Wang-Li proposed a new user authentication scheme using smart cards which can offer forward secrecy. However, this paper will demonstrate that Wang-Li's scheme is vulnerable to parallel session attack and reflection attack. Furthermore, the current paper presents a more efficient and secure scheme that not only resolves such problems, but also involves fewer computations and communications than Wang-Li's scheme. Keywords: Network security, Secure protocol, Smart card, Authentication, Password. [ABSTRACT FROM AUTHOR]

Despite the introduction of information technologies in governmental administrations, most bureaucratic processes are still paper-based. In this paper we present a framework to transfer conventional, paper-based processes to electronic workflows. Thereby, the transformation to e-Government applications has two challenges. First, to find an equivalent description for the single activities and their interaction for defining the entire process. Second, to ensure the security of the process. We identified four types of activities that can be used as basic components for the workflows considered in our work. The security aspects of the electronic representation are ensured by further framework components, for example authentication or authorization. Finally, we present how this framework can be used for other scenarios and discuss some details of our prototype implementation. Keywords: Workflow Security, Digitize Workflows, Workflow Engine, XPDL, XACML. [ABSTRACT FROM AUTHOR]

The Border Gateway Protocol (BGP) [1] is the foundation of inter-domain Internet routing. A number of papers have described how BGP is highly vulnerable to a wide range of attacks [2, 3], and several proposals have been offered to secure BGP [4, 5, 6, 7, 8]. Most of these proposed mechanisms rely on a PKI, to provide trusted inputs for routing security mechanisms, to enable BGP routers to reject bogus routing advertisements. This paper provides a detailed proposal for a PKI, including a repository system, representing IP address allocation and Autonomous System number assignment,. This infrastructure offers a near term opportunity to improve routing security, since it does not require changes to routers, while also setting the stage for more comprehensive BGP security initiatives in the future. [ABSTRACT FROM AUTHOR]

A cryptography for enforcing multilevel security in a system where hierarchy is represented by a partially ordered set was introduced by Akl et al. But the key generation algorithm of Akl et al. is infeasible when there is a large number of users. To overcome this shortage, in 1985, MacKinnon et al. proposed a paper containing a condition which prevents cooperative attacks and optimizes the assignment. In 2005, Kim et al. proposed key management systems for multilevel security using one-way hash function, RSA algorithm, Poset dimension and Clifford semigroup in the context of modern cryptography. In particular, the key management system using Clifford semigroup of imaginary quadratic non-maximal orders is based on the fact that the computation of a key ideal K0 from an ideal EK0 seems to be difficult unless E is equivalent to O. We, in this paper, show that computing preimages under the bonding homomorphism is not difficult, and that the multilevel cryptosystem based on the Clifford semigroup is insecure and improper to the key management system. Keywords: Hierarchy, Key generation algorithm, Class semigroup, Key exchange system. [ABSTRACT FROM AUTHOR]

Users are often forced to trust potentially malicious terminals when trying to interact with a remote secure system. This paper presents an approach for ensuring the integrity and authenticity of messages sent through an untrusted terminal by a user to a remote trusted computing base and vice versa. The approach is both secure and easy to use. It leverages the difficulty computers have in addressing some artificial intelligence problems and therefore requires no complex computation on the part of the user. This paper describes the general form of the approach, analyzes its security and user-friendliness, and describes an example implementation based on rendering a 3-D scene. Keywords: Authentication, Human Cryptography. [ABSTRACT FROM AUTHOR]

This paper presents computationally "lightweight" schemes for performing biometric authentication that carry out the comparison stage without revealing any information that can later be used to impersonate the user (or reveal personal biometric information). Unlike some previous computationally expensive schemes — which make use of slower cryptographic primitives — this paper presents methods that are particularly suited to financial institutions that authenticate users with biometric smartcards, sensors, and other computationally limited devices. In our schemes, the client and server need only perform cryptographic hash computations on the feature vectors, and do not perform any expensive digital signatures or public-key encryption operations. In fact, the schemes we present have properties that make them appealing even in a framework of powerful devices capable of public-key signatures and encryptions. Our schemes make it computationally infeasible for an attacker to impersonate a user even if the attacker completely compromises the information stored at the server, including all the server's secret keys. Likewise, our schemes make it computationally infeasible for an attacker to impersonate a user even if the attacker completely compromises the information stored at the client device (but not the biometric itself, which is assumed to remain attached to the user and is not stored on the client device in any form). Keywords: biometrics, authentication, smart cards, cryptographic hash functions. [ABSTRACT FROM AUTHOR]

Approximate Message Authentication Code (AMAC) is a recently introduced cryptographic primitive with several applications in the areas of cryptography and coding theory. Briefly speaking, AMACs represent a way to provide data authentication that is tolerant to acceptable modifications of the original message. Although constructs had been proposed for this primitive, no security analysis or even modeling had been done. In this paper we propose a rigorous model for the design and security analysis of AMACs. We then present two AMAC constructions with desirable efficiency and security properties. AMAC is a useful primitive with several applications of different nature. A major one, that we study in this paper, is that of entity authentication via biometric techniques or passwords over noisy channels. We present a formal model for the design and analysis of biometric entity authentication schemes and show simple and natural constructions of such schemes starting from any AMAC. [ABSTRACT FROM AUTHOR]

Recent high profile data thefts have shown that perimeter defenses are not sufficient to secure important customer data. The damage caused by these thefts can be disastrous, and today an enterprise with poor data security may also find itself violating privacy legislation and be liable to civil lawsuits. The Ingrian DataSecure Platform presents an approach for protecting data inside the enterprise - and so to help eliminate many of the threats of data theft. This paper demonstrates how an enterprise can prevent unauthorized data exposure by implementing column encryption in commercially available databases. Adding security at the database layer allows an enterprise to protect sensitive data without rewriting associated applications. Furthermore, large enterprises require scalable and easily administrable solutions. In order to satisfy this demand this paper introduces the concept of a Network-Attached Encryption Server, a central device with secure storage and extensive user access permissions for protecting persistent security credentials. [ABSTRACT FROM AUTHOR]

We propose a new notion of short identity-based signature scheme. We argue that the identity-based environment is essential in some scenarios. The notion of short identity-based signature schemes can be viewed as identity-based (partial) message recovery signatures. Signature schemes with message recovery has been extensively studied in the literature. This problem is somewhat related to the problem of signing short messages using a scheme that minimizes the total length of the original message and the appended signature. In this paper, firstly, we revisit this notion and propose an identity-based message recovery signature scheme. Our scheme can be regarded as the identity based version of Abe-Okamoto's scheme [1]. Then, we extend our scheme to achieve an identity-based partial message recovery signature scheme. In this scheme, the signature is appended to a truncated message and the discarded bytes are recovered by the verification algorithm. This is to answer the limitation of signature schemes with message recovery that usually deal with messages of fixed length. This paper opens a new research area, namely how to shorten identity based signatures, in contrast to proposing a short signature scheme. We present this novel notion together with two concrete schemes based on bilinear pairings. [ABSTRACT FROM AUTHOR]

This paper discusses the state-of-the-art software optimization methodology for symmetric cryptographic primitives on Pentium III and 4 processors. We aim at maximizing speed by considering the internal pipeline architecture of these processors. This is the first paper studying an optimization of ciphers on Prescott, a new core of Pentium 4. Our AES program with 128-bit key achieves 251 cycles/block on Pentium 4, which is, to our best knowledge, the fastest implementation of AES on Pentium 4. We also optimize SNOW2.0 keystream generator. Our program of SNOW2.0 for Pentium III runs at the rate of 2.75 íops/cycle, which seems the most efficient code ever made for a real-world cipher primitive. For FOX128 block cipher, we propose a technique for speeding-up by interleaving two independent blocks using a register group separation. Finally we consider fast implementation of SHA512 and Whirlpool, two hash functions with a genuine 64-bit architecture. It will be shown that new SIMD instruction sets introduced in Pentium 4 excellently contribute to fast hashing of SHA512. [ABSTRACT FROM AUTHOR]

After the presentation of SMASH at FSE 2005, the proposal was broken [15]This paper presents a new hash function design, which is different from the popular designs of the MD4-family. Seen in the light of recent attacks on MD4, MD5, SHA-0, SHA-1, and on RIPEMD, there is a need to consider other hash function design strategies. The paper presents also a concrete hash function design named SMASH. One version has a hash code of 256 bits and appears to be at least as fast as SHA-256. [ABSTRACT FROM AUTHOR]

T-functions were introduced by Klimov and Shamir in a series of papers during the last few years. They are of great interest for cryptography as they may provide some new building blocks which can be used to construct efficient and secure schemes, for example block ciphers, stream ciphers or hash functions. In the present paper, we define the narrowness of a T-function and study how this property affects the strength of a T-function as a cryptographic primitive. We define a new data strucure, called a solution graph, that enables solving systems of equations given by T-functions. The efficiency of the algorithms which we propose for solution graphs depends significantly on the narrowness of the involved T-functions. Thus the subclass of T-functions with small narrowness appears to be weak and should be avoided in cryptographic schemes. Furthermore, we present some extensions to the methods of using solution graphs, which make it possible to apply these algorithms also to more general systems of equations, which may appear, for example, in the cryptanalysis of hash functions. Keywords: Cryptanalysis, hash functions, solution graph, T-functions, w-narrow. [ABSTRACT FROM AUTHOR]

A T-function is a mapping from n-bit words to n-bit words in which for each 0 ≤ i

In this paper, the concept of statistical bandwidth of multi-access systems are studied and extended to the case of unknown statistical descriptors. The results can improve the statistical characterization of the tail distribution of aggregated load presented to a multi-access system which is traditionally based on the logarithmic moment generation function (LMGF)[1]. In the paper, an extended moment generating function is introduced for calculating the statistical bandwidth and as a result a novel admission algorithm is presented. To further maximize the admitted load into the multi-access system the free parameter of the extended statistical bandwidth is optimized based on the geometrical optimization of polygonal surfaces. In this way, the system utilization can be near-optimal. [ABSTRACT FROM AUTHOR]

The self-assembly process for bottom-up construction of nanostructures is of key importance to the emerging scientific discipline Nanoscience. However, self-assembly at the molecular scale is prone to a quite high rate of error. Such high error rate is a major barrier to large-scale experimental implementation of DNA tiling. The goals of this paper are to develop theoretical methods for compact error-resilient self-assembly and to analyze these methods by stochastic analysis and computer simulation. Prior work by Winfree provided an innovative approach to decrease tiling self-assembly errors without decreasing the intrinsic error rate ε of assembling a single tile. However, his technique resulted in a final structure that is four times the size of the original one. This paper describes various compact error-resilient tiling methods that do not increase the size of the tiling assembly. These methods apply to assembly of boolean arrays which perform input sensitive computations (among other computations). Our 2-way (3-way) overlay redundancy construction drops the error rate from ε to approximately ε2 (ε3), without increasing the size of the assembly. These results were further validated using stochastic analysis and computer simulation. [ABSTRACT FROM AUTHOR]

$p\ {\overset{x}{\rightarrow}}\ q$ This paper discusses a problem of checking the structure freeness of DNA and RNA sequences. A set R of sequences over Σ is said to be structure free if for every α ∈ R, the minimum free energy of α is greater than or equal to 0. It was open whether or not there exists a polynomial time algorithm for testing the structure freeness of a given regular set R. In this paper, we will solve this problem. Keywords: Molecular Computing, DNA Computing, Sequence Design, Secondary Structures. [ABSTRACT FROM AUTHOR]

Conflicts naturally arise in optimistically replicated systems. The common way to detect update conflicts is via version vectors, whose storage and communication overhead are number of replicas × number of objects. These costs may be prohibitive for large systems. This paper presents predecessor vectors with exceptions (PVEs), a novel optimistic replication technique developed for Microsoft's WinFS system. The paper contains a systematic study of PVE's performance gains over traditional schemes. The results demonstrate a dramatic reduction of storage and communication overhead in normal scenarios, during which communication disruptions are infrequent. Moreover, they identify a cross-over threshold in communication failure-rate, beyond which PVEs loses efficiency compared with traditional schemes. [ABSTRACT FROM AUTHOR]

This paper studies implementations of concurrent objects that exploit the absence of step contention. These implementations use only reads and writes when a process is running solo. The other processes might be busy with other objects, swapped-out, failed, or simply delayed by a contention manager. We study in this paper two classes of such implementations, according to how they handle the case of step contention. The first kind, called obstruction-free implementations, are not required to terminate in that case. The second kind, called solo-fast implementations, terminate using powerful operations (e.g., C&S). We present a generic obstruction-free object implementation that has a linear contention-free step complexity (number of reads and writes taken by a process running solo) and uses a linear number of read/write objects. We show that these complexities are asymptotically optimal, and hence generic obstruction-free implementations are inherently slow. We also prove that obstruction-free implementations cannot be gracefully degrading, namely, be nonblocking when the contention manager operates correctly, and remain (at least) obstruction-free when the contention manager misbehaves. Finally, we show that any object has a solo-fast implementation, based on a solo-fast implementation of consensus. The implementation has linear contention-free step complexity, and we conjecture solo-fast implementations must have non-constant step complexity, i.e., they are also inherently slow. [ABSTRACT FROM AUTHOR]

Wireless sensor networks are useful for monitoring physical parameters and detecting objects or substances in an area. Most ongoing research consider the use of stationary sensors or controlled mobile sensors, which incur substantial equipment costs and coordination efforts. Alternatively, this paper considers using uncoordinated mobile nodes, who is not directed for any specific sensing activity. Each node independently observes a cross section of the field along its own path. The limited observation can be extended via information exchange among nodes coming across each other. For this model, the inherently noisy mobile measurements, incomplete individual observations, different sensing objectives, and collaboration policies must be addressed. The paper proposes a design framework for uncoordinated mobile sensing and one sensing approach based on profile estimation for target detection, field estimation, and edge detection. With simulations, we study its strengths and tradeoffs with stationary and controlled mobile approaches. [ABSTRACT FROM AUTHOR]

Sensor localization can be divided into two categories: range-based approaches, and rang-free approaches. Although range-based approaches tend to be more accurate than range-free approaches, they are more sensitive to errors in distance measurement. Despite of the efforts on recovering sensors' Euclidean coordinates from erroneous distance measurements, as will be illustrated in this paper, they are still prone to distance errors, particularly in an obstruction abundant environment. In this paper, we propose a new algorithm for sensor localization based on Multiscale Radio Transmission Power(MRTP). It gradually increases the scale level of transmission power, and the distance is determined by the minimal scale of received signals. Unlike the range-based approaches, which treat each measured distance as an approximation of the true one, in our new approach, the measured distance serves as a constraint that limits the feasible location of sensors. Our simulations have shown that the MRTP-based approach is able to provide accurate and robust estimation of location, especially in an area abundant in obstructions, where most current approaches fail to perform well. [ABSTRACT FROM AUTHOR]

The next generation wireless communication devices are expected to be capable of communicating with the best possible network as well as to utilize multiple networks, simultaneously. Existing solutions such as the interoperability mechanisms and the Always Best Connected (ABC) paradigm limit the access of wireless devices to only one, preferably the best possible network. Such schemes, though found to be better than the traditional single interface communication, are limited in their ability to utilize the services in the best possible way. Existing work focuses mainly on network layer or transport layer bandwidth aggregation mechanisms which either need to change the existing TCP protocol or require proxy nodes to perform the bandwidth scheduling process. We, in this paper, propose a new wireless access paradigm for multi-homed hosts based on a session layer bandwidth aggregation mechanism. The major advantages of our solution are the high end-to-end throughput, glitch free transition during both mobility and interface changes, dynamic selection of number of end-to-end paths, and above all our solution can work with existing transport and network layer protocols in today's Internet. In this paper, we provide the architectural and protocol solutions for the proposed scheme and results from extensive simulations and a Linux based implementation. [ABSTRACT FROM AUTHOR]

In this paper we approach the solution of large instances of the distribution design problem. Traditional approaches do not consider that the size of the instances can significantly affect the efficiency of the solution process. This paper shows the feasibility to solve large scale instances of the distribution design problem by compressing the instance to be solved. The goal of the compression is to obtain a reduction in the amount of resources needed to solve the original instance, without significantly reducing the quality of its solution. In order to preserve the solution quality, the compression summarizes the access pattern of the original instance using clustering techniques. In order to validate the approach we tested it on a new model of the replicated version of the distribution design problem that incorporates generalized database objects. The experimental results show that our approach permits to reduce the computational resources needed for solving large instances, using an efficient clustering algorithm. We present experimental evidence of the clustering efficiency of the algorithm. [ABSTRACT FROM AUTHOR]

An efficient deployment of a mobile Ad Hoc network (MANET) requires a realistic approach towards the mobility of the hosts who want to communicate with each other over a wireless channel. Since Ad Hoc networks are driven by the human requirements, instead of considering the random movement of the mobile nodes, we concentrate on the social desire of the nodes for getting connected with one another and provide here a framework for the mobility model of the nodes based on Social Network Theory. In this paper, we capture the preferences in choosing destinations of pedestrian mobility pattern on the basis of social factor (ψF) and try to find out the essential impact of ψF on the pause time of the nodes. Further, our paper also provides a mobility distribution pattern, and a relative comparison has been done with Random Way- Point (RWP) Model under a certain constrained simulation. [ABSTRACT FROM AUTHOR]

The impact of different routing and wavelength assignment algorithms on the in-band crosstalk performance of a 4 x 4 mesh-torus and a 15-node network has been studied. This paper considers both switch-induced crosstalk and the crosstalk induced by the multiplexers and demultiplexers. Fixed routing and fixed-alternate routing of connection requests have been considered. First-fit and random wavelength assignment algorithms have been employed. A crosstalk-aware wavelength assignment has also been considered. In-band crosstalk leads to poor received signal quality at the destination node. This results in increased receiver bit error rate (BER). This implies that some of the routes will deliver a signal quality which is unsatisfactory. To ensure that no resources are wasted on those connections which cannot deliver an unacceptable signal quality, this paper uses an event-driven simulation which incorporates on-line BER calculations. A call request is accepted only if the BER at the destination node is less than 10-12; otherwise it is rejected. [ABSTRACT FROM AUTHOR]

The fundamental question considered in this paper is when program Q, if executed immediately after program P, is guaranteed not to interfere with P and be safe from interference by P. If a message sent by one of these programs is received by the other, it may affect and modify the other's execution. The notion of communication closed layers (CCLs) introduced by Elrad and Francez in 1982 is a useful tool for studying such interference. CCLs have been considered mainly in the context of reliable FIFO channels (without duplication), where one can design programs layers that do not interfere with any other layer. When channels are less than perfect such programs are no longer feasible. The absence of interference between layers becomes context-dependent. In this paper we study the impact of message duplication and loss on the safety on the safety of layer composition. Using a communication phase operator, the fits after relation among programs is defined. If program Q fits after P then P and Q will not interfere with each other in executions of . For programs P and Q in a natural class of programs we outline efficient algorithms for the following: (1) deciding whether Q fits after P; (2) deciding whether QsealsP, meaning that Q fits after P and no following program can communicate with P; and (3) constructing a separatorS that both fits after P and satisfies that Q fits after . [ABSTRACT FROM AUTHOR]

This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling gives each node v of G a label containing the port numbers of all the tree edges incident to v. The upward tree labeling labels each node v by the number of the port leading from v to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted Mup(T) and Sup(T) for and Mall(T) and Sall(T) for . The problem studied in this paper is the following: Given a graph G and a predefined port labeling for it, with the ports of each node v numbered by , select a rooted spanning tree for G minimizing (one of) these measures. We show that the problem is polynomial for Mup(T), Sup(T) and Sall(T) but NP-hard for Mall(T) (even for 3-regular planar graphs). We show that for every graph G and port numbering there exists a spanning tree T for which Sup(T) = O(n log log n). We give a tight bound of O(n) in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port assignments. We conclude by discussing some applications for our tree representation schemes. [ABSTRACT FROM AUTHOR]

Complex and large-scale distributed systems are characterized by numerous interactive data communication among distributed components over network. This paper proposes a communication data multiplexing approach as an efficient message traffic reduction scheme. This approach encodes joint outputs of sender components into a single message and applies to a distributed system involving components moving and interacting in multi-dimensional space. For performance evaluation, this paper applies uses a projectile/missile case study with realistic multi-dimensional dynamics. This paper investigates variation of system accuracy and network bandwidth requirement, while a ratio of active components and a time granule are varied. Analytical and empirical data clearly indicate the advantages of multiplexing in saving communication resources in a large-scale distributed simulation. In addition, this paper discusses effectiveness and limitation of the multiplexing approach while considering the tradeoff between system accuracy and performance. [ABSTRACT FROM AUTHOR]

Computational Grids provide an emerging highly distributed computing platform for scientific computing. Recently, service oriented architecture (SOA) is a trend of implementing software systems including Grid computing systems. SOA provides more flexibilities for Grid users at the service level. Since performance is still one of the major concerns in Grid environments, Grid service performance issues needs to be extensively investigated and studied. However, a lot of issues are still open to be explored and few work has been done on them. In this paper, we propose a Grid service monitoring architecture for flexible monitoring on various Grid services. We implemented it for monitoring WSRF (Web Service Resource Framework) services in this paper. We show how the service oriented Grid monitor work with a simple example WSRF-compliant MathService. Moreover, the relationship of the monitor and Grid super scheduler is also analyzed. In this way, the scheduler may produce service performance oriented policies that ensure optimal quality of services for Grid applications. Keywords: Grid Performance Monitoring, Grid Service Performance, Service Oriented Grid Architecture. [ABSTRACT FROM AUTHOR]