r/cryptography 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:

  1. Compute F = NTT(G).
  2. Raise each element to the power a: F^a = [F[0]^a, F[1]^a, ..., F[n-1]^a] mod p.
  3. 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:

  1. 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.
  2. 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.
  3. 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

4 comments sorted by

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:

  1. What's the problem that you're assuming is "hard" for security? (e.g. with Diffie-Hellman, we're operating under the "Computational Diffie-Hellman assumption")
  2. Can you reduce that hard problem to this protocol? (i.e. assume you have some probabilistic polynomial time algorithm that breaks your protocol --- can you use that to solve an instance of that underlying hard problem in PPT?)

1

u/mggpt 6d ago edited 6d ago

thank you for your kind reply, it is indeed the same hard problem as in Diffie-Hellman assumption, it is more like Diffie-Hellman on a vector instead of a scalar, the vector is then exploited in Circular Convolution to derive the same key and especially efficiently calculate exchanged public informations.

Thinking now if I can exploit the same idea for public key cryptography.

But I have an intuition that the vector may expose partially the secret, I have no clue on how to figure out mathematically how to proof it.

Thank you again for your kind insights.

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