|
Anonymous Identification in Ad-Hoc Groups
|
|
Yevgeniy Dodis, Aggelos Kiayias, Antonio Nicolosi and Victor Shoup
|
|
Proceedings of Advances in Cryptology --- Eurocrypt 2004,
to appear, Lecture Notes in Computer Science, Springer 2004.
|
| Abstract.
We introduce Ad-hoc Anonymous Identification schemes, a new
multi-user cryptographic primitive that allows participants from a
user population to form ad-hoc groups and then prove membership
anonymously in such groups.
Our schemes are based on the notion of accumulator with
one-way domain , a natural extension of cryptographic accumulators we
introduce in this work.
We provide a formal model for Ad hoc Anonymous Identification schemes
and design secure such schemes both generically (based
on any accumulator with one-way domain) and for a specific
efficient implementation of such an accumulator based on
the Strong RSA Assumption.
A salient feature of our approach is that all the identification
protocols take time independent of the size of the ad-hoc group.
All our schemes and notions can be generally and efficiently amended
so that they allow the recovery of the signer's identity by an
authority, if the latter is desired.
Using the Fiat-Shamir transform, we also obtain
constant-size, signer-ambiguous group and ring signatures (provably
secure in the Random Oracle Model). For ring signatures, this is the
first such constant-size scheme, as all the previous proposals had
signature size proportional to the size of the ring. For group
signatures, we obtain schemes comparable in performance with
state-of-the-art schemes, with the additional feature that the role of
the group manager during key registration is extremely simple and
essentially passive: all it does is accept the public key of
the new member (and update the constant-size public key of the
group).
|
Download: [pdf]] [ps] [BibTeX]
[link]
|
|
|
Traceable Signatures
|
|
Aggelos Kiayias, Yiannis Tsiounis and Moti Yung
|
|
Proceedings of Advances in Cryptology --- Eurocrypt 2004,
to appear, Lecture Notes in Computer Science, Springer 2004.
|
| Abstract.
This work presents a new privacy primitive called
``Traceable Signatures'', together with an efficient
provably secure implementation.
To this end, we develop the underlying
mathematical and protocol tools, present the concepts and the underlying
security model, and then realize the scheme and its security proof.
Traceable signatures support an extended set of fairness mechanisms
(mechanisms for anonymity management and revocation) when compared
with the traditional group signature mechanism.
The extended functionality of traceable signatures is needed for proper
operation and adequate level of privacy in various settings and
applications. For example, the new notion allows (distributed)
tracing of all signatures of a single (misbehaving) party without
opening signatures and revealing identities of any other user in the
system.
In contrast, if such tracing is implemented by a state of the art
group signature system, such wide opening of all signatures of a
single user is a (centralized) operation that requires the opening
of all anonymous signatures and revealing the users associated
with them, an act that violates the privacy of all users.
To allow efficient implementation of our scheme we develop a number of
basic tools, zero-knowledge proofs, protocols, and primitives that we
use extensively throughout. These novel mechanisms work directly over
a group of unknown order, contributing to the efficiency and
modularity of our design, and may be of independent interest.
The interactive version of our signature scheme yields the notion of
``traceable (anonymous) identification.''
|
Download: [pdf]] [ps] [BibTeX]
[link]
|
|
|
The Vector-Ballot E-Voting Approach
|
|
Aggelos Kiayias and Moti Yung
|
|
Proceedings of the eight international Conference on Financial Cryptography 2004,
to appear, Lecture Notes in Computer Science, Springer 2004..
|
| Abstract.
Looking at current cryptographic-based e-voting protocols, one
can distinguish three
basic design paradigms (or approaches): (a) Mix-Networks based, (b)
Homomorphic Encryption based, and (c) Blind Signatures based.
Each of the three possesses different advantages and
disadvantages w.r.t. the {\em basic properties} of (i) efficient
tallying, (ii) universal verifiability, and (iii) allowing write-in
ballot capability (in addition to predetermined candidates). In fact,
none of the approaches results in a scheme that simultaneously
achieves all three.
This is unfortunate, since the three basic properties are crucial for
efficiency, integrity and versatility (flexibility), respectively.
Further, one can argue that a serious business offering of voting
technology should offer a flexible technology that achieves various
election goals with a single user interface.
This motivates our goal, which is to suggest a new
``vector-ballot'' based approach for secret-ballot e-voting
that is based on three new
notions: Provably Consistent Vector Ballot Encodings,
{\em Shrink-and-Mix Networks} and
Punch-Hole-Vector-Ballots.
At the heart of our approach is the combination of mix networks
and homomorphic encryption under a single user interface; given
this, it is rather surprising that it achieves much more than any
of the previous approaches for e-voting achieved in terms of the
basic properties. Our approach is presented in two generic designs
called ``homomorphic vector-ballots with
write-in votes'' and ``multi-candidate punch-hole
vector-ballots''; both of our designs can be instantiated over any
homomorphic encryption function.
|
Download: [ pdf] [ps] [BibTeX]
[link]
|
|
|
Scalable public-key tracing and revoking
|
|
Yevgeniy Dodis, Nelly Fazio, Aggelos Kiayias and Moti Yung
|
|
Proceedings of the twenty-second annual symposium on Principles of distributed computing (PODC)
2003. Boston, USA. ACM Press. pp. 190-199.
|
| Abstract.
Traitor Tracing Schemes constitute a very useful tool against piracy in the context of digital content broadcast. In such multi-recipient encryption schemes, each decryption key is fingerprinted and when a pirate decoder is discovered, the authorities can trace the identities of the users that contributed in its construction (called traitors). Public-key traitor tracing schemes allow for a multitude of non trusted content providers using the same set of keys, which makes the scheme "server-side scalable." To make such schemes also "client-side scalable," i.e. long lived and usable for a large population of subscribers that changes dynamically over time, it is crucial to implement efficient Add-user and Remove-user operations. Previous work on public-key traitor tracing did not address this dynamic scenario thoroughly, and there is no efficient scalable public key traitor tracing scheme that allows an increasing number of Add-user and Remove-user operations.To address these issues, we introduce the model of Scalable Public-Key Traitor Tracing, and present the first construction of such a scheme. Our model mandates for deterministic traitor tracing and an unlimited number of efficient Add-user operations and Remove-user operations. A scalable system achieves an unlimited number of revocations while retaining high level of efficiency by dividing the run-time of the system into periods. Each period has a saturation level for the number of revocations. When a period becomes saturated, an efficient new-period operation is issued by the system server that resets the saturation level. We present a formal adversarial model for our system taking into account its periodic structure, and we prove our construction secure, both against adversaries that attempt to cheat the revocation mechanism as well as against adversaries that attempt to cheat the traitor tracing mechanism.
|
Download: [pdf] [ps] [BibTeX]
[ link ]
|
|
|
Decoding of Interleaved Reed Solomon Codes over Noisy Data
|
|
Daniel Bleichenbacher, Aggelos Kiayias and Moti Yung
|
|
Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP)
Springer, Lecture Notes in Computer Science Volume 2719, pp. 97-108.
|
| Abstract.
We consider error-correction over the Non-Binary Symmetric Channel (NBSC) which is a natural probabilistic extension of the Binary Symmetric Channel (BSC). We propose a new decoding algorithm for interleaved Reed-Solomon Codes that attempts to correct all "interleaved" codewords simultaneously. In particular, interleaved encoding gives rise to multi-dimensional curves and more specifically to a variation of the Polynomial Reconstruction Problem, which we call Simultaneous Polynomial Reconstruction. We present and analyze a novel probabilistic algorithm that solves this problem. Our construction yields a decoding algorithm for interleaved RS-codes that allows efficient transmission arbitrarily close to the channel capacity in the NBSC model.
|
Download: [pdf] [ps] [BibTeX]
[ link ]
|
|
|
Extracting Group Signatures from Traitor Tracing Schemes
|
|
Aggelos Kiayias and Moti Yung
|
|
Proceedings of Advances in Cryptology - EUROCRPYT 2003: International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003. Springer, Lecture Notes in Computer Science,
Volume 2656, pp. 630 - 648.
|
| Abstract.
Digital Signatures emerge naturally from Public-Key Encryption based on trapdoor permutations, and the "duality" of the two primitives was noted as early as Diffie-Hellman's seminal work. The present work is centered around the crucial observation that two well known cryptographic primitives whose connection has not been noticed so far in the literature enjoy an analogous "duality." The primitives are Group Signature Schemes and Public-Key Traitor Tracing. Based on the observed "duality," we introduce new design methodologies for group signatures that convert a traitor tracing scheme into its "dual" group signature scheme.
Our first methodology applies to generic public-key traitor tracing schemes. We demonstrate its power by applying it to the Boneh-Franklin scheme, and obtaining its "dual" group signature. This scheme is the first provably secure group signature scheme whose signature size is not proportional to the size of the group and is based only on DDH and a random oracle. The existence of such schemes was open. Our second methodology introduces a generic way of turning any group signature scheme with signature size linear in the group size into a group signature scheme with only logarithmic dependency on the group size. To this end it employs the notion of traceability codes (a central component of combinatorial traitor tracing schemes already used in the first such scheme by Chor, Fiat and Naor). We note that our signatures, obtained by generic transformations, are proportional to a bound on the anticipated maximum malicious coalition size. Without the random oracle assumption our schemes give rise to provably secure and efficient Identity Escrow schemes.
|
Download: [pdf] [ps] [BibTeX]
[ link ]
|
|
|
Non-interactive Zero-Sharing with Applications to Private Distributed Decision Making
|
|
Aggelos Kiayias and Moti Yung
|
|
Proceedings of the Seventh International Financial Cryptography Conference 2003.
Springer, Lecture Notes in Computer Science, Volume 2742, pp. 303 - 320.
|
| Abstract.
We employ the new primitive of non-interactive zero-sharing to realize efficiently and privately various ``distributed decision making'' procedures. Our methodology emphasizes non-interactiveness and universal verifiability. Non-interactiveness suggests that there is no bilateral communication between the active participants; instead decision making is achieved by unilateral communication between active participants and a security-wise non-trusted server that participates faithfully in the protocol. Universal verifiability suggests that the participants' actions produce a public audit trail ensuring publicly that they have followed the protocol's specifications. Based on non-interactive zero-sharing, we present constructions for a private veto protocol, a protocol for simultaneous disclosure of information and a privacy-enhancing ``plug-in'' tool for electronic voting that can be incorporated in homomorphic-encryption based schemes. Keywords. Distributed Decision Making, Privacy, Veto, Simultaneous Disclosure, Electronic Voting, Proofs of Knowledge.
|
Download: [pdf] [ps] [BibTeX]
[ link ]
|
|
|
Breaking and Repairing Asymmetric Public-Key Traitor Tracing
|
|
Aggelos Kiayias and Moti Yung
|
|
Proceedings of Digital Rights Management: DRM 2002, Washington, DC, USA, Revised Papers.
Springer, Lecture Notes in Computer Science, Volume 2696, pp. 32-50.
|
| Abstract.
Traitor tracing schemes are a very useful tool for preventing piracy in digital content distribution systems. A traitor tracing procedure allows the system-manager to reveal the identities of the subscribers that were implicated in the construction of a pirate-device that illegally receives the digital content (called traitors). In an important variant called asymmetric traitor tracing, the system-manager is not necessarily trusted, thus the tracing procedure must produce undeniable proof of the implication of the traitor subscribers. This non-repudiation property of asymmetric schemes has the potential to significantly increase the effectiveness of the tracing procedure against piracy.
In this work, we break the two previous proposals for efficient asymmetric public-key traitor tracing, by showing how traitors can evade the proposed traitor tracing procedures. Then, we present a new efficient Asymmetric Public-Key Traitor Tracing scheme for which we prove its traceability in detail (in the non-black-box model); to the best of our knowledge this is the first such scheme. Our system is capable of proving the implication of all traitors that participate in the construction of a pirate-key. We note that even though we break the earlier schemes we employ some of their fundamental techniques and thus consider them important developments towards the solution.
|
Download: [pdf] [ps] [BibTeX]
[ link ]
|
|
|
Traitor Tracing with Constant Transmission Rate
|
|
Aggelos Kiayias and Moti Yung
|
|
Proceedings of Advances in Cryptology - EUROCRYPT 2002: International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands.
Springer, Lecture Notes in Computer Science, Volume 2332, pp. 450-465.
|
| Abstract.
An important open problem in the area of Traitor Tracing is designing a scheme with constant expansion of the size of keys (users' keys and the encryption key) and of the size of ciphertexts with respect to the size of the plaintext. This problem is known from the introduction of Traitor Tracing by Chor, Fiat and Naor. We refer to such schemes as traitor tracing with constant transmission rate. Here we present a general methodology and two protocol constructions that result in the first two public-key traitor tracing schemes with constant transmission rate in settings where plaintexts can be calibrated to be sufficiently large. Our starting point is the notion of "copyrighted function" which was presented by Naccache, Shamir and Stern. We first solve the open problem of discrete-log-based and public-key-based "copyrighted function." Then, we observe the simple yet crucial relation between (public-key) copyrighted encryption and (public-key) traitor tracing, which we exploit by introducing a generic design paradigm for designing constant transmission rate traitor tracing schemes based on copyrighted encryption functions. Our first scheme achieves the same expansion efficiency as regular ElGamal encryption. The second scheme introduces only a slightly larger (constant) overhead, however, it additionally achieves efficient black-box traitor tracing (against any pirate construction).
|
Download: [pdf] [ps] [BibTeX]
[ link ]
|
|
|
Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes
|
|
Aggelos Kiayias and Moti Yung
|
|
Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP)
Springer, Lecture Notes in Computer Science Volume 2380, pp. 232-243.
|
| Abstract.
We investigate the decoding problem of Reed-Solomon Codes (aka: the Polynomial Reconstruction Problem - PR) from a cryptographic hardness perspective. Following the standard methodology for constructing cryptographically strong primitives, we formulate a decisional intractability assumption related to the PR problem. Then, based on this assumption we show: (i) hardness of partial information extraction and (ii) pseudorandomness. This lays the theoretical framework for the exploitation of PR as a basic cryptographic tool which, as it turns out, possesses unique properties. One such property is the fact that in PR, the size of the corrupted codeword (which corresponds to the size of a ciphertext and the plaintext) and the size of the index of error locations (which corresponds to the size of the key) are independent and can even be super-polynomially related. We then demonstrate the power of PR-based cryptographic design by constructing a stateful cipher.
|
Download: [pdf] [ps] [BibTeX]
[ link ]
|
|
|
Self-tallying Elections and Perfect Ballot Secrecy
|
|
Aggelos Kiayias and Moti Yung
|
|
Proceedings of Public Key Cryptography: 5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002, Paris, France. Springer, Lecture Notes in Computer Science, Volume 2274, pp. 141-158.
|
| Abstract.
Strong voter privacy, although an important property of an election scheme, is usually compromised in election protocol design in favor of other (desirable) properties. In this work we introduce a new election paradigm with strong voter privacy as its primary objective. Our paradigm is built around three useful properties of voting schemes we define: (1) Perfect Ballot Secrecy, ensures that knowledge about the partial tally of the ballots of any set of voters is only computable by the coalition of all the remaining voters (this property captures strong voter privacy as understood in real world elections). (2) Self-tallying, suggests that the post-ballot-casting phase is an open procedure that can be performed by any interested (casual) third party. Finally, (3) Dispute-freeness, suggests that disputes between active parties are prevented altogether, which is an important efficient integrity component.
We investigate conditions for the properties to exist, and their implications. We present a novel voting scheme which is the first system that is dispute-free, self-tallying and supports perfect ballot secrecy. Previously, any scheme which supports (or can be modified to support) perfect ballot secrecy suffers from at least one of the following two deficiencies: it involves voter-to-voter interactions and/or lacks fault tolerance (one faulty participant would fail the election). In contrast, our design paradigm obviates the need for voter-to-voter interaction (due to its dispute-freeness and publicly verifiable messages), and in addition our paradigm suggests a novel "corrective fault tolerant" mechanism. This mechanism neutralizes faults occurring before and after ballot casting, while self-tallying prevents further faults. Additionally, the mechanism is secrecy-preserving and "adaptive" in the sense that its cost is proportional to the number of faulty participants. As a result, our protocol is more efficient and robust than previous schemes that operate (or can be modified to operate) in the perfect ballot secrecy setting.
|
Download: [pdf] [ps] [BibTeX]
[ link ]
|
|
|
Acceptor-Definable Counting Classes
|
|
Aggelos Kiayias, Aris Pagourtzis, Kiron Sharma and Stathis Zachos
|
|
Proceedings of the Panhellenic Conference on Informatics 2001, PostProceedings,
Springer, 2003, Lecture Notes in Computer Science, Volume 2563, pp. 453-463.
|
| Abstract.
Counting functions that can be defined on non-deterministic acceptors (Turing machines without output), as opposed to those defined by transducers (Turing machines with output), have attracted much interest since 1979, when Valiant introduced the important class #P [19]. Apart from #P, several such classes have been defined in the literature [2,5,3,12,6]. Here we study the path-order complexity classes RAP, LAP and MAP, introduced in [6], which consist of functions that output the order of the rightmost, leftmost and middle accepting computation path (respectively) of a polynomial-time non-deterministic Turing acceptor (PNTM). We also consider TotP [6], the class of functions that output the total number of paths of a PNTM. We show several properties of these classes. In particular we prove that RAP and LAP are are equivalent under the Cook[1] sense with #P and TotP. This implies that all these classes are equally powerful when used as oracles to a polynomial computation, even if only one query is allowed. We also show that problems #PERFECT MATCHINGS and #DNF-SAT are complete for RAP and LAP in the Cook[1] sense and for MAP in the Cook sense. Path-order classes give rise to corresponding path-order operators; these operators applied on the class NP provide alternative characterizations for known classes of optimization problems. Using these characterizations, we present natural complete problems for optimization classes.
|
Download: [pdf] [ps] [BibTeX]
[ link ]
|
|
|
Self Protecting Pirates and Black-Box Traitor Tracing
|
|
Aggelos Kiayias and Moti Yung
|
|
Proceedings of CRYPTO 2001, 21st Annual International Cryptology Conference
Springer, Lecture Notes in Computer Science Volume 2139, pp. 63-79.
|
| Abstract.
We present a new generic black-box traitor tracing model in which the pirate-decoder employs a self-protection technique. This mechanism is simple, easy to implement in any (software or hardware) device and is a natural way by which a pirate (an adversary) which is black-box accessible, may try to evade detection. We present a necessary combinatorial condition for black-box traitor tracing of self-protecting devices. We constructively prove that any system that fails this condition, is incapable of tracing pirate-decoders that contain keys based on a superlogarithmic number of traitor keys. We then combine the above condition with specific properties of concrete systems. We show that the Boneh-Franklin (BF) scheme as well as the Kurosawa-Desmedt scheme have no black-box tracing capability in the self-protecting model when the number of traitors is superlogarithmic, unless the ciphertext size is as large as in a trivial system, namely linear in the number of users. This partially settles in the negative the open problem of Boneh and Franklin regarding the general black-box traceability of the BF scheme: at least for the case of superlogarithmic traitors. Our negative result does not apply to the Chor-Fiat-Naor (CFN) scheme (which, in fact, allows tracing in our self-protecting model); this separates CFN black-box traceability from that of BF. We also investigate a weaker form of black-box tracing called single-query "black-box confirmation." We show that, when suspicion is modeled as a confidence weight (which biases the uniform distribution of traitors), such single-query confirmation is essentially not possible against a self-protecting pirate-decoder that contains keys based on a superlogarithmic number of traitor keys.
|
Download: [pdf] [ps] [BibTeX] [link]
|
|
|
On Crafty Pirates and Foxy Tracers
|
|
Aggelos Kiayias and Moti Yung
|
|
Proceedings of the First ACM Workshop on Security and Privacy in Digital Rights Management --- DRM 2001,
LNCS Vol. 2320, pp. 22--39, Springer, 2002.
|
| Abstract.
Piracy in digital content distribution systems is usually identified as the illegal reception of the material by an unauthorized (pirate) device. A well known method for discouraging piracy in this setting is the usage of a traitor tracing scheme that enables the recovery of the identities of the subscribers who collaborated in the construction of the pirate decoder (the traitors). An important type of tracing which we deal with here is ``black-box traitor tracing'' which reveals the traitors' identity using only black-box access to the pirate decoder. The only existing general scheme which is successful in general black-box traitor tracing was introduced by Chor Fiat and Naor. Still, this scheme employs a pirate decoder model that despite its generality it is not intended to apply to all settings. In particular it is assumed that (1) the pirate decoder is ``resettable'', i.e. the tracer is allowed to reset the pirate decoder to its initial state after each trial (but in many settings this is not possible: the pirate decoder is ``history-recording''), and that (2) the pirate decoder is ``available'', i.e. it does not employ an internal reactive mechanism that, say, disables the tracing process (such as shutting down) --- we will call such reactive decoders ``abrupt.''
In this work we discuss pirate-decoders of various types which we categorize according to their capabilities: resettable vs. history recording, and available vs. abrupt. These (crafty) pirate decoders of ``enhanced capabilities'' (compared to the model of Chor et al.) appear in many plausible piracy scenaria. We then present new (foxy) black-box traitor tracing schemes which cope with such pirate decoders. We present a generic black box traitor tracing technique against any abrupt/resettable decoder. This generic tracing method can be implemented readily in a linear ciphertext size traitor tracing scheme. Employing a new relaxation technique which we call list-tracing we describe a traitor tracing scheme with sublinear ciphertext size that is successful against abrupt/resettable pirate decoders. Finally, we present the first black-box traitor-tracing scheme that is successful against abrupt/history-recording pirate decoders (in the multimedia transmission setting).
|
Download: [pdf] [ps] [BibTeX]
[link]
|
|
|
Polynomial Reconstruction Based Cryptography (A Short Survey)
|
|
Aggelos Kiayias and Moti Yung
|
|
Proceedings of Selected Areas in Cryptography, 8th Annual International Workshop, SAC 2001 Toronto, Ontario, Canada, August 16-17, 2001, Springer 2001, Lecture Notes in Computer Science 2259, pp.129-133.
|
| Abstract.
Cryptography and Coding Theory are closely knitted in many respects. Recently, the problem of Decoding Reed Solomon Codes (aka Polynomial Reconstruction) was suggested as an intractability assumption upon which the security of cryptographic protocols can be based. This has initiated a line of research that exploited the rich algebraic structure of the problem and related subproblems of which in the cryptographic setting. Here we give a short overview of recent works on the subject and the novel applications that were enabled due to this development.
|
Download: [pdf] [ps] [BibTeX] [link]
|
|
|
Secure Games with Polynomial Expressions
|
|
Aggelos Kiayias and Moti Yung
|
|
Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP)
Springer, Lecture Notes in Computer Science Volume 2076, pp. 939-950.
|
Download: [pdf] [ps] [BibTeX] [link]
|
|
|
Path-order Complexity Classes
|
|
Aggelos Kiayias, Aris Pagourtzis and Stathis Zachos
|
|
Proceedings of the 8th Panhellenic Conference of Informatics, 2001.
|
Download: [pdf] [ps] [BibTeX]
[link]
|
|
|
Cook-Reductions Blur Structural Differences between Functional Complexity Classes
|
|
Aggelos Kiayias, Aris Pagourtzis and Stathis Zachos |
|
Proceedings of the 3nd Panhellenic Logic Symposium -- PLS, Delfi Greece, 1999.
|
Download: [pdf] [ps] [BibTeX] [link]
|
|
|
The Complexity of Determining the Order of Solutions
|
|
Aggelos Kiayias, Aris Pagourtzis, Kiron Sharma and Stathis Zachos |
|
Proceedings of the First Southern Symposium on Computing 1998.
|
| Abstract.
Computations of a non-deterministic Turing machine (NTM) can be represented by trees. Early on it was noted that in most cases we can restrict computation trees to binary trees without loss of generality w.r.t. the computational power. Recently the trend has been to study the influence of even more detailed structural properties of (binary) computation trees (e.g. whether complete, balanced, etc.). An important question in this context is whether the computational power of a complexity class decreases if only computation trees belonging to a special family are allowed.
Hertrampf, Vollmer and Wagner defined the class Path which is based on the value of the i-th path of a NTM. Path is supposedly a class much higher than P. In their paper it is stated that if the definition of the class Path were restricted only to balanced computation trees the corresponding complexity class would be lower than P. Path has an "irregular" behavior, since most known complexity classes remain invariant under similar "reasonable" definitional restrictions. For example NP, #P, PP possess the same computational power even if we restrict shapes of computation trees to complete binary.
In this paper we emphasize that such "irregular" behavior is related to the fact that both accepting and rejecting paths are important for determining the outcome of the computation. This is the reason that, in particular, complexity classes whose definition involves order of paths have such behavior: indeed determining the order of a path in a general tree may be difficult whereas in the case of a regular tree (e.g. complete or balanced) it is easy.
To demonstrate the power of determining path order, we introduce three functionclasses, RAP, LAP and MAP, which differ from their restricted versions unless the polynomial hierarchy collapses. These classes are closely related to other well-known complexity classes. We also present TotP, a class of functions that output the total number of paths (rejecting plus accepting) This class is proved to be equally powerfull to #P when used as an oracle; the same holds for all our classes: P RAP = P LAP = P MAP = P TotP = P #P.
We also introduce the concept of class-shape, in order to provide a formal framework for investigating complexity classes whose possible computation trees are restricted. If a family of trees S is sufficient to describe all computations of all members of a class C, then we say that S is a sufficient shape for C. We focus on the family of complete binary trees (CBT) that turns out to be a sufficient shape for many known complexity classes but not for our path-order classes (unless PH collapses). Some CBT-restricted versions of our new classes are closely related to classes of optimization problems. Thus, for example, we provide an alternative description for Krentel's OptP and Toda's MidP classes. Finally our path-order classes are natural extensions of the classes max-P and min-P defined by Hempel and Wechsung and M_ed P defined by Vollmer and Wagner.
|
Download: [pdf] [ps] [BibTeX] [link]
|
|
Book Chapters