search

cloudflare / circl

CIRCL: Cloudflare Interoperable Reusable Cryptographic Library
http://blog.cloudflare.com/introducing-circl
Other
1.26k stars 138 forks source link

Compatiblity with JJChiDguez/sibc #306

Open cblaettl opened 2 years ago

cblaettl commented 2 years ago

Hi,

First of all thank you very much for this awesome library!

Im currently working on a Go project which has to work with SCIDH keys generated by sibc. I'd like to use this library for the Go part, but I couldn't get them to work together.

I've opened an issue in the repo of the sibc library, if they are compatible at all and here's the answer of the maintainer:

Hello there!

It's good to read you are enjoying and using the library. I hope this library helps increase the use of isogeny-based primitives (at least, as a toolkit for learning/using isogenies in practice).

Answering

Do you know if these libraries are even compatible at all?

In summary, both libraries are not directly compatible; see below the main difference:

  1. The Go-code is doing a non-constant-time implementation of csidh (at least at field operation level).
  2. The keyspace from the Go-code is [-5,5]⁷⁴ ≈ 2²⁵⁶, that is, private keys are integer vectors e with entries eᵢ in [-5,5]. On the other hand, sibc works with "optimal" bound vectors, that is, eᵢ is an integer in [-mᵢ, mᵢ] where each mᵢ is fixed and possibly different from another mⱼ.
  3. In the Go-code private keys are arrays of 37=74/2 bytes (see var privateOut [37]byte), while in the csidh-default configuration of sibc, this array has length 74.

As a consequence, private keys generated by the Go-code are not compatible with the private keys from sibc because of

  1. Different private key entry ranges: eᵢ is an integer in [-mᵢ, mᵢ]. For instance, sibc use these bounds;
  2. Different array lengths (I think this is the main issue why sibc is failing, it tries to access to (for example) the 38th entry of e, but it fails because the Go-code output has just 37 entries).

Since I'm not experienced with SCIDH I'd like to ask if it would be possible to make these two libraries compatible and if so, how hard it would be?

Thanks in advance!

armfazh commented 2 years ago

Thanks @cblaettl for raising this issue. I will reach @JJChiDguez so we can agree on a binary version for keys for making these implementations compatible.

JJChiDguez commented 2 years ago

Check! @armfazh and I will sync up to handle compatibility!

cblaettl commented 2 years ago

I'm amazed how quickly that worked out, thanks a lot! 😄 Let me know once there is a version ready for testing.