Questions regarding Falcon-512

[Jannis Fengler]

I am thinking to use Falcon-512 in a blockchain setting. For ecdsa keys, it is common to take 12 or 24 random words from a wordlist (for example BIP 39).  Usually  128 bits of entropy map to a 12-word seed phrase and 256 to a 24-word seed phrase. These words are concatenated and after a sha2 and a checksum, the result is the private ecdsa key. The derivation from the seed phrase to the private key is deterministic.  

The construction of Falcon keys is very difficult. Is it possible to derive a private key deterministically?     

Ecdsa signatures always have a fixed length. I was playing around with lib-oqs and it seems that the Falcon signatures have a variable length. I need a fixed length in my setting, so I was thinking about padding the signatures with zeros. But space is expensive in a blockchain.  So my Questions are:

What is the maximum Falcon signature length?

Does it undermine security, if I generate multiple signatures for one message and choose the shortest one? 

Best regards,

Jannis | www.eomii.org

[Bas Westerbaan]

The construction of Falcon keys is very difficult. Is it possible to derive a private key deterministically?     

For every scheme it's possible to make key generation deterministic by replacing "randombytes()" calls by calls to a XOF that has been seeded by the "private key seed". For some, like RSA, it's not practical because key generation is slow. For Falcon it should be fast enough for this application.

I think for applications like these (eg. FIDO), it'd be great if these private key seeds be part of the standard.

 

Ecdsa signatures always have a fixed length. I was playing around with lib-oqs and it seems that the Falcon signatures have a variable length.

The latest version of Falcon has fixed signature size. This was a change from round 2 to 3 IIRC.

 

Best,

 Bas

[Jannis Fengler]

Oh, that's great. Thank you so much for your fast response!

[Fx FRT]

Bas, if You're are trying make Some ramdorizem words part of bytes un ASCII can make múltiple un if if else if else do do if else etc..well is common think un baremo to put schemes un the rate of random and derivations NOR NAND  o OR AND   NOT, etc by percent of variability with time and what is your case? What you want to move, I think is 66665 or 66666 high 66664 is in c like  said considered low level to circunstance of 1,5 ×10 ^ 24 (G bytes)hz to be the normal processors and now with dynamic floats ssdd memories 

 can trap others concussion respond in the program automatically too  to be confident I make the random of the ramdoms in 1997 when I appear with my 33×01tt 64 bits ramdoms of 32 in up and 32 in down and if you also make it possible you also can do a good conversor or data in your phone or include a good compressor but also if you know algorithms with sense like (1-x)ⁿ=d(x)and you put =xⁿ-1 so only had to press if else x=((x*-x)-x*+x)=01×x so you can trust to be 1 and then if is 0 but not nominal so you also can change the algorithm or something or you can divide to make with key this others programs codification or multiplexer or de multiplexer if key is simple ramdorizem const are to be byte BITTER  and then run 

But instead I said this like compressor in ultimate think well is all right in C + 

Others lenguages requires ramdoms of entry or back lines that I'd likes after req or resq etc well for more complex you also, well it like if you also make my 3301tt you also came to the back stars in our case psyquiatrism and problems that you don't like very well 

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAMjbhoUQ8YsGyJvv%3DhnCORxkp0ARhVvXxzGOrOMkW5O14MuQ4Q%40mail.gmail.com.

[Doge Protocol]

>>>>The latest version of Falcon has fixed signature size. This was a change from round 2 to 3 IIRC.

The reference implementation in the following Round 3 link for Falcon512 still creates variable length signatures https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/submissions/Falcon-Round3.zip

Would be helpful if Falcon inventors can kindly confirm if Round 3 version is supposed to use fixed length signatures or not.

[Jannis Fengler]

Is it possible to derive the public key deterministically from the private key?

https://github.com/open-quantum-safe/liboqs-go/issues/18

[Thom Wiggers]

Hi,

For Falcon, yes: see 

https://falcon-sign.info/impl/falcon.h.html falcon_make_public.

However, it may not be generally true.

Cheers,

Thom

Op ma 20 feb. 2023 om 02:05 schreef Jannis Fengler <fengle...@gmail.com>

--

You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/5b511574-a67d-4324-b8cd-2f3830548f08n%40list.nist.gov.

[Anjan Roy]

Hi Jannis,

> Is it possible to derive the public key deterministically from the private key?

Yes one can deterministically derive public key from private key in Falcon. Imagine you've byte encoded Falcon private key, you can do following

1) Decode private key to extract polynomials f, g and F ( more @ https://github.com/itzmeanjan/falcon/blob/cce934dcd092c95808c0bdaeb034312ee7754d7e/include/decoding.hpp#L48-L171 )

2) And now one can compute public key h = fg^-1 mod q ( more @ https://github.com/itzmeanjan/falcon/blob/cce934dcd092c95808c0bdaeb034312ee7754d7e/include/keygen.hpp#L63-L90 )

Hope it helps.

Regards.

Anjan Roy

[Jannis Fengler]

Hi Anjan and Thom,

thank you for your fast response!

That's great that the public key can be deterministically derived from the private key. 

It would be great if this function(falcon_make_public) would be visible from outside and could be part of the PQClean and liboqs library.

Right now, users would have the headache to back up their private AND public keys.

[Thom Wiggers]

Hi,

I can't speak for liboqs here, but in PQClean, we have a fairly strictly defined API (namely the NIST API). Also it would be a bit weird if only one scheme supported this new API function. I am not sure if Dilithium supports this (the private key contains only a hash of the public key I think), and while I think that SPHINCS+ could implement this function pretty easily (the second half of the secret key is the public key), it's also currently not explicitly a function that is part of the reference implementation afaik.

Frankly, I think that the assumption that you can just recompute a public key from a secret is a very RSA/ECC-esque assumption, and if we keep implementing and designing APIs based on this assumption then we may be holding back schemes that do not honor it. To me, it seems better to manage them separately: maybe we should even add the public key as an input to e.g. crypto_sign so that schemes do not need to copy public keys into secret keys if they do need access to it.

There are plenty of standards that define file formats where public keys and secret keys can be stored together, e.g. PKCS#12 (even though using PKCS#12 for this problem is probably like shooting a fly with a bazooka).

Cheers,

Thom

Op do 23 feb. 2023 om 11:23 schreef Jannis Fengler <fengle...@gmail.com>:

[Jannis Fengler]

I understand that it cannot be part of the API if it is prescribed by NIST. The rationale behind the functionality was as follows: in most blockchain applications, users do not send funds to the public key directly, but to the hash of the public keys (address). When the user wants to spend the funds, a transaction is created that contains the message, signature, and public key.

During verification, the first check is whether the public key belongs to the address, followed by whether the signature is valid. Backups, such as Metamask, typically only contain the private key or a random seed.

Therefore, my first question was whether it is deterministically derivable.

[Tony Arcieri]

On Thu, Feb 23, 2023 at 3:45 AM Thom Wiggers <th...@thomwiggers.nl> wrote:

There are plenty of standards that define file formats where public keys and secret keys can be stored together, e.g. PKCS#12 (even though using PKCS#12 for this problem is probably like shooting a fly with a bazooka).

What would really be helpful here is PKCS#8, specifically v2 as specified in RFC5958, which defines a `OneAsymmetricKey` message containing an optional `publicKey` field:

https://www.rfc-editor.org/rfc/rfc5958#section-2

Standardizing PKCS#8 usage with the NIST post-quantum algorithms seems like important work, regardless of where it happens.

--

Tony Arcieri

[Paul Hoffman]

On Feb 23, 2023, at 6:43 PM, Tony Arcieri <bas...@gmail.com> wrote:
>
> On Thu, Feb 23, 2023 at 3:45 AM Thom Wiggers <th...@thomwiggers.nl> wrote:
> There are plenty of standards that define file formats where public keys and secret keys can be stored together, e.g. PKCS#12 (even though using PKCS#12 for this problem is probably like shooting a fly with a bazooka).
>
> What would really be helpful here is PKCS#8, specifically v2 as specified in RFC5958, which defines a `OneAsymmetricKey` message containing an optional `publicKey` field:
>

> https://www.rfc-editor.org/rfc/rfc5958#section-2 [rfc-editor.org]

>
> Standardizing PKCS#8 usage with the NIST post-quantum algorithms seems like important work, regardless of where it happens.

This would require everyone to have ASN.1 compilers/interpreters, which might not be a good use of everyone's programming time. Converting the needed data into something for which there are more serializers/deserializers, like CBOR, would probably take only a little development time. I don't see anything active in this in the IETF, but I could take it on if people thought it would be used in the PQC signing algorithms.

--Paul Hoffman

[Tony Arcieri]

On Thu, Feb 23, 2023 at 8:09 PM Paul Hoffman <paul.h...@icann.org> wrote:

This would require everyone to have ASN.1 compilers/interpreters, which might not be a good use of everyone's programming time. Converting the needed data into something for which there are more serializers/deserializers, like CBOR

For CBOR there's COSE as specified in RFC8152.

However, there's no reason the NIST PQC algorithms shouldn't be standardized for use with many private key formats including PKCS#8 and COSE (not to mention JOSE/JWK and several other key formats).

The advantage of PKCS#8 (and by extension PKCS#12) is it's one of the most widely supported private key formats.

--

Tony Arcieri

[D P]

>>> For every scheme it's possible to make key generation deterministic by replacing "randombytes()" calls by calls to a XOF that has been seeded by the "private key seed".

Hi Bas, thanks for your suggestion. Following your suggestion, we were exploring this route. Will it be safe if the "private key seed" is from another csprng the operation system provides natively? Asking because in some operating systems like Android recent versions, there is no access to the native entropy pool (dev/random), to get the private seed from. 

We were exploring on lines of getting the "private key seed" by calling native OS csprng (urandom) and then feeding that seed into ChaCha20 drng.  The "private key seed" will become the secret. But since the original seed was from another csprng and not from the native entropy pool, we aren't sure if this is safe (safe as in not being able to guess the private seed).

Any suggestions on this will be very helpful!

[Kerckhoffs's Ghost]

void ENTROPY_MIX(unsigned char *out, unsigned char *entropy1, unsigned char *entropy2, const unsigned char *entropy3) {
unsigned char tmp_entropy_buffer[DIGEST_WIDTH]={0};
EVP_MD_CTX *hash_mdctx;
hash_mdctx = EVP_MD_CTX_new();
unsigned x;
EVP_DigestInit_ex(hash_mdctx, EVP_sha3_512(), NULL);
EVP_DigestUpdate(hash_mdctx,entropy1,DIGEST_WIDTH);
EVP_DigestUpdate(hash_mdctx,entropy2,DIGEST_WIDTH);
EVP_DigestFinal_ex(hash_mdctx, tmp_entropy_buffer, &x);
EVP_MD_CTX_free(hash_mdctx);
for (int i =0; i < DIGEST_WIDTH; i++) {
out[i] = tmp_entropy_buffer[i]^entropy3[i];
}
}

We use an approach like this in environments that have no constraints on entropy. It would also work in your situation, in theory. 

Best,

Sam

-- 
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/8cae2bd2-088e-40f4-bd6a-77fde27c92c7n%40list.nist.gov.

[D P]

>>> We were exploring on lines of getting the "private key seed" by calling native OS csprng (urandom) and then feeding that seed into ChaCha20 drng.

To give some more context on what we were trying to do, the seeded ChaChaa20 drng will be used for randombytes() when creating the actual keypair. But since it's a drng based on csrng (which likely is based on ChaCha20 depending on OS), we weren't sure if this is safe.

>>>We use an approach like this in environments that have no constraints on entropy. It would also work in your situation, in theory. 

Thanks, will check it out.