2
$\begingroup$

I came across Prof. Bill Buchanan's video "Lattice Crypto: Ring LWE with Key Exchange" explaining the RLWE-KEX. I understood everything he explained until the last part, where he is talking about removing errors from the shared key using probabilistic encryption.

  • Alice has the shared key as: $\text{sh} = \mathbf{A \cdot S_b \cdot S_a} + E_b \cdot S_a$
  • Bob has the shared key as : $\text{sh} = \mathbf{A \cdot S_a \cdot S_b} + E_a \cdot S_b$

where;

  • $\text{sh}$ represents the shared key,
  • $\mathbf{A}$ represents the shared polynomial,
  • $S_a$ represents Alice's secret key,
  • $S_b$ represents Bob's secret key,
  • $E_a$ represents Alice's error,
  • $E_b$ represents Bob's error.

The bold part is the same for both parties, the Italics part contains the secret for each party and the error from the other party.

My question is: how errors ($E_a$ and $E_b$) could be removed using the probabilistic algorithm?

$\endgroup$

1 Answer 1

2
$\begingroup$

The $E_b \cdot S_a$ and $E_a \cdot S_b$ cannot be fully removed, however they are polynomials with small coefficients whereas $A \cdot S_b \cdot S_a$ is a polynomial with large coefficients. This allows both sides to possess close approximations to the coefficients of $A \cdot S_b \cdot S_a$.

By extracting only crude information about the size of a coefficient (e.g. is the coefficient between $q \over 4$ and $3q \over 4$) both sides can obtain one or two shared secret bits per coefficient with high probability.

$\endgroup$
4
  • $\begingroup$ Many thanks for your reply.. I'm not an expert as you are, how can I determine when to use (q/4 ... 3q/4) or (q ... 0) or (q/4 ... -q/4) or any other area? Also, I have been trying to find a full question with a step-by-step solution that clarifies every step but with no luck! could you help me with that please? $\endgroup$
    – A. H
    Oct 15, 2023 at 19:48
  • 1
    $\begingroup$ The choice of which extraction method to use can be specified in advance between the communicating parties or can be based on "hints" as part of information reconciliation between the two parties. $\endgroup$
    – Daniel S
    Oct 16, 2023 at 8:46
  • 1
    $\begingroup$ Although its not quite the scenario that you describe, you might like to see my step-by-step simplified description of Kyber $\endgroup$
    – Daniel S
    Oct 16, 2023 at 8:46
  • $\begingroup$ Many thanks for your help. Much appreciated $\endgroup$
    – A. H
    Oct 16, 2023 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.