Mobile agent security through multi-agent cryptographic protocols. Page: 30
This dissertation is part of the collection entitled: UNT Theses and Dissertations and was provided to UNT Digital Library by the UNT Libraries.
Extracted Text
The following text was automatically extracted from the image on this page using optical character recognition software:
Definition 2.1.3 Indistinguishability by Repeated Sampling (Definition 3.2.4 of [35])
Two ensembles, X def {Xn}nEN and Y def {Yn}nEN are indistinguishable by polynomial-time
sampling if for every probabilistic polynomial-time algorithm D, every two positive polynomials
m(.) and p(.), and all sufficiently large n's,
Pr [D(X(1),... ,Xnm(n))) = 1] - Pr [D(Yn1),... (m(n)))= 1] < 1
where X n1 through Xem(n)) and Y(1) through Y(m(n)) are independent random variables, with each
X /) identical to Xn and each Y(i) identical to Y,.
An ensemble is efficiently constructible if its sampling can be done within polynomial time. The
following theorem asserts that for two efficiently constructible ensembles, indistinguishability by a
single sample implies indistinguishability by repeated sampling.
Theorem 2.1.4 (Theorem 3.2.6 of [35])
Let X def {Xn}nEN and Y def {Yn}nEN be two polynomial-time-constructible ensembles, and suppose
X and Y are indistinguishable in polynomial time (as in Definition 2.1.2). Then X and Y are
indistinguishable by polynomial-time sampling (as in Definition 2.1.3).
As a special case, the distributions of the outputs of the environment constitute a binary distri-
bution ensemble, X = {X(k,a)}kEN,aE{0,1}*, which only consists of distributions over {0, 1}. In the
index (k, a), k corresponds to the security parameter, and a represents the input.
Definition 2.1.5 Indistinguishability of Two Binary Distribution Ensembles [20]
C
Two binary distribution ensembles X and Y are indistinguishable (written X m Y) if for any
c e N there exists ko E N such that for all k > ko and for all a we have
1
Pr(X(k,a) 1) Pr(Y(k,a) kc1) <30
Upcoming Pages
Here’s what’s next.
Search Inside
This dissertation can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Dissertation.
Xu, Ke. Mobile agent security through multi-agent cryptographic protocols., dissertation, May 2004; Denton, Texas. (https://digital.library.unt.edu/ark:/67531/metadc4473/m1/38/: accessed April 25, 2024), University of North Texas Libraries, UNT Digital Library, https://digital.library.unt.edu; .