14904191
Games and the Impossibility of Realizable Ideal Functionality
A cryptographic primitive or a security mechanism can be specified in a variety of ways, such as a condition involving a game against an attacker, construction of an ideal functionality, or a list of properties that must hold in the face of attack. While game conditions are widely used, an ideal functionality is appealing because a mechanism that is indistinguishable from an ideal functionality is therefore guaranteed secure in any larger system that uses it. We relate ideal functionalities to games by defining the set of ideal functionalities associated with a game condition and show that under this definition, which reflects accepted use and known examples, bit commitment, a form of group signatures, and some other cryptographic concepts do not have any realizable ideal functionality.
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...
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.
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
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.
2490428
A maximumb-matching problem arising from median location models with applications to the roommates problem
We consider maximumb-matching problems where the nodes of the graph represent points in a metric space, and the weight of an edge is the distance between the respective pair of points. We show that if the space is either the rectilinear plane, or the metric space induced by a tree network, then theb-matching problem is the dual of the (single) median location problem with respect to the given set of points. This result does not hold for the Euclidean plane. However, we show that in this case theb-matching problem is the dual of a median location problem with respect to the given set of points, in some extended metric space. We then extend this latter result to any geodesic metric in the plane. The above results imply that the respective fractionalb-matching problems have integer optimal solutions. We use these duality results to prove the nonemptiness of the core of a cooperative game defined on the roommate problem corresponding to the above matching model. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
7212084
Finding large sticks and potatoes in polygons
We study a class of optimization problems in polygons that seek to compute the "largest" subset of a prescribed type, e.g., a longest line segment ("stick") or a maximum-area triangle or convex body ("potato"). Exact polynomial-time algorithms are known for some of these problems, but their time bounds are high (e.g., O(n7) for the largest convex polygon in a simple n-gon). We devise efficient approximation algorithms for these problems. In particular, we give near-linear time algorithms for a (1 - ∈)-approximation of the biggest stick, an O(1)-approximation of the maximum-area convex body, and a (1 - ∈)-approximation of the maximum-area fat triangle or rectangle. In addition, we give efficient methods for computing large ellipses inside a polygon (whose vertices are a dense sampling of a closed smooth curve). Our algorithms include both deterministic and randomized methods, one of which has been implemented (for computing large area ellipses in a well sampled closed smooth curve).
37648029
Folding flat silhouettes and wrapping polyhedral packages: New results in computational origami
Abstract We show a remarkable fact about folding paper: from a single rectangular sheet of paper, one can fold it into a flat origami that takes the (scaled) shape of any connected polygonal region, even if it has holes. This resolves a long-standing open problem in origami design. Our proof is constructive, utilizing tools of computational geometry, resulting in efficient algorithms for achieving the target silhouette. We show further that if the paper has a different color on each side, we can form any connected polygonal pattern of two colors. Our results apply also to polyhedral surfaces, showing that any polyhedron can be “wrapped” by folding a strip of paper around it. We give three methods for solving these problems: the first uses a thin strip whose area is arbitrarily close to optimal; the second allows wider strips to be used; and the third varies the strip width to optimize the number or length of visible “seams” subject to some restrictions.
5235672
An Efficient Algorithm for Euclidean Shortest Paths Among Polygonal Obstacles in the Plane
Abstract. We give an algorithm to compute a (Euclidean) shortest path in a polygon with h holes and a total of n vertices. The algorithm uses O(n) space and requires 
 $O(n+h^2\log n)$ time.
207159283
Minimum-cost coverage of point sets by disks
We consider a class of geometric facility location problems in which the goal is to determine a set <i>X</i> of disks given by their centers <i>(t<sub>j</sub>)</i> and radii <i>(r<sub>j</sub>)</i> that cover a given set of demand points <i>Y∈R</i><sup>2</sup> at the smallest possible cost. We consider cost functions of the form Ε<i><sub>j</sub>f(r<sub>j</sub>)</i>, where <i>f(r)=r</i><sup>α</sup> is the cost of transmission to radius <i>r</i>. Special cases arise for α=1 (sum of radii) and α=2 (total area); power consumption models in wireless network design often use an exponent α>2. Different scenarios arise according to possible restrictions on the transmission centers <i>t<sub>j</sub></i>, which may be constrained to belong to a given discrete set or to lie on a line, etc.We obtain several new results, including (a) exact and approximation algorithms for selecting transmission points <i>t<sub>j</sub></i> on a given line in order to cover demand points <i>Y∈R</i><sup>2</sup>; (b) approximation algorithms (and an algebraic intractability result) for selecting an optimal line on which to place transmission points to cover <i>Y</i>; (c) a proof of NP-hardness for a discrete set of transmission points in <i>R<sup>2</sup></i> and any fixed α>1; and (d) a polynomial-time approximation scheme for the problem of computing a <i>minimum cost covering tour</i> (MCCT), in which the total cost is a linear combination of the transmission cost for the set of disks and the length of a tour/path that connects the centers of the disks.