13984646
A probabilistic polynomial-time process calculus for the analysis of cryptographic protocols
We prove properties of a process calculus that is designed for analysing security protocols. Our long-term goal is to develop a form of protocol analysis, consistent with standard cryptographic assumptions, that provides a language for expressing probabilistic polynomial-time protocol steps, a specification method based on a compositional form of equivalence, and a logical basis for reasoning about equivalence.The process calculus is a variant of CCS, with bounded replication and probabilistic polynomial-time expressions allowed in messages and boolean tests. To avoid inconsistency between security and nondeterminism, messages are scheduled probabilistically instead of nondeterministically. We prove that evaluation of any process expression halts in probabilistic polynomial time and define a form of asymptotic protocol equivalence that allows security properties to be expressed using observational equivalence, a standard relation from programming language theory that involves quantifying over all possible environments that might interact with the protocol.We develop a form of probabilistic bisimulation and use it to establish the soundness of an equational proof system based on observational equivalences. The proof system is illustrated by a formation derivation of the assertion, well-known in cryptography, that El Gamal encryption's semantic security is equivalent to the (computational) Decision Diffie-Hellman assumption. This example demonstrates the power of probabilistic bisimulation and equational reasoning for protocol security.
215952437
Beyond proof-of-compliance: security analysis in trust management
Trust management is a form of distributed access control that allows one principal to delegate some access decisions to other principals. While the use of delegation greatly enhances flexibility an...
9031501
Design of a role-based trust-management framework
We introduce the RT framework, a family of role-based trust management languages for representing policies and credentials in distributed authorization. RT combines the strengths of role-based access control and trust-management systems and is especially suitable for attribute-based access control. Using a few simple credential forms, RT provides localized authority over roles, delegation in role definition, linked roles, and parameterized roles. RT also introduces manifold roles, which can be used to express threshold and separation-of-duty policies, and delegation of role activations. We formally define the semantics of credentials in the RT framework by presenting a translation from credentials to Datalog rules. This translation also shows that this semantics is algorithmically tractable.
3062362
Managing Digital Rights using Linear Logic
Digital music players protect songs by enforcing licenses that convey specific rights for individual songs or groups of songs. For licenses specified in industry, we show that deciding whether a license authorizes a sequence of actions is NP-complete, with a restricted version of the problem solvable efficiently using a reduction to maximum network flow. The authorization algorithm used in industry is online, deciding which rights to exercise as actions occur, but we show that all online algorithms are necessarily non-monotonic: each allows actions under one license that it does not allow under a more flexible license. In one approach to achieving monotonicity, we exhibit the unique maximal set of licenses on which there exists a monotonic online algorithm. This set of well-behaved licenses induces an approximation algorithm by replacing each license with a well-behaved license. In a second approach, we consider allowing the player to revise its past decisions about which rights to exercise while still ensuring compliance with the license. We propose an efficient algorithm based on linear logic, with linear negation used to revise past decisions. We prove our algorithm monotonic, live, and sound with respect to the semantics of licenses
16397953
Parametricity and Variants of Girard's J Operator
Abstract The Girard–Reynolds polymorphic λ -calculus is generally regarded as a calculus of parametric polymorphism in which all well-formed terms are strongly normalizing with respect to β -reductions. Girard demonstrated that the addition of a simple “non-parametric” operation, J , to the calculus allows the definition of a non-normalizing term. Since the type of J is not inhabited by any closed term, one might suspect that this may play a role in defining a non-normalizing term using it. We demonstrate that this is not the case by giving a simple variant, J′ , of J whose type is otherwise inhabited and which causes normalization to fail. It appears that impredictivity is essential to the argument; predictive variants of the polymorphic λ -calculus admit non-parametric operations without sacrificing normalization.
18708753
Unification and ML-Type Reconstruction
We study the complexity of type reconstruction for a core fragment of ML with lambda abstraction, function application, and the polymorphic let declaration. We derive exponential upper and lower bounds on recognizing the typable core ML expressions. Our primary technical tool is uniication of succinctly represented type expressions. After observing that core ML expressions, of size n, can be typed in DTIME(2 n), we exhibit two diierent families of programs whose principal types grow exponentially. We show how to exploit the expressiveness of the let-polymorphism in these constructions to derive lower bounds on deciding typability: one leads naturally to NP-hardness and the other to DTIME(2 n k)-hardness for each integer k 1. Our generic simulation of any exponential time Turing Machine by ML type reconstruction may be viewed as a nonstandard way of computing with types. Our worst-case lower bounds stand in contrast to practical experience, which suggests that commonly used algorithms for type reconstruction do not slow compilation substantially.
10207039
A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane
We show that any rectilinear polygonal subdivision in the plane can be converted into a "guillotine" subdivision whose length is at most twice that of the original subdivision. "Guillotine" subdivisions have a simple recursive structure that allows one to search for "optimal" such subdivisions in polynomial time, using dynamic programming. In particular, a consequence of our main theorem is a very simple proof that the k-MST problem in the plane has a constant-factor polynomial-time approximation algorithm: we obtain a factor of 2 (resp., 3) for the L1 metric, and a factor of $2\sqrt{2}$ (resp., 3.266) for the L2 (Euclidean) metric in the case in which Steiner points are allowed (resp., not allowed).
608653
Distributed localization using noisy distance and angle information
Localization is an important and extensively studied problem in ad-hoc wireless sensor networks. Given the connectivity graph of the sensor nodes,along with additional local information (e.g. distances, angles, orientations etc.), the goal is to reconstruct the global geometry of the network. In this paper, we study the problem of localization with noisy distance and angle information. With no noise at all, the localization problem with both angle (with orientation) and distance information is trivial. However, in the presence of even a small amount of noise, we prove that the localization problem is NP hard.Localization with accurate distance information and relative angle information is also hard. These hardness results motivate our study of approximation schemes. We relax the non-convex constraints to approximating convex constraints and propose linear programs (LP) for two formulations of the resulting localization problem, which we call the weak deployment and strong deployment problems.These two formulations give upper and lower bounds on the location uncertainty respectively: No sensor is located outside its weak deployment region, and each sensor can be anywhere in its strong deployment region without violating the approximate distance and angle constraints. Though LP-based algorithms are usually solved by centralized methods, we propose distributed, iterative methods, which are provably convergent to the centralized algorithm solutions. We give simulation results for the distributed algorithms, evaluating the convergence rate, dependence on measurement noises,and robustness to link dynamics.
42803318
File Servers
This chapter discusses file servers that are accessible via some form of local network or internetwork. It characterizes file services from the client point of view along a number of dimensions; distributivity of the service itself, the network environment of the service, the file model supported by the service, the kind(s) of atomic update provided by the service, the techniques used for controlling the allocation of files. It then describes the client interfaces to three existing file services. Finally, the impact of these features on design and implementation is discussed. An appendix contains characterizations of a variety of existing network-based file services using the criteria developed in the chapter.
11907078
Optimal decomposition of polygonal models into triangle strips
Motivated by applications in computer graphics, we study the problem of computing an optimal encoding in "triangle strips" of a triangulation of a polygonal surface model. The goal is to facilitate the transmission and rendering of a polygonal model by decomposing its triangulation into a minimum number of "tristrips," each of which has its connectivity stored implicitly in the ordering of the data points. While this optimization problem has been conjectured to be hard, its complexity status has been open. We prove that the tristrip decomposition problem is, in fact, NP-complete. We also propose two methods for solving the problem to optimality, one based on an integer programming formulation, one based on a branch-and-bound scheme that relies on lower bounding techniques for its efficiency. We perform an extensive set of experiments to test the efficiencies of these methods and some of their variants. These methods have been integrated also with the practical system FTSG (Fast Triangle Strip Generator), in order to utilize optimization methods on small subproblems to improve the quality of the heuristic solutions obtained by FTSG. We use experimentation to judge the quality of the improvements.
57900050
Computational Geometry Column 42
A compendium of thirty previously published open problems in computational geometry is presented.