Re: Question on definition of semantic security: why "probability ensemble"?



Sergei <silentser@xxxxxxxxx> wrote:

Kristian Gjøsteen wrote:
Try an A' that always outputs 1.

A' that always outputs 1 will work when A also always outputs 1.
Algorithms A and A' have different quantifiers in the definition: "for
every A" and "there exists A' ". So, the choice of A' depends on the
choice of A.

It is _allowed_ to depend on A. It does not have to. (Well, if it has to,
run A first, then discard its output and output 1 instead.) For what A
does an A' that simply outputs 1 always not satisfy the inequality?

--
Kristian Gjøsteen
.



Relevant Pages

  • Re: Question on definition of semantic security: why "probability ensemble"?
    ... Kristian Gjøsteen wrote: ... Algorithms A and A' have different quantifiers in the definition: ... (When I've used semantic security, I've used different, but equivalent, ...
    (sci.crypt)
  • theorems/problems with lots of quantifiers
    ... For example, if you formalize the fundamental thm of arithmetic, you ... students of automata/computability) has 4 quantifiers. ... I suppose I care more about "natural" problems rather than ... most of the algorithms we care about are ...
    (comp.theory)
  • theorems/problems with lots of quantifiers
    ... For example, if you formalize the fundamental thm of arithmetic, you ... students of automata/computability) has 4 quantifiers. ... I suppose I care more about "natural" problems rather than ... most of the algorithms we care about are ...
    (sci.math)
  • theorems/problems with lots of quantifiers
    ... For example, if you formalize the fundamental thm of arithmetic, you ... students of automata/computability) has 4 quantifiers. ... I suppose I care more about "natural" problems rather than ... most of the algorithms we care about are ...
    (sci.logic)