[Proof of Concept] Ring-LWE Key Exchange

Note: If you've missed my reply on a proper API, check out this for a math.random-free version of RLWE with some extra spices on top of it. Please don't use the raw PoC for anything but concept proving.

Inspired by the lack of asymmetric cryptography in my search results and by some spare time, I'm giving this a go. Hopefully, I didn't miss anything. If this actually works, I'll be surprised.

The Ring Learning With Errors Key Exchange is an algorithm that lets two users share a secret key through a public channel without revealing any information about such key. It relates to hard problems on lattices and is believed to be resistant to attacks involving quantum computers.

The PoC uses a key encapsulation mechanism to generate a shared secret μ and an encapsulation c using the recipient's public key b, who uses the private key s₁ to decapsulate c and get μ.

Here's the pastebin: https://pastebin.com/dZsGKNbC
Here's the paper I've based it on: https://eprint.iacr.org/2015/138.pdf
And here's its Wikipedia article: https://en.wikipedia...rs_key_exchange

Oh wow, this is neat! It's always nice to see real-life encryption algorithms implemented in Lua, and asymmetric/key exchange implementations are even better. Just wondering what the performance of this is like? I think I've seen people try Diffie-Hellman before, but given up as it was far too slow.

SquidDev, on 25 September 2017 - 10:48 AM said:

Oh wow, this is neat! It's always nice to see real-life encryption algorithms implemented in Lua, and asymmetric/key exchange implementations are even better. Just wondering what the performance of this is like? I think I've seen people try Diffie-Hellman before, but given up as it was far too slow.

Thanks man! :D/>
A quick (using math.random) test says that performance actually isn't bad:

• ~97 New Key Pairs per second
• ~46 Encapsulations per second
• ~205 Decapsulations per second

(Results may vary depending on your RNG)

By any chance could you provide a way that this could be used beyond this proof of concept? An actual API would be amazingly helpful especially for someone who would really like to use it, and has no idea how to de-proof-of-concept-ify it (myself). :P/>

It's a key exchange program, so you use it to negotiate a key between two computers. So taking the example from the bottom:

--# On computer 1, generate a key pair
local s1, b = keyPair()

--# Send b to computer 2 (note that s1 is kept secret) and generate a shared secret
--# on computer 2.
local mu, c = encapsulate(B)/>/>/>/>

--# Send c back to computer 1, and generate the same shared secret on computer 1
local mu_ = decapsulate(s1, c)

--# Note that computer 1 and computer 2 now have the same key - this can
--# can be used as an input for some encryption algorithm (AES).
print(table.concat(mu) == table.concat(mu_))

It's worth warning you that, like any encryption system, you have to handle verification yourself: it would be possible for someone to impersonate your target computer and send its own generated secret. Given that this is CC, it's unlikely anyone will go to the trouble of doing so, but something worth bearing in mind nonetheless.

I'd really recommend reading the Wikipedia article linked in the OP (and the source code) which, despite it using a lot of unfamiliar terminology, is actually relatively approachable. Edit: Actually, the original paper isn't too bad either and provides some additional insight into the verification problem.

Thanks Squid, the code block really helped with my understanding. I look forward to utilizing this!

Heey I was working with an Actual API actually (low productivity tho). It's mostly done apart from entropy gathering and maybe some more testing so I might get to work on it a bit more but here it is.
In theory, it should be enough for authenticated and encrypted communication with forward secrecy and protection against replay attacks. I'll also be testing more things on it through the week, dealing with network attacks might be harder than implementing the scheme itself. :o/>
Also shoutouts to Anavrins for the SHA256 and Chacha20 APIs and to KillaVanilla for Base64 (they're reeeally helpful and exposed on that Actual API)

My goodness this is awesome! I decided to do something a bit simpler and just use the PoC you provided here, remove the bottom few lines that prove the concept, and then use Squid's aes implementation. I may slowly move the project that I'm working on over to this. Thanks for the amazing key exchange implementation though, nothing is better than something that works, and is fast!