Vulnerabilities in Anonymous Credential Systems

We show the following:

(i) In existing anonymous credential revocation systems, the revocation authority can link the transactions of any user in a subset T of users in O(log|T|) fake failed sessions.

(ii) A concern about the DLREP-I anonymous credentials system described in [Stefan Brands: Rethinking public key infrastructure and Digital Certificates; The MIT Press, Cambridge Massachusetts, London England. ISBN 0-262-02491-8] and [Stefan Brands: A Technical Overview of Digital Credentials; February 2002 (was a white paper in credentica.com)].

Weakly useful sequences

An infinite binary sequence x is defined to be

(i) strongly useful if there is a computable time bound within which every decidable sequence is Turing reducible to x; and

(ii) weakly useful if there is a computable time bound within which all the sequences in a non-measure 0 subset of the set of decidable sequences are Turing reducible to x.

Juedes, Lathrop, and Lutz [Theorectical Computer Science 132 (1994) 37] proved that every weakly useful sequence is strongly deep in the sense of Bennett [The Universal Turing Machine: A Half-Century Survey, 1988, 227] and asked whether there are sequences that are weakly useful but not strongly useful. The present paper answers this question affirmatively. The proof is a direct construction that combines the martingale diagonalization technique of Lutz [SIAM Journal on Computing 24 (1995) 1170] with a new technique, namely, the construction of a sequence that is “computably deep” with respect to an arbitrary, given uniform reducibility. The abundance of such computably deep sequences is also proven and used to show that every weakly useful sequence is computably deep with respect to every uniform reducibility.

Programmable Rewriting Strategies in Haskell: — White Paper —

Programmable rewriting strategies provide a valuable tool for implementing traversal functionality in grammar-driven (or schema-driven) tools. The working Haskell programmer has access to programmable rewriting strategies via two similar options: (i) the Strafunski bundle for generic functional programming and language processing, and (ii) the “Scrap Your Boilerplate” approach to generic functional programming. Basic rewrite steps are encoded as monomorphic functions on datatypes. Rewriting strategies are polymorphic functions composed from appropriate basic strategy combinators.We will briefly review programmable rewriting strategies in Haskell. We will address the following questions:

• What are the merits of Haskellish strategies?

• What is the relation between strategic programming and generic programming?

• What are the challenges for future work on functional strategies?

On the relationship between parametrisation and invariance for curve functions

Many parametric curves, e.g., Splines and Lagrange, require sets of ‘parameter' functions to be specified in addition to control-, or interpolation-point sets. It is shown here that simple group theoretic methods can be applied to this type of curve function to provide complete answers to fundamental questions such as:

1. if the control point set is held fixed, under what conditions do different sets of parameter functions determine the same curve?

and the related question:

1. what properties are required of the parameter functions to ensure invariance of curve shape with respect to a given set of geometric transformations of the control point set?

Computational modeling issues and methods for the “regulatory problem” in engineering – Solutions to the structural dynamics and static frame problems

Many of the problems addressed through engineering analysis include a set of regulatory (or other) probabilistic requirements that must be demonstrated with some degree of confidence through the analysis. Problems cast in this environment can pose new challenges for computational analyses in both model validation and model-based prediction. The “regulatory problems” given for the “Sandia challenge problems exercise”, while relatively simple, provide an opportunity to demonstrate methods that address these challenges. This paper describes and illustrates methods that can be useful in analysis of the regulatory problem. Specifically, we discuss:

(1) an approach for quantifying variability and uncertainty separately to assess the regulatory requirements and provide a statement of confidence; and

(2) a general validation metric to focus the validation process on a specific range of the predictive distribution (the predictions near the regulatory threshold).

These methods are illustrated using the challenge problems. Solutions are provided for both the static frame and structural dynamics problems.

JUDGES: A descriptive group decision support system for the ranking of items

A set of tools for group decision support are presented. Decision problems involving several decision makers, here-after called judges, that have to rank several alternatives, are considered. The toolbox is called JUDGES. It includes the four following procedures:

• - a hierarchical representation of the judges allows to display the existing conflicts between groups of judges,

• - enhanced box-plots representations of the alternatives are generated in order to detect those that are responsible for the major conflicts,

• - specific advice is issued to each judge in order to reach more easily a consensus,

• - a general framework for a pairwise group preference structure is proposed, and can be used to finalise the decision.

These procedures are embedded in an interactive software, implemented on micro-computer, which currently simulates the use on a network. Actual network implementation is foreseen in the near future. Several applications are presented and future developments are discussed.

Lightweight Static Capabilities

We describe a modular programming style that harnesses modern type systems to verify safety conditions in practical systems. This style has three ingredients:

(i) A compact kernel of trust that is specific to the problem domain.

(ii) Unique names (capabilities) that confer rights and certify properties, so as to extend the trust from the kernel to the rest of the application.

(iii) Static (type) proxies for dynamic values.

We illustrate our approach using examples from the dependent-type literature, but our programs are written in Haskell and OCaml today, so our techniques are compatible with imperative code, native mutable arrays, and general recursion. The three ingredients of this programming style call for (1) an expressive core language, (2) higher-rank polymorphism, and (3) phantom types.

On systems of word equations with simple loop sets

Consider the infinite system S of word equations

For each , let T_k be the subsystem of S given by i{k,k+1,k+2}. We prove two properties of the above system.

(1) Let k≥1. If φ is a solution of T_k such that primitive roots of are of equal length, as well as primitive roots of , then φ is a solution of the whole S.

(2) If n=1 then, for any k≥2, a solution φ of T_k is also a solution of S.

Explicit Substitutions à la de Bruijn: the local and global way

Kamareddine and Nederpelt[9], resp. Kamareddine and Ríos [11] gave two calculi of explicit of substitutions highly influenced by de Bruijn's notation of the λ-calculus. These calculi added to the explosive pool of work on explicit substitution in the past 15 years. As far as we know, calculi of explicit substitutions: a) are unable to handle local substitutions, and b) have answered (positively or negatively) the question of the termination of the underlying calculus of substitutions. The exception to a) is the calculus of [9] where substitution is handled both locally and globally. However, the calculus of [9] does not satisfy properties like confluence and termination. The exception to b) is the λs_e-calculus of [11] for which termination of the s_e-calculus, the underlying calculus of substitutions, remains unsolved. This paper has two aims:

(i) To provide a calculus à la de Bruijn which deals with local substitution and whose underlying calculus of substitutions is terminating and confluent.

(ii) To pose the problem of the termination of the substitution calculus of [11] in the hope that it can generate interest as a termination problem which at least for curiosity, needs to be settled. The answer here can go either way. On the one hand, although the λσ-calculus [1] does not preserve termination, the σ-calculus itself terminates. On the other hand, could the non-preservation of termination in the λs_e-calculus imply the non-termination of the s_e-calculus?

Feedback affinization of nonlinear control systems

In this paper conditions for the nonlinear control system

to have a nonlinear feedback control

u=(x,v), vΩ′R^m′, m′m, 0Ω′

such that the nonlinear system takes a form of an affine system

are presented. All results require algebraic operations and differentiation of functions only.     

A relationship between difference hierarchies and relativized polynomial hierarchies

Chang and Kadin have shown that if the difference hierarchy over NP collapses to levelk, then the polynomial hierarchy (PH) is equal to thekth level of the difference hierarchy over ₂ ^p . We simplify their poof and obtain a slightly stronger conclusion: if the difference hierarchy over NP collapses to levelk, then PH collapses to (P _(k–1) ^NP )^NP, the class of sets recognized in polynomial time withk – 1 nonadaptive queries to a set in NP^NP and an unlimited number of queries to a set in NP. We also extend the result to classes other than NP: For any classC that has _m ^p -complete sets and is closed under _conj ^p -and _m ^NP -reductions (alternatively, closed under _disj ^p -and _m ^co-NP -reductions), if the difference hierarchy overC collapses to levelk, then PH ^C = (P _(k–1)–tt ^NP ) ^C . Then we show that the exact counting class C_P is closed under _disj ^p - and _m ^co-NP -reductions. Consequently, if the difference hierarchy over C_P collapses to levelk, then PH^PP(= PH^C_P) is equal to (P _(k–1)–tt ^NP )^PP. In contrast, the difference hierarchy over the closely related class PP is known to collapse.Finally we consider two ways of relativizing the bounded query class P _k–tt ^NP : the restricted relativization P _k–tt ^{NP C} and the full relativization (P _k–tt ^NP ) ^C . IfC is NP-hard, then we show that the two relativizations are different unless PH ^C collapses.Richard Beigel was supported in part by NSF Grants CCR-8808949 and CCR-8958528. Richard Chang was supported in part by NSF Research Grant CCR 88-23053. This work was done while Mitsunori Ogiwara was at the Department of Information Science, Tokyo Institute of Technology, Tokyo, Japan.     

Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?

The class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such functions are hard, for example, if TFNP is computable in polynomial-time does this imply the polynomial-time hierarchy collapses? By computing a multivalued function in deterministic polynomial-time we mean on every input producing one of the possible values of the function on that input. We give a relativized negative answer to this question by exhibiting an oracle under which TFNP functions are easy to compute but the polynomial-time hierarchy is infinite. We also show that relative to this same oracle, P≠UP and TFNP^NP functions are not computable in polynomial-time with an NP oracle.     

Preface: Volume 68 Issue 4

This issue contains the Proceedings of the First International Workshop on Parallel and Distributed Model Checking (PDMC 2002) held in Brno, Czech Republic, August 19, 2002 as a satellite event to the 13th International Conference on Concurrency Theory (CONCUR 2002).The aim of the PDMC 2002 workshop was to cover all aspects of parallel and distributed model checking and supporting techniques. The mission was on one side to introduce people to the field of parallel and distributed model checking and on the other side to be a working forum for describing new research building thus the relationship between people working in the area of parallel and distributed approaches to the verification of large-scale systems and to encourage cross-fertilization of ideas.The workshop programme consisted of:

2 invited talks, respectively by Moshe Vardi on Model Checking: A Complexity-Theoretic Perspective and by Orna Grumberg on Different directions in parallel and distributed model checking,

8 regular presentations, and

5 short presentations.

The proceedings contains the regular papersonly. The regular papers and short presentations have been accepted by the following programme committee:

Lubos Brim (MU Brno, Czech Republic) - Co-chair

Gianpiero Cabodi (Torino, Italy)

Hubert Garavel (INRIA, France)

Orna Grumberg (Technion, Israel) - Co-chair

Boudewijn R. Haverkort (Aachen, Germany)

Kim Larsen (BRICS Aalborg, Denmark)

Rajeev Ranjan (Real Intent, USA)

We would like to thank very much to all members of the programme committee for nice cooperation and for detailed reports and comments and to all the authors for their contributions. For online-information see http://www.fi.muni.cz/concur2002/PDMC/.

August 19, 2002	Lubos Brim
	Orna Grumberg

Full-size table

     

On relativizations with restricted number of accesses to the oracle set

Conflicting relativizations, also known as Baker-Gill-Solovay phenomena, are common place in complexity theory. However, Book, Long, and Selman (SIAM J. Comput.,13 (1984), 461–487) have shown thatP(A) = NP _B (A) for all oraclesA if and only ifP = NP, whereNP _B (A) denotes the class of languages accepted by nondeterministic machines which possess only a polynomial number of query strings in the computation tree. It is shown in this paper that any superpolynomial bound on the number of queries already yields the BGS phenomenon. Similar results hold for theNP = co-NP andNPC = NP questions. A second objective of this paper is to point out a technique of Hartmanis with which to achieve oracle constructions by using the Kolmogorov complexity. This relatively new technique seems to be adequate for obtaining separation results for complexity classes which are not enumerable.     

MRT: A tool developed for predicting the mean message response time of communication channels in sizeable networks exemplified by the Internet

In this paper an algorithm M²RT for predicting the mean message response time (MMRT) of a communication channel is proposed with emphasis on Internet applications. The M²RT development went through four major phases. They include:

(a) Formulating the theoretical foundation with the central limit theorem.

(b) Determining the parameters of the algorithm by simulations.

(c) Performing off-line verification tests for the algorithm with local Internet/Intranet nodes and well-known middleware (MPI and CORBA).

(d) Performing on-line validation of the M²RT over the Internet involving both local and international sites.

The acceptance criteria for the algorithm include:

(a) It must perform efficiently for different conditions of workload, geography, and traffic.

(b) It must perform consistently with the same software entities (e.g., MPI) for similar operations.

(c) It must be able to exist both as an off-line tool and an on-line program object (to be invoked on a real-time basis).

(d) Its computation time should be sufficiently small so that the result actually reflects the current physical conditions.

All the results from simulations, verification tests, and validation experiments have confirmed that the M²RT algorithm indeed meets all the acceptance criteria. In these tests, we also discovered that the algorithm could be developed into a powerful tool for measuring the relative performance between firmware products. This development will be explored in the near future.     

The complexity of stochastic games

We consider the complexity of stochastic games—simple games of chance played by two players. We show that the problem of deciding which player has the greatest chance of winning the game is in the class NP co-NP.     

Sample complexity of worst-case H-identification

We show that the sample complexity of qorst-case H^∞-identification is of order n², by proving that the minimal length of a fractional H^∞-cover for C_n, regarded as the linear space of complex-valued sequences of length n, is of order n². A unit vector u in ^∞ is a fractional H^∞-cover for C_n if for some

Full-size image

for all rh ε C_n, where is the z-transform of h. We also give similar results for real-valued sequences.     

Exact Transversal Hypergraphs and Application to Boolean μ-Functions

Call an hypergraph, that is a family of subsets (edges) from a finite vertex set, an exact transversal hypergraph iff each of its minimal transversals, i.e., minimal vertex subsets that intersect each edge, meets each edge in a singleton. We show that such hypergraphs are recognizable in polynomial time and that their minimal transversals as well as their maximal independent sets can be generated in lexicographic order with polynomial delay between subsequent outputs, which is impossible in the general case unless P= NP. The results obtained are applied to monotone Boolean μ-functions, that are Boolean functions defined by a monotone Boolean expression (that is, built with ∧, ∨ only) in which no variable occurs repeatedly. We also show that recognizing such functions from monotone Boolean expressions is co-NP-hard, thus complementing Mundici's result that this problem is in co-NP.     

Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds

We show that if Arthur-Merlin protocols can be derandomized, then there is a language computable in deterministic exponential-time with access to an NP oracle that requires circuits of exponential size. More formally, if every promise problem in prAM, the class of promise problems that have Arthur-Merlin protocols, can be computed by a deterministic polynomial-time algorithm with access to an NP oracle, then there is a language in E^NP that requires circuits of size Ω(2 ⁿ /n). The lower bound in the conclusion of our theorem suffices to construct pseudorandom generators with exponential stretch.