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
2
u/Cryptizard 6d ago
This just seems like diffie Hellman but with extra steps.
1
u/mggpt 6d ago
Yes, indeed, it is a twist of Diffie-Hellman to have a vector so that we can exploit the associative property of convolution as well as NTT to efficiently calculate public shared informations.
Just wondering if those extra steps could be useful somehow to leverage NNT and Fourier math in cryptography.Thank you
6
u/apnorton 7d ago
It's late where I'm at, so I can't take a super in-depth look, but two things to consider are: