Clément Poncelet
email: clement.poncelet@ircam.fr

Florent Jacquemard
email: florent.jacquemard@inria.fr

Model Based Testing of an Interactive Music System *

The role of an interactive music system (IMS) is to accompany musicians during live performances, like a real musician. It reacts in realtime to audio signals from musicians, according to a timed specification called mixed score, written in a domain specific language. Such goals imply strong requirements of temporal reliability and robustness to unforeseen errors in input, yet not so much studied in the computer music community.

We present the application of model-based testing techniques and tools to a state-of-the-art IMS, including the following tasks: generation of relevant input data for testing (including timing values) following coverage criteria, computation of the corresponding expected output, according to the semantics of a given mixed score, black-box execution of the test data and verdict. Our method is based on formal models compiled directly from mixed scores, and passed, after conversion to timed automata, to the model-checker Uppaal. This fully automatic approach has been applied to real mixed scores used in concerts and the results obtained have permitted to identify bugs in the target IMS.

Introduction

Score based interactive music systems (IMS) [START_REF] Rowe | Interactive Music Systems: Machine Listening and Composing[END_REF] are involved in live music performances and aim at acting as an electronic musician playing with other human musicians. Such a system requires a mixed score describing the parts of human musicians (input) together with electronic parts (output). During a performance, it aligns in real-time the performance of the human musicians to the score, handling possible errors, detects the current tempo, and plays the electronic part. Playing is done by passing messages to an external audio environment such as MAX [START_REF] Puckette | Combining event and signal processing in the max graphical programming environment[END_REF]. A popular example of this scenario is automatic accompaniment [START_REF] Cont | Correct Automatic Accompaniment Despite Machine Listening or Human Errors in Antescofo[END_REF].

An IMS is therefore a reactive system, interacting with the outside environment (the musicians), under strong timing constraints: the output messages must indeed be emitted at the right moment, not too late but also not too early. It is important to be able to assess the behavior of an IMS on a given score before its real use in a concert. A traditional approach is to rehearse with musicians, trying to detect potential problems manually, i.e. by audition. This tedious method offers no real guaranty since it is not precise, not complete (it covers only one or a few particular musician's performances), and error prone (it relies on a subjective view of the expected behavior instead of a formal specification). In this paper, we present the application of model based testing (MBT) techniques to a score based IMS called Antescofo, used frequently in world class concerts in the contemporary repertoire. Roughly, our method proceeds with the following steps depicted in Figure 1. First, a given mixed score is compiled into an intermediate representation (IR). This formalism can be presented as a table of finite state machines extended with delays and asynchronous communications with the environment (using input and output symbols) and between machines. It is viewed as the model M of the Antescofo reactions according to the score. The IR is then transformed into a timed automata (TA) network [START_REF] Alur | A theory of timed automata[END_REF], assuming some restrictions. TA's are processed by tools from the Uppaal suite [START_REF] Hessel | Testing real-time systems using Uppaal[END_REF] to generate covering suites of test cases: input timed traces together with the corresponding expected output; the input traces are then sent to the IMS (as a virtual musician's performance of the score) and the real outcome of the IMS is analyzed, resulting in a test verdict.

Several works like [START_REF] David | Testing real-time systems under uncertainty[END_REF] and [START_REF] Hessel | Testing real-time systems using Uppaal[END_REF]

Preliminaries

We first introduce the IMS Antescofo, its domain specific language (DSL) for mixed scores and our MBT framework.

The score-based IMS Antescofo

Figure 2 describes roughly the architecture of Antescofo, which is made of two main modules. A listening machine (LM) decodes an audio or midi stream incoming from a musician and infers in realtime: (i) the musician's position in the given mixed score, (ii) the musician's instantaneous pace (tempo, in beats per minute) [START_REF] Cont | A coupled duration-focused architecture for realtime music to score alignment[END_REF]. These values are sent to a reactive engine (RE) which schedules the electronic actions to be played, as specified in the mixed score. The actions are messages emitted on time to an audio environment. Therefore, the information exchanged between LM and RE as well as between RE and the output environment of the system is made of discrete events. The mixed scores of Antescofo are written in a textual reactive synchronous language enabling the description of the electronic accompaniment in reaction to the detected instrumental events. We give here a simplified abstract syntax corresponding to a fragment of this language, in order to illustrate our test framework (see [START_REF] Echeveste | Operational semantics of a domain specific language for real time musiciancomputer interaction[END_REF] for more complete descriptions). Let O be a set of output messages (also called action symbols and denoted a) which can be emitted by the system and let I be a set of event symbols (denoted e) to be detected by the LM (i.e. positions in score We consider here two time units for expressing delays and durations d: (i) the number of beats (default unit): a logical time unit traditionally used in music scores that we call relative time, and (ii) milliseconds (ms), referred to as physical time. The reconciliation of the relative and physical times is done through the detected tempo values.

Example 1 Figure 3 displays a small extract of a mixed score, in abstract syntax and traditional musical notation. The top stave is the musician part, it contains three quarter notes (whose duration is one beat): D4, B3 and E4. The bottom field is the electronic part with output messages a 0 , . . . , a 7 . Note that actions are triggered only by the first event which fires the top group s1 when detected. s1 fires concurrently and simultaneously (0 delay) the atomic action a 0 and the loose global group s 2 . A delay of 1 2 (action a 2 ) corresponds to an eighth note i.e. half of a beat.

The high-level attributes attached to an action act(d, s, al ) are indications regarding musical expressiveness [START_REF] Cont | Correct Automatic Accompaniment Despite Machine Listening or Human Errors in Antescofo[END_REF]. We consider here four attributes for illustration purpose (their interpretation will be defined formally in Section 3.2): two attributes are used to express the synchronization of the group s to the musician's part: loose (synchronization on tempo) and tight (synchronization on events) and two attributes describe strategies for handling errors in input: local (skip actions) and global (play actions immediately at the detection of an error). An error is in particular an event of the score missing during performance, either because the musician did not play it or because it was not detected by the LM.

Example 2

The possible interpretations of the actions in our running example according to 4 combinations of strategies for err and sync is depicted in Figure 4.

Model-Based Testing

We consider a black-box testing conformance approach for Antescofo, based on timed traces comparisons. We assume a given mixed score M with a default tempo value.

A timed trace is a sequence of pairs a, t made of a symbol a ∈ I ∪ O, and a timestamp t ∈ R + , either in physical or relative time. A trace containing symbols exclusively in I (resp. O) is called an input trace (resp. an output trace). We denote below T in (resp. T out ) the set of input (resp. output) traces with relative timestamps. The ideal trace is the input trace consisting in the projection of all events in M with their duration.

Example 3

The ideal trace for the score in Figure 3 is the following: e 1 , 1 • e 2 , 2 • e 3 , 3 .

By definition of music performance, traces of real executions can be arbitrarily far from ideal traces: the tempo and delays can diverge from the written values (the musician adding her/his own expressiveness values), and moreover their can be errors during a performance (missing notes).

We shall, in Section 3, associate to the model M two formal models: a specification E of the possible behaviors of the environment (i.e. the events of the musician playing M, as detected by the LM) and a specification S of the behavior of the system on M. In our case, E can be seen as a subset of T in and S as a function from T in into T out . This disymmetry between E and S reflects our case study, with on one side the musician and the LM and on the other side the RE (see Figure 2).

A test case is a pair t in , t out ∈ T in ×T out where t in ∈ E and t out = S(t in ). Two complementary approaches for the offline generation of t in are presented in Section 4.

The execution of a test case t in , t out consists in several tasks summarized in the following definition of conformance. First, we pass the events of t in to the implementation under test (IUT), i.e. the IMS Antescofo, respecting the timestamps. Second, we monitor the outcome of the IUT in an output trace t out = IUT(t in ). Finally, we compare t out to t out = S(t in ). We define the conformance of the IUT to S wrt E as: ∀t in ∈ E, IUT(t in ) = S(t in ). This is a particular case of the relation rtioco considered in [START_REF] David | Testing real-time systems under uncertainty[END_REF][START_REF] Hessel | Testing real-time systems using Uppaal[END_REF].

This definition makes sense only if the timestamps of t in , t out and t out are in the same time unit. We will show how this important issue is addressed in practice in Section 4, with several options for the conversion of all traces into physical time (thanks to the addition of tempo values).

Models

We present a procedure for compiling a mixed score into an intermediate representation (IR) used as a model for test case generation in our MBT framework.

Intermediate Representation

The IR has the form of an executable code modeling the expected behavior of Antescofo on a given score. We present here a simplified version of Antescofo's IR suitable for our presentation, leaving features such as thread creation, conditional branching, and variable handling outside of the scope of this paper.

Syntax. An IR is a finite sequence (called network ) of FSMs of the form A = Σ, Q, 0 , ∆ 0 , ∆ 1 where Σ is an alphabet partitioned into Σ = Σ in Σ out Σ sig (respectively the sets of input, output symbols and internal signals

), Q is a finite set of locations, parti- tioned into Q = Q 0 Q 1 , 0 ∈ Q is the initial lo- cation, ∆ 0 ⊆ Q 0 × (Σ out Σ sig ) × Q is a finite set of synchronous transitions (denoted --→ σ!
), and

∆ 1 ⊂ Q 1 ×((Σ in Σ sig R + )×Q) + is a finite set of asyn- chronous transitions. We write -------→ τ1?|...|τp? 1 | . . . | p , for , τ 1 , 1 , . . . , τ p , p ∈ ∆ 1 where p ≥ 1, ∈ Q 1 ,
1 , . . . , p ∈ Q, and τ 1 , . . . , τ p ∈ Σ in ∪ Σ sig ∪ R + . Moreover, there must be at most one delay d ∈ R + , and at most one input event in Σ in amongst τ 1 , . . . , τ p . Informally, every synchronous transition --→ σ! in ∆ 0 describes the emission, while in source location , of the output message or signal σ, followed by the change of location to the target location , and every asynchronous transition -------→ τ1?|...|τp? 1 | . . . | p in ∆ 1 describes the concurrent wait, in source location , of τ 1 , . . . , τ p . The first event τ i occurring provokes a change of location to the target i . Moreover, every location can be the source of at most one transition in ∆ 0 ∪ ∆ 1 . Semantics. In the above partition of Σ, Σ in and Σ out are sets of symbols used for communication with the environment, and Σ sig is an auxiliary set of internal signals used for communication between FSMs of a network.

We consider a model of superdense time [START_REF] Manna | The Temporal Logic of Reactive and Concurrent Systems[END_REF][START_REF] Ptolemaeus | System Design, Modeling, and Simulation using Ptolemy II. Ptolemy.org[END_REF] with timestamps in (t, n) ∈ R + × N, where t is a date in relative time called logical instant. The logical time can flow only when in locations of Q 1 (sources of asynchronous transitions). In locations of Q 0 , t is fixed and the execution of synchronous transitions will increase the second

component n ∈ N. Let Ā = A 1 . . . A k be a network of k FSMs composed in parallel with A i = Σ, Q i , i 0 , ∆ i 0 , ∆ i 1 for all 1 ≤ i ≤ k. A state of Ā is a tuple of the form t, n, [ 1 , . . . , k ], Θ, ω where (t, n) is a timestamp, [ 1 , . . . , k ] ∈ Q 1 × . . . × Q k the
array of current locations, Θ ⊂ Σ sig is a finite set of internal signals or messages and ω ∈ Σ out {⊥}. The initial state of Ā is s 0 = 0, 0, [ 1 0 , . . . , k 0 ], ∅, ⊥ . An external event τ can be the arrival of an input in Σ in or the expiration of a delay d ∈ R + (we assume external timers are in charge of notifying the expiration with the necessary (re)-conversion of delays in physical time using (updated) tempo values, see [START_REF] Echeveste | Operational semantics of a domain specific language for real time musiciancomputer interaction[END_REF]). We assume that a given input trace t in ∈ T in specifies the arrivals of inputs in Σ in .

The moves of Ā (between states) are defined as follows.

t, n, [ 1 , . . . , k ], Θ, ω → t, n+1, [ 1 , . . . , k ], Θ∪{σ}, ⊥ (es) t, n, [ 1 , . . . , k ], Θ, ω → t, n + 1, [ 1 , . . . , k ], Θ, σ (em
) where the locations 1 , . . . , k are defined as follows. Let i be the smallest index (in the array of current locations) such that i ∈ Q 0 , and there exists i --→ σ! i ∈ ∆ i 0 , with σ ∈ Σ sig for (es), and σ ∈ Σ out for (em). Then, i = i and j = j for all j = i. Here, a synchronous transition is executed and the signal (es) (resp. message (em)) emitted is added to Θ (resp. ω).

t, n, [ 1 , . . . , k ], Θ, ω → t, n + 1, [ 1 , . . . , k ], ∅, ⊥ (rs
) where 1 , . . . , k ∈ Q 1 , and for all i, 1 ≤ i ≤ k, there exists i ---------→ τi,1?|...|τi,p i ? i,1 | . . . | i,pi ∈ ∆ 1 . Moreover, let j be the smallest j such that 1 ≤ j ≤ p i and τ i,j ∈ Θ ∩ Σ sig . If j exists, then i = i,j , and otherwise i = i . Here, the signals expected and present in Θ are all received at once, and Θ and ω are flushed.

t, n, [ 1 , . . . , k ], Θ, ω → t , 0, [ 1 , . . . , k ], ∅, ⊥ (rx) where 1 , . . . , k ∈ Q 1 , and for all i, 1 ≤ i ≤ k, there ex- ists i ---------→ τi,1?|...|τi,p i ? i,1 | . . . | i,pi ∈ ∆ i
1 , and moreover, letting T i = {τ 1,1 , . . . , τ k,p k }, it holds that T i ∩ Θ = ∅ (i.e. (rs) cannot be fired). Then t ≥ t is the first date (after t) of occurrence of an external event τ ∈ T i , with a priority for delays (R + ) over inputs (Σ in ). For all 1 ≤ i ≤ k, if τ i,j = τ for some 1 ≤ j ≤ p i , then i = i,j , otherwise i = i . Here, t is the date of the first event τ after t in t in or the expiration of a delay d ∈ R + and in the latter case, t = t + d.

Note that with the above definitions, the moves are mutually exclusive and performed in the given priority order. In particular, the steps (es) and (em) are repeated as long as there exists executable synchronous transitions (i.e. locations of Q 0 in the state). Note also

0 1 2 3 e1! e2! e3! e 2 ! e 3 !
Figure 5: The FSM for environment E (score of Fig. 3).

that the steps (es) and (rs) may loop in the same logical instant.

A run ρ is a sequence of states s 0 , s 1 , . . . such that for all i ≥ 0, there is a move between s i and s i+1 . We associate to ρ the output trace t out defined as the projection of ρ on its first and last components different from ⊥. The above definitions ensure determinism of IRs, in the sense that there exists exactly one run ρ (hence one output trace t out ) for a given input trace t in ∈ T in . This implies that S is functional when it is defined as an IR. By abuse of notations we shall keep writing t in ∈ E and S(t in ) when E and S are IRs.

The synchronous aspect and the set of instant logic signals of the IR model are inspired by the programming language Esterel for reactive systems [START_REF] Berry | The Esterel Synchronous Programming Language: Design, Seman-tics, Implementation[END_REF].

Compiling mixed scores into IR

An IR is constructed directly from a given mixed score sc, during the parsing of the latter.

For the sake of conciseness, we do not give the inferences defining recursive constructions, but instead, a graphical representation of the IR obtained for our running example. The environment IR (E) is built with a single pass through score events. There are several options for constructing E, regarding missed notes (see Section 4). In Figure 5, the musician modeled by E, when in 0 , can miss the first note e 1 (upper edge to location 2 ) or e 1 and e 2 ( 3 ). In 1 , he can miss e 2 (going to 3 ).

The proxy IR (P) in Figure 6 provides a definition of errors. We assume one internal signal e i ∈ Σ sig for each input event in e i ∈ I. The proxy P emits this signal when e i is detected as missing, because an event e j with j > i was received. The proxy IR will simplify the complex task of specifying error management in other IRs.

Figure 7 and 8 show the IR obtained from the running example, for two different synchronization strategies (resp. loose and tight). Those models of the IUT behavior are constructed by iteratively traversing the sequence of actions in a group. The parts build at each step are framed and annotated as T g , for starting the

0 1 2 3 1 2 3
e1? e2? e3?

e2 ? e 1 ! e 3 ? e1! e 2 ! e 3 ?

Figure 6: The FSM for proxy P (score of Fig. 3). group, G a , for handling one atomic action a, or F, for ending the IR. In Figure 7 (attributes loose, global), the top part of the IR (locations 1 , ..., 6 ) corresponds to a mode for a normal behavior (in absence of errors), which consists in sending successively the actions with their respective delays. The bottom part of the IR (locations 1 , ..., 6 ) corresponds the behavior in case of error: send instantaneously all actions (without delay) until the next detected event (location 4 ).

In Figure 8 (attributes tight, global), the top and bottom parts also correspond to normal and error modes.

There is a possible switch (location 4 ) from the normal to the error mode if a missed event is detected. Also, in location 2 , if the event e 2 is earlier than expected, either as detected (edge e 2 ?) or as missing (edge e 2 ?) then there is a switch to an intermediate mode (respective locations e2 and e2 ).

Implementation and Results

Let us now present the implementation and results of our MBT approach, applied to the score-based IMS Antescofo.

Compiling mixed score into IR

Compiling mixed scores into IR has been implemented as a command line tool, written in C++ on the top of the original Antescofo's parser. The parsing produces an abstract syntax tree which is traversed using a visitor pattern in order to build the IR following the approach presented in Section 3.2. Several options are offered for the production of the IR corresponding to the environment E, in particular regarding the number of possible successive errors (missed notes). The most general case (any note can be missed) results in a model E with a quadratic (in score's size) number of transitions and an exponential number of input traces. The explosion can be controlled by choosing appropriate hypotheses on the environment E.

Translation of IR into Timed Automata

The IR is then translated into a network of timed automata (TA), in a format that can be handled by tools of the Uppaal suite for MBT. Some graphical coordinates are computed during compiling, and used for a nice display of the score models under Uppaal, providing composers with useful visual feedbacks of the low level control-flow in their mixed score. The translation of IR, in the simplified version presented in Section 3.1, into equivalent TA is possible whenever all the delays are expressed in relative time. Indeed, in TA, all the clock values are expressed in a unique abstract model time unit (mtu). For the TA associated to the environment IR model E, several options are offered for adding lower and upper bounds on the duration of each event, in order to limit the state exploration for the generation of t in .

Some care has to be taken for the simulation of the move rule (rs) in the semantics of IR. In fact, in the states of IR runs, signals are stored in an unordered set at each logical instant, and hence can be received in an arbitrary order. This is not the case with TA models. In order to sort the the interleaving between signals and external input events, an auxiliary step is performed, possibly modifying the IR structure (e.g. with urgent state in proxy, and early signals for group's triggers).

We have chosen to use an IR instead of directly translating mixed scores into TA [START_REF] Echeveste | Operational semantics of a domain specific language for real time musiciancomputer interaction[END_REF] because there is a clear correspondence between this ad'hoc model and the semantics of Antescofo's DSL, and the general IR format is used for other purposes and includes features not supported by TA (such as variables and dynamic thread creation).

Model-based generation of covering suites of test cases

We use the Uppaal extension called CoVer [START_REF] Hessel | Testing real-time systems using Uppaal[END_REF] to generate automatically suites of test cases, under a certain E, that cover the possible behavior of the specification S according to some coverage criteria. These criteria are defined by a finite state automaton Obs called observer monitoring the parallel execution of A E and A S , the TA associated to the IR E and S. Every transition of Obs is labeled by a predicate checking whether a transition of A E A S is fired. The model checker Uppaal is used by CoVer to generate the set of input traces t in ∈ T in resulting from an execution of the Cartesian product of A E A S with Obs reaching a final state of Obs.

For loop-free IR S and E, with an observer checking that all transitions of A E and A S are fired, CoVer will return a test suite T complete for non-conformance: if there exists an input trace t in ∈ E such that IUT(t in ) and S(t in ) differ, then T will contain such an input trace. Note that the IR produced by the fragment of the DSL of Section 2.1, using the procedure of Section 3.2, are loop-free. However this is not true for the general DSL which allows e.g. jump to label instructions.

In practice, we avoid state explosion with appropriate restrictions on E (number of missed events, see above) and the associated TA A E (bounds on event's durations).

Test cases generation by fuzzing ideal trace

An alternative method for the generation of relevant test cases is to start with the ideal trace associated to a mixed score and add deformations of several kinds. Time-warps [START_REF] Dannenberg | Abstract time warping of compound events and signals[END_REF] and variants like Time-Maps (Jaffe 1985), Time-deformations (Anderson and Kuivila 1990), are continuous and monotonically increasing functions used to define either variations of tempo or variations of the duration of individual notes wrt the written score events (time-shift). Some models of performance [START_REF] Honing | Structure and interpretation of rhythm and timing[END_REF][START_REF] Dannenberg | Abstract time warping of compound events and signals[END_REF] are defined by combination of these two transformations, defined independently. We consider a discrete version of such models, with extended input traces t in made of triples a, t, p , where a, t are like in Section 2.2 and p is a tempo value in beats per minute (BPM). The time-shifts are applied to the timestamps t (they are expressed in relative time), and the tempi b are values on a tempo curve. An important difference with [START_REF] Honing | Structure and interpretation of rhythm and timing[END_REF][START_REF] Dannenberg | Abstract time warping of compound events and signals[END_REF] is the possibility to include missed notes in input traces.

Tests execution and verdicts

We have developed several scenarios for the execution of a test case t in , t out , corresponding to several boundaries for the black box tested inside the whole systemsee Figure 2.

In a first scenario, t in contains triples like in the above paragraph. The tempo values are either values in a curve, in the case of traces generated by fuzzing, or a fixed value in the case of trace generated by CoVer. This scenario is performed on a standalone version of Antescofo equipped with an internal test adapter module. The adapter iteratively reads one element e, d, p of a file containing t in , converts d into a physical time value d (remember that delays are expressed in relative time in t in ), and waits d seconds before sending e and p to the RE. More precisely, it does not physically wait, but instead notifies a virtual clock in the RE that the time has flown of d seconds. This way the test needs not to be executed in realtime but can be done in fast-forward mode. This is very important for batch execution of huge suites of test cases. The timestamps in the expected trace t out are converted from relative to physical time using the tempo values in t in , in order to be compared to the monitored trace t out . Here, the blackbox is the RE (the LM is idle).

In a second scenario, the tempo values are not read in t in but detected by the LM. The rest of the scenario follows the first case. Here, the blackbox is the RE plus the part of the LM in charge of tempo inference.

A third scenario is executed in a version of Antescofo embedded into MAX (as a MAX patch). In this case, the blackbox is the whole IMS Antescofo, and instead of seeing discrete events to the IUT (like in scenarios 1 and 2), we generate an audio stream with a MIDI synthesizer (in MAX), using the events in t in as MIDI events.

The verdicts are produced offline by a tool comparing the expected and monitored traces t out and t out with an acceptable latency (about 0.1 ms). The comparison is not totally obvious since we have no clue a priori about missed or added actions/events in the traces and about the order of items.

Experiments

Two case studies will be reported: B, a benchmark made of hundreds of little mixed scores, covering many features of the IUT's DSL and EIN , a real mixed score of the piece of Einspielung by Emmanuel Nunes 1 . The first benchmark can be useful for the development (debugging and regression tests) of further versions of the system Antescofo. It aims at covering the IUT's DSL functionality and checking the reactions of the system. The second is a long real test case, for evaluating the scalability of our test method. It is composed of two extracts: the first 4 bars (22 events and 112 actions) and 14 bars (72 events and 389 messages).

Each case study is processed three times, with different numbers of possible consecutive missing events (0, 3 and 6 events) and a bound of 5% for the variation of the duration in the interpretation on each event. A script creates the IR and TA models, generates test suites (using CoVer), executes them according to the first scenario presented above and compares the outcome to test cases. Table 1 summarizes the results for the Benchmark B, reporting the number of traces generated by CoVer and the time taken by the whole test. Note that the increase of the number of traces with missing events (the length of the tested scores is generally between 3 to 6 events).The second table summarizes the results for Einspielung, with the number of IR locations, traces and testing time for each extract. Co-Ver did not succeed to generate the input traces for the 14 bars extract in the case of 6 possible missed events. Despite CoVer scalability (that can be bypassed with other scenarios), generated suites of traces are relevant and test the IUT for an exhaustive set of possible performances.

A problem encountered with CoVer is that it generates only time optimal test suites, i.e. input trace with minimum time-delay satisfying a given reachability property. This is not well suited to our case study. Indeed, since the trace t in is stamped in relative time, a time optimal t in will result in a geometric progression of the tempo.

Conclusion and further work

Thanks to an ad'hoc intermediate representation for mixed scores, and conversion into timed automata, we have developed a fully automatic offline model-based testing procedure dedicated to an interactive music system. An advantage of this case study for MBT is the possibility to generate the formal specifications (as IR) automatically from the given scores. A drawback is the necessity to deal with different time units, in particular relative time. This latter problem prevented us from using the online testing tool Tron [START_REF] Hessel | Testing real-time systems using Uppaal[END_REF] (roughly, Tron can deal with several clocks but they must all be defined as a factor of the wall clock).

Our method is designed to test the behaviour of the IMS on one given score, by generation of a covering set of input traces describing a range of musical performance of the score. This approach is advantageous both for IMS debugging, thanks to coverage criteria, and for user assistance to authors of mixed scores, using fuzzing based on models of musical performance. A more general perspective could be to test the behavior of the IMS on any score. This would require a complete specification of the IMS (written manually) as e.g. an hybrid system, and the automatic generation, as test input, of a covering set of "extreme" scores and covering sets of performance traces for these scores.

Figure 1 :

 1 Figure 1: Score-based IMS testing workflow

Figure 2 :

 2 Figure 2: Architecture of Antescofo

Figure 4 :

 4 Figure 4: Interpretation of the running example when the first note is missed, for various attributes.

3 FFigure 7 :

 37 Figure 7: The group s 2 FSM with al = [loose; global]

3 Figure 8 :

 38 Figure 8: The group s 2 FSM with al = [tight; global]

  implement different MBT techniques using Uppaal model checker features. The test problems are reduced into reachability or safety constraints delegated to Uppaal. Our case study presents important originalities compared to

	musicians	mixed score	audio
	stream audio or MIDI	Listening Machine	tempo pos.	Reactive Engine	software messages

  ). An action is a term BPM 144 evt(e 1 , 1, s 1 ); evt(e 2 , 1, []); evt(e 3 , 1, []) where s 1 = act(0, [a 0 ], [ ]); act(0, s 2 , [loose; global]) s 2 = act(0, [a 1 ], [ ]);Figure 3: A mixed score in abstract syntax. act(d, s, al ) where d is the delay before starting the action, s is either an atom in O or a finite sequence of actions (such a sequence is called a group), and al is a list of attributes. A mixed score is a finite sequence of input events of the form evt(e, d, s) where e ∈ I, d is a duration and s is the top-level group triggered by e. Sequences are denoted with square brackets [, ] and the empty sequence is [ ].

	act(1/2, [a 2 ], [ ]);
	act(1/2, [a 3 ], [ ]);
	act(1/2, [a 4 ], [ ]);
	act(1/2, [a 5 ], [ ]);
	act(1/3, [a 6 ], [ ]);
	act(1/3, [a 7 ], [ ])

Table 1 :

 1 1 http://brahms.ircam.fr/works/work/32409/ Results of experiments

	case c. miss nb score nb trace time (s)
		0	582	1843	140
	B	3	582	5718	334
		6	582	6387	405
	case c. miss locations nb trace time (s)
		0	400/1394	7/35	1/24
	EIN	3	518/1812	36/50	3/198
		6	771/2815 67/NA	97/400

Acknowledgments

The authors wish to thank the members of the teams developing Uppaal and Antescofo for their help.

This work has been partly supported by a DGA-MRIS scholarship and the project Inedit (ANR-12-CORD-009).


Vivien Dubois
email: vivien.dubois@m4x.org

Jean-Gabriel Kammerer
email: jean-gabriel.kammerer@m4x.org

Cryptanalysis of Cryptosystems Based on Non-commutative Skew Polynomials

Keywords:

Ten years ago, Ko et al. described a Diffie-Hellman like protocol based on decomposition with respect to a non-commutative semigroup law. Instantiation with braid groups had first been considered, however intense research on braid groups revealed vulnerabilities of the group structure and of the braid based DH problem itself. Recently, Boucher et al. proposed a similar scheme based on a particular non-commutative multiplication of polynomials over a finite field. These so called skew polynomials have a well-studied theory and have many applications in mathematics and coding theory, however they are quite unknown in a cryptographic application. In this paper, we show that the Diffie-Hellman problem based on skew polynomials is susceptible to a very efficient attack. This attack is in fact general in nature, it uses the availability of a one-sided notion of gcd and exact division. Given such tools, one can shift the Diffie-Hellman problem to a linear algebra type problem.

Introduction

Since the proposal of the original Diffie-Hellman key exchange [START_REF] Diffie | New Directions in Cryptography[END_REF], many variations around the same principle have been proposed. The core structure of a Diffie-Hellman-like key exchange is as follows. Let K and D denote fixed domains and let F be a function from D × K to D such that 1. for any z in D, F (z, •) is a one-way function, 2. the set of functions F a = F (•, a), a in K is commutative for the composition of maps, that is, for any a, b in K,

F a • F b = F b • F a .
In a Diffie-Hellman like protocol the function F and a particular element z of D are public information. In a first pass, each party chooses a random element on his own in the set K (a for Alice's and b for Bob's), encrypts z with it and sends the result to the other party. Then each party encrypts again the received data with his element of K. In the end, they both hold

F a (F b (z)) = F b (F a (z)).
The security of the protocol assumes that given F a (z) and F b (z) it is infeasible to compute this common data (computational DH assumption). Of course, the assumption cannot be true if F (•, z) is not a one-way function since one can (for instance) recover a from F a (z) and stand in the same position as Alice.

The original proposal by Diffie and Hellman was to set F to the exponentiation of z by a in a multiplicative group [START_REF] Diffie | New Directions in Cryptography[END_REF]. When z is a fixed group element, its powers describe a cyclic (hence commutative) subgroup. The one-wayness of F (z, •) means the infeasability of identifying the power (discrete logarithm) of z corresponding with an arbitrary element of z . This proposal seems to find satisfactory instantations and is by far the most widely used. On the other hand, there has been several attempts at building functions F for a Diffie-Hellman protocol from non-commutative algebraic structures. In general, these schemes rely on a particular factorization problem rather than on discrete logarithms. Furthermore, they all appear as variations of the following construction [START_REF] Ko | New public-key cryptosystem using braid groups[END_REF].

Generic Diffie-Hellman protocol based on a non-commutative semigroup. Let (D, ) be a non-commutative semigroup (that is, it needs not have either a neutral element nor all elements to have an inverse). Elements of D may decompose in a large number of ways in general. Therefore it is assumed that given elements z, z of D such that z admits a factorization of the shape u z v, it is intractable to find such left and right factors u, v. Hence, one defines the set K to be ordered pairs [u, v] and one defines F : (z, [u, v]) → u z v. When the aforementioned decomposition problem is intractable, F has Property 1. For Property 2 to be fulfilled too, we need functions F (•, [u, v]) to commute. This is ensured by choosing elements u, v in a commutative sub-semigroup S. Hence, K = S × S. Note that this specialization modifies the one-wayness property of F . It becomes: given an element z of D and an element z in S z S where S is a commutative sub-semigroup, find u and v in S such that z = u z v.

At this point, it is not clear whether picking left and right factors in a commutative sub-semigroup weakens the decomposition problem. Either way, the cryptosystem can hardly save such a property. Encountered variations of the above description are choosing u and v in distinct subsets L, R that are either both commutative or commute the one with the other (in this case, one party of the Diffie-Hellman protocol uses L × R while the other one uses R × L). A more general setting may not require the commutative semigroup S to be a subset of D: it simply needs to act in a different way on the left and on the right of D. This is even more analogous to a general discrete log scheme where D may be an arbitrary cyclic group while S is a set of modular integers.

Instantiations. A well-known example of such a scheme based on a full group structure is the one on braid groups [START_REF] Ko | New public-key cryptosystem using braid groups[END_REF]. In this setting, pairs of the shape [u, u -1 ] are considered and the associated decomposition problem is called conjugacy problem. There had already been partial (still exponential) attacks on the general conjugacy problem in braid groups (see for instance [START_REF] Mahlburg | An overview of braid group cryptography[END_REF] for a survey). It turned out a specific polynomial time algorithm exists to attack the Diffie-Hellman assumption in braid groups [START_REF] Hee | A polynomial time algorithm for the braid Diffie-Hellman conjugacy problem[END_REF]. The attack uses the property that braid group elements can be represented by invertible matrices over some (complicated) ring. For any element z of the braid group, we denote by Z the associated matrix. Then, the conjugacy problem arising in the DH-like protocol rewrites to finding U in the representation of the particular commutative set S such that Z = U ZU -1 where Z, Z are public matrices such that at least one such solution U exists. Candidate solutions can be found by solving the linear algebraic problem: find a matrix U such that Z U -U Z = 0 and S i U -U S i = 0 for any generator s i of S. The above system in general has many solutions that are not representatives of elements of the braid groups. When it is not possible to sieve them, it does not solve the conjugacy problem. However, the authors further observed that any invertible solution of the above linear system (a random solution is invertible with high probability) has the property of commuting with the elements of S, and as a consequence is equally useful to uncover the shared output of the Diffie-Hellman protocol. Albeit polynomial, this attack did not yield a practical break as is. Yet, instantiation of the Diffie-Hellman protocol with braid groups does not seem to be still investigated.

Recently, Boucher et al. proposed a Diffie-Hellman scheme (and a companion ElGamal scheme) based on so called skew polynomials [START_REF] Boucher | Key exchange and encryption schemes based on non-commutative skew polynomials[END_REF]. Skew polynomials are polynomials over a finite field with a particular non-commutative multiplication which uses the Frobenius field automorphism. They were introduced by Ore in 1933 [START_REF] Ore | Theory of non-commutative polynomials[END_REF] and have found many applications in applied mathematics and coding theory. The proposed Diffie-Hellman scheme follows the previous description with multiplication of skew polynomials as the non-commutative law. Hence, it is an instantiation of the non-commutative Diffie-Hellman protocol which is not based on a full group law.

Our contribution. In this paper, we show that the scheme of Boucher et al. is susceptible to a very efficient attack. The attack in fact only remotely uses the structure of skew polynomials, it only uses the availability of a notion of left (or right) gcd and of a related exact division procedure in the underlying domain. In any such setting, one can shift solving the relevant decomposition problem to a linear algebra type problem.

Similarly to the attack on the braid DH scheme, not all solutions of the linear type problem are solutions of the initial decomposition problem. Real solutions satisfy one additional condition (such as invertibility in the case of the braid DH scheme). Particular heuristics must be used, then, to find real solutions among the solutions of the linear problem. Based on an assumption which is satisfied in practice for skew polynomials, one can very easily get a real solution by means of gcds, and the attack is completely polynomial time.

We first describe the precise setting and working of the attack without reference to skew polynomials and then describe application to this particular case. Then we consider a possible variation of the scheme based on modular skew polynomials. While our attack seems unfit to this case, we show that density of invertible elements makes it completely weak. Finally we point out that examples based on matrix multiplication can be reduced to modular skew polynomials.

Hence, although the attack looks general in nature, we could not produce another case of application of this attack, and we must leave it as an open problem.

General Strategy of the Attack

The Invertible Case

As a preliminary, let us consider the case when the commutative subsemigroup S is a group, that is, all its elements are invertible. In this case, a pair [u, v] in S × S is a solution to the Diffie-Hellman decomposition problem for given z in D and z in S z S if and only if z = u z v, that is u z = z v where u = u -1 . (Let us denote public variables in bold letters.) As a consequence, when S is a group, the quadratic looking equation z = u z v with unknown (u, v) can be directly turned into a linear looking equation u z = z v with unknown (u = u -1 , v). Of course it is the case in braid groups, where one additionally has u = v. Then, representing braid groups elements by matrices (see [START_REF] Hee | A polynomial time algorithm for the braid Diffie-Hellman conjugacy problem[END_REF]), the linear looking equation is turned into a linear relation on matrices (over a ring), which can be solved as shown in [START_REF] Hee | A polynomial time algorithm for the braid Diffie-Hellman conjugacy problem[END_REF]. Note that the attack may not solve the DH conjugacy problem. The same approach can also be used to find a linear invertible change of variables mapping two sets of quadratic multivariate equations over a field (which is a particular instance of the problem of 'isomorphism of polynomials' [START_REF] Patarin | Hidden fields equations (HFE) and isomorphisms of polynomials (IP): Two new families of asymmetric algorithms[END_REF]). Quadratic multivariate polynomials can be represented by upper triangular matrices (with the same number of non-zero coefficients), and whenever a linear invertible change of coordinates U maps a quadratic polynomial p to a polynomial p , it translates into the matrix identity P = U t P U (where superscript t denotes transposition). Since U is invertible, one can attack this problem by solving the linear equation V P -P U = 0 with unknown (V = (U t ) -1 , U ). It can easily be seen that roughly 3 independent pairs (p, p ) with the same U only are heuristically needed to directly solve this problem (i.e. find a one-dimensional space of solutions). Higher degree cases can be attacked as well from the identity between degree 2 homogeneous parts. A less immediate attack to this problem was also developed in [START_REF] Perret | A fast cryptanalysis of the isomorphism of polynomials with one secret problem[END_REF]. A similar attack was independently developed in [START_REF] Bouillaguet | Differential-algebraic algorithms for the isomorphism of polynomials problem[END_REF].

The Setting of our Attack

In this paper, we consider cases where the elements of S are not invertible, but breaking the Diffie-Hellman problem can also be shifted to solving a commutatortype (linear looking) equation. The basic structure of D that we need is that of a domain with a computable notion of left (or right) gcd and computable left (right) exact division (and S is a multiplicative commutative sub-semigroup).

Here, domain means that it has no divisors of zero: u v = 0 ⇒ u or v = 0. Note that it needs not be a form of Euclidean ring.

Before we describe the attack, let us recall the problem hierarchy on which the protocol relies. The Diffie-Hellman problem is: given

z A = u A z v A and z B = u B z v B , compute z AB = u A z B v A = u B z A v B .
A sufficient way of breaking the DH problem is the one of solving the decompositional problem arising in the Diffie-Hellman protocol: given z in D and z in S z S, compute u, v in S such that z = u z v. However, it was noted in [START_REF] Hee | A polynomial time algorithm for the braid Diffie-Hellman conjugacy problem[END_REF][START_REF] Shpilrain | The conjugacy search problem in public key cryptography: unnecessary and insufficient[END_REF] that breaking a relaxed variant of this problem is enough to break the DH problem: given z in D and z in S z S, compute u, v commuting with the elements of S such that z = u z v. Indeed, if an attacker can recover u A , v A commuting with the elements of S and such that z

A = u A z v A , she can compute u A z B v A = u B u A z v A v B = u B z A v B = z AB .
Hence, with obvious notation, the problem hierarchy is DH ≤ RelaxedDecomposition-DH ≤ Decomposition-DH.

The Attack

Now we describe the attack. Assume that D is a domain such that the left (or right) greatest common divisor of two elements always exists and can be computed efficiently and left (or right) exact division can performed efficiently. The attack originates from the following observation. Elements in the set S z S are changed in a particular way when multiplying on the left (or on the right) by an element of S. This property is used to create the Diffie-Hellman protocol.

Here we use it to attack the scheme. Let indeed λ be an arbitrary element of S. Then,

λ (u z v) = u λ z v.
Hence, we obtain another element which too has u as a left divisor. As a consequence, taking the left gcd of z = u z v and λ z , one obtains a (non-zero) multiple of u. The same can be done for any element λ of S. Let λ 1 , . . . , λ s be generators of S. For S to be transmittable data, these generators must be in very practical number (which we do not consider). Let g be the left gcd of {z , λ 1 z , . . . , λ s z }, obtained iteratively from pairwise left gcds. Hopefully, relying on the non-commutativity of z with the elements of S, g might be u itself. It can happen that we actually have a way to distinguish between u and its non-trivial multiples. In this case and if g actually equals u, then we use the left exact division algorithm and get v, and the decomposition problem is already broken. Otherwise, let anyway a be such that g = u a. By using the exact division algorithm, we obtain m and m i , i = 1, . . . , s such that

z = g m λ i z = g m i .
(

) 1
Since there are no divisors of zero in D, this system of equations rewrites

z v -a m = 0 λ i z v -a m i = 0.
(

) 2
Hence we obtain a set of linear looking equations in the unknown (v, a). Since relevant solutions v commute with S, one has the additional linear looking equations λ i v -v λ i for any i = 1, . . . , s. Not all solutions to these linear conditions, however, are solutions of the initial decomposition problem. This is because when shifting from the initial system (1) to the linear system (2), one loses the information that z v is a right divisor of z . For instance, any linear combination of such solutions satisfies the linear conditions while not necessarily satisfying the divisibility condition.

Let divisor solutions refer to the linear solutions (v, a) such that z v is a right divisor of z . We first show that any divisor solution is enough to break the relaxed decomposition problem. Assume indeed that the linear-looking system can be solved, and let (v , a ) be an arbitrary divisor solution. By using the exact division algorithm, we get u such that z = u z v . From z v = a m, we find z = u a m, and therefore we also have g = u a . Furthermore, u commutes with all generators of S:

from λ i z v = a m i , we get u λ i z v = g m i = λ i z = λ i u z v ,
and therefore u λ i = λ i u . As a consequence, (u , v ) is a pair of elements that both commute with S and satisfy z = u z v . Hence the relaxed decomposition problem is broken.

The only unproven step in the attack is the one of finding a divisor solution among the solution linear space. This part may only be heuristically approached. We first need to understand the structure of the solution linear space itself. Observe the following property. One easily sees that the property generalizes to solutions (v, a) of the complete linear system and left multiplication by

I = C(z) ∩ i C(λ i z) ∩ (•, S)
where S is the elements that commute with S. One easily checks that I = C(z) ∩ ( S, S). Also note that I is a ring for coordinate-wise addition and multiplication.

Additivity and left multiplication by I are degeneracies that are independent of the existential solution. Save these degeneracies, we expect the system of equations to be characteristic of the existential solution. Hence, we expect:

Claim. the solutions of the linear system are all spanned by a single generator through addition and left multiplication by I. Let (v g , a g ) denote this generator.

Then, since I is a ring, the linear solutions write simply I (v g , a g ). For the existential solution (v, â) in particular, there exists (ĉ, ĉ ) in I such that (v, â) = (ĉ, ĉ ) (v g , a g ). This means that (v g , a g ) is (v, â) purged out of its factors in I. This shows that (v g , a g ), just like (v, â), is a divisor solution. The other ones are spanned by factors (c, c ) related to left factors c of v or right factors c of u. Finally note that (v g , a g ) is a common right factor of all linear solutions and since it includes itself, it is in fact the right gcd of the linear solutions.

Application to Skew Polynomials Cryptosystems

Diffie-Hellman and ElGamal-like schemes based on skew polynomials were recently presented at PQCrypto 2010 [START_REF] Boucher | Key exchange and encryption schemes based on non-commutative skew polynomials[END_REF]. The Diffie-Hellman protocol follows the general construction described in the introduction and developed by the earlier group-based proposals. We first recall the particularities of skew polynomials and review the setting up of the cryptosystem. Then, we describe unrolling the attack in this particular case. Since the ElGamal scheme relies on the DH problem, we only consider the DH protocol.

Skew Polynomials

Skew polynomials are polynomials over a finite field with a particular noncommutative inner product. Let F q denote the finite field with q elements, and p be the characteristic of the field. Automorphisms of F q are the so-called Frobenius maps which are powering to a power of p. Let θ be such an automorphism. We denote by the inner product of skew polynomials. It is defined inductively for all a ∈ F q by X a = θ(a)X. The ring of skew polynomials is sometimes denoted F q [X, θ].

The ring of skew polynomials is a left and right Euclidean domain, that is, there are both a left and a right Euclidean division algorithm. Using the Euclidean algorithms one can thus compute left and right greatest common divisors, and also perform exact division.

As priorly addressed, due to the non-commutativity of the inner product, skew polynomials admit many factorizations instead of a single one. The cardinality of the number of possible factorizations is expected to be exponential in the degree of the polynomial.

Generation of the Scheme

For the sake of completeness, we recall part of the specification given in [START_REF] Boucher | Key exchange and encryption schemes based on non-commutative skew polynomials[END_REF]. However the attack is not tied to any particular key generation.

A brute-force approach is suggested to construct the commutative subset S. One iteratively constructs a set of generators G 0 , . . . , G s of small degree δ. At each step, a polynomial of degree δ is picked at random and tested for commuting with the current set of generators. If it does, it increments the set of generators, otherwise repeat. The set S is the commutative algebra spanned by these generators.

Let d be the security parameter of the protocol. A public polynomial Z of degree d is generated. At the execution of the Diffie-Hellman protocol, each participant selects two elements U and V in S with degree d through combination of the generators of S. More precisely, any picked element is a product of sums of products of the generators.

All tasks performed during the protocol can clearly be made practical, however the cost of generating a set of generators for S is quoted as a long computation without further detail. The proposed instantiation is with skew polynomials over F 4 , generators of S have degree δ = 8 or 9, and the protocol uses polynomials of degree d = 600. For these parameters, they give two examples of S through generator sets with ≥ 90 polynomials.

Commutativity Among Skew Polynomials

Before we go on with the attack, it is useful to investigate commutation properties of skew polynomials.

There are particular skew polynomials that commute with any other. This subset is called the center and we denote it by C. A characterization of these elements can be found in [START_REF] Boucher | Key exchange and encryption schemes based on non-commutative skew polynomials[END_REF]. Let m be the order of θ (say the degree of F q over F p to simplify). Then, the center polynomials are the polynomials over F p and in the only powers of

X m . C = F p [X m ].
Also, for any polynomial P , let C P denote the set of polynomials that commute with P . Of course, P commutes with itself and the elements of the center. As a consequence, C P contains the algebra generated by P and C, that is, the set of sums and multiples of elements of C and P . This algebra is a vector space over F p . On the other hand, if P has all its coefficients in F p , it commutes with any polynomial with coefficients in F p , not only itself and C. Hence,

if P ∈ F p [X], C P ⊇ F p [X] otherwise, C P ⊇ C, P = C[P ].
On the other hand, for any degree bound r, one can easily compute the elements of C P with degree ≤ r. Indeed, the equation P Q = Q P in the degree ≤ r indeterminate Q is a linear system over F p , and one can find its solutions through linear algebra. We ran experiments for many random choices of P (not with all coefficients in F p ) of degree δ = 8 and we found that at least up to degree r = 30 the elements of C P in fact all were in C[P ]. It suggests that when one picks generators for S during the key generation, one actually obtains polynomials in C[P 0 ], where P 0 is any smallest degree polynomial in S modulo C (modulo is well defined for central polynomials). Hence it is pointless to generate this set by brute force. This is confirmed for the proposals of S in [START_REF] Boucher | Key exchange and encryption schemes based on non-commutative skew polynomials[END_REF]: we respectively found P 0 = X 5 + X 3 + α and P 0 = X 3 + X + α.

Unrolling the Attack

Let Z = U Z V be the data transmitted by one of the participants of the protocol. Our first step is to take the gcd of Z and Λ i Z over all generators Λ i of S. Due to our previous comment on these generators having a common generator P 0 , we actually take the gcd of Z and P 0 Z . We find a polynomial G which is a right multiple of U : there exists a polynomial A such that G = U A. Also we compute M , M 0 such that

Z = G M P 0 Z = G M 0 .
Since the ring is a domain, one deduces from these equations,

Z V = A M P 0 Z V = A M 0 .
In addition, one has P 0 V = V P 0 since V commutes with S. These three equations are not linear over F q , as it would be with the usual product of polynomials, however they are linear alright over F p . Expanding these equations over F p , and degree bounding the search space according to the expected degree of the existential (V, A), we can solve the system through linear algebra.

The output of the previous phase is a degree bounded restriction of the entire solution subspace of the linear system. Recall from Section 2.3 that the entire solution space is closed under left multiplication by I = C(Z)∩( S, S). If the entire solution space indeed is monogeneous under linearity and left multiplication by I, then this generator is the lowest degree solution (V, A). Then, it can also be found as the right gcd of a linear basis of the bounded degree solution subspace.

We checked the previous expectations in practice with the recommended parameters and beyond. In any tested case, the bounded degree solution admitted only one lowest degree solution (up to F p multiples) and any other solution was a multiple of it by a central factor. It incidentally shows that I = C (1, 1) up to the fixed degree bound. Let (V g , A g ) denote the found generator. We verified that it is a divisor solution and also that it is the right gcd of a linear basis of the bounded degree solutions. We also checked that (V g , A g ) is the greatest central factor of the original solution ( V , Â). This greatest central factor can be extracted by taking the left gcd of ( V , Â) and arbitrary left multiples of it.

The attack has theoretical complexity in (md) 3 . It takes about a minute with the recommended parameters and with a straightforward implementation in C++ using the NTL library [START_REF] Shoup | NTL: A library for doing number theory[END_REF].

The Case of Modular Skew Polynomials

We consider a possible variation of the Diffie-Hellman protocol based on modular skew polynomials.

Constructing Modular Skew Polynomial Rings

Let R denote a skew polynomial ring F q [X, θ] and let N be an arbitrary element of R. Let N denote the set of left multiples of N . Congruence modulo N is an equivalence relation over R and the associated partition elements are called left classes modulo N . Obviously right classes can be defined all the same from N . Reduction modulo N (resp. N ) can be performed by using the left (resp. the right) Euclidean division algorithm.

One awkward property of left classes is that they cannot be multiplied the ones with the others unless N commutes with their elements in a certain sense. Indeed, let U + Λ N and V + Λ N be arbitrary reprensentatives of two classes. Their product

(U + Λ N ) (V + Λ N ) = U V + Λ N V + (U Λ + Λ N Λ ) N does not equal U V modulo N unless Λ N V is right divisible by N . Since
Λ may be chosen arbitrarily, it means N V is right divisible by N , or again that there exists W such that N V = W N . When such a W exists, we say that N quasi-commutes with V .

When we want the set of classes to itself be a (non-commutative) ring, we need N to quasi-commute with all elements of R. Let N denote the set of such N 's; we call it the quasi-center of R. Observe that the elements with which N quasi-commutes is closed under the ring operations. Therefore, N quasicommutes with all elements of R if and only it quasi-commutes with X and all the constants. This yields an easy characterization of such polynomials N . If a constant a quasi-commutes with N , because of the degree, its dual element is also a constant b. For any a,

N a = i n i θ i (a)X i = b N = i n i bX i
implies that there is k such that all non-zero terms are at i ≡ k mod m (where m is the order of θ, assumed equal to the degree of F q over F p ). Next, we do the same with X: there are constants a, c such that

N X = i n i X i+1 = (aX + c) N = i (aθ(n i ) + cn i+1 )X i+1 + cn 0 .
Let j be the smallest i such that n i = 0. Then, c.n j = 0 implies c = 0, and for any i such that n i = 0, a = n i /θ(n i ). Let ā satisfy ā/θ(ā) = a. Finally the quasi-center N is the union of the sets

N k,a = āX k C, k ∈ {0, . . . , m -1}, a ∈ F q , where C = F p [X m ] is the center of R. More concisely, this is ∪ m-1 k=0 F q X k C.
For any polynomial N of the quasi-center, left and right multiples of N are just the same sets and classes modulo these sets are simply said classes modulo N . These classes form a ring, which we denote by R N .

The Modified Scheme

Modular skew polynomial rings might be considered at the basis of a noncommutative Diffie-Hellman protocol following exactly the same construction as proposed in [START_REF] Boucher | Key exchange and encryption schemes based on non-commutative skew polynomials[END_REF]. Let d denote the degree of N . Any class admits a unique representative with degree < d. Multiplication of classes is realized through multiplication of canonical representatives and subsequent reduction mod N . We denote this operation by •.

A commutative set S may again be constructed by selecting commuting classes with canonical representatives of small degree δ. Since δ is a small constant while d is the security parameter, one can assume 2δ < d. In this case, the picked canonical representatives in fact commute without modulo. Then, following 3.3, these representatives are spanned over the center by a single polynomial P 0 . Elements of S are arbitrary combinations of P 0 over C reduced mod N .

First Remarks

It is immediate that R N is not a domain: for any pairwise factorization U V of N , we get U V = 0 mod N while neither U or V is divisible by N . Now, by definition a class Ū is a left factor of a class P if P lies in the image space of the map µ( Ū ) :

R N -→ R N V -→ Ū • V .
Recall the product Ū • V equals U V mod N where U and V are arbitrary elements of Ū and V . Observe that the set U +N is independent of the particular U in Ū . As a consequence, the left gcd G of U and N is independent of U in Ū . Now, from U +N = G , we get that right multiples of U and G are the same mod N . As a consequence, the image of µ( Ū ) is the set Ḡ•. Finally, Property 2. the set of left factors of a class P is the set of classes Ū whose left gcd G with N is a left factor of the canonical representative P of P .

In particular, classes that are left coprime with N are left factors of any class (they are the units of the ring). As one can see, the relationship between divisors and multiples is very loose in R N . Then, the fact that a class Z is computed as Ū • Z • V hardly carries information on the particular Ū and V . Therefore, there is not much information to be obtained in using gcds on Z and P0 • Z . Instead, since P is loosely related to the initial ( Ū , V ), one may take advantage of the many equivalent pairs ( Ū , V ).

Attacking the Modular Decomposition

Given a class Z , we search for a decomposition Ū • Z • V where Ū and V are in S (that is, commute with P 0 mod N ). At least one exists by construction of Z and we expect many others. We target pairs ( Ū , V ) in S × S such that (e.g.) Ū is left coprime with N . Before going on, observe that being left or right coprime with N is the same when N is in the quasi-center. From Ū being left coprime with N , we get W such that Ū • W = 1. Then right multiplication by Ū is clearly injective (right multiply by W ), and therefore bijective, and Ū is right coprime with N . Using associativity, one also gets that the left and right inverses are the same. Now, for any ( Ū , V ) in S × S where Ū is coprime with N ,

Z = Ū • Z • V ⇐⇒ W • Z = Z • V .
Also, Ū commutes with P0 iff W commutes with P0 . Therefore, the decompositional pairs ( Ū , V ) in S × S with Ū invertible are in bijection with the solutions ( W , V ) in S × S of the linear equation W

• Z = Z • V with W invertible.
For the attack to be successful, we simply need to extract a pair ( W , V ) with an invertible W from the solutions of the linear system. For this, we rely on the density of such pairs. First observe that restricting elements of pairs in S can only negligibly impact the density of invertible elements. Indeed, the modular condition is exact for all classes whose canonical representative has degree under deg(N ) -deg(P 0 ). Since deg(P 0 ) asymptotically remains a small constant, the fraction of classes for which the condition involves N is negligible. Besides, we see no reason why the density of W among solution pairs ( W , V ) (not restricted to S) of the equation W • Z = Z • V should differ from the global density.

Claim. The density of invertible W among solutions ( W

, V ) in S × S of W • Z = Z • V is the same as the density of invertible classes in R N .
Although N can have many distinct irreducible left factors, these are a subcollection of all possible irreducible left factors of degree deg(N ) polynomials. As a consequence, we expect the fraction of classes left coprime with N to be asymptotically a constant close to 1. For the sake of intuition, for any u < d, the fraction of right multiples of degree u monic polynomial L among degree < d polynomials is q -u . Then, the probability that two degree < d polynomials be both right multiples of L is q -2u . Then, the probability that they not share a common left multiple of degree u is 1 -q u q -2u = 1 -q -u . We estimate the probability of they be coprime by the probability not to share degree 1 left factors: 1 -1/q. This is our expectation of the density of invertible elements.

We checked the above properties in practice. We checked (through sampling) the density of invertible classes both among the left coordinates W of the solution space and among all classes. We found densities of the same order in both cases: equal in large characteristic and indeed close to 1 -1/q, but slightly different in small characteristic. Hence, we could in any case extract a decompositional solution almost at once.

Interestingly, the attack can be slightly generalized. We may more generally target decompositional solutions ( Ū , V ) such that Ū has a right gcd with N not necessarily 1 but a target right factor G of N which commutes with P 0 (for instance a central polynomial). Then, for any such Ū , there exist W such that W • Ū = Ḡ. Since both Ū and Ḡ commute with P 0 , the same holds for W . Then, we simply compute solutions ( W , V ) in S × S of W • Z = Ḡ • Z • V , and extract W such that the left gcd of W and N is G.

Beyond the Case of Skew Polynomials?

Another usual example of a non-commutative algebra are square matrices over a finite field. Then, the question arises as to whether this algebra can be used to build a non-commutative Diffie-Hellman protocol. We answer this question negatively by simply describing a well-known connection between square matrices over a finite field and modular skew polynomials (see for instance [START_REF] Coulter | Giesbrecht's algorithm, the HFE cryptosystem, and Ore's ps-polynomials[END_REF]): square matrices are modular skew polynomials with particular moduli.

Let F p be an arbitrary finite field and let F q = F p n be the degree m extension field of F p . It is well-known that F q is an m-dimensional vector space over F p . Hence, fixing arbitrary basis elements of F q over F p , one can encode any element of F q into an n-dimensional vector. This correspondence also induces a one-toone correspondence between F p -linear maps on F q and F p -linear maps on (F p ) m . The latter simply are represented by m×m matrices over F p . Hence, composition of F p -linear maps on F q is the same as matrix multiplication. We can now regard the ring of m × m matrices over F p as the ring of F p -linear maps on F q for + and the composition of maps, which we denote by L p (F q ). We now describe a generator basis for L p (F q ). It is well-known that powerings to the power of p are F p -linear bijections on F q called the Frobenius maps. We let θ be the first Frobenius map. Multiplication by an element of F q is also F p -linear. Therefore, linear combinations over F q of Frobenius maps (powers of θ) also are F p -linear. It can be seen that this representation is injective and finally, by a simple cardinality argument, one-to-one. As a consequence, L p (F q ) is the set of linear combinations over F q of the Frobenius maps, m-1 i=0 a i • θ i . These maps can be identified with polynomials m-1 i=0 a i X i . Mapping the ring structure of L p (F q ) to these polynomials, one obtains the usual + law but multiplication following the identities X • a = θ(a)X and X n = 1. This is exactly the identities defining skew polynomials F q [X, θ] modulo the center polynomial X m -1.

{m × m matrices over F p } = L p (F q ) = F q [X, θ]/(X m -1).

Property 1 .

 1 Let C(z) denote the set of pairs (c, c ) such that z c = c z. For any solution (v, a) of the linear looking equation z v -a m = 0 and any (c, c ) in C(z), the pair (c v, c a) is also a solution. As a consequence, the solutions of the equation z v -a m = 0 are closed under left (coordinate-wise) multiplication by C(z). Of course, they are also closed under addition.

Acknowledgements

We wish to thank Pierre Loidreau for helpful discussion on the subject of skew polynomials at the early stage of this work. We also wish to thank the anonymous referees of PKC 2011 for their detailed and helpful comments.