The Experts below are selected from a list of 282 Experts worldwide ranked by ideXlab platform

Yehuda Lindell - One of the best experts on this subject based on the ideXlab platform.

  • Handling Expected Polynomial-Time Strategies in Simulation-Based Security Proofs
    Journal of Cryptology, 2008
    Co-Authors: Jonathan Katz, Yehuda Lindell
    Abstract:

    The standard class of adversaries considered in cryptography is that of strict Polynomial-Time probabilistic machines. However, expected Polynomial-Time machines are often also considered. For example, there are many zero-knowledge protocols for which the only known simulation techniques run in expected (and not strict) Polynomial Time. In addition, it has been shown that expected Polynomial-Time simulation is essential for achieving constant-round black-box zero-knowledge protocols. This reliance on expected Polynomial-Time simulation introduces a number of conceptual and technical difficulties. In this paper, we develop techniques for dealing with expected Polynomial-Time adversaries in simulation-based security proofs.

  • Strict Polynomial-Time in Simulation and Extraction
    SIAM Journal on Computing, 2004
    Co-Authors: Boaz Barak, Yehuda Lindell
    Abstract:

    The notion of efficient computation is usually identified in cryptography and complexity with (strict) probabilistic Polynomial-Time. However, until recently, in order to obtain \emph{constant-round} zero-knowledge proofs and proofs of knowledge, one had to allow simulators and knowledge extractors to run in Time that is only Polynomial on the average (i.e., expected Polynomial-Time). Recently Barak gave the first constant-round zero-knowledge argument with a strict (in contrast to expected) Polynomial-Time simulator. The simulator in his protocol is a nonblack-box simulator (i.e., it makes inherent use of the description of the code of the verifier). In this paper, we further address the question of strict Polynomial-Time in constant-round zero-knowledge proofs and arguments of knowledge. First, we show that there exists a constant-round zero-knowledge argument of knowledge with a strict Polynomial-Time knowledge extractor. As in the simulator of Barak's zero-knowledge protocol, the extractor for our argument of knowledge is not black-box and makes inherent use of the code of the prover. On the negative side, we show that nonblack-box techniques are essential for both strict Polynomial-Time simulation and extraction. That is, we show that no (nontrivial) constant-round zero-knowledge proof or argument can have a strict Polynomial-Time black-box simulator. Similarly, we show that no (nontrivial) constant-round zero-knowledge proof or argument of knowledge can have a strict Polynomial-Time black-box knowledge extractor.

  • Strict Polynomial-Time in Simulation and Extraction.
    IACR Cryptology ePrint Archive, 2002
    Co-Authors: Boaz Barak, Yehuda Lindell
    Abstract:

    The notion of efficient computation is usually identified in cryptography and complexity with (strict) probabilistic Polynomial Time. However, until recently, in order to obtain constant-round zero-knowledge proofs and proofs of knowledge, one had to allow simulators and knowledgeextractors to run in Time that is only Polynomial on the average (i.e., expected Polynomial Time). Recently Barak gave the first constant-round zero-knowledge argument with a strict (in contrast to expected) Polynomial-Time simulator. The simulator in his protocol is a non-blackbox simulator (i.e., it makes inherent use of the description of the code of the verifier). In this paper, we further address the question of strict Polynomial-Time in constant-round zero-knowledge proofs and arguments of knowledge. First, we show that there exists a constantround zero-knowledge argument of knowledge with a strict Polynomial-Time knowledge extractor. As in the simulator of Barak’s zero-knowledge protocol, the extractor for our argument of knowledge is not black-box and makes inherent use of the code of the prover. On the negative side, we show that non-black-box techniques are essential for both strict Polynomial-Time simulation and extraction. That is, we show that no (non-trivial) constant-round zero-knowledge proof or argument can have a strict Polynomial-Time black-box simulator. Similarly, we show that no (non-trivial) constant-round zero-knowledge proof or argument of knowledge can have a strict Polynomial-Time black-box knowledge extractor.

  • STOC - Strict Polynomial-Time in simulation and extraction
    Proceedings of the thiry-fourth annual ACM symposium on Theory of computing - STOC '02, 2002
    Co-Authors: Boaz Barak, Yehuda Lindell
    Abstract:

    The notion of efficient computation is usually identified in cryptography and complexity with probabilistic Polynomial Time. However, until recently, in order to obtain constant-round zero-knowledge proofs and proofs of knowledge (for NP), one had to allow simulators and knowledge-extractors to run in Time which is only Polynomial on the average (i.e., expected Polynomial Time). Whether or not allowing expected Polynomial-Time is necessary for obtaining constant-round zero-knowledge proofs and proofs of knowledge, has been posed as an important open question. This question is interesting not only for its theoretical ramifications, but also because expected Polynomial Time simulation is not closed under composition. Therefore, in some cases security is not maintained when a protocol that utilizes expected Polynomial Time simulation (or extraction) is used as a part of a larger protocol.A partial answer to the question of the necessity (or non-necessity) of expected Polynomial-Time was provided recently by Barak, who gave the first constant-round zero-knowledge argument with a strict (in contrast to expected) Polynomial-Time simulator. His was also the first protocol that is not black-box zero-knowledge. That is, the simulator in his protocol utilizes the description of the code of the verifier in an essential way.In this paper, we completely resolve the question of expected Polynomial-Time in zero-knowledge arguments and arguments of knowledge. First, we show that there exist constant-round zero-knowledge arguments of knowledge with strict Polynomial-Time extractors. As in the simulator of Barak's zero-knowledge protocol, the extractor for our proof of knowledge is not black-box and uses the code of the prover in an essential way.On the negative side, we show that non-black-box techniques are essential to both strict Polynomial-Time simulation and extraction. That is, we show that no constant-round zero-knowledge argument (or proof) can have a strict Polynomial-Time black-box simulator. Similarly, we show that no constant-round zero-knowledge argument (or proof) of knowledge can have a strict Polynomial-Time black-box knowledge extractor. Thus, for constant-round black-box zero-knowledge arguments (resp., arguments of knowledge), it is imperative that the simulator (resp., extractor) be allowed to run in expected Polynomial-Time.

Phokion G. Kolaitis - One of the best experts on this subject based on the ideXlab platform.

  • Unification Algorithms Cannot Be Combined in Polynomial Time
    Information and Computation, 2000
    Co-Authors: Miki Hermann, Phokion G. Kolaitis
    Abstract:

    We establish that there is no Polynomial-Time general combination algorithm for unification in finitary equational theories, unless the complexity class #P of counting problems is contained in the class FP of function problems solvable in Polynomial-Time. The prevalent view in complexity theory is that such a collapse is extremely unlikely for a number of reasons, including the fact that the containment of #P in FP implies that P = NP. Our main result is obtained by establishing the intractrability of the counting problem for general AG-unification, where AG is the equational theory of Abelian groups. More specifically, we show that computing the cardinality of a minimal complete set of unifiers for general AG-unification is a #P-hard problem. In contrast, AG-unification with constants is known to be solvable in Polynomial Time. Since an algorithm for general AG-unification can be obtained as a combination of a Polynomial-Time algorithm for AG-unification with constants and a Polynomial-Time algorithm for syntactic unification, it follows that no Polynomial-Time general combination algorithm exists, unless #P is contained in FP. This implication of our main results holds not only for the combination of unification algorithms, but for the combination of constraint solvers as well. We also show that the counting problem for Boolean ring unification is #P-hard; this gives a lower bound on the performance of all algorithms for general BR-unification.

  • CADE - Unification Algorithms Cannot be Combined in Polynomial Time
    Automated Deduction — Cade-13, 1996
    Co-Authors: Miki Hermann, Phokion G. Kolaitis
    Abstract:

    We establish that there is no Polynomial-Time general combination algorithm for unification in finitary equational theories, unless the complexity class #P of counting problems is contained in the class FP of function problems solvable in Polynomial-Time. The prevalent view in complexity theory is that such a collapse is extremely unlikely for a number of reasons, including the fact that the containment of #P in FP implies that P=NP. Our main result is obtained by establishing the intractrability of the counting problem for general AG-unification, where AG is the equational theory of Abelian groups. Specifically, we show that computing the cardinality of a minimal complete set of unifiers for general AG-unification is a #P-hard problem. In contrast, AG-unification with constants is solvable in Polynomial Time. Since an algorithm for general AG-unification can be obtained as a combination of a PolynomialTime algorithm for AG-unification with constants and a Polynomial-Time algorithm for syntactic unification, it follows that no Polynomial-Time general combination algorithm exists, unless #P is contained in FP.

Harald Racke - One of the best experts on this subject based on the ideXlab platform.

Boaz Barak - One of the best experts on this subject based on the ideXlab platform.

  • Strict Polynomial-Time in Simulation and Extraction
    SIAM Journal on Computing, 2004
    Co-Authors: Boaz Barak, Yehuda Lindell
    Abstract:

    The notion of efficient computation is usually identified in cryptography and complexity with (strict) probabilistic Polynomial-Time. However, until recently, in order to obtain \emph{constant-round} zero-knowledge proofs and proofs of knowledge, one had to allow simulators and knowledge extractors to run in Time that is only Polynomial on the average (i.e., expected Polynomial-Time). Recently Barak gave the first constant-round zero-knowledge argument with a strict (in contrast to expected) Polynomial-Time simulator. The simulator in his protocol is a nonblack-box simulator (i.e., it makes inherent use of the description of the code of the verifier). In this paper, we further address the question of strict Polynomial-Time in constant-round zero-knowledge proofs and arguments of knowledge. First, we show that there exists a constant-round zero-knowledge argument of knowledge with a strict Polynomial-Time knowledge extractor. As in the simulator of Barak's zero-knowledge protocol, the extractor for our argument of knowledge is not black-box and makes inherent use of the code of the prover. On the negative side, we show that nonblack-box techniques are essential for both strict Polynomial-Time simulation and extraction. That is, we show that no (nontrivial) constant-round zero-knowledge proof or argument can have a strict Polynomial-Time black-box simulator. Similarly, we show that no (nontrivial) constant-round zero-knowledge proof or argument of knowledge can have a strict Polynomial-Time black-box knowledge extractor.

  • Strict Polynomial-Time in Simulation and Extraction.
    IACR Cryptology ePrint Archive, 2002
    Co-Authors: Boaz Barak, Yehuda Lindell
    Abstract:

    The notion of efficient computation is usually identified in cryptography and complexity with (strict) probabilistic Polynomial Time. However, until recently, in order to obtain constant-round zero-knowledge proofs and proofs of knowledge, one had to allow simulators and knowledgeextractors to run in Time that is only Polynomial on the average (i.e., expected Polynomial Time). Recently Barak gave the first constant-round zero-knowledge argument with a strict (in contrast to expected) Polynomial-Time simulator. The simulator in his protocol is a non-blackbox simulator (i.e., it makes inherent use of the description of the code of the verifier). In this paper, we further address the question of strict Polynomial-Time in constant-round zero-knowledge proofs and arguments of knowledge. First, we show that there exists a constantround zero-knowledge argument of knowledge with a strict Polynomial-Time knowledge extractor. As in the simulator of Barak’s zero-knowledge protocol, the extractor for our argument of knowledge is not black-box and makes inherent use of the code of the prover. On the negative side, we show that non-black-box techniques are essential for both strict Polynomial-Time simulation and extraction. That is, we show that no (non-trivial) constant-round zero-knowledge proof or argument can have a strict Polynomial-Time black-box simulator. Similarly, we show that no (non-trivial) constant-round zero-knowledge proof or argument of knowledge can have a strict Polynomial-Time black-box knowledge extractor.

  • STOC - Strict Polynomial-Time in simulation and extraction
    Proceedings of the thiry-fourth annual ACM symposium on Theory of computing - STOC '02, 2002
    Co-Authors: Boaz Barak, Yehuda Lindell
    Abstract:

    The notion of efficient computation is usually identified in cryptography and complexity with probabilistic Polynomial Time. However, until recently, in order to obtain constant-round zero-knowledge proofs and proofs of knowledge (for NP), one had to allow simulators and knowledge-extractors to run in Time which is only Polynomial on the average (i.e., expected Polynomial Time). Whether or not allowing expected Polynomial-Time is necessary for obtaining constant-round zero-knowledge proofs and proofs of knowledge, has been posed as an important open question. This question is interesting not only for its theoretical ramifications, but also because expected Polynomial Time simulation is not closed under composition. Therefore, in some cases security is not maintained when a protocol that utilizes expected Polynomial Time simulation (or extraction) is used as a part of a larger protocol.A partial answer to the question of the necessity (or non-necessity) of expected Polynomial-Time was provided recently by Barak, who gave the first constant-round zero-knowledge argument with a strict (in contrast to expected) Polynomial-Time simulator. His was also the first protocol that is not black-box zero-knowledge. That is, the simulator in his protocol utilizes the description of the code of the verifier in an essential way.In this paper, we completely resolve the question of expected Polynomial-Time in zero-knowledge arguments and arguments of knowledge. First, we show that there exist constant-round zero-knowledge arguments of knowledge with strict Polynomial-Time extractors. As in the simulator of Barak's zero-knowledge protocol, the extractor for our proof of knowledge is not black-box and uses the code of the prover in an essential way.On the negative side, we show that non-black-box techniques are essential to both strict Polynomial-Time simulation and extraction. That is, we show that no constant-round zero-knowledge argument (or proof) can have a strict Polynomial-Time black-box simulator. Similarly, we show that no constant-round zero-knowledge argument (or proof) of knowledge can have a strict Polynomial-Time black-box knowledge extractor. Thus, for constant-round black-box zero-knowledge arguments (resp., arguments of knowledge), it is imperative that the simulator (resp., extractor) be allowed to run in expected Polynomial-Time.

Marius Zimand - One of the best experts on this subject based on the ideXlab platform.

  • Almost-Everywhere Superiority for Quantum Polynomial Time
    Information and Computation, 2002
    Co-Authors: Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand
    Abstract:

    Simon as extended by Brassard and Hoyer shows that there are tasks on which Polynomial-Time quantum machines are exponentially faster than each classical machine infinitely often. The present paper shows that there are tasks on which Polynomial-Time quantum machines are exponentially faster than each classical machine almost everywhere.

  • Polynomial-Time Semi-Rankable Sets
    1995
    Co-Authors: Lane A. Hemaspaandra, Mohammed J. Zaki, Marius Zimand
    Abstract:

    We study the Polynomial-Time semi-rankable sets (P-sr), the ranking analog of the P-selective sets. We prove that P-sr is a strict subset of the P-selective sets, and indeed that the two classes differ with respect to closure under complementation, closure under union with P sets, closure under join with P sets, and closure under P-isomorphism. While P/poly is equal to the closure of P-selective sets under Polynomial-Time Turing reductions, we build a tally set that is not Polynomial-Time reducible to any P-sr set. We also show that though P-sr falls between the P-rankable and the weakly-P-rankable sets in its inclusiveness, it equals neither of these classes.