| Popis: |
Key Exchange is an essential primitive in cryptography that originated from the breakthrough idea of Diffie Hellman (DH) protocol presented in 1976. Following this work, there are many successful variants of DH using Elliptic curves, Isogeny and RLWE (Ring Learning with Errors). The Ring-Leaning with Errors (RLWE), Search and Decision version are hard problems in mathematics and it has been shown that solving worst case hard problems in ideal lattices can be reduced to solving RLWE in the average case. The reduction forms the basis of provable security for RLWE based key exchange against passive adversaries. The hardness of the decision version of RLWE, which means indistinguishability of RLWE samples from Uniform, makes it challenging to validate a RLWE form public key. This proves to be an advantage for malicious users to create public keys that deviate from a protocol to recover the secret of reused keys in Key Exchange (KE) protocols. In this thesis, we provide a cryptanalysis of RLWE key exchange, presenting two polynomial time strategies to exploit key reuse. Then we propose a defense against such exploits by presenting a Zero Knowledge authentication protocol to verify the prover's knowledge of a secret corresponding to his public key. The protocol is Statistical Zero Knowledge with negligible soundness and completeness errors so that the prover does not reveal any information about the secret in the proof. This is to ensure that a malicious verifier cannot impersonate the prover after the proof. The authentication protocol uses the signal function defined in RLWE key exchange to perform the verification. |
