Round 1 (Additional Signatures) OFFICIAL COMMENT: Biscuit

[Charles Bouillaguet]

Dear all,

This messages argues that the parameters chosen by the designers of
Biscuit are a bit too small.

Biscuit relies on the hardness of the so-called "PowAff2" problem,
namely to solve polynomial systems of a special kind. The secret key
contains a secret vector s and the public key contains random
polynomials f_1, ..., f_m along with a vector t such that t_i = f_i(s).
Signatures are non-interactive proofs of knowledge of s. Solving the
corresponding polynomial system reveals the secret key.

To make the scheme more efficient, the polynomials have a special shape
f_i = w_i + u_i * v_i, where the w_i, u_i and v_i are affine forms. The
point is that evaluating f_i requires a single multiplication (by a
non-constant).

These special polynomial systems (product of two affine forms) are
easier to solve than arbitrary quadratic systems. For instance, the
designers of Biscuit show a simple algorithm that works in q**(0.75*n)
operations, where n is the number of variables. No such simple
algorithms are known in general.

However, here is another simple "crossbred-style" algorithm that
requires only q**(0.5n) operations:
1) perform a linear change of the n variables y == Mx that yields v_i(y)
= y_i + cst for (0 <= i < n)
2) guess the first n/2 variables
3) the first n/2 quadratic equations become affine in the remaining n/2
variables.
4) solve the linear system in the remaining n/2 variables
5) rinse, repeat.

This comes down to a loop with q**(n/2) iterations, and each iteration
requires O(n^3) operations.

This implies that the secret key can be recovered in 2**174 and 2**236
iterations of this simple procedure for the parameter sets that are
claimed to offer 192 and 256 bits of security, respectively.

There is a simple fix: increase the number of variables to 96 and 128.
Some extra margin is probably required as well, because the simple
technique outlined above can be improved.

In addition, the idea underlying this simple observation ("guess one
variable, get one linear equation for free") has other implications on
the security against forgery attacks that are a bit less clear.

More details will appear on the eprint.

Best regards,
--
Charles BOUILLAGUET
Sorbonne Université
Campus Pierre & Marie Curie
LIP6/ALMASTY, Office 24-25/410
4 place Jussieu, 75252 Paris Cedex 05
homepage: https://www-almasty.lip6.fr/~bouillaguet

[Ludovic Perret]

Dear Charles, 

On behalf of the Biscuit team, we would like to thank you for your comments.  We acknowledge that the approach described below is correct 

and yields an algorithm whose complexity is O((n/2)^3q^(n/2)). In your computations, you did not included the cost of the linear algebra part. 

Taking into account this additional factor: 

• Cat I still reach the security level  
• Cat III is only1 bit off (206.32 instead of 207) 
• Cat V is 3 bits off (269.6 instead of 272)      

Your approach improves our previous structured algorithm for solving the problem underlying Biscuit, PowAff2, which has a complexity of q**(0.75*n). 

We will update the specification document to take into account your new algorithm and modify  the parameters accordingly. As you mentioned, the fix is 

rather minor and has a minimal impact on the signature sizes.  

The parameters of Biscuit are derived taking into account two approaches : "ad-hoc" algorithms dedicated to Pow2 that use the structure of the equations and general-purpose algorithms  

(such as Groebner bases, polynomial approximation, etc …). The latter type of algorithms were faster and used to derive the parameters.  

We disagree on you statement that PowAff2 systems are computationally easier to solve than quadratic algorithms. It is of course correct to say that simple algorithms exist for PowAff2, 

but this does not necessarily implies that such algorithms are faster than general-purpose algorithms. At this stage, your new ad-hoc algorithm has — in fact — roughly the same asymptotical 

complexity as general-purpose algorithms.

Best Regards, 

The Biscuit team,

------ Message d'origine ------

De "Charles Bouillaguet" <charles.b...@gmail.com>

À pqc-co...@nist.gov

Cc pqc-...@list.nist.gov

Date 19/07/2023 09:13:37

Objet [pqc-forum] Round 1 (Additional Signatures) OFFICIAL COMMENT: Biscuit

-- 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/808d0ef8-1590-53b8-743e-2754081d2424%40gmail.com.

[Charles Bouillaguet]

Dear Ludovic, designers of the Biscuit teams, other members of the mailing-list,

> We disagree on you statement that PowAff2 systems are
> computationally easier to solve than quadratic

> algorithms. [...] At this stage, your new ad-hoc algorithm has

> — in fact — roughly the same asymptotical complexity as
> general-purpose algorithms.

Let us look at what happens over the field with 2 elements.

For arbitrary Boolean quadratic systems, the best algorithm known to mankind at
this time, which is due to Dinur [1], requires 2^(0.6943*n) operations.  The
simple algorithm outlined in my previous message, which is specific to the
"PowAff2" problem, requires 2^(0.5*n), and thus is exponentially better.

So, at least over the field with two elements, PowAff2 is much easier than the
problem of solving random quadratic systems.

Regarding concrete security levels, I agree that the naive algorithm I outlined
in my previous message was not enough to go beyond the pain threshold. However,
it is easy to improve upon. Combining it with the (self-proclaimed) dumbest
possible algorithm that beats brute force [2] yields the following:

1) perform a linear change of the n variables y == Mx that yields v_i(y) = y_i + cst for (0 <= i < n)

2') Set k := 0.5 * (n - sqrt(2*m - n + 1) + 1).  Guess the first k variables
3') The first k quadratic equations become affine in the remaining n - k variables.  Use these to eliminate k variables in the last m-k quadratic polynomials
    [at this stage, m-k quadratic polynomials in n-2k variables remain]
4') Solve the resulting quadratic system by linearization (it has less than m-k monomials of degree <= 2).
5') Go back to step 2' until a solution is found

Step 4' costs O((m-k)^3) operations, which is 8 times more than before.
However, the number of iterations is decreased compared to my first message.
This results in:

| instance   |   n |   m |  k | #monomials (1) | log2(#operations) (2) |
|------------+-----+-----+----+----------------+-----------------------|
| biscuit128 |  64 |  67 | 29 |             27 |                 130.2 |
| biscuit192 |  87 |  90 | 40 |             35 |                 175.4 |
| biscuit256 | 118 | 121 | 54 |             65 |                 234.0 |
|------------+-----+-----+----+----------------+-----------------------|

(1) There are 1/2*(n-2*k + 3)*(n-2*k) non-constant monomials of degree <= 2 in n-2*k variables
(2) This is (#monomials)^3 * q^k

This beats the claimed bit-security levels given in Table 11 of the submission
document by 30, 34 and 42 bits for biscuit128, biscuit192 and biscuit256,
respecticely, if I'm not mistaken.

Note that these results are obtained using the simplest possible methods, that
require no memory and just combine exhaustive search with small, dense linear
algebra. I consider this to be an indication that the "PowAff2" problem is
easier than arbitrary quadratic systems.

In any case, it seems likely that even better results will be obtained using
more sophisticated techniques. As such, if I were you, I would be conservative
in revising the parameters.

Best regards,
-----
Charles Bouillaguet

[1] Itai Dinur. Improved algorithms for solving polynomial systems over GF(2) by
    multiple parity- counting. In Dániel Marx, editor, Proceedings of the 2021
    ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference,
    January 10 - 13, 2021, pages 2550–2564. SIAM, 2021.

[2] Charles Bouillaguet, Claire Delaplace, and Monika Trimoska. A simple
    deterministic algorithm for systems of quadratic polynomials over GF(2) . In
    Karl Bringmann and Timothy Chan, editors, 5th Symposium on Simplicity in
    Algorithms, SOSA@SODA 2022, Virtual Conference, January 10-11, 2022, pages
    285–296.  SIAM, 2022.

[Ludovic Perret]

Charles,

Again, many thanks for the effort to analyze the security of Biscuit. The approach seems correct and we like the idea of using the hybrid approach.

Still, the complexities that you computed below are field operations. In our documents 

(Table 11), we provide bit operations  (using the fact that a field operations cost (log(q))^2 bit operations). If you use the same unit for the comparison, we obtain the following complexities.

Set k num_mon   num_polys           n_bit_op

I    29       27         38          146.2646625064904

III 40       35         50           191.3878490508349

V     54       65         67           250.06710343908537

 

So, still Cat I parameters are above the security margin.  Of course, we were planning to take into careful consideration of your comments and adapt the parameters accordingly.

Best Regards,

The Biscuit team 

Le 25 juil. 2023 à 00:18, Charles Bouillaguet <charles.b...@gmail.com> a écrit :

Dear Ludovic, designers of the Biscuit teams, other members of the mailing-list,

[Charles Bouillaguet]

Dear Ludovic,

> Still, the complexities that you computed below are field operations. In our
> documents (Table 11), we provide bit operations (using the fact that a field
> operations cost (log(q))^2 bit operations). If you use the same unit for the
> comparison, we obtain the following complexities.

The numbers you provide are taken by adding 16 to what I came up with.  Indeed,
each field operation requires O(log2(16)**2) == O(16) bit operations in some
simplified abstract model... assuming that this has any meaning at all.

However, in the table I provided, the complexities are given as the base-2
logarithms of the number of operations. So, if you want to include the fact that
a multiplication over GF(16) requires about 16 bit operations, then you should
have added log2(16) == 4, and not 16.

In fact, the structure of PowAff2 instances has the following consequence
(already stated in my first message): after a suitable change of variable, if
you guess one variable, you get one extra linear equation for free, and this allows you
to eliminate another variable.  The point is that this shifts the tradeoff of
the "hybrid method" in a more favorable way (or unfavorable way, depending on
the point of view).

Starting with n variables and m polynomials, hereafter denoted as (n, m), the
usual hybrid method consists in guessing k variables; this goes from (n, m) to
(n-k, m).

With PowAff2, the strategy I described above goes from (n, m) to (n-2k, m-k).
This is almost certainly more efficient asymptotically, even though I have not
yet worked out the precise details yet.

In the following, I use the MQEstimator, as suggested in the submission
document.  I checked that it computes "bit complexities": it considers that a
finite-field multiplication requires 2 * log2(q)**2 + log2(q) "gates".

Here is a table that shows the difference in efficiency between the "classic"
hybrid method (the only one that is applicable to an arbitrary system of
quadratic polynomials) and the "improved" hybrid method (applicable to PowAff2
systems).  k and k' are the number of variables that are guessed in both case.
The complexity is obtained by assuming that the subsequent system is solved with
the F5 algorithm, and using MQEstimator to get its number of bit operations.
The "claimed bit-security" is taken from table 11 of the submission document.

 | instance   |          claimed |   n |   m |   |  k | Classic hybrid method |   | k' | Improved hybrid method |
|            | bit-security (*) |     |     |   |    | (log2 bit complexity) |   |    |  (log2 bit complexity) |
|------------+------------------+-----+-----+---+----+-----------------------+---+----+------------------------|
| biscuit128 |              160 |  64 |  67 |   | 11 |                 151.3 |   | 17 |                  124.2 |
| biscuit192 |              210 |  87 |  90 |   | 17 |                 200.6 |   | 26 |                  163.4 |
| biscuit256 |              276 | 118 | 121 |   | 21 |                 266.5 |   | 31 |                  214.9 |
|------------+------------------+-----+-----+---+----+-----------------------+---+----+------------------------|

The bit complexity of the improved hybrid method (using the F5 algorithm) are
always below what they should be, including for biscuit128, although only by a
small margin (4 bits).

Best regards,
--
Charles Bouillaguet