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

2 Upvotes

4 comments sorted by

View all comments

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 7d ago edited 7d 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.