Help Verifying/Completing Basic Cryptography Proofs

• Apr 15th 2013, 08:01 PM
HowDoIMath
Help Verifying/Completing Basic Cryptography Proofs
I'm not sure if there's a lot of different types of notation for this stuff, but just to be clear S(a) means the support of a, w(a) means the weight of a, h(a,b) is the hamming distance between a and b, $\displaystyle \mu(C)$ is the minimum hamming distance between any two words in the group code C, and S(a;b) is a sphere where a is the center and b is the radius.

1. "Given $\displaystyle$\alpha \in Z^{n}_{2}$$and a nonnegative integer r, find a formula for |S(\displaystyle \alpha$$;r)|. Use it to find |S(0110101;4)|"

For this one I said |S($\displaystyle$\alpha$$;r)| = \displaystyle \sum^{r}_{i=0} \dfrac{n!}{i!(n-i)!}$$
Substituting 7 for n and 4 for r, I got |S(0110101;4)| = $\displaystyle$\sum^{4}_{i=0} \dfrac{7!}{i!(7-i)!} $$= 99 2. "If C is a code contained in \displaystyle Z^{n}_{2}$$ and $\displaystyle$\alpha$$a fixed word in \displaystyle Z^{n}_{2}$$ , prove that $\displaystyle$\mu(C) = \mu(C + \alpha)$$where \displaystyle C + \alpha = \{\gamma + \alpha|\gamma \in C\}$$ "

By adding $\displaystyle$\alpha$$to words \displaystyle \gamma_1 and \gamma_2 \in C, \displaystyle h(\gamma_1,\gamma_2)$$ is unchanged since each coordinate position i in $\displaystyle$\gamma_1$$that gets changed is also changed in \displaystyle \gamma_2$$ (with each coordinate position $\displaystyle$i \in S(\alpha)$$. The hamming distance between any two elements of C are unchanged when \displaystyle \alpha$$ is added to all of them, therefore the minimum hamming distance of C is equal to the minimum hamming distance of C + $\displaystyle$\alpha$$. 3. "For \displaystyle \alpha \in Z^{n}_{2}$$ and any nonnegative real number r, define $\displaystyle$S(\alpha;r) = \{\gamma | h(\alpha,\gamma)\leq r\}$$. Prove that if \displaystyle \alpha,\beta \in Z^{n}_{2}$$ and p and q are nonnegative integers, then $\displaystyle$S(\alpha;p) \cap S(\beta;q) \neq \varnothing$$if and only if \displaystyle h(\alpha,\gamma) \leq p + q$$."

Consider the following 3 possible Cases:
Case 1:
If $\displaystyle$S(\alpha;p) \cap S(\beta;q) = {\gamma}$$, then \displaystyle h(\alpha,\beta) = p+q$$
Case 2:
Let $\displaystyle k < n, k \in Z$
If $\displaystyle$S(\alpha;p) \cap S(\beta;q) = {\gamma_1,\gamma_2, ..., \gamma_k}$$, then \displaystyle h(\alpha,\beta) < p+q$$
Case 3:
$\displaystyle$S(\alpha;p) \cap S(\beta;q) = {\varnothing}$$, then \displaystyle h(\alpha,\beta) > p+q$$

Therefore $\displaystyle$S(\alpha;p) \cap S(\beta;q) \neq \varnothing$$implies \displaystyle h(\alpha,\beta) \leq p+q$$

So I did the "if" part, but I'm not sure how to do the "only if" part or if that's necessary (I've seen proofs that said it's ok to omit it, but I don't know when that's true?)

4. "Let $\displaystyle$\alpha = a_{1}a_{2}...a_{n}$$and \displaystyle \beta = b_{1}b_{2}...b_{n}$$ be words of $\displaystyle$Z^{n}_{2}$$. Define \displaystyle \alpha \bullet \beta$$ to be $\displaystyle$a_{1}b_{1} + a_{2}b_{2} +...+ a_{n}b_{n}$$(ie \displaystyle 110101 \bullet 101101 = 1$$). Let C be an (n,k) code (code of length n with n-k check digits) and define$\displaystyle$ C^{\bot} = \{\alpha \in Z^{n}_{2} | \alpha \bullet \beta = 0, \forall \beta \in C\}$$. This is the so-called dual of C. (i) Prove \displaystyle C^{\bot}$$ is a subgroup of $\displaystyle$Z^{n}_{2}$$(ii) Prove that if M is the generator matrix of C, then \displaystyle C^{\bot} = ker F_{M^{T}} where \displaystyle M^{T} is the transpose of M, i.e., the matrix obtained by interchanging rows and columns. Hence show that \displaystyle |C^{\bot}| = 2^{n-k}" part (i) I know that I need to show that the elements of \displaystyle C^{\bot}$$ are closed, have an identity, an inverse, and are associative (all under addition), but I don't know how to do it though?
part(ii)
M is a $\displaystyle n \times k$ matrix of the form $\displaystyle \dfrac{A}{I_{k}}$. I need to show that $\displaystyle \forall \alpha \in C^{\bot}, M^{T}.\alpha = 0$, but I don't know how to show this or $\displaystyle |C^{\bot}| = 2^{n-k}$
• Apr 21st 2013, 04:04 PM
HowDoIMath
Re: Help Verifying/Completing Basic Cryptography Proofs
Quote:

$\displaystyle$h(\alpha,\gamma) \leq p + q$$should be: \displaystyle h(\alpha,\beta) \leq p + q$$