page id: 481, 1259 hits, unlocked, unhidden, current: v2
v1:2005-10-18 19:42:26(4,857), v2:2005-10-18 19:44:36(4,828)
diff v1:jiinny v2:jiinny
| = \@ocat |
| = \@cat{QKD} |
| = \@ecat |
| = from http://www.ai.sri.com/~goldwate/quantum.html |
| = !!!Privacy Amplification |
| = |
| - <p>At this point, Alice and Bob posses identical strings, but those |
| + At this point, Alice and Bob posses identical strings, but those |
| = strings are not completely private. Eve may have gained some |
| = information about them either by beamsplitting or through |
| = intercept/resend. Although this second strategy may cause some errors |
| = in Bob's string, if Eve uses it on only a small number of bits, the |
| = induced errors will be lost among the errors caused by noise in the |
| = detectors and other physical problems. During the reconciliation |
| = phase, Eve did not gain any information, since the last bit of each |
| = parity check set was discarded. However, some of her original |
| = information about specific bits may have been converted to information |
| = about parity bits. For instance, if she knew the value of a bit |
| = <i>x</i> in string <i>y</i>, and Alice and Bob revealed the parity of |
| = <i>y</i> and discarded <i>x</i>, Eve would then know the parity of the |
| = remaining bits of <i>y</i>. If we say that Eve knows a parity bit |
| = about a string if she knows the parity of a non-empty subset of that |
| = string, then if Eve started out knowing at most <i>k</i> physical bits |
| = of the key, she will know at most <i>k</i> parity bits of the key |
| = after reconciliation \[1\]. |
| = |
| - |
| - |
| - <p>In any case, Alice and Bob share an <i>n</i>-bit string S, and we |
| + In any case, Alice and Bob share an <i>n</i>-bit string S, and we |
| = will suppose that Eve knows at most <i>k</i> deterministic |
| = (i.e. parity or physical) bits of S. Alice and Bob wish to compute an |
| = <i>r</i>-bit key K, where <i>r</i> < <i>n</i>, such that Eve's |
| = expected information about K is below some specified bound. To do so, |
| = they will choose a compression function <i>g</i>: |
| = {0,1}<sup><i>n</i></sup> -> {0,1}<sup><i>r</i></sup> and compute K = |
| - |
| = <i>g</i>(S). The question is, what kinds of functions are appropriate |
| = for this purpose? That is, which functions, when applied to S, will |
| = yield a K about which Eve knows almost nothing? |
| = |
| - |
| - <p><b>Definition:</b> \[2\] A class <i>G</i> of functions <i>A</i> -> |
| + <b>Definition:</b> \[2\] A class <i>G</i> of functions <i>A</i> -> |
| = <i>B</i> is universal<sub>2</sub> if for any distinct |
| - |
| = <i>x<sub>1</sub></i> and <i>x<sub>2</sub></i> in A</i>, the |
| = probability that <i>g(x<sub>1</sub>)</i> = <i>g(x<sub>2</sub>)</i> is |
| = at most 1/|<i>B</i>| when <i>g</i> is chosen at random from <i>G</i> |
| - |
| = according to the uniform distribution. |
| = |
| - |
| - <p>An example of a universal class is the set of permutations of |
| + An example of a universal class is the set of permutations of |
| = <i>A</i> onto itself, since for any <i>g</i> in the set, the |
| = probability that <i>g(x<sub>1</sub>)</i> = <i>g(x<sub>2</sub>)</i> is |
| = zero, which is less than 1/|<i>A</i>|. It is shown in \[2\] that if Eve |
| = knows <i>k</i> deterministic bits of S, and Alice and Bob choose their |
| = compression function <i>g</i> at random from a universal class of hash |
| = functions {0,1}<sup><i>n</i></sup> -> {0,1}<sup><i>r</i></sup> where |
| - |
| = <i>r</i> = <i>n - k - s</i> for some safety parameter 0 < <i>s</i> < |
| = <i>n-k</i>, then Eve's expected information about K = <i>g</i> (S) is |
| = less than or equal to 2<sup><i>-s</i></sup>/ln2 bits. One such hash |
| = function to generate K \[1\] is for Alice and Bob to compute an |
| = additional <i>r</i> random subset parities of S, this time keeping the |
| = results secret. The <i>r</i> results of the parities will be the final |
| - |
| = <i>r</i>-bit key. |
| = |
| - |
| - <p>Given this result, one might ask how Alice and Bob are to determine |
| + Given this result, one might ask how Alice and Bob are to determine |
| = the value of <i>k</i>, i.e. how much information has been leaked to |
| = Eve. As a conservative estimate, they can simply assume that all |
| = transmission errors were caused by eavesdropping (although most likely |
| = some came from detection errors). Eavesdropping errors could come from |
| = either intercept/resend or beamsplitting. Alice and Bob can use the |
| = beam intensity <i>m</i> and the bit error rate to calculate the expected |
| = fraction of S that Eve has learned. If they are conservative in their |
| = assumptions and add several standard deviations to their results, they |
| = will have a safe upper bound on the number of bits leaked to Eve. (See |
| = \[1\] for more details.) |
| = |
| - |
| - <p>The above discussion assumes that Eve knows only deterministic |
| + The above discussion assumes that Eve knows only deterministic |
| = bits, so another issue is whether it might be more useful to her to |
| = obtain probabilistic information about S instead. In other words, |
| = rather than measuring photons in the same bases as Alice and Bob, she |
| = could pick a basis halfway in between them. This will give her a |
| = result that matches Alice's with probability approximately 85%, |
| = regardless of which basis Alice uses \[3\]. She will not gain any |
| = information when Bob reveals his measurement choices, so with this |
| = strategy all of her information is probabilistic rather than |
| = deterministic. Conceivably, this probabilistic information could be |
| = more resistant to privacy amplification than deterministic |
| = information. However, it turns out that this is not the case \[3\], so |
| = if Eve wishes to optimize her expected information on the final key, |
| = she should use the same bases as Alice and Bob, obtaining only |
| = deterministic bits. |
|
ViewPage |
info |
<diff> 2005-10-18 19:44:36 v2:jiinny 1259 hits |