UOV parameters

[Bo-Yin Yang]

Dear PQC-list:

In view of the recent Beullens attack on Rainbow and the new NIST upcoming call stressing longstanding digital signature schemes, it is surely important to select some parameter sets for Unbalanced Oil and Vinegar, the most venerable non-lattice extant PQ digital signature scheme.

Our team has examined the design space and come up with the following parameter sets and will implement them for the public good.  The numbers are (where q is the field size, n is #oil+#vinegar, and m=#oil) for NIST security levels 1, 3, and 5.

q: 16,   n: 160, m: 64, (SL1)
q: 256, n: 112, m: 44, (SL1)
q: 256, n: 184, m: 72, (SL3)
q: 256, n: 244, m: 96, (SL5)

best wishes,
Ward Beullens, Ming-Shing Chen, Jintai Ding, Matthias J. Kannwischer, Jacques Patarin, Albrecht Petzoldt, Dieter Schmidt, Chengdong Tao, and Bo-Yin Yang

[Daniel Apon]

Thanks, guys.

Have you benchmarked these new parameter sets for clock cycles of KG/Sign/Verify?

--Daniel

--
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/16e85f78-a37a-4213-81cb-f2dd48d85e02n%40list.nist.gov.

[Bo Lin]

Hi,

Thanks for the update.

Does this mean that the key size of UOV is as follows?

q	n	m	key size (bits)	key size (bytes)
			(q*m*n^2)/2	(key size (bits)) / 8
16	160	64	5,242,880	655,360
256	122	44	30,232,576	3,779,072
256	184	72	122,093,568	15,261,696
256	244	96	287,834,112	35,979,264

Regards,

Bo

--

[Matthias Kannwischer]

Dear Bo, 

No, the public-key size of plain UOV is log_256(q)*m*n*(n+1)/2 bytes.

So, you have public keys of  

412160 bytes
278432 bytes
1225440 bytes
2869440 bytes

Cheers, 

Matthias 

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAL3OXVzDkhG%2BW3Lo4yXJ1v-T4iL9rwVma8cOEQ0of_jJOGZZBA%40mail.gmail.com.

[Bo Lin]

Thanks Matthias.

Yes, indeed, I missed the log operation and misplaced the m and n in the Spreadsheet. The (n+1) item was not known to me though. The following table is a re-calculation according to your correction:

parameters

key size (bits)

key size (bytes)

q	log(q)	n	m	(log(q)*m*n*(n+1))/2

(key size (bits)) / 8

16	4	160	64	3,297,280	412,160
256	8	122	44	2,641,056	330,132
256	8	184	72	9,803,520	1,225,440
256	8	244	96	22,955,520	2,869,440

[Matthias Kannwischer]

Dear Bo, 

n should be 112 for the second parameter set. 

Cheers, 

Matthias

[wa...@beullens.com]

Dear all,

Note that a large part of a UOV public key is uniformly random and can be expanded from a short seed. (see https://eprint.iacr.org/2010/424 for the details)

So, the public key size is really only log(q)m^2(m+1)/2 bits + a short seed.

This reduces the public key size from 412.2KB to 66.6 KB for the first parameter set.

All the best,
Ward

 

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAKaNK-4LwM6NmfpzPwXU0LPHznJVP6n0nJbUknBdg9VLHKSpQw%40mail.gmail.com.

[Bo Lin]

Hi, Matthias,

Thanks for the correction. It is ratified as

parameters				key size (bits)	key size (bytes)
q	log(q)	n	m	(log(q)*m*n*(n+1))/2	(key size (bits)) / 8
16	4	160	64	3,297,280	412,160

256

8

112

44

2,227,456

278,432

256	8	184	72	9,803,520	1,225,440
256	8	244	96	22,955,520	2,869,440

[Matthias Kannwischer]

Dear Daniel,

thanks for your question about performance benchmarks.

We are currently finalizing AVX2, SSSE3, Arm Neon, and Arm Cortex-M4 implementations of the proposed UOV parameter sets and we will be posting the benchmarking results on the forum soon.

Best regards,
The Team

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAPxHsSJkzqNrPth_qHxHgYDPgXAMM5ipOPFBVnPVsXhXkhzP0A%40mail.gmail.com.

[andy yi]

Does anyone know what the Rainbow algorithm is about submitting the updated parameters?

[Jintai Ding]

Yes. Soon, we are doing final check our numbers. 

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/7a13f798-e89f-4596-85ac-97dba686dc18n%40list.nist.gov.

--

Jintai Ding, PhD
Professor of Mathematics
Tsinghua University