Nicolas Veyrat-Charvillon

Benoît Gérard

François-Xavier Standaert

Soft Analytical Side-Channel Attacks

come   L'archive ouverte pluridisciplinaire

Introduction

The great majority of side-channel attacks published in the literature follow a divide and conquer strategy (DC). That is, they first attack independent parts of the key separately (divide), and then combine these pieces of information (conquer). Information on individual parts of the key is obtained by studying correlations between key-dependent leakage predictions and the actual sidechannel measurements. The information can then be combined either by simply concatenating the most probable values of each key part together, or by using an enumeration algorithm [START_REF] Veyrat-Charvillon | An optimal key enumeration algorithm and its application to sidechannel attacks[END_REF][START_REF] Veyrat-Charvillon | Security evaluations beyond computing power[END_REF]. Examples of distinguishers exploiting such a strategy include Kocher et al.'s Differential Power Analysis (DPA) [START_REF] Paul | Differential power analysis[END_REF], Brier et al.'s Correlation Power Analysis (CPA) [START_REF] Brier | Correlation power analysis with a leakage model[END_REF], Gierlichs et al.'s Mutual Information Analysis (MIA) [START_REF] Gierlichs | Mutual information analysis[END_REF], Chari et al.'s Template Attacks (TA) [START_REF] Chari | Template attacks[END_REF] and Schindler et al.'s Stochastic Approach (SA) [START_REF] Schindler | A stochastic model for differential side channel cryptanalysis[END_REF]. The popularity of these tools is due to their simplicity and versatility: they can be adapted to essentially any implementation, have low time complexity and work in a gray box manner. That is, they do not require a precise understanding of the underlying hardware, but their data complexity is highly dependent on the quality of the adversary's leakage predictions. Therefore, the knowledge of implementation details and some engineering intuition can usually be exploited to improve their time and data complexity.

In this context, one fundamental question regarding DC distinguishers is whether they are sufficient for security evaluations. That is, are the security levels estimated with such tools close enough to the worst-case? In view of the previously listed qualities (and in particular, their excellent time complexity), the most likely drawback candidate for DC strategies is a suboptimal data complexity. As a result, a number of research works have investigated whether the application of analytical strategies (i.e. targeting the full key at once) could provide improved results. To the best of our knowledge, one of the first attempts in this direction was Mangard's Simple Power Analysis (SPA) against the AES key expansion algorithm [START_REF] Mangard | A simple power-analysis (SPA) attack on implementations of the AES key expansion[END_REF]. The Side-Channel Collision Attacks (SCCA) in [START_REF] Bogdanov | Algebraic methods in side-channel collision attacks and practical collision detection[END_REF][START_REF] Schramm | A collision-attack on AES: Combining side channel-and differential-attack[END_REF][START_REF] Schramm | A new class of collision attacks and its application to DES[END_REF] were next interesting steps, in which the key is recovered by solving a set of (mostly) linear equations corresponding to the first cipher round(s). Following, Algebraic Side-Channel Attacks (ASCA) were introduced in [START_REF] Renauld | Algebraic side-channel attacks[END_REF][START_REF] Mathieu Renauld | Algebraic side-channel attacks on the AES: Why time also matters in DPA[END_REF] and probably constitute the most representative example of analytical strategy to date. Under certain conditions, they are able to extract the key of an AES implementation from a single leakage trace, in an unknown plaintext/ciphertext scenario.

So to some extent, ASCA could be viewed as an extreme opposite to DC attacks, with a minimum data complexity coming at the cost of a (much) more complex and sensitive solving phase -hence raising questions regarding their practical relevance. For example in the first papers from Renauld et al., the adversary represents the target block cipher and its leakages as an instance of satisfiability problem that she sends to a generic sat solver (other types of solvers, e.g. based on Gröbner bases, have also been analyzed [START_REF] Carlet | Analysis of the algebraic side channel attack[END_REF]). The main issue with this approach is a very weak resistance to noise, since the solver essentially needs to be fed with correct hard information. For this purpose, the usual strategy was to group certain leakage values according to a model with lower cardinality, e.g. the well-known Hamming weight one, in order to trade robustness for informativeness. Improved heuristics are presented in [START_REF] Saied | Improved algebraic side-channel attack on AES[END_REF][START_REF] Zhang | Improved algebraic fault analysis: A case study on piccolo and applications to other lightweight block ciphers[END_REF]. More recently, Oren et al. proposed to replace the use of a solver by that of an optimizer, leading to Tolerant ASCA (TASCA) able to exploit more general models [START_REF] Oren | Algebraic sidechannel analysis in the presence of errors[END_REF][START_REF] Oren | Algebraic side-channel attacks beyond the hamming weight leakage model[END_REF]. Yet, even these last attempts were quite inefficient in exploiting soft information, mainly because of the difficulty to translate a vector of probabilities (e.g. as provided by classical TA) into an optimizer-friendly format. In fact TASCA essentially encode these vectors as exhaustive hard information, hence limiting the number of leaking operations that could be included in the optimizer to a couple of rounds (compared to the full cipher in ASCA), because of memory issues. Eventually, the results in [START_REF] Guo | Exploiting the incomplete diffusion feature: A specialized analytical side-channel attack against the AES and its application to microcontroller implementations[END_REF] provide yet another powerful approach to analytical side-channel attacks, based smart enumeration and specialized to the AES, but so far they also remain limited to the exploitation of hard information. This state-of-the-art seems to suggest that the probabilistic information provided by side-channel leakages can be easily exploited with DC attacks, while analytical strategies require a preprocessing step to translate this soft information into hard one. In this paper, we argue that this intuition is flawed, and in fact relates to the way of formulating the problem rather than to its nature. That is, while previous analytical attacks were expressing the target block ci-phers and their leakages as equations, we propose to describe the same problem as a code. As a result, and for the first time, we detail a Soft Analytical Side-Channel Attack (SASCA) that combines the best of two worlds, namely the noise robustness and low time complexity of DC strategies with the low data complexity of analytical ones. In this respect, our first contribution is to exhibit a natural way to encode a side-channel cryptanalysis problem. Next, we show that we can efficiently decode such problems thanks to the Belief Propagation algorithm (BP). Using these new tools, we are able (i ) for low noise levels: to attack the aes furious implementation that was targeted in previous works on ASCA/TASCA with a single leakage trace, with significantly reduced time and memory complexities, (ii ) for large noise levels: to attack the same implementation with multiple plaintexts, but with 2 3 to 2 4 less traces than a standard TA. Summarizing, the proposed technique bridges the gap between DPA and ASCA.

Related works. While the motivation for SASCA quite directly derives from previous works in ASCA/TASCA, its mathematical modeling fundamentally differs from them and is in fact much closer to some results exploiting techniques from coding theory. In particular, the application of Hidden Markov Models in the context of time-randomized implementations [START_REF] Durvaux | Efficient removal of random delays from embedded software implementations using hidden markov models[END_REF][START_REF] Karlof | Hidden markov model cryptoanalysis[END_REF] or side-channel disassemblers [START_REF] Eisenbarth | Building a side channel based disassembler[END_REF], and the decoding of Low Density Parity Check (LDPC) codes in the context of SCCA [START_REF] Gérard | Unified and optimized linear collision attacks and their application in a non-profiled setting[END_REF] were sources of inspiration for the following work.

Cautionary note. In order to show the applicability of SASCA at different noise levels, our empirical results are based on simulated experiments. Yet, we insist that SASCA is (in general) just as realistic as any TA, since it relies on the same assumptions for the profiling phase (i.e. the knowledge of a single key -see Appendix A). Furthermore, we paid attention to exploit exhaustive templates (i.e. used 256 profiles per intermediate value attacked) which can be generalized to any leakage function and corresponds to the worst-case time complexity.

Soft Analytical Side-Channel Attacks

We first emphasize the differences between previous solver-or optimizer-based approaches to analytical side-channel attacks and our decoder-based solution. We then describe the BP algorithm and discuss its connection to the exploitation of side-channel leakage. We finally detail how to describe an AES implementation as a factor graph, that can be efficiently decoded by BP. The following descriptions assume a profiled attack scenario, as usual in worst-case evaluations [START_REF] Standaert | A unified framework for the analysis of side-channel key recovery attacks[END_REF].

Solving (or optimizing) vs. decoding

In the course of a profiled side-channel attack, the adversary extracts information from leakage traces. This information comes from the processing of intermediate values throughout the cryptographic computations. By comparing these leakages with previously estimated templates, she obtains for each target value X i a conditional posterior distribution Pr[X i |L]. Provided the device is not perfectly side-channel resistant, most of the posterior distributions will have an entropy lower than that of a uniform distribution. In this context, the most interesting pieces of information relate to the encryption key. For this purpose, not only the leakages that directly correspond to key bytes -informally denoted as SPA leakages -are exploited, but also those of intermediate variables that depend on both the key and the (usually known) plaintext -informally denoted as DPA leakages -such as the sbox outputs in the first aes round, typically. For example, starting from the posterior probability of the output value S out given the leakage L out , one can deduce its image before the substitution layer:

Pr[S in = v|L out ] = Pr[S out = sbox(v)|L out ].
For a known plaintext value P , one can compute a posterior distribution on a key byte K by unrolling the computation one step further:

Pr[K = k|P = p, L out ] = Pr[S out = sbox(k ⊕ p)|L out ].
These simple equations show that it is possible to derive information about the key using intermediate variables. Furthermore, one can easily combine the leakage obtained from multiple plaintexts, by marginalizing Pr(K = k) over the corresponding traces: this is in fact what DC attacks do. Next, and since multiple key-dependent variables can usually be found within cryptographic implementations, a natural problem is to find ways to exploit them efficiently. But this is exactly where the DC strategy faces limitations. Namely, combining the leakage of these intermediate variables is trivial as long as they only depend on a single key byte, e.g. the sbox inputs and outputs in a first block cipher round. One just deals with the additional variable as with an additional plaintext in this case. Taking the example of aes, this can even be extended to the first mixcolumns operation, if 32-bit key hypotheses are performed by the adversary. But the DC approach is inherently limited to the exploitation of predictable parts of the key. So as soon as the diffusion is complete (which very rapidly occurs in modern ciphers and therefore corresponds to most of their intermediate computations), the leakages are left unexploited by such strategies. This limitation directly leads to the main problem we tackle in this paper, namely: How to efficiently exploit the leakage of any intermediate variable in a side-channel attack?

Previous ASCA were a first attempt to answer this question, by trying to solve a system of equations describing the target cryptographic algorithm, complemented with the information extracted. These attacks typically begin by sieving intermediate values, keeping only the most probable ones. A usual approach is to coalesce the leakages by Hamming weights for this purpose. The set of remaining values is then verified one against another (e.g. using heuristic sat-solvers). Unfortunately, this algebraic approach cannot easily deal with the probability distributions output by TA, which are thus discretized and sieved. Whenever the measurement noise is not negligible, this introduces "errors" that are fatal to algebraic solvers. As mentioned in introduction, optimizers allow mitigating this problem, but are still limited in the exhaustive way they encode the probabilities (which is too expensive for describing more than a couple of aes rounds).

Our method works differently, by operating directly on the posterior distributions of the intermediate values extracted from leakage traces, and propagating the information throughout the computation steps of the algorithm. When attacking a cryptographic implementation, we first build a large graphical model containing the intermediate variables, which are linked by constraints corresponding to the atomic operations executed. For instance, the exclusive-or and sbox functions are usually found in software implementations of the aes. Next, the goal is to find the marginal distribution of the key, given the distributions of all the intermediate variables. While this is generally a hard problem, we observe that an important feature of cryptographic algorithms is that intermediate values tend to appear only in a few places. A similar behavior is present in Gallager codes [START_REF] Robert | Low-density parity-check codes[END_REF], also called Low-Density Parity Check codes (LDPC). In such a code, codeword bits are linked together by a small number of parity constraints (i.e. linear in the codeword size). Decoding such a construction is generally performed via application of the BP algorithm, also known as sum-product algorithm. Our application in the following sections is a (conceptually) simple extension, where values are not limited to bits, and parity constraints go beyond exclusive-ors.

The Belief-Propagation algorithm

Our description of the BP algorithm is largely based on the (excellent) description provided in [14, chapter 26]. Let us consider a set of N variables x ≡ {x n } N n=1 , and define a function P * of x which is a product of M factors:

P * (x) = M m=1 f m (x m ),
where each factor f m (x m ) is a function of a subset x m of x. The P * function is typically depicted using a factor graph, in which circles correspond to variables x i and squares to functions f m . An edge is drawn between x i and f m if x i ∈ x m , meaning that the m-th factor depends on the i-th variable. For example, the parity functions and factor graph of a simple 3-repetition code are shown below:

f 1 (x 1 ) = Pr(x 1 = 1) f 2 (x 2 ) = Pr(x 2 = 1) f 3 (x 3 ) = Pr(x 3 = 1) f 4 (x 1 , x 2 ) = 1 if x 1 ⊕ x 2 = 0 0 otherwise f 5 (x 2 , x 3 ) = 1 if x 2 ⊕ x 3 = 0 0 otherwise f 1 f 2 f 3 f 4 f 5 x 1 x 2 x 3
The task we are interested in is that of marginalization. That is, we aim to be able to compute the following function:

Z n (x n ) = x,xn=xn P * (x),
and more importantly it normalized version P n (x n ) = Z n (x n )/Z, where:

Z = x M m=1 f m (x m ).
These tasks are intractable in general. Even when the factor functions are limited to three variables, the cost of computing the exact marginal is believed to grow exponentially with the number of variables N . The BP algorithm can circumvent this problem and compute marginals efficiently as long as the factor graph is treelike. We will denote by N (m) the set of variables involved in factor f m , by M(n) the set of factors where variable x n appears, and shorthand the set of variables in x m with x n excluded as:

x m \ n ≡ {x n : n ∈ N (m) \ n}.
The algorithm works by passing two types of messages along the edges of the factor graph, from variables to factors (q n→m ) and from factors to variables (r m→n ). The sets of messages are updated using two rules:

q n→m (x n ) = m ∈M(n)\m r m →n (x n ). r m→n (x n ) = xm\n   f m (x m ) n ∈N (m)\n q n →m (x n )   .
Convergence should occur after a finite number of iterations, at most equal to the longest path. Once the network has converged, the marginal function (also called belief ) of a variable x n can be recovered by multiplying together all incoming messages at the corresponding node:

Z n (x n ) = m∈M(n) r m→n (x n ).
The normalized value P n (x n ) = Z n (x n )/Z is easily obtained by summing together the marginal functions Z = xn Z n (x n ). As already mentioned, the BP algorithm returns the exact marginals as long as the factor graph is a tree-shaped graphical model. Yet, in many useful cases such as decoding, the graph contains cycles. Fortunately, BP can be applied directly on general factor graphs as well, raising the so-called "loopy" BP. While this version does not guarantee to return the correct marginals, and may even not converge to a fixed point in some cases, it usually gives results that are good enough for most applications.

Efficient representation of an AES implementation

Our method for SASCA consists in an application of the BP algorithm to the decoding of keys using plaintexts, ciphertexts and side-channel traces. In this section, we illustrate it in the context of an implementation of the aes in an 8bit device. For this purpose, the x i variables defined in the description of the BP algorithm will represent the intermediate values handled by the cryptographic algorithm, and the parity functions will be separated into two sets:

-The first set corresponds to the a priori knowledge on the variables acquired through side-channel leakages, denoted as

f i (x i ) = Pr[x i = v|L].
-The second set corresponds to the operations executed by the implementation. In the case of a binary operation op(x i1 , x i2 ), the function is defined by:

f i (x i1 , x i2 , x i3 ) = 1 if op(x i1 , x i2 ) = x i3 , 0 otherwise.
Based on these notations, an adversary first has to encode the aes computations in a form that is compatible with the BP algorithm. For illustration, and because it is publically available, we will describe how to build a factor graph for the aes furious implementation (http://point-at-infinity.org/avraes).

Concretely, our program takes in a description which is very similar to the assembly code of aes furious, with the memory related operations left out, but where any assignment requires a newly named variable. Namely, variable nodes are denoted by names starting with a capital letter, such as K[2,4]_0 for the intermediate key in row 2 and column 4 of key scheduling round 0, which also happens to be the second master key byte (noted K 0 2,4 in the factor graph), or SB[2,1]_0 for the sbox output in row 2 and column 1 of round 0 (SB 0 2,1 in the factor graph). These variable nodes correspond to intermediate values computed during encryption, such as the state (ST), key addition or mixcolumns intermediate results (AK and MC), outputs of xtime operations (XT), . . . Besides, factor node names start with an underscore such as _Xor (exclusive or) and _Xtime (polynomial multiplication by x). They correspond to instructions executed during encryption. For example, Table 1 gives samples of the correspondence between the assembly code, input description and factor graph. Note that the factor nodes for the prior probabilities of the variables are not drawn.

Assembly code Graph description

Factor graph ld H1, Y+ eor ST11, H1 mov ZL, ST11 lpm ST11, Z

* _Xor AK[1,1]_0 ST[1,1]_0 K[1,1]_0 * _Sbox SB[1,1]_0 AK[1,1]_0 xor sbox AK 0 1,1 ST 0 1,1 K 0 1,1 SB 0 1,1 mov H3, ST11 eor H3, ST21 mov ZL, H3 lpm H3, Z * _Xor MC[3,1]_0 SB[1,1]_0 SB[2,1]_0 * _Xtime XT[1,1]_0 MC[3,1]_0 xor xtime SB 0 1,1 SB 0 2,1 M C 0 3,1 XT 0 1,1 mov ZL, ST24 lpm H3, Z eor ST11, H3 eor ST11, H1 * _Sbox SK[1,1]_1 K[2,4]_0 _Xor XK[1,1]_1 SK[1,1]_1 K[1,1]_0 _XorCst K[1,1]_1 XK[1,1]_1 0x1 sbox xor xorcst K 0 2,4 SK 1 1,1 K 0 1,1 XK 1 1,1 K 1 1,1

Table 1: Factor graph representation of an aes encryption

There are two notable differences between SASCA and the classical decoding of LDPC codes. First, variable nodes are not binary digits, but rather elements of GF(2 8 ). Second, factor nodes are not limited to exclusive or's, but may include any of the variety of functions used in cryptographic implementations (e.g. xor, sbox, xtime). However, these factor nodes are not much more complex than for classical decoding, as illustrated with our three previous examples:

xor(A, B, C) = 1 if A ⊕ B = C, 0 otherwise. sbox(A, B) = 1 if A = S(B), 0 otherwise. xtime(A, B) = 1 if A = Xt(B), 0 otherwise.
This natural representation of operations is very efficient, as opposed to the contrived way aes encryptions are translated to sat instances (roughly, it corresponds to 1,200 equations and variables in GF(2 8 ) compared to 18,000 equations in 10,000 variables in sat-based ASCA). Taking advantage of it, the SASCA adversary then tries to compute the key marginal probability for P n (K) given the leakages. For this purpose, one simply has to incorporate the implicit factor nodes corresponding to prior knowledge on variable nodes, as given by the templates of the side-channel attack. For instance, the factor for the output of the first sbox in the first round f m (SB 0 1,1 ) is the posterior distribution P r[SB 0 1,1 |L]. In addition, any known value (for instance the plaintext bytes) has a prior knowledge with entropy zero, and any value that does not leak (either because it is protected or precomputed) has a uniform prior. Eventually, the loopy BP algorithm propagates information throughout the factor graph: if successful (i.e. in case of convergence), it should return the approximate marginal probabilities of the key bytes P n (K 0 1,1 ) to P n (K 0 4,4 ), i.e. the answer we are looking for.

Attacking with several traces

The ability to efficiently exploit (i.e. combine the information of) several leakage traces is one of the reasons that have made DPA attacks so popular -since it typically leads to the noise vs. data complexity tradeoff that is at the core of most side-channel attacks. It also remains one of the main practical issue for ASCA and follow-up works. So far, the only way several traces can be useful is when they are repetitions of the same encryption (without randomizations), so that the noise can be averaged out. By contrast, adding traces corresponding to multiple plaintexts could only be managed with the construction of larger systems, that are too memory consuming for TASCA, and increasing the probability that one piece of hard information in such systems is incorrect for ASCA.

Interestingly, SASCA are able to improve the key recovery success rate with each additional trace observed. Practically, the factor graph used for decoding is first replicated for each trace. Yet, since the master key stays the same during the course of the attack, the part of our factor graph corresponding the key Key Schedule aes k (P3)

aes k (P2) aes k (P1) K 0 1,1 K 0 1,2 K 0 1,3 . . . K 10 4,4
Fig. 1: Factor graph connections for several traces.

scheduling also remains constant: it forms a kind of "backbone" where all the encryption rounds connect, as depicted in Figure 1. As a result, whenever several messages are used, the probability distributions are propagated from each replicated graph towards the key schedule. The impact of such propagation is in fact very similar to the one resulting from using several traces in a classical TA, where probabilities are multiplied together and the success rate increases.

Experimental results

We now validate the method described in the previous section with illustrative simulated attacks against the aes furious implementation. For this purpose, we assume a setup that is essentially similar to the one used to demonstrate the applicability of ASCA to the AES in [START_REF] Mathieu Renauld | Algebraic side-channel attacks on the AES: Why time also matters in DPA[END_REF]. The only difference is that we will consider implementations with and without the key scheduling leakages. As previously explained (and illustrated in Table 1), all the operations found in the assembly code are translated into factor nodes, excluding memory related operations. For illustration, we considered Hamming weight leakages affected by a noise of variance σ 2 n , but the attack is independent of this choice: any function could be incorporated without performance penalty. The only important parameter in our case is the informativeness of the leakages which, in the first-order setting we investigate, can be measured with a Signal-to-Noise Ratio (SNR) [START_REF] Mangard | One for allall for one: unifying standard differential power analysis attacks[END_REF]. Since the signal (i.e. variance) of a Hamming weight leakage function for 8-bit intermediate values equals 2, one can simply derive the SNR as 2/σ 2 n . For illustration, we compared our results with the ones of two standard TA. Namely, one univariate exploiting only the first-round S-box output leakages, and one bivariate exploiting the first-round S-box input and output leakages.

The results of our experiments are shown in figure 2. The x-axis corresponds to the number of messages used for the attack (in log scale), and the y-axis is a stack of success rate curves for decreasing SNRs (i.e. increasing noise levels). An alternative view is provided in Figure 3, which sums up these simulation results by showing the data complexity gains of SASCA over TA. It appears 2: Attacks results for our simulated furious implementation. Each graph gives the success rate (SR, ranging from 0 to 1) for a given signal-to-noise ratio (SNR, ranging from 2 4 down to 2 -6 ) as a function of the number of traces (in logarithmic scale, ranging from 1 to 5000). The attacks are:

0 1 2 3 0 1 2 2 0 1 2 1 0 1 2 0 0 1 2 -1 0 1 2 -2 0 1 -3 0 1 2 -4 0 1 2 -5
----univariate TA targetting the sbox output (in dark gray ), bivariate TA targetting the sbox input and output (in blue ), -SASCA attack ignoring the key schedule leakages (in violet ), -SASCA attack exploiting all the intermediate values (in orange ).

from both figures that these gains are significant and consistently observed for any noise level. Eventually, the unknown inputs and outputs scenario is detailed for SASCA in Figure 4. We see that its impact is limited if the key scheduling leaks (confirming the results from [START_REF] Mangard | A simple power-analysis (SPA) attack on implementations of the AES key expansion[END_REF]) and more significant otherwise.

2 0 2 -1 2 -2 2 -3 2 -4
Message ratio

2 4 2 3 2 2 2 1 2 0 2 -1 2 -2 2 -3 2 -4 2 -5 2 -6 SNR
Fig. 3: Data complexity gain of SASCA compared to TA given as the fraction of measurements needed to reach a success rate of 0.9 (same colors as in Figure 2).

Discussion. Compared to previous results in ASCA/TASCA, our new tools bring two main advantages. First, from the SNR point of view, these works were typically limited to scenarios where a single leakage trace was enough to recover the master key (i.e. to SNRs > 2 2 ). We can deal with any SNR. Second, the time and memory complexity of the BP decoding is much improved compared to sat-solver based ASCA and optimizer-based TASCA. Our implementation deals with a factor graph of size proportional to the number of messages, with a relatively high (yet easily tractable in practice) constant of approximately 16M per message. Its computation time is proportional to both the diameter of the graph (constant after the second message) which sets the number of decoding iterations, and the number of measurements which sets the amount of messages exchanged at each iteration. This makes the evolution of the time and memory complexity of SASCA quite comparable to the one in divide and conquer TA (i.e. linear in the number of messages). Yet, decoding the AES encryption factor graph with the BP algorithm implies a larger computation time of approximately one second per message in our prototype implementation, running on an Intel i7-2720QM. This (constant) overhead is the main penalty to enjoy the substantially smaller data complexities of SASCA (i.e. similar to ASCA/TASCA) which is, as expected, the main advantage of analytical strategies over DC ones.

As detailed in Appendix A, the practical relevance of such attacks is quite similar to TA, since it requires the same profiling assumptions (i.e. the knowledge of a single key). Admittedly, the profiling effort is significantly more expensive for SASCA, since it requires characterizing all the target intermediate values. But since all these target values can be profiled independently, building their templates can be done quite efficiently (with essentially the same amount of measurements as needed to characterize the first-round operations exploited in TA), and is easily automated with standard side-channel attack techniques.

2 4 2 3 2 2 2 1 2 0 2 -1 2 -2

Conclusions

By modeling the side-channel analysis problem adequately, SASCA bring the missing link between standard DC distinguishers and analytical strategies for key recoveries. As a result and for the first time, we are able to efficiently exploit the probabilistic information of all the leaking operations in a software implementation. Our resulting attacks are optimal in data complexity and efficient in time and memory. Yet, we note that the tools exploited in this first instantiation of SASCA can certainly be improved. For example, the BP algorithm performs too many computations for our needs. Indeed, it propagates every distribution throughout the factor graph whereas in practice, we are mostly interested in the key. Hence, further works could exploit the propagation of messages only towards the schedule (i.e. perform Bayesian inference). This would additionally allow the attack to be performed one message at a time, by accumulating information retrieved from each trace onto the nodes of the key schedule, hence reducing the memory requirements to that of a single trace (i.e. 16M).

In view of the improved noise robustness of SASCA, an important open problem is to determine whether the strong results obtained with this new type of analytical strategy also apply to implementations protected with countermeasures. Masking, shuffling and leakage-resilient cryptography appear as the most interesting targets in this respect. Besides, the experiments in this work considered a worst-case scenario where the adversary could take advantage of all the leaking operations of an AES implementation (i.e. assuming the knowledge of the source code, essentially). But the investigation of an intermediate scenario where the adversary would exploit less leaking observations (e.g. the ones he could guess without knowing the source code) and its resulting time and data complexity is another interesting scope for additional investigations.

A Attack requirements

In this section, we provide a brief discussion of the profiling step that precedes the application of SASCA. In particular, we argue that the profiling overhead and required knowledge for this purpose are similar to those of standard TA.

Profiling Overhead. Similarly to classical TA, SASCA require profiling the leakage corresponding to their target intermediate values. In this respect, the only difference is that they can take advantage of many such values, whereas DC strategies only exploit the first round(s) leakages. In general, one can assume that all target intermediate values leak a similar amount of information. And if it is not the case, it is usually the first round(s) leakages that have lower SNRs. As a result, and given that the set of profiling traces corresponds to random inputs, one can essentially build all the SASCA templates with the same traces as for a TA, by simply re-organizing these traces according to the target intermediate values. This process can be automated based on the implementation knowledge, and its computational cost grows linearly with the number of targets. Concretely, this cost should be small for most concrete implementations, and if needed can be speeded up by assuming sets of intermediate values to leak according to the same model (possibly at the cost of some information loss).

Required Knowledge. Since templates are built by grouping the leakage traces according to some target intermediate values, it requires being able to predict these values. Both for TA and SASCA, this is usually achieved thanks to some key knowledge (or a profiling device). So both attacks can be based on the same assumptions. In fact, their main difference is that any intimate knowledge of the target implementations can -but does not have to -be exploited by SASCA (while, e.g. the middle round leakages are useless for DC attacks). The experiments in this paper consider a worst-case scenario where the adversary knows the implementation source code. Another extreme scenario would be to consider only "standard" attack points that can be guessed from the algorithms specifications (e.g. S-boxes inputs/outputs), which would reduce the gain of SASCA compared to TA. Any intermediate situation could be investigated, corresponding to various tradeoffs between implementation details and attack efficiency.

  Fig.2: Attacks results for our simulated furious implementation. Each graph gives the success rate (SR, ranging from 0 to 1) for a given signal-to-noise ratio (SNR, ranging from 2 4 down to 2 -6 ) as a function of the number of traces (in logarithmic scale, ranging from 1 to 5000). The attacks are:

Fig. 4 :

 4 Fig.4: SASCA with unknown input and output for different SNRs.The x-axis is the number of traces used for the attack (in log scale), and the y-axis gives the probability of key recovery. The top graph corresponds to a leaky key schedule, and the lower graph gives the results for a leak-free key schedule.

Acknowledgements. François-Xavier Standaert is a research associate of the Belgian Fund for Scientific Research (FNRS-F.R.S.). This work has been funded in parts by the European Commission through the ERC project 280141 (acronym CRASH) and by the PAVOIS project (ANR 12 BS02 002 01).


Nicolás Ás Botbol

Laurent Bus É
email: laurent.buse@inria.fr

Marc Chardin
email: chardin@math.jussieu.fr

FITTING IDEALS AND MULTIPLE-POINTS OF SURFACE PARAMETERIZATIONS

Given a birational parameterization φ of an algebraic surface S ⊂ P 3 , the purpose of this paper is to investigate the sets of points on S whose preimage consists in k or more points, counting multiplicities. These points are described explicitly in terms of Fitting ideals of some graded parts of the symmetric algebra associated to the parameterization φ. To obtain this description, we show that the degree and dimension of a fiber could be computed by comparing the drop of rank of two explicit (representation) matrices associated to φ.

Introduction

Parameterized algebraic surfaces are ubiquitous in geometric modeling because they are used to describe the boundary of 3-dimensional shapes. To manipulate them, it is very useful to have an implicit representation in addition to their given parametric representation. Indeed, a parametric representation is for instance well adapted for drawing or sampling whereas an implicit representation allows significant improvements in intersection problems that are fundamental operations appearing in geometric processing for visualization, analysis and manufacturing of geometric models. Thus, there exists a rich literature on the change of representation from a parametric to an implicit representation under the classical form of a polynomial implicit equation. Although this problem can always be solved in principle, for instance via Gröbner basis computations, its practical implementation is not enough efficient to be useful in practical applications in geometric modeling for general parameterized surfaces.

In order to overcome this difficulty, alternative implicit representations of parameterized surfaces under the form of a matrix have been considered. The first family of such representations comes from the resultant theory that produces a non-singular matrix whose determinant yields an implicit equation from a given surface parameterization. But the main advantage is also the main drawback of these resultant matrices: since they are universal with respect to the coefficients of the given surface parameterization, they are very easy to build in practice, but they are also very sensitive to the presence of base points. As a consequence, a particular resultant matrix has to be designed for each given particular class of parameterized surfaces. A second family of implicit matrix representations is based on the syzygies of the coordinates of a surface parameterization. Initiated by the geometric modeling community [START_REF] Sederberg | Implicitization using moving curves and surfaces[END_REF], these matrices have been deeply explored in a series of papers (see [START_REF] Busé | On the closed image of a rational map and the implicitization problem[END_REF][START_REF] Busé | Implicitizing rational hypersurfaces using approximation complexes[END_REF][START_REF] Botbol | Matrix representations for toric parametrizations[END_REF][START_REF] Botbol | Implicit equation of multigraded hypersurfaces[END_REF] and the references therein).

Compared to the resultant matrices, they are still very easy to build, although not universal, but their sensitivity to the presence of base points is much weaker. However, these matrices are in general singular matrices and the recovering of the classical implicit equation from them is more involved. Therefore, to be useful these matrices have to be seen as implicit representations on their own, without relying on the more classical implicit equation. In this spirit, the use of these singular matrix representations has recently been explored for addressing the curve/surface and surface/surface intersection problems [START_REF] Busé | The surface/surface intersection problem by means of matrix based representations[END_REF][START_REF] Luu Ba | Curve/surface intersection problem by means of matrix representations[END_REF].

In geometric modeling, it is of vital importance to have a detailed knowledge of the geometry of the object one is working with. In a first step, it is of interest to determine whether a given point on the surface is a singular point or a smooth point, that is, to know whether that point "is being painted twice, or not". In a second step, it is important to give a computationally efficient criterion to answer this question.

To ask the question of how many times is the same point being painted, it should be clear that this question is relevant on the parameterization and not on the surface itself. It is for this reason that (among computational difficulties) when studying directly the implicit equation of the surface, this essential information is lost, while the direct treatment of searching multiple pre-images often involves questions of existence that are computationally difficult to implement. In this paper, we show that this information is all contained in the above-mentioned matrix representations of the parameterization.

The main goal of this paper is to respond to a very simple but useful question: given a point P in a parametrized surface S, how is related the rank of a matrix representation of S with the geometry of S at P ? The answer to this question is given in Theorem 16 and Theorem 21.

More precisely, let φ be a parameterization from P 2 to P 3 of a rational algebraic surface S and let M (φ) be one of its matrix representations. In Theorem 16 it is shown that the drop of rank of M (φ) at a given point P ∈ P 3 is in relation with the nature of the fiber of the graph of φ over P . Thus, the Fitting ideals attached to M (φ) provide a filtration of the surface which is in correspondence with the degree and the dimension of the fibers of the graph of the parameterization φ. This result is extended in Theorem 21 to parameterizations which are given by bigraded polynomials. This type of parameterizations is actually widely used in geometric modeling where they are called rational tensor product surfaces -see for instance [START_REF] Schenck | Syzygies and singularities of tensor product surfaces of bidegree[END_REF] for a detailed study of a special case and the references therein.

Finally, it turns out that related results have been investigated for different purposes in the field of intersection theory under the name of multiple-point formulas. Given a finite map of schemes ϕ : X → Y of codimension one, its source and target double-point cycles have been extensively studied (see e.g. [START_REF] Kleiman | The multiple-point schemes of a finite curvilinear map of codimension one[END_REF][START_REF] Kleiman | The source double-point cycle of a finite map of codimension one[END_REF][START_REF] Piene | Polar classes of singular varieties[END_REF][START_REF] Teissier | The hunting of invariants in the geometry of discriminants[END_REF]). Moreover, in [START_REF] Mond | Fitting ideals and multiple points of analytic mappings[END_REF] Fitting ideals are used to give a scheme structure to the multiple-point loci. Therefore, in the particular case where φ : P 2 → P 3 has no base point (hence is a finite map), our results are partially contained in the above literature. Thus, the main contribution of this paper is to extend these previous works to the case where φ is not necessarily a finite map under ubiquitous conditions. The theory in this article is thus applicable to most of the parameterizations that appear in applications.

In what follows, we give a description of the content of the paper. In Section 2, with a briefly overview on matrix representations and defining some Fitting ideals attached to them. There we compile the main useful results on matrix representations and Fitting ideals, as well as technical new results Castelnuovo-Mumford regularity that are needed for the sequel.

The main contribution of this paper are Theorem 9, Theorem 12, and Theorem 15, proved in Section 3. These results give a precise relation between the rankdrop of a representation matrix and the nature of the 0, 1 and 2-dimensional fibers respectively. There we give a complete characterization of the Hilbert polynomial of the fibre of the graph of φ at p, in terms of the drop of rank of the representation matrices of φ.

In Section 4 we sum up the results given before looking forward to emphasize the computational aspects. We end Section 4 by pulling back the geometric information to the source of the map, by evaluating the representation matrix in the parametrization φ. This provides an interesting description of the singular locus of φ in the source space P 2 , that is very useful in applications.

In Section 5 we discuss on the link with multiple-points formulas developed in the field of intersection theory. We show that in the very particular case where the parametrization map φ is finite, we are under a well understood setting, where its source and target double-point cycles have been extensively studied loc. cit.

Finally, in Section 6, we will treat the case of parameterizations φ whose source is P 1 ×P 1 instead of P 2 . In this section, we show that we can treat similarly rational surfaces that are parameterized by a birational map from P 1 × P 1 to P 3 .

Fitting ideals associated to surface parameterizations

Let k be a field and φ : P 2 k P 3 k be a rational map given by four homogeneous polynomials f 0 , f 1 , f 2 , f 3 of degree d. We will denote by S the closure of its image. Set s := (s 0 , s 1 , s 2 ), x := (x 0 , x 1 , x 2 , x 3 ), and let S := k[s] and R := k[x] be the polynomial rings defining P 2 k and P 3 k respectively. Finally, define the ideal I = (f 0 , f 1 , f 2 , f 3 ) ⊂ S d . In the sequel, we will assume that:

-S is a surface in P 3 k , φ is a birational map onto S, -V (I) is finite and locally a complete intersection.

   (H)
2.1. Matrix representations of φ. The approximation complex of cycles associated to the sequence of polynomials f 0 , f 1 , f 2 , f 3 is of the form (see e.g. [START_REF] Busé | On the closed image of a rational map and the implicitization problem[END_REF]§4] for an introduction to these complexes in this context)

Z • : 0 → Z 3 → Z 2 → Z 1 M (φ) -→ Z 0 → 0. ( 1
)
The map M (φ) sends a 4-tuple (g 0 , g 1 , g 2 , g 3 ) to the form 3 i=0 g i x i , with the condition that (g 0 , g 1 , g 2 , g 3 ) ∈ Z 1 if and only if 3 i=0 g i f i = 0. The complex Z • inherits a grading from the canonical grading of the polynomial ring S. Thus, the notation M (φ) ν stands for the matrix in (Z • ) ν that corresponds to the degree ν part of M (φ).

Under our hypothesis, the symmetric algebra S I := Sym S (I) of the ideal I ⊂ S is projectively isomorphic to the Rees algebra R I := Rees S (I). In other words, the graph Γ ⊂ P 2 k × P 3 k of the parameterization φ is the subscheme of P 2 k × P 3 k defined by S I . As a consequence, the approximation complex of cycles Z • can be used to determine an implicit representation of the closed image of φ, i.e. the surface S (recall that H 0 (Z • ) = Sym S (I)).

Definition 1. Under the assumptions (H), for all integer ν ν 0 the matrix M (φ) ν of the graded map of free R-modules (Z 1 ) ν → (Z 0 ) ν is called a matrix representation of φ.

In order to give a clear description of the matrices M (φ) ν , let us take

ν 0 := 2d -2 -indeg(I sat ), (2)
where indeg(I sat ) = min{ν ∈ Z | (I sat ) ν = 0}. This integer will be used and discussed all along next section. But, for the sake of simplicity, the integer ν 0 can be taken equal to 2d -2. A deeper and wider discussion about this bound is given in [START_REF] Busé | Torsion of the symmetric algebra and implicitization[END_REF].

Here are the main features of the collection of matrix representations M (φ) ν of φ, for ν ν 0 :

• Its entries are linear forms in R = k[x 0 , . . . , x 3 ],

• it has ν+2 2 rows and at least as many columns as rows,

• it has maximal rank ν+2 2 at the generic point of P 3 k , that is to say

rank M (φ) ν ⊗ R Frac(R) = ν + 2 2 ,
• when specializing M (φ) ν at a point P ∈ P 3 , its rank drops if and only if P ∈ S.

2.2.

Fitting ideals associated to φ. From the properties of matrix representations of φ, for all ν ν 0 the support of the Fitting ideal F 0 ((S I ) ν ) is S and hence provides a scheme structure for the closure of the image of φ. Following [START_REF] Teissier | The hunting of invariants in the geometry of discriminants[END_REF] (and [EH00, V.1.3]), we call it the Fitting image of φ.

Remark 2. Observe that by definition, the ideals F 0 ((S I ) ν ) depend on the integer ν (it is generated in degree ν) whereas ann R ((S I ) ν ) = ker(φ ♯ ) for all ν ν 0 (see [BJ03, Proposition 5.1] and [BC05, Theorem 4.1]), where φ ♯ : R → S is the map of rings induced by φ (it sends each x i to f i (s) for all i = 0, . . . , 3) and ker(φ ♯ ) is the usual ideal definition of the image of φ.

In this paper, we will push further the study of F 0 ((S I ) ν ) by looking at the other Fitting ideals F i ((S I ) ν ), i > 0, since they provide a natural stratification :

F 0 ((S I ) ν ) ⊂ F 1 ((S I ) ν ) ⊂ F 2 ((S I ) ν ) ⊂ • • • ⊂ F ( ν+2 2 ) ((S I ) ν ) = R.
As we will see, these Fitting ideals are closely related to the geometric properties of the parameterization φ. For simplicity, the Fitting ideals F i ((S I ) ν ) will be denoted

F i ν (φ). We recall that F i ν (φ) ⊂ R is generated by all the minors of size ν+2 2 -i of any matrix representation M (φ) ν .
Example 3. Consider the following parameterization of the sphere

φ : P 2 C P 3 C (s 0 : s 1 : s 2 ) → (s 2 0 + s 2 1 + s 2 2 : 2s 0 s 2 : 2s 0 s 1 : s 2 0 -s 2 1 -s 2 2 ).
Its matrix representations M (φ) ν have the expected properties for all ν 1, since d = 2 and indeg(I sat ) = 1 (see the next section for details). The computation of the smallest such matrix yields

M (φ) 1 =   0 X 1 X 2 -X 0 + X 3 X 1 0 -X 0 -X 3 X 2 -X 2 -X 0 -X 3 0 X 1   .
Here is a Macaulay2 [GS] code computing this matrix (and others by tuning its inputs: the parameterization φ and the integer ν): We can use this very simple example to understand the power of Fitting ideals in describing the nature of the image of φ. The routine implemented above only uses very simple linear algebra subroutines, which in this case takes a total time of 0.001578 seconds † .

>A=QQ[s0,
In order to illustrate the results we obtain in this paper we will compute the Fitting ideals associated to M = M (φ) 1 , which involves computing determinants of minors and later a primary decomposition of these ideals. In real applications symbolic computations of determinants, radicals or primary decompositions of ideals are very costly.

A primary decomposition of the 3 × 3 minors of M (φ)

1 , i.e. F 0 1 (φ), returns (X 2 0 -X 2 1 -X 2 2 -X 2 3 ) ∩ (X 2 , X 1 , X 2 0 + 2X 0 X 3 + X 2
3 ) which corresponds to the implicit equation of the sphere plus one embedded double point (1 : 0 : 0 : -1). Now, a primary decomposition of the 2 × 2 minors of M (φ)

1 , i.e. F 1 1 (φ), returns (X 2 , X 1 , X 0 + X 3 ) ∩ (X 3 , X 2 2 , X 1 X 2 , X 0 X 2 , X 2 1 , X 0 X 1 , X 2
0 ) which corresponds to the same embedded point (1 : 0 : 0 : -1), now with multiplicity one, plus an additional component supported at the origin. Finally, the ideal of 1-minors of M (φ) 1 , i.e. F 2 1 (φ), is supported at the origin (i.e. is empty as a subscheme of P 2 ).

The point (1 : 0 : 0 : -1) is actually a singular point of the parameterization φ (but not of the sphere itself). Indeed, the line L = (0 :

s 1 : s 2 ) is a P 1 that is mapped to (s 2 1 + s 2 2 : 0 : 0 : -(s 2 1 + s 2 2 )).
In particular, the base points of φ, (0 : 1 : i) and (0 : 1 : -i), are lying on this line, and the rest of the points are mapped to the point (1 : 0 : 0 : -1). Outside L at the source and P at the target, φ is an isomorphism.

2.3. Regularity of the symmetric algebra. Hereafter, we give an upper bound for the regularity of the symmetric algebra S I in our setting. We will use it in the sequel of this paper. We begin with some classical notation.

Given a finitely generated graded S-module N , we will denote by HF N its Hilbert function and by HP N its Hilbert polynomial. Recall that for every µ, one has

HF N (µ) := dim k (N µ ),
and the Grothendieck-Serre formula ([BH93, Theorem 4.3.5])

HP N (µ) := HF N (µ) - i (-1) i HF H i m (N ) (µ) (3)
where m denotes the ideal m = (s 0 , s 1 , s 2 ) ⊂ S. It is well-known that HF H i m (N ) (µ) is finite for any i and µ, and that HP N is a polynomial function.

We also recall the definition of three classical invariants attached to a graded module N . We will denote

a i (N ) := sup{µ ∈ Z | H i m (N ) µ = 0}, a * (N ) := max i {a i (N )}, and reg(N ) := max i {a i (N ) + i}
for the a i -invariant, the a * -invariant and the Castelnuovo-Mumford regularity of N , respectively. Finally, the notation µ(J) for a given ideal J stands for its minimal number of generators.

The following lemma will be useful in some places (see [Sza08, Corollary A12] for a self contained elementary proof) : Lemma 4. Let J be a graded ideal in S, generated in degree d such that dim(S/J) 1 and µ(J p ) 3 for every prime ideal m p ⊃ J. Then, reg(S/J sat ) 2d -3 and reg(S/J) 3d -3indeg(J sat ) unless µ(J) = 2, in which case J = J sat and reg(S/J) = 2d -2.

Proof. We may assume that k is infinite. Let f and g be two general forms of degree d in J. They form a complete intersection. Hence, by liaison (see e.g. [CU02, 4.1

(a)]) reg(S/J sat ) = reg(S/(f, g)) -indeg(((f, g) : J sat )/(f, g)).
Hence reg(S/J sat ) 2d -3, unless (f, g) ⊇ J sat in which case J = (f, g). Let J ′ ⊆ J be an ideal generated by 3 general forms of degree d. As µ(J p ) 3 for every prime ideal m p, J ′ and J have the same saturation. Therefore, it suffices to show that H 0 m (S/J ′ ) µ+d = 0. Observe that by Koszul duality (see for instance

[Cha04, Lemma 5.8]) H 0 m (S/J ′ ) µ+d = 0 is equivalent to H 0 m (S/J ′ ) 2d-3-µ = 0. But since 2d -3 -µ < d we indeed have H 0 m (S/J ′ ) 2d-3-µ = (J ′ ) sat 2d-3-µ = J sat 2d-3-µ = 0 since 2d -µ -3 < indeg(J sat ).
Proposition 5. Assume that dim(S/I) 1 and µ(I p ) 3 for every prime ideal m p ⊃ I, then Z • is acyclic, a * (S I ) + 1 ν 0 (defined in Equation (2)), and reg(S I ) ν 0 , unless I is a complete intersection of two forms of degree d ‡ , in which case a * (S I ) = d -3 and reg(S

I ) = d -1 = ν 0 + 1. Proof. The acyclicity of Z • is proved in [BC05, Lemma 4.2]. Furthermore, H i m (S I ) = 0 for i / ∈ {0, 1, 2, 3}
, so we only need to examine H i m (S I ) for i ∈ {0, 1, 2, 3}. The case i = 0 is treated in [BC05, Theorem 4.1]. The proof uses the spectral sequence

H j m (Z i+j ) µ+(i+j)d ⊗ k R ⇒ H i m (S I ) µ (4)
from which we will also deduce the vanishing for i > 0.

For i = 1, let µ ν 0 . We will show that

H 2 m (Z 1 ) µ+d = H 3 m (Z 2 ) µ+2d = 0 as by (4) it implies that H 1 m (S I ) µ = 0 as claimed (recall that H 1 m (Z 0 ) = H 1 m (S) = 0). By [BC05, Lemma 4.1], H 3 m (Z 2 ) ≃ (Z 1 ) * [3 -4d] and we deduce that H 3 m (Z 2 ) µ+2d ≃ ((Z 1 ) * [3 -4d]) µ+2d ≃ (Z 1 ) * µ-2d+3 . But 2d -µ -3 < indeg(I sat ) d as µ ν 0 . Hence (Z 1 ) 2d-µ-3 = 0 since Z 1 ⊂ S(-d) 4 , proving that H 3 m (Z 2 ) µ+2d = 0. The exact sequence 0 → Z 1 → S(-d) 4 → S → S/I → 0 provides a graded isomorphism H 2 m (Z 1 ) ≃ H 0 m (S/I). By Lemma 4, reg(S/I) 3d -3 -indeg(I sat ) = d + ν 0 -1, hence H 2 m (Z 1 ) µ+d = 0. For i = 2, consider the canonical exact sequence defining K 0 → K → S I → R I → 0.
As K is the direct sum of the S-modules ker(Sym t S (I) → I t ) that are supported on V (I), we have

H i m (K) = 0 for i > dim S/I. It follows that H 2 m (S I ) ≃ H 2 m (R I ). Now, a 2 (R I ) = max t 1 {a 2 (I t ) -td} = max t 1 {a 1 (S/I t ) -td}. The surjective map (S/I)(-td) ( t+3
3 ) → I t /I t+1 provides the inequality a 1 (I t /I t+1 ) a 1 (S/I) + td, and it remains to estimate a 1 (S/I). By Lemma 4,

a 2 (R I ) a 1 (S/I) -d d -4, unless µ(I) = 2. As indeg(I sat ) d it follows that a 2 (R I ) ν 0 -2, unless I = (f, g), in which case a 2 (R I ) = ν 0 -1. For i = 3, H 3 m (Z 0 ) µ = H 3 m (S) µ = 0 for all µ > -3, hence a 3 (S I ) -3. Finally, a 3 (S I ) = ⊕ t 0 H 3 m (S)(td), hence a 3 (S I ) = -3. Remark 6. If V (I) = ∅ then a 2 (S I ) = -∞ and a 1 (S I ) = a 1 (I) -d = reg(S/I) -d.
Also, when dim(S/I) = 1 and V (I) is locally a complete intersection, one has a 2 (S I ) = a 2 (I)d as above and a 1 (S I ) = max{a 1 (I)d, a 1 (I 2 ) -2d}. This shows in particular that a 1 (S I ) and a 2 (S I ) can be (very quickly) computed from I, using a dedicated software. ‡ Notice that in this case the closed image of φ cannot be a surface.

Fibers of the canonical projection of the graph of φ onto S

Let Γ ⊂ P 2 P 3 be the graph of φ and R + = (X 0 , . . . , X 3 ) the graded maximal ideal of R. We have the following diagram

Γ π1 π2 # # / / P 2 k × k P 3 k P 2 k P 3 k (5)
where all the maps are canonical. For any p ∈ Proj(R), we will denote by κ(p) its residue field R p /pR p . The fiber of π 2 at p ∈ Proj(R) is the subscheme

π -1 2 (p) := Proj(S I ⊗ R κ(p)) ⊂ P 2 κ(p)
. For simplicity, we set N p ν := dim κ(p) (S I ⊗ R κ(p)) ν for the Hilbert function of the fiber π -1 2 (p) in degree ν. It turns out that this quantity governs the support of the Fitting ideals F i ν (φ) we are interested in. Proposition 7. For any p ∈ Proj(R)

F i ν (φ) ⊗ R κ(p) = 0 if 0 i < N p ν κ(p) if N p ν i Proof.
First, as a consequence of the stability under base change of the Fitting ideals, one has

F i ((S I ) ν ) ⊗ R κ(p) = F i ((S I ) ν ⊗ R κ(p)
). Now, for any ν 0 the κ(p)-vector space

(S I ) ν ⊗ R κ(p) = (S I ⊗ R κ(p)) ν is of dimension N p ν .
The result then follows from the fact that the i-th Fitting ideals of a κ(p)-vector space of dimension N is 0 for i < N and κ(p) for i N .

This leads us to focus on the behavior of the Hilbert functions N p ν . By (3), it suffices to control the local cohomology of the fiber S I ⊗ κ(p) with respect to the ideal m. Part of this control is already known, Lemma 8 ([Cha12, Prop. 6.3]). Let p ∈ Proj(R) and v p := dim(S I ⊗ R κ(p)). Then,

a vp (S I ⊗ R κ(p)) = a vp (S I ⊗ R R p ) a vp (S I ) and a vp-1 (S I ⊗ R κ(p)) max{a vp-1 (S I ⊗ R R p ), a vp (S I ⊗ R R p )} max{a vp-1 (S I ), a vp (S I )}.
We are now ready to describe the support of the ideals F i ν (φ) with i 0 and ν ν 0 . We begin with the points on S whose fiber is 0-dimensional.

Theorem 9 (0-dimensional fibers). Let p ∈ Proj(R). If dim π -1 2 (p) = 0 then for all ν ν 0 p ∈ V (F i ν (φ)) ⇔ deg(π -1 2 (p)) i + 1. ( 6
)
Proof. By Proposition 5 and Lemma 8, we have H i m (S I ⊗ R κ(p)) ν = 0 for all ν ν 0 and i 0. Then, the conclusion follows from Proposition 7 and the equality (3) since the Hilbert polynomial of the fiber π -1 2 (p) is a constant polynomial which is equal to the degree of this fiber.

We now turn to points on S whose fiber is 1-dimensional.

Lemma 10. Assume that the f i 's are linearly independent, the fiber over a closed point p of coordinates (p 0 : p 1 : p 2 : p 3 ) is of dimension 1, and its unmixed component is defined by h p ∈ S. Let ℓ p be a linear form with ℓ p (p 0 , . . . , p 3 ) = 1 and set ℓ i (x) := x ip i ℓ p (x). Then, h p = gcd(ℓ 0 (f ), . . . , ℓ 3 (f )) and I = (ℓ p (f )) + h p (g 0 , . . . , g 3 ) with ℓ i (f ) = h p g i and ℓ p (g 0 , . . . , g 3 ) = 0. In particular

(ℓ p (f )) + h p (g 0 , . . . , g 3 ) sat ⊆ I sat ⊆ (ℓ p (f )) + (h p ). Proof. A syzygy L = i a i x i = i a i (p i ℓ p (x) + ℓ i (x)
) provides an equation for the fiber : L = i a i p i . Recall that h p = gcd(L 1 , . . . , L t ) where the L j are generators of the syzygies of I.

The particular syzygy

L (i) := ℓ i (f )ℓ p (x) -ℓ p (f )ℓ i (x) satisfies L (i) = ℓ i (f ). It follows that h p divides h := gcd(ℓ 0 (f ), . . . , ℓ 3 (f )). Set ℓ i (f ) = hg i for some g i ∈ S.
The ℓ i 's span the linear forms vanishing at p, and are related by the equation ℓ p (ℓ 0 , . . . , ℓ 3 ) = 0. It follows that I = (ℓ p (f ), ℓ 0 (f ), . . . , ℓ 3 (f )) = (ℓ p (f )) + h(g 0 , . . . , g 3 ), and ℓ p (g 0 , . . . , g 3 ) = 0. Now if one has a relation aℓ p (f ) + i b i hg i = 0, then h divides a, as the f i 's have no common factor. This in turn shows that h divides h p and completes the proof.

Notice that if p i = 0, g i is a linear combination of the g j 's for j = i as ℓ p (g 0 , . . . , g 3 ) = 0. For instance if p 0 = 0, I = (ℓ p (f )) + h(g 1 , . . . , g 3 ).

Remark 11. The above lemma shows that fibers of dimension 1 can only occur when V (I) = ∅ as V (I) ⊇ V ((ℓ p (f ), h p )). It also shows that

d deg(h p ) deg(I)
if there is a fiber of dimension 1 of unmixed part given by h p . Furthermore, any element F in I sat of degree < d has to be a multiple of h p for any fiber of dimension 1. As h p and h p ′ cannot have a common factor for p = p ′ , the product of these forms divide F . This gives a simple method to compute 1 dimensional fibers if such an F exists.

Theorem 12 (1-dimensional fibers). Let p ∈ Proj(R) be a k-rational closed point. If dim π -1 2 (p) = 1 then, setting δ := deg(π -1 2 (p))), a 0 (S I ⊗ κ(p)) ν 0 -δ -1 and reg(S I ⊗ κ(p)) max{ν 0 -δ -1, reg(I) -d} ν 0 -1. As a consequence, a * (S I ⊗ κ(p)) ν 0 -2.
Proof. By Lemma 10, I = (f ) + h(g 1 , g 2 , g 3 ) with h the equation of the unmixed part of the fiber. Let I ′ := (g 1 , g 2 , g 3 ).

We may assume for simplicity that p = (1 : 0 : 0 : 0) (i.e. f = f 0 and f i = hg i for i = 1, 2, 3), and we then have an exact sequence

0 → Z ′ 1 (d) → Z 1 (d) → S → S I ⊗ κ(p) → 0, with Z ′ 1 the syzygy module of (f 1 , f 2 , f 3 ), the first map sending (b 1 , b 2 , b 3 ) to (0, b 1 , b 2 , b 3
) and the second (a 0 , a 1 , a 2 , a 3 ) to a 0 .

It follows that reg(S

I ⊗ κ(p)) max{reg(S), reg(Z 1 ) -d -1, reg(Z ′ 1 ) -d -2} and a 0 (S I ⊗ κ(p)) a 2 (Z ′ 1 ) -d reg(Z ′ 1 ) -d -2 as H 0 m (S) = H 1 m (Z 1 ) = 0. By Lemma 10, h = gcd(f 1 , f 2 , f 3 ) is of degree δ. Set f i = hf ′
i for all i = 1, 2, 3. The syzygies of (f 1 , f 2 , f 3 ) and

I ′ := (f ′ 1 , f ′ 2 , f ′
3 ) are equal, up to a degree shift by δ, and the exact sequence 0 → Z ′ 1 (δ) → S(-d + δ) 3 → I ′ → 0 shows that : reg(Z ′ 1 ) = reg(I ′ ) + 1 + δ. Notice that hI ′ ⊂ I, hence h(I ′ ) sat ⊆ I sat and indeg(I sat ) δ + indeg((I ′ ) sat ). By Lemma 4 we obtain

reg(I ′ ) 3(d -δ) -2 -indeg((I ′ ) sat ) 3d -2δ -indeg(I sat ) -2 hence a 0 (S I ⊗ κ(p)) 2d -δ -3 -indeg(I sat ) = ν 0 -δ -1. Finally, reg(Z 1 ) -d -1 = reg(I) -d ν 0 -1 by Lemma 4.
To conclude the above case discussion, let us state a simple corollary :

Corollary 13. Let p ∈ Proj(R). (i) If π -1 2 (p) = ∅ then a * (S I ⊗ κ(p)) = reg(S I ⊗ κ(p)) ν 0 -1. (ii) If dim(π -1 2 (p)) = 0 then a * (S I ⊗ κ(p)) ν 0 -1 and reg(S I ⊗ κ(p)) ν 0 .
(iii) If dim(π -1 2 (p)) = 1 then a * (S I ⊗ κ(p)) ν 0 -2 and reg(S I ⊗ κ(p)) ν 0 -1. Let us now remark that there is no fiber of dimension two (i.e. equal to P 2 ) over a point p ∈ Proj(R). More generally : Lemma 14. Let φ : P n-1 k P m k be a rational map and Γ be the closure of the graph of φ. The following are equivalent : (i) π : Γ → P m k has a fiber F x equal to P n-1 x , (ii) φ is the restriction to the complement of a hypersurface of the constant map sending any point to the zero dimensional and k-rational point x.

Proof. For (i)⇒(ii), notice that P n-1 k × {x} is a subscheme of the absolutely irreducible scheme Γ that has same dimension n -1. Hence F x = Γ showing (ii).

Theorem 15 (2-dimensional fibers). For all ν ν 0 ,

p ∈ Proj(R) : HP π -1 2 (p) (ν) = HP P 2 (ν) = ν + 2 2 = ∅
Proof. It follows from Proposition 5 that the defining ideal of the fiber is generated in degree at most ν 0 . As this ideal is non trivial for any point in Proj(R) by Lemma 14, we deduce that HP p ν < ν+2 2 for any prime in Proj(R) if ν ν 0 .

It is worth mentioning two facts that are direct consequences of the above results. First, the embedded components of F 0 ν (φ) are exactly supported on

V (F 1 ν (φ)) ⊂ V (F 0 ν (φ)) = S .
Second, the set-theoretical support of each F i ν (φ), i fixed, stabilizes for ν ≫ 0; its set-theoretical support then corresponds to those points on S whose fiber is either a curve or a finite scheme of degree greater or equal to i + 1.

Computational aspects

In this section, we detail the consequences of the previous results for giving a computational description of the singular locus of the parameterization φ of the surface S.

4.1. Description of the fiber of a given point on S . Given a point p on S , we summarize the results we obtained with Figure 1. The dotted curve corresponds to a finite fiber, i.e. a point p such that dim π -1 2 (p) = 0, the dashed curve corresponds to a one dimensional fiber, i.e. a point p such that dim π -1 2 (p) = 1, and the solid curve represents the Hilbert polynomial of S, the coordinate ring of P 2 k .

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 HP S (ν)

HP SI ⊗Rκ(p) (ν) a * (S I ⊗ R κ(p)) ν 0 -1 Figure 1. Graph of N p
ν as a function of ν for a given p ∈ Proj(R).

The fact that p belongs or not to the support of F i ν (φ) can be checked by the computation of the rank of a matrix representation M ν (φ) evaluated at the point p. So, from what we proved in the previous section, we deduce the following properties.

Theorem 16. With the above notation

• If dim π -1 2 (p) 0 then for all ν ν 0 corank(M ν (φ)(p)) = deg(π -1 2 (p)). • If dim π -1 2 (p) = 1 then for all ν ν 0 -1 corank(M ν (φ)(p)) = deg(π -1 2 (p))ν + c where c ∈ Z is such that HP π -1 2 (p) (ν) = deg(π -1 2 (p))ν + c.
From here, we get an algorithm to determine the Hilbert polynomial of a fiber π -1 2 (p) of a given point p by comparing the rank variation of the matrix M ν (φ)(p) for two consecutive integers ν and ν + 1, assuming ν ν 0 . Before giving a more precise description in the form of an algorithm, we refine the distinction between finite and non-finite fibers.

Proposition 17. Let p be a point on S and choose an integer ν such that

ν 0 ν 2d -2. If corank(M ν (φ)(p)) ν then π -1
2 (p) is necessarily a finite fiber.

Proof. We know that the Hilbert function of the fiber π -1 2 (p) coincides with its Hilbert polynomial for all ν ν 0 . Therefore, to prove our claim it is enough to show that if the fiber π

-1 2 (p) of p is of dimension 1, then corank(M ν (φ)(p)) = HP π -1 2 (p) (ν) ν + 1. So, assume that π -1 2 (p) is 1-dimensional and set δ := deg(π -1 2 (p)) so that HP π -1 2 (p) (ν) = δν + 1 - δ -1 2 + N where δ-1 2
is the arithmetic genus of the unmixed dimension one part of the fiber π -1 2 (p) and N 0 is the degree of its remaining finite part. Observe that δ d. Now, a straightforward computation yields

HP π -1 2 (p) (ν) = δ(2ν + 3 -δ) 2 + N.
From here, we see that

HP π -1 2 (p) (ν) is an increasing function of δ on the interval [-∞; ν + 3 2 ] which takes value ν + 1 + N for δ = 1. Observe moreover that ν + 3 2 δ as soon as ν d -1. And if ν = d -2, then HP π -1 2 (p) (d -2) takes the same value for δ = d -1 and δ = d.
An interesting consequence of the above proposition is that for all integer 0

n 2d -2 corank(M 2d-2 (φ)(p)) = n ⇔ π -1
2 (p) is finite of degree n. Therefore, as soon as d 2 we have corank(M 2d-2 (φ)(p)) = 1 ⇔ p has a unique preimage.

Observe in addition that once we know that a point p has a unique preimage, this preimage can be computed from the kernel of the transpose of M 2d-2 (φ)(p). Indeed, this kernel is generated by a single vector. But it is clear by the definition of M 2d-2 (φ) that the evaluation of the basis of S ν chosen to build M 2d-2 (φ) evaluated at the point (s 0 : s 1 : s 2 ) is also a nonzero vector in the kernel of the transpose of M 2d-2 (φ)(p). Hence, from this property it is straightforward to compute the pre-image of p if it is unique.

Algorithm : Determination of the characters of a fiber π -1 2 (p)

Input: a parameterization φ of a surface S satisfying (H) and a point p ∈ P 3 . Output: the hilbert polynomial of the fiber π -1 2 (p).

1. Pick an integer ν ν 0 (e.g. ν = 2d -2 which is always valid). 2. Compute a matrix representation M ν (φ).

3. Compute r ν := corank(M ν (φ))(p). 4. If r ν = 0 then p does not belong to S (and stop). 5. If 0 < r ν ν then π -1 2 (p) is a finite set of r ν points, counted with multiplicity. 6. If r ν > ν then compute M ν+1 (φ). 7. Compute r ν+1 := corank(M ν+1 (φ))(p). 8. If r ν = r ν+1 then π -1 2 (p) is a finite set of r ν points, counted with multiplicity. 9. If r ν < r ν+1 then dim(π -1 2 (p)) = 1 and the Hilbert polynomial of π -1 2 (p) is written as

HP π -1 2 (p) (t) = (r ν+1 -r ν )t + r ν -(r ν+1 -r ν )ν, which means that π -1
2 (p) is made of a curve of degree r ν+1r ν plus eventually additional isolated or embedded points. 4.2. Pull-back to the parameter space. So far, we have seen that the fibers of π 2 can be described from the Fitting ideals F i ν (φ) which are homogeneous ideals in the ring R of implicit variables. However, for applications in geometric modeling, it is also interesting to get such a description of the singular locus of φ in the source space P 2 in place of the target space P 3 . From a computational point of view, this also allows to reduce the number of ambient variables by one. For that purpose, we just have to pull-back our Fitting ideals through φ. For all integers i 0 and ν ν 0 we define the ideals of S φ -1 (F i ν ) := φ ♯ (F i ν ).S It is clear that for all i we have φ -1 (F i ν ) ⊂ I, that is to say that the base points of φ are always contained in the support of φ -1 (F i ν ) for all i 0 and all ν ν 0 . By Lemma 15, this support is exactly the base points of φ if i = ν+2 2 -1. In other words we have

φ -1 F ( ν+2 2 )-1 ν = I, ∀ ν ν 0 .
For all ν ν 0 , we clearly have φ -1 (F 0 ν ) = (0) ⊂ S. Notice that this behavior is similar to substituting the parameterization φ into an implicit equation of S which returns 0. However, φ -1 (F 1 ν ) is nonzero since we have assumed φ birational. Actually, as a consequence of the results of Section 3, the sequence of ideals

φ -1 (F 1 ν ) ⊂ φ -1 (F 2 ν ) ⊂ • • • ⊂ φ -1 F ( ν+2 2 )-1 ν = I
yields a filtration of P 2 which is in correspondence with the singularities of φ. Here is an illustrative example where we focus on the singularities of the parameterization φ in a situation where S is smooth and very simple.

Example 18. Take four general linear forms l 0 , l 1 , l 2 , l 3 in S 1 and consider the parameterization φ : P 2 C → P 3 C : (s 0 : s 1 : s 2 ) → (l 1 l 2 : l 0 l 3 : l 0 l 1 : l 0 l 1 ). The closed image of φ is the plane of equation S : X 2 -X 3 = 0. There are three base points that are all local complete intersections:

P 01 = {l 0 = 0} ∩ {l 1 = 0}, P 02 = {l 0 = 0} ∩ {l 2 = 0}, P 13 = {l 1 = 0} ∩ {l 3 = 0}.
The fiber of each base point by π 1 (see the diagram (5)) gives a line on S , the projection of the associated exceptional divisor, say D 01 , D 02 and D 13 . The equations of the graph Γ are l 0 X 0l 2 X 2 , l 1 X 1l 3 X 2 , (l 3l 2 )X 2 , X 2 -X 3 so that we have D 01 : {X 2 = 0} ∩ S , D 02 : {l 1 (P 02 )X 1l 3 (P 02 )X 2 = 0} ∩ S , D 13 : {l 0 (P 13 )X 0l 2 (P 13 )X 2 = 0} ∩ S . Now, let P be a point on S . If P / ∈ D 01 ∪ D 02 ∪ D 13 then π 1 (π -1 2 (P )) does not contain any base point and is necessarily zero-dimensional. Moreover, π 1 π -1 2 (D 01 ∩ D 13 ) = {l 1 = 0}, so that we have the one-dimensional fiber over D 01 ∩ D 13 = (0 : 1 : 0 : 0) that goes through only two of the three base points. A similar property appears for π 1 π -1 2 (D 01 ∩ D 02 ) = {l 0 = 0}. Notice that the three lines D 01 , D 02 , D 13 are not in the image of φ except for the two points: (0 : 1 : 0 : 0) and (1 : 0 : 0 : 0). Moreover, the fibers over these two points are lines and they are the only points with a one-dimensional fiber.

Link with multiple-point schemes of finite maps

Given a finite map of schemes ϕ : X → Y of codimension one, its source and target double-point cycles have been extensively studied in the field of intersection theory (see e.g. [START_REF] Kleiman | The multiple-point schemes of a finite curvilinear map of codimension one[END_REF][START_REF] Kleiman | The source double-point cycle of a finite map of codimension one[END_REF][START_REF] Piene | Polar classes of singular varieties[END_REF][START_REF] Teissier | The hunting of invariants in the geometry of discriminants[END_REF]). In [START_REF] Mond | Fitting ideals and multiple points of analytic mappings[END_REF], Fitting ideals are used to give a scheme structure to the multiple-point loci.

Under the hypothesis that φ : P 2 → P 3 is a finite map, our results are partially contained in the above literature. Recall that if φ has no base point then φ is finite (see Remark 11).

The contribution of our paper is hence mainly an extension to the case where φ is not finite. It is known that it is always possible to remove the base points by blowing-up, and this is exactly the role of the symmetric algebra in our approach of matrix representations, but still some one-dimensional fibers might remain.

In loc. cit. the basic ingredient is the direct image of the structural sheaf of P 2 : ϕ * (O P 2 ). Since ϕ is assumed to be finite, then ϕ * (O P 2 ) is a coherent sheaf and hence one can consider its Fitting ideal sheaves [START_REF] Mond | Fitting ideals and multiple points of analytic mappings[END_REF]. In our approach, we did not considered this sheaf, but the sheafification of the graded part of degree ν of the symmetric algebra S I (ν ν 0 ). It turns out that they are isomorphic as soon as φ is finite. Let us be more precise.

Assume that φ is finite (e.g. φ has no base point). In the following diagram

Γ ⊂ P 2 k × P 3 k π1 π2 % % P 2 k φ / / P 3 k the morphism π 1|Γ : Γ → P 2 k is an isomorphism, so that π ♯ 1 : O P 2 ≃ π 1 * (O Γ ) by definition.
In particular, we have the sheaf isomorphisms

π 2 * (O Γ ) = φ * π 1 * (O Γ ) ≃ φ * (O P 2 ). (7)
Given an integer ν, we can consider two sheaves of O P 3 -modules:

π 2 * (O Γ ⊗ O P 2 ×P 3 π * 1 (O P 2 (ν)))
and the sheaf associated to the graded R-module (S I ) ν that we will denote by (S I ) ν .

Lemma 19. For all ν ν 0 we have 8) where the last equality follows from the definition of π 2 * (-) and the fact that π -1 2 (Spec(R)) = P 2 × Spec(R). Since ( 8) is an equality of graded R-modules, we deduce that

φ * (O P 2 ) ≃ (S I ) ν Proof. The exact sequence of R-modules 0 → H 0 m (S I ) ν → (S I ) ν → H 0 (P 2 Spec(R) , O Γ ⊗ π * 1 (O P 2 (ν))) → H 1 m (S I ) ν → 0 shows that for all ν ν 0 we have (extending π 2 to P 2 × Spec(R) → Spec(R)) (S I ) ν = H 0 (P 2 Spec(R) , O Γ ⊗π * 1 (O P 2 (ν))) = H 0 (Spec(R), π 2 * (O Γ ⊗π * 1 (O P 2 (ν)))) (
(S I ) ν ≃ π 2 * (O Γ ⊗ O P 2 ×P 3 π * 1 (O P 2 (ν))
). Comparing this with (7) we obtain that for all ν ν 0 φ

* (O P 2 ) ≃ (S I ) ν (because π * 1 (O P 2 (ν)
) is an invertible sheaf). In particular, we get that

F 0 P 3 (π * 1 (O P 2 (ν))) ≃ F 0 P 3 ( (S I ) ν ) ≃ F 0 ν (φ)
where the last isomorphism follows from the stability of Fitting ideals under base change and the classical properties of the sheaves associated to graded modules.

The case of bi-graded parameterizations of surfaces

In this paper, we have treated rational surfaces that are parameterized by a birational map from P 2 to P 3 . In the field of geometric modeling such surfaces are called rational triangular Bézier surfaces (or patches). In this section, we will (briefly) show that we can treat similarly rational surfaces that are parameterized by a birational map from P 1 × P 1 to P 3 ; such surfaces are called rational tensor product surfaces in the field of geometric modeling where they are widely used.

Suppose given a rational map φ : P 1 k × P 1 k P 3 k where f 0 , f 1 , f 2 , f 3 are four bi-homogeneous polynomials of bi-degree d := (d 1 , d 2 ), that is to say that f i ∈ S := k[s 0 , s 1 , t 0 , t 1 ] is homogeneous of degree d 1 with respect to the variables s 0 , s 1 and is homogeneous of degree d 2 with respect to the variables t 0 , t 1 . As in Section 2, denote by S the closure of the image of φ, set x = (x 0 , x 1 , x 2 , x 3 ), R := k[x], I = (f 0 , f 1 , f 2 , f 3 ) ⊂ S d and assume that conditions (H) hold. In this setting, the approximation complex of cycles can still be considered and it inherits a bigraduation from the ring S with respect to the two sets of variables s 0 , s 1 and t 0 , t 1 . It is proved in [START_REF] Botbol | Implicit equation of multigraded hypersurfaces[END_REF] that matrix representations of φ still exist in this setting. To be more precise, define the following region (see Figure 2)

R d := {(n 1 , n 2 ) ∈ Z 2 such that (n 1 d 1 -2), or (n 2 d 2 -2), or (n 1 2d 1 -2 and n 2 2d 2 -2)} ⊂ Z 2 .
Then, for all ν = (ν 1 , ν 2 ) / ∈ R d the matrix M (φ) ν , which corresponds to the νgraded part of the matrix M (φ) in (1), is a matrix representation of φ with all the expected properties, in particular (see [START_REF] Botbol | Implicit equation of multigraded hypersurfaces[END_REF] for the details):

• its entries are linear forms in R = k[x 0 , . . . , x 3 ],

• it has (ν 1 + 1)(ν 2 + 1) rows and at least as many columns as rows,

• it has maximal rank (ν 1 + 1)(ν 2 + 1) at the generic point of P 3 k , • when specializing M (φ) ν at a point P ∈ P 3 , its rank drops if and only if P ∈ S.

(2d 1 -2, 2d 2 -2) (d 1 -2, 2d 2 -2) (2d 2 -1, d 2 -2) R d
Therefore, one can also consider the Fitting ideals F i ν (φ) ⊂ R associated to M (φ) ν for which Proposition 7 holds. Notice that in this setting, the projective plane P 2 is replaced by P 1 × P 1 in (5), so that for any point p ∈ Proj(R) the fiber of π 2 at p is a subscheme of P 1 κ(p) × P 1 κ(p) : We proceed as in the proof of Theorem 12. We may assume for simplicity that p = (1 : 0 : 0 : 0) so that I = (f 0 ) + h(g 1 , g 2 , g 3 ) with h the equation of the unmixed part of dimension 2 of the fiber at p; it is a bi-homogeneous polynomial of bi-degree e = (e 1 , e 2 ). Setting where the curve component of π -1 2 (p) is of bi-degree (e 1 , e 2 ) and c ∈ Z. From here, an algorithm similar to the one presented in §4.1 can be derived, for all ν / ∈ R d , in order to determine the characters of a fiber π -1 2 (p) by comparing matrix representations with consecutive indexes. Typically, the first matrix representation to consider is M (φ) (d1-1,2d2-1) (or M (φ) (2d1-1,d2-1) ) which has 2d 1 d 2 rows. Then, informations on the fiber at a given point p can be obtained by comparing the rank at p of M (φ) (d1-1,2d2-1) with the ranks at p of M (φ) (d1,2d2-1) and M (φ) (d1-1,2d2) .

Figure 2 .

 2 Figure 2. The region R d is represented in grey color.

  ) = BiProj(S I ⊗ R κ(p)) ⊂ P 1 κ(p) × P 1 κ(p) .Thus, the Hilbert function of a fiber π -1 2 (p) is a function of Z 2 . Similarly to Section 3, we set N p ν := HF S I ⊗ R κ(p) (ν). It turns out that an equality similar to (3) also holds:HP S I ⊗ R κ(p) (ν) := HF S I ⊗ R κ(p) (ν)i (-1) i HF H i B (S I ⊗ R κ(p)) (ν)where the ideal B denotes the product of ideals B := (s 0 , s 1 )(t 0 , t 1 ) ⊂ S. The function HP S I ⊗ R κ(p) is a polynomial function called the Hilbert polynomial (see[START_REF] Colomé-Nin | Multigraded structures and the depth of blow-up algebras[END_REF] or [BC13, Chapter 4.6] for more details). The following result allows to control the vanishing of the Hilbert function of the local cohomology modules of the fibers.Theorem 20. For all p ∈ Spec(R), all integer i and ν / ∈ R d ,H i B (S I ⊗ R κ(p)) ν = 0Proof. We will only outline the proof of this result because it follows the main lines of the proof of Corollary 13.Assume first that δ := dim(S I ⊗ R κ(p)) = 1. Lemma 8 implies thatH 0 B (S I ⊗ R κ(p)) ν = H 1 B (S I ⊗ R κ(p)) ν = 0 if H 0 B (S I ) ν = H 1 B (S I ) ν = 0.As proved in [Bot11, Theorem 4.7], this latter condition holds if ν / ∈ R d . Now, we turn to the case δ = 2 for which we have to control the vanishing of H 0 B (S I ⊗ R κ(p)) ν , H 1 B (S I ⊗ R κ(p)) ν and H 2 B (S I ⊗ R κ(p)) ν .

•

  If dim π -1 2 (p) = 1 then for all ν / ∈ R d corank(M ν (φ)(p)) = e 1 ν 1 + e 2 ν 2 + c

† This time was computed running the complete routine in a 2012's notebook with i3 core.

Acknowledgments. We would like to thank Ragni Piene and Bernard Teissier for enlightening discussions about the singularities of finite maps. Most of this work was done while the first author was hosted at INRIA Sophia Antipolis with a financial support of the european Marie-Curie Initial Training Network SAGA (ShApes, Geometry, Algebra), FP7-PEOPLE contract PITN-GA-2008-214584.

was partially supported by Marie-Curie Network "SAGA" FP7 contract PITN-GA-2008-214584, EU.

I ′ := (g 1 , g 2 , g 3 ), we have an exact sequence 0 → Z ′ 1 (d) → Z 1 (d) → S → S I ⊗ κ(p) → 0, with Z ′ 1 the syzygy module of (f 1 , f 2 , f 3 ), the first map sending (b 1 , b 2 , b 3 ) to (0, b 1 , b 2 , b 3 ) and the second (a 0 , a 1 , a 2 , a 3 ) to a 0 . The two spectral sequences associated to the double complex

-2 and ν 2 -2, and that H 2 B (S) ν = 0 if and only if ν 1 -2 and ν 2 0, or ν 1 0 and ν 2 -2 (see [Bot11, Lemma 6.7 and §7]).

To control the local cohomology of Z 1 we consider the long exact sequence of local cohomology associated to the canonical short exact sequence

We get H 1 B (Z 1 ) = 0 and the exact sequences

). Since we know the local cohomology of S, it remains to estimate the vanishing of the local cohomology modules H 1 (I) and H 2 (I). For that purpose, we examine the two spectral sequences associated to the double complex

). We obtain that H 1 B (I) ν = 0 for all ν such that H 2 B (S(-2d)) ν = H 3 B (S(-3d)) ν = 0 and that H 2 B (I) ν = 0 for all ν such that H 2 B (S(-d)) ν = H 3 B (S(-2d)) ν = 0. From here, we deduce that

Similarly, to control the local cohomology of Z ′ 1 we consider the long exact sequence of local cohomology associated to the canonical short exact sequence

). As in the previous case, it remains to estimate the vanishing of the local cohomology modules H 1 (I ′ ) and H 2 (I ′ ). We proceed similarly by inspecting the two spectral sequences associated to the double complex C • B (K • ((g 1 , g 2 , g 3 ); S)) and finally deduce that

As a consequence of this result, all the properties we obtained in Section 4 also applied to the setting of a bi-graded parameterization. In particular, we have the following properties.