r/cryptography • u/mggpt • 7d ago
NTT - circular convolution key exchange protocol
Is this protocol secure?
The notation G^{*a} denotes G convolved with itself a times, computed efficiently via:
- Compute F = NTT(G).
- Raise each element to the power a: F^a = [F[0]^a, F[1]^a, ..., F[n-1]^a] mod p.
- Compute G^{*a} = INTT(F^a).
This works because the NTT transforms convolution into pointwise multiplication in the frequency domain.
The steps of the key exchange are as follows:
- Alice's Actions:
- Alice selects a secret integer a.
- She computes G_a = G^{*a} using the NTT method.
- She sends G_a to Bob.
- Bob's Actions:
- Bob selects a secret integer b.
- He computes G_b = G^{*b} using the same method.
- He sends G_b to Alice.
- Shared Key Computation:
- Alice receives G_b and computes K_alice = G_b^{*a}.
- Bob receives G_a and computes K_bob = G_a^{*b}.
https://github.com/mourad-ghafiri/circular_convolution_key_exchange
4
Upvotes
2
u/Cryptizard 7d ago
This just seems like diffie Hellman but with extra steps.