Irene Senna
email: irene.senna@uni-ulm.de

Lucilla Cardinali

Alessandro Farnè

Claudio Brozzoli

Aim and Plausibility of Action Chains Remap Peripersonal Space

Keywords: multisensory, grasping, peripersonal space, kinematics, motor act chains, action's aim, naturalistic neuroscience

Successful interaction with objects in the peripersonal space requires that the information relative to current and upcoming positions of our body is continuously monitored and updated with respect to the location of target objects. Voluntary actions, for example, are known to induce an anticipatory remapping of the peri-hand space (PHS, i.e., the space near the acting hand) during the very early stages of the action chain: planning and initiating an object grasp increase the interference exerted by visual stimuli coming from the object on touches delivered to the grasping hand, thus allowing for hand-object position monitoring and guidance. Voluntarily grasping an object, though, is rarely performed in isolation. Grasping a candy, for example, is most typically followed by concatenated secondary action steps (bringing the candy to the mouth and swallowing it) that represent the agent's ultimate intention (to eat the candy). However, whether and when complex action chains remap the PHS remains unknown, just as whether remapping is conditional to goal achievability (e.g., candy-mouth fit). Here we asked these questions by assessing changes in visuo-tactile interference on the acting hand while participants had to grasp an object serving as a support for an elongated candy, and bring it toward their mouth. Depending on its orientation, the candy could potentially enter the participants' mouth (plausible goal), or not (implausible goal). We observed increased visuo-tactile interference at relatively late stages of the action chain, after the object had been grasped, and only when the action goal was plausible. These findings suggest that multisensory interactions during action execution depend upon the final aim and plausibility of complex goal-directed actions, and extend our knowledge about the role of peripersonal space in guiding goaldirected voluntary actions.

INTRODUCTION

Recent evidence has shown that the representation of the space near the body, known as peripersonal space, might serve as a multisensory-motor interface that guides voluntary objectoriented actions such as grasping [START_REF] Brozzoli | Grasping actions remap peripersonal space[END_REF][START_REF] Brozzoli | Action specific remapping of peripersonal space[END_REF][START_REF] Brozzoli | Multisensory representation of the space near the hand: from perception to action and interindividual interactions[END_REF]. The existence of such representation, which relies on the integration of multisensory inputs close to the body, has been demonstrated in monkeys, as well as in humans. In monkeys, bimodal neurons in cortical and subcortical structures are activated by tactile inputs delivered to a specific body part, and by visual stimuli close to the same body part, thus promoting a body part-centered representation of the near space (e.g., [START_REF] Rizzolatti | Afferent properties of periarcuate neurons in macque monkeys. II. Visual responses[END_REF][START_REF] Rizzolatti | Functional organization of area 6 in the macaque monkey. II. Area F5 and the control of distal movements[END_REF][START_REF] Rizzolatti | The space around us[END_REF][START_REF] Fogassi | Space coding by premotor cortex[END_REF][START_REF] Fogassi | Coding of peripersonal space in inferior premotor cortex (area F4)[END_REF][START_REF] Graziano | A bimodal map of space: somatosensory receptive fields in the macaque putamen with corresponding visual receptive fields[END_REF][START_REF] Graziano | The representation of extrapersonal space: a possible role for bimodal, visuo-tactile neurons[END_REF], 1998;[START_REF] Graziano | Coding of visual space by premotor neurons[END_REF][START_REF] Graziano | Visuospatial properties of ventral premotor cortex[END_REF][START_REF] Graziano | Where is my arm? The relative role of vision and proprioception in the neuronal representation of limb position[END_REF]. Behavioral and neuroimaging studies suggest the existence of homologous body part-centered representations of peripersonal space in humans (e.g., di [START_REF] Di Pellegrino | Seeing where your hands are[END_REF][START_REF] Di Pellegrino | Direct evidence from parietal extinction of enhancement of visual attention near a visible hand[END_REF]Farnè and Làdavas, 2000;Farnè et al., 2000Farnè et al., , 2005a,b;,b;[START_REF] Pavani | Binding personal and extrapersonal space through body shadows[END_REF]Spence et al., 2004a,b;[START_REF] Brozzoli | Neglect and extinction: within and between sensory modalities[END_REF][START_REF] Brozzoli | Grasping actions remap peripersonal space[END_REF][START_REF] Brozzoli | Action specific remapping of peripersonal space[END_REF][START_REF] Brozzoli | fMRI adaptation reveals a cortical mechanism for the coding of space near the hand[END_REF]Brozzoli et al., , 2012a,b;,b;[START_REF] Sereno | A human parietal face area contains aligned head-centered visual and tactile maps[END_REF][START_REF] Makin | Is that near my hand? Multisensory representation of peripersonal space in human intraparietal sulcus[END_REF][START_REF] Huang | Mapping multisensory parietal face and body areas in humans[END_REF].

It has been hypothesized that such representation plays an important role in detecting potential threats approaching the body in order to facilitate defensive reactions (e.g., [START_REF] Graziano | Complex movements evoked by microstimulation of precentral cortex[END_REF]Cooke et al., 2003;Cooke and Graziano, 2003;[START_REF] Graziano | Parieto-frontal interactions, personal space, and defensive behavior[END_REF][START_REF] Makin | Coding of visual space during motor preparation: approaching objects rapidly modulate corticospinal excitability in hand-centred coordinates[END_REF]. [START_REF] Brozzoli | Grasping actions remap peripersonal space[END_REF] extended this view, by highlighting the role that perihand space (PHS) has also in guiding voluntary object-oriented manual actions. In their study, the authors used a modified version of the cross-modal congruency task, first introduced by [START_REF] Spence | What crossing the hands can reveal about crossmodal links in spatial attention[END_REF]. In the cross-modal congruency task, participants typically hold an object between their thumb and index fingers and make speeded elevation discrimination responses to vibrotactile targets delivered to either the index finger ("up") or thumb ("down"), while ignoring simultaneous visual distractors embedded in the object either at the same (i.e., congruent) or different (i.e., incongruent) elevation. Participants are not able to completely ignore the distractors in one modality while responding to the targets in the other modality: they are slower and less accurate when the elevation of the visual distractor is incongruent with the tactile target, a result taken to indicate the two stimuli (tactile and visual) interact. The cross-modal congruency effect (CCE, typically calculated as the difference in performance between incongruent and congruent trials on reaction times and/or accuracy) is indeed used as a measure of the interference between target tactile stimuli and visual distractors. The CCE is stronger when visual and tactile stimuli are close to each other, and thus it is used as an index of common representations of space across different sensory modalities (Spence et al., 2004a). The CCE gradually decays as the tactile stimulus and visual distractor become distant, such as when the object is moved away from the hand and outside the boundaries of the peripersonal space (see [START_REF] Maravita | Multisensory integration and the body schema: close to hand and within reach[END_REF]Spence et al., 2004a,b). In a modified version of the original task, Brozzoli and colleagues placed the object embedding the visual distractors far from the hand, but at a reachable distance, and asked participants to discriminate tactile stimuli delivered to the hand while grasping the object [START_REF] Brozzoli | Grasping actions remap peripersonal space[END_REF]. As soon as the hand moved to reach and grasp the object, the interference between visual and tactile stimuli grew stronger (i.e., the CCE increased), as compared to a static condition, well before the hand approached the object, and the effect was specific for the acting hand.

This finding shows that the execution of a simple goal-directed action triggers a dynamic on-line remapping of visuo-tactile interactions, as the action unfolds. In other words, the representation of the relative position between the tactile and visual stimuli is updated as a function of the action: the action's target, originally distant from the hand, is "remapped" as if it were closer (i.e., inside the PPS boundaries) to the hand before it actually gets close to it.

A more recent study reported that such a multisensory enhancement (i.e., an increase of the CCE) starts even before the hand moves, that is, during the action planning phase [START_REF] Patané | Action planning modulates peripersonal space[END_REF]. Thus, planning and executing voluntary object-oriented manual actions induce a remapping of the multisensory space near the hand, starting during the planning phase and continuing during early stages of action execution (i.e., at the action onset), hence well before the hand touches the object. Moreover, such anticipatory remapping of multisensory space (i.e, occurring before an actual contact between hand and object) further increases during action execution, as the hand gets closer to the target object [START_REF] Brozzoli | Grasping actions remap peripersonal space[END_REF], and is modulated by the type and complexity of object-oriented actions, with more complex sensorimotor transformations triggering stronger visuo-tactile interactions [START_REF] Brozzoli | Action specific remapping of peripersonal space[END_REF]. These findings suggest that performing a goal-directed voluntary action, such as grasping, induces a continuous update of the spatial relationship between signals in different modalities throughout the entire action, involving sensory information near and onto the moving body part. This multisensory update might play a role in the control and guidance of the action [START_REF] Brozzoli | Grasping actions remap peripersonal space[END_REF][START_REF] Brozzoli | Action specific remapping of peripersonal space[END_REF][START_REF] Brozzoli | fMRI adaptation reveals a cortical mechanism for the coding of space near the hand[END_REF](Brozzoli et al., , 2012a,b;,b;[START_REF] Makin | Keeping the world at hand: rapid visuomotor processing for hand-object interactions[END_REF][START_REF] Belardinelli | Mental space maps into the future[END_REF][START_REF] Patané | Action planning modulates peripersonal space[END_REF].

Previous studies have so far investigated this dynamic PHS remapping only in case of simple actions, restricted to one component (i.e., grasping an object) and devoid of any ecological aim. However, in the naturalistic conditions of the real world, such aimless and constrained actions are an exceptional occurrence. When we perform voluntary actions, grasping is embedded within a more complex chain of motor acts with a specific aim. Typically, we grasp an object (e.g., a candy), and then lift it to either displace it or eat it, requiring the subject to execute a series of motor steps that ultimately specify the reason why (i.e., the intention) an object has been initially reached and grasped. In these more complex actions, the goal is usually achieved only at the very end of the chain. Thus, in this case, grasping the object is not the final goal of the action (i.e., to hold the candy), but a means to an end (i.e., to eat the candy).

In the present study, we used the version of the cross-modal congruency task as modified by [START_REF] Brozzoli | Grasping actions remap peripersonal space[END_REF] to investigate visuo-tactile interactions during the execution of a relatively complex voluntary action chain, composed by an initial reach to grasp step, followed by a bring to the mouth step. The first aim was to explore the timing of PHS remapping (as measured by modulations of the CCE) during the execution of such complex action chains. As previously shown with a simpler one-step action [START_REF] Brozzoli | Grasping actions remap peripersonal space[END_REF][START_REF] Brozzoli | Action specific remapping of peripersonal space[END_REF][START_REF] Patané | Action planning modulates peripersonal space[END_REF], an increase of the CCE might take place already at the beginning of the action, when the whole action is planned and started. However, according to the view that the PHS plays a role in supporting voluntary hand actions, we also anticipated that in the case of complex chains of motor acts consisting of multiple "steps, " the update of visuo-tactile interactions might be tuned to the final aim. Therefore, the multisensory effect (i.e., an increase of the CCE) might either appear in each step, or shift to a later phase of action execution, for instance taking place only once the first sub-movement toward the object is completed.

In this case, to be functional to guide the hand fulfilling the main action aim (i.e., bring the object to the mouth), an updating of the visuo-tactile interactions might occur after the hand has grasped the object to be further displaced. The two alternatives are not mutually exclusive, and two moments of the action may indeed update visuo-tactile interactions: action planning [START_REF] Brozzoli | Grasping actions remap peripersonal space[END_REF][START_REF] Patané | Action planning modulates peripersonal space[END_REF] and later action stages, when additional update of the multisensory information would be functional to achieve the final goal.

The second aim was to investigate whether the plausibility of an action (i.e., bringing to the mouth a piece of food that potentially could/could not enter the mouth) may affect the remapping of the PHS. Indeed, if remapping occurs when approaching the final goal of the action, it is possible to hypothesize that the plausibility of the goal achievement might induce different modulations of visuo-tactile interactions.

Finally, we aimed to explore whether two similar actions differing only in their plausibility present similar or different kinematic profiles. Previous studies reported that, when performing complex actions constituted by a sequence of motor acts, the kinematics of the initial phase is affected by the presence and the type of the subsequent one (e.g., [START_REF] Marteniuk | Constraints on human arm movement trajectories[END_REF][START_REF] Gentilucci | Planning an action[END_REF][START_REF] Cohen | Where grasps are made reveals how grasps are planned: generation and recall of motor plans[END_REF][START_REF] Ansuini | Effects of end-goal on hand shaping[END_REF][START_REF] Ansuini | An object for an action, the same object for other actions: effects on hand shaping[END_REF][START_REF] Schuboe | Subsequent actions influence motor control parameters of a current grasping action[END_REF][START_REF] Naish | To eat or not to eat? Kinematics and muscle activity of reach-tograsp movements are influenced by the action goal, but observers do not detect these differences[END_REF]. In other words, the kinematics of a grasping movement toward the same pen will be different whether I want to write or put the pen away. Moreover, familiarity with the to-be-grasped object influences the prior-to-contact grasping kinematics, probably because familiar objects automatically elicit the type of interactions that we habitually have with them [START_REF] Gentilucci | Object motor representation and reaching-grasping control[END_REF]see also De Stefani et al., 2012). In daily life, grasping a piece of food is frequently followed by the motor act of bringing it to the mouth, and it has been suggested that, at least in monkeys, viewing an eatable object may automatically activate the motor chain associated with eating [START_REF] Fogassi | Parietal lobe: from action organization to intention understanding[END_REF]. If the plausibility of the action plays a role in influencing the control of the first sub-movement, we could find differences in the kinematics of the two actions already at the initial sub-movement.

To answer all these questions, we compared two hand actions in which the same object (i.e., a cylinder) served as a support for a piece of food (i.e., a candy), and had to be grasped to bring the candy toward the (closed) mouth. Even if the two actions required the execution of the same movements, they differed in their plausibility. In one case, the candy had a horizontal orientation, compatible with the possibility for the candy to enter the mouth (plausible action); in the other, its vertical orientation made it, in principle, impossible for the candy to enter the mouth (implausible action).

Participants were instructed to reach for the cylinder with their right hand, grasp it with a precision grip, and bring the candy that was stuck on it close to the mouth (without contact), their movements' kinematics being recorded for offline analysis. Visuo-tactile interactions were measured on-line, by having participants to decide whether they were touched on their right index finger (up) or thumb (down), while ignoring (either congruent or incongruent) visual distractors displayed on the object [START_REF] Brozzoli | Grasping actions remap peripersonal space[END_REF][START_REF] Brozzoli | Action specific remapping of peripersonal space[END_REF].

MATERIALS AND METHODS

Participants

Fourteen healthy naïve individuals (nine men, mean age: 20.8 ± 1.85 years), with normal or corrected-to-normal vision, took part in the study. All participants were right handed and, according to the Inserm Ethics Committee policy in terms of anonymization procedures, gave verbal consent to participate in the study, which was approved by the INSERM Ethics Committee (CEEI/IRB 00003888).

Apparatus

Participants faced a vertical panel holding a wooden cylinder (7 cm height, 1.7 cm diameter), vertically aligned with their mid-sagittal plane and placed at eye level at a distance of 56 cm from the right hand starting position (see below). A 2-mm thin rod, orthogonally protruding by 6 cm from the center of the cylinder, served as a support for a candy (3.5 cm long, and without the wrapper, see Figure 1). When rotated vertically (i.e., aligned with the cylinder), the candy orientation would make it in principle impossible to enter the average participant's max opening of the mouth (implausible action). Instead, when rotated horizontally, the candy size would fit the mouth opening, thus being potentially eatable by the participant (plausible action). Two LEDs, embedded in the cylinder at 1 cm from each extremity, were used to present visual distractor stimuli, consisting of a single flash (200 ms) delivered from either the upper or the bottom LED.

Procedure

Participants sat at a table in front of the setup, with the thumb and the index finger of each hand laying, in a closed pinchgrip posture, on two switches fixed to the table, one on each side, and with their right foot pressing onto two pedals, one under the heel and the other under the toes. They were instructed to maintain fixation on the candy throughout the entire experimental session, and to never open the mouth. On each trial, a supra-threshold electro-cutaneous stimulus was delivered on either the index finger (up) or the thumb (down) of participant's right hand. The stimulus was a square wave pulse (100 μs, 400 V) released by constant-current stimulators (ISO-Flex, AMPI, Israel) through self-adhesive surface electrodes (700 15-k, Neuroline, Ambu). Synchronous with the tactile stimulation onset, a visual distractor could be presented from either the upper or the bottom LED of the cylinder, thus being spatially congruent or incongruent with respect to the position of the tactile stimulation.

Participants had to judge the location of the tactile stimulus (i.e., up: index, or down: thumb) as fast as possible, while ignoring the visual distractor, by lifting the heel for thumb stimulation, and the toes for index stimulation. Visual-tactile stimulations were given at different time intervals during the motor task, consisting in two main sub-movements: (1) reaching to grasp the cylinder (i.e., the candy's support) along its vertical axis with the index and thumb (precision grip) and (2) bringing the candy close to their mouth (without touching it). During the intertrial interval, participants repositioned the cylinder and returned their hand to the starting position, waiting for the warning sound that announced the upcoming new trial. Importantly, the cylinder was always vertically oriented, irrespective of the (vertical or horizontal) orientation of the candy, thus imposing similar movement requirements to be grasped. Participants were instructed to execute the action "as naturally as possible" with their right hand. The spatial position of the hand was recorded on line by means of an Optotrak 3,020 system (Northern Digital Inc., sampling at 100 Hz, 0.01-mm 3D resolution at 2.25 m distance). Infra-red emitting diodes (IREDs) placed on the lateral part of the nail of thumb and index finger, and on the interior part of the wrist at the styloid process level [START_REF] Jeannerod | Mechanisms of visuomotor coordination: a study in normal and brain-damaged subjects[END_REF], were used to record kinematics parameters.

Each trial started with an auditory warning signal followed, after a variable delay (randomized between 1,700-1900 ms), by a second auditory cue which served as a go signal for the motor task. In each trial, the visuo-tactile stimulation was randomly delivered in different phases of the two sub-movements, corresponding to one of five possible timings: (1) before movement started, randomly after 800-1,000 ms from the warning signal, and 700 ms before the go signal (Static condition);

(2) during action planning, 200 ms after the go signal (Planning condition); (3) during first sub-movement execution, 200 ms after the movement onset (as determined by start switch release (Execution condition); (4) during object gripping (Grasping-end condition), when index and thumb were stationary on the object and the grip was stable (i.e., absence of any acceleration for at least 100 ms and maximum grip aperture of 7 cm ± 5 mm); and (5) during second sub-movement execution, when the object was moved (by at least 3 mm) toward the mouth (Bringing condition).

Overall, the experiment consisted of 16 trials (eight congruent, eight incongruent) for each of the five stimulation timings, and for each orientation of the candy (vertical or horizontal), thus yielding a total of 160 trials.

Statistical Analyses

Multisensory Remapping of Peri-hand Space

Reaction times (RTs) to the tactile stimulation were log-transformed, in order to normalize their distribution, and then converted to Z-scores for each participant, to account for individual differences. As in previous studies, the (hereafter) CCE, calculated as the difference between RTs in incongruent and congruent trials, was used as an index of the amount of multisensory interference between tactile stimuli and visual distractors. A repeated measures analysis of variance (ANOVA) with the factors Candy Orientation (horizontal, vertical) and Phase (before, planning, execution, grasping-end, bringing) was conducted on the CCE scores.

Horizontal Vertical (implausible action) (plausible action)

Tactile stimuli

Visual stimuli Candy

FIGURE 1 | Experimental setup and task. Participants sat in front of a target object, which they had to grasp with a precision grip (i.e., with index and thumb) and bring close to the mouth. A candy was fixed on the target object, either oriented horizontally, thus potentially capable of entering the mouth (plausible action) or vertically, in an orientation that would make impossible for the candy to enter the mouth (implausible action). At the same time, they had to discriminate the position (i.e., up or down) of an electro-cutaneous stimulus (gray circles) delivered up (index finger) or down (thumb), while a concurrent task-irrelevant visual distractor (yellow circles) could be displayed on either the same (congruent) or different (incongruent) position from one of two LEDs embedded into the cylinder's extremities.

Grasping Kinematics

The following parameters (as defined in previous work by [START_REF] Brozzoli | Grasping actions remap peripersonal space[END_REF] were analyzed: acceleration, velocity, deceleration peaks, and their relative latencies since movement onset, movement reaction times (i.e., the temporal delay between the go signal and motion onset), and movement duration (from the beginning of hand movement up to the moment in which the object has reached the minimal distance from the mouth, before being moved back to its support). For each parameter, we ran an ANOVA with the factors Candy Orientation (horizontal vs. vertical), Phase (static, planning, execution, grasping-end, bringing), and Stimulation (congruent vs. incongruent).

RESULTS

Multisensory Remapping of Peri-hand Space

Overall, participants were faster in responding to congruent (mean ± standard deviation = 0.01 ± 0.8) than incongruent trials (0.38 ± 0.8, t 13 = 4.19, p = 0.001), thus replicating previous findings on the cross-modal congruency effect (CCE, see Spence et al., 2004a,b;[START_REF] Brozzoli | Grasping actions remap peripersonal space[END_REF][START_REF] Brozzoli | Action specific remapping of peripersonal space[END_REF]. The ANOVA on the CCE values revealed a significant Candy Orientation by Phase interaction (F 4,52 = 2.63, p = 0.044, η 2 = 0.086). Duncan post hoc tests showed that the CCE was modulated by the phase of the action only when the candy was oriented horizontally, that is, when the action was plausible. In particular, for the plausible action, the CCE was significantly stronger during the Grasping-end condition (0.72 ± 0.72) as compared to the Static (0.01 ± 0.38, p = 0.006), Execution (0.31 ± 0.35, p = 0.049), and Bringing (0.17 ± 0.55, p = 0.01) phases of the action (Figure 2). The Grasping-end condition for the horizontal orientation differed also from the Static (0.16 ± 0.47, p = 0.009) and Grasping-end (0.13 ± 0.78, p = 0.007) phases of the action performed when the candy was oriented vertically (Figure 2). All other comparisons and main effects were not significant (all p > 0.05). For completeness, absolute reaction times for the different phases of the two actions are reported in Table 1.

To assess whether our design had enough statistical power, we ran a post hoc power analysis, with the effect size we observed for the interaction (partial η 2 = 0.17), the sample size of 14 participants, and alpha set at 0.05. The analysis revealed a power of 0.94, which is above the recommended 0.8 level [START_REF] Cohen | Statistical power analysis for the behavioral sciences[END_REF], thus showing that our study had an adequate power.

Grasping Kinematics

The analyses on the kinematics parameters showed that kinematics was influenced by the orientation of the candy. Even if the action required to reach for and grasp its cylindrical support was the same for both candy orientations, participants showed a greater acceleration peak when the candy was oriented horizontally (7,528 mm/s 2 ), than when it was oriented vertically (7,398 mm/s 2 , F 1,13 = 15.38, p = 0.0017, η 2 = 0.017). Moreover, the latency of the acceleration peak occurred earlier for the horizontal (132.5 ms) than for the vertical orientation (137.2 ms, F 1,13 = 5.27, p = 0.039, η 2 = 0.016). Similarly, the latency of the velocity peak occurred earlier for the horizontal orientation (319 ms), as compared to the vertical one (323 ms, F 1,13 = 8.13, p = 0.014, η 2 = 0.016). In other words, both acceleration and velocity peaks occurred earlier, and the acceleration peak was stronger when the action was plausible (i.e., when the candy was oriented horizontally), than when the action was implausible (see Figure 3). Movement kinematics was also partially modulated Bar plots (with SEM) show the modulation of the cross-modal congruency effect (CCE) as a function of action phase and object orientation. The CCE significantly increased during the Grasping-end phase only when the action was plausible (i.e., when the candy was oriented horizontally). by the phase of the action at which the stimulation was delivered.

The acceleration peak was more important in Planning than in any other condition, irrespective of the candy's orientation (phase: F 4,52 = 3.28, p = 0.018, η 2 = 0.014, all p's < 0.03). The analysis run on the movement reaction times revealed a significant main effect of Phase (F 4,52 = 10.94, p < 0.001, η 2 = 0.3), indicating that participants were faster in starting the action in the Static phase, as compared to any other action phases (all p's < 0.001). No modulations were found in the other parameters (all p's > 0.1) 1 .

DISCUSSION

Previous evidence has shown that, when grasping an object, the visuo-tactile interactions occurring between target object and grasping hand are updated as to remap the target location closer to the hand, well before the hand gets in contact with the object [START_REF] Brozzoli | Grasping actions remap peripersonal space[END_REF][START_REF] Brozzoli | Action specific remapping of peripersonal space[END_REF]. Such a spatial remapping of PHS, initially reported to occur at the early phases of action execution [START_REF] Brozzoli | Grasping actions remap peripersonal space[END_REF][START_REF] Brozzoli | Action specific remapping of peripersonal space[END_REF][START_REF] Belardinelli | Mental space maps into the future[END_REF], has recently been shown to occur already during the motor planning phase [START_REF] Patané | Action planning modulates peripersonal space[END_REF]. The PHS remapping continues being updated during the subsequent phases of the grasping action as the hand approaches the target, thus revealing its highly dynamic, time-sensitive nature [START_REF] Patané | Action planning modulates peripersonal space[END_REF].

The fact that the update of the multisensory interactions leads, rather than follows, movement execution suggests that the representation of the peripersonal space might play a crucial role in guiding the execution of voluntary goal-directed actions, such as grasping [START_REF] Brozzoli | Grasping actions remap peripersonal space[END_REF][START_REF] Brozzoli | Action specific remapping of peripersonal space[END_REF][START_REF] Brozzoli | Peripersonal space: a multisensory interface for body objects interactions[END_REF][START_REF] Brozzoli | Multisensory representation of the space near the hand: from perception to action and interindividual interactions[END_REF][START_REF] Makin | Keeping the world at hand: rapid visuomotor processing for hand-object interactions[END_REF].

In the present study, we assessed the modulation of visuotactile interactions during the execution of more complex actions, consisting of a sequence of motor acts aimed at 1 In our experiment, participants were asked to perform two tasks (i.e., perceptual and motor) at the same time. To additionally explore the effect of performing a second motor task on participants' overall reaction times (RTs) in the different phases of the action, we ran an ANOVA on the absolute RTs (log-transformed to normalize their distribution) with the within-subject factors Phase and Candy orientation. Results revealed a significant main effect of phase (F 4,56 = 11.67, p < 0.01), and post hoc test showed that RTs were significantly slower in the planning and execution phases as compared to the grasping-end and bringing phases (all p's < 0.02). Thus, planning and starting an action overall slowed down the RTs to the perceptual task. However, faster RTs in the grasping-end condition cannot explain the effect we found in the CCE. First of all, although RTs were faster also in the bringing phase as compared to planning and execution, we do not see a modulation of the CCE in the bringing phase analogous to that found in the grasping-end phase, despite the fact that also in this phase the participant is holding the object, and he is still executing the movement. Second, the effect we found on the CCE is specific for the plausible action only. Thus, if the effect we found was driven by the mere presence of a simultaneous motor task, we should have found a similar CCE modulation for both plausible and implausible actions. Similarly, if kinematics parameters were reflecting the priority trade-off between performances in the two tasks (perceptual and motor), we should have found similar effects for the plausible and implausible actions. Indeed, the two actions are equivalent in terms of required movements, and thus an effect of having a dual task rather than one should lead to analogous kinematics parameters for both actions. Instead, we found that kinematics was affected by the candy orientation only.

grasping an object holding a piece of food (a candy), and bringing it to the mouth. We showed that action goal and plausibility influence PHS representation. Indeed, the visual information (on the object) interacts with the tactile stimuli (on the hand) more strongly when the hand has already reached the object (as compared to the previous action phases). Crucially, the effect is present only when the action is plausible, i.e., when the candy is oriented horizontally, thus making the action goal potentially achievable in the subsequent motor component of the action (bring-to-themouth). Previous research has shown that the multisensory interference is maximal when the participant is holding the object containing the visual distractors (and thus when the tactile and visual stimuli are spatially adjacent) (e.g., Spence et al., 2004a). Here, multisensory interference upon grasping increased only when the action was plausible, thus ruling out the possibility that the effect we report is driven by the mere spatial proximity between the two stimuli. In fact, were this the case, the increase in multisensory interference observed while the participant is holding the object should take place for both conditions (i.e., plausible and implausible). Instead, it was observed selectively in the plausible condition. Yet, we cannot exclude that other variables might have partially contributed to the observed effect. Indeed, while the to-begrasped support for the candy was always vertically oriented (so that the movement required to grasp it would be comparable between the plausible and implausible actions), the orientation of the candy could be either parallel (implausible action) or perpendicular (plausible action) to the support. It is thus possible that different orientations of the candy with respect to its support may introduce perceptual differences between the two conditions. Overall, given that the CCE was comparable between the two conditions in most action phases, potential perceptual differences between the two conditions do not seem to affect task performance.

These findings suggest that the modulation of visuo-tactile interactions triggered by action planning may vary in time depending upon the final aim and plausibility of the action itself. Here, visuo-tactile interactions were not updated at early phases of the action, as it happens with simpler grasping actions [START_REF] Brozzoli | Grasping actions remap peripersonal space[END_REF][START_REF] Brozzoli | Action specific remapping of peripersonal space[END_REF][START_REF] Patané | Action planning modulates peripersonal space[END_REF]. Instead, such modulation occurs later in time, when the hand holds the object and is about to initiate the second action step. Moreover, movement kinematics was partially affected by the plausibility of the action. Both acceleration and velocity peaks occurred earlier, and the acceleration peak was greater when the candy was oriented horizontally (plausible action), than when it was oriented vertically (implausible action). In a sequence of motor acts aimed at reaching for an object to manipulate it, the aim of the motor steps following the grasping phase affects the kinematics of the initial stages of the action (e.g., [START_REF] Marteniuk | Constraints on human arm movement trajectories[END_REF][START_REF] Gentilucci | Planning an action[END_REF][START_REF] Cohen | Where grasps are made reveals how grasps are planned: generation and recall of motor plans[END_REF][START_REF] Ansuini | Effects of end-goal on hand shaping[END_REF][START_REF] Ansuini | An object for an action, the same object for other actions: effects on hand shaping[END_REF][START_REF] Schuboe | Subsequent actions influence motor control parameters of a current grasping action[END_REF][START_REF] Naish | To eat or not to eat? Kinematics and muscle activity of reach-tograsp movements are influenced by the action goal, but observers do not detect these differences[END_REF]. In particular, reaching movements are generally slower when the post-grasp movements require greater precision (e.g., [START_REF] Ansuini | Effects of end-goal on hand shaping[END_REF][START_REF] Ansuini | An object for an action, the same object for other actions: effects on hand shaping[END_REF][START_REF] Schuboe | Subsequent actions influence motor control parameters of a current grasping action[END_REF][START_REF] Naish | To eat or not to eat? Kinematics and muscle activity of reach-tograsp movements are influenced by the action goal, but observers do not detect these differences[END_REF][START_REF] Quinlan | Direct comparisons of hand and mouth kinematics during grasping, feeding and fork-feeding actions[END_REF]. For instance, an earlier acceleration peak takes place in the reaching phase of a reach-to-grasp action when the grasped object is then brought close to the mouth as compared to when it is placed in another location [START_REF] Naish | To eat or not to eat? Kinematics and muscle activity of reach-tograsp movements are influenced by the action goal, but observers do not detect these differences[END_REF]. Such differences in the kinematics reflect the fact that the action of bringing an object to the mouth requires greater accuracy and precision than the action of placing it somewhere else. Our study confirms and extends these findings, by suggesting that the prior-to-contact grasping kinematics is affected not only by the goal of an action, but also by its plausibility.

In conclusion, these results expand our knowledge regarding the link between multisensory processes dedicated to encode target objects within reaching space and the sensorimotor computations required to plan and execute a complex chain of actions. Previous research had shown that voluntary objectoriented actions induce an on-line, continuous remapping of the peri-hand space, speaking in favor of a role for peri-hand space in the motor control and guidance of actions [START_REF] Brozzoli | Grasping actions remap peripersonal space[END_REF][START_REF] Brozzoli | Action specific remapping of peripersonal space[END_REF][START_REF] Belardinelli | Mental space maps into the future[END_REF][START_REF] Patané | Action planning modulates peripersonal space[END_REF].

In the present study, we extend this previous finding by showing that the remapping of the peripersonal space is driven by the final aim of the action, and by its plausibility.

ETHICS STATEMENT

This study was carried out in accordance with the recommendations of the INSERM Ethics Committee (CEEI/ IRB 00003888). According to such recommendations, all participants gave verbal consent to participate in the study, which was approved by the INSERM Ethics Committee (CEEI/ IRB 00003888).

Frontiers

  in Psychology | www.frontiersin.org 2 July 2019 | Volume 10 | Article 1681

Frontiers

Frontiers

  in Psychology | www.frontiersin.org 4 July 2019 | Volume 10 | Article 1681

Frontiers

FIGURE 2 |

 2 FIGURE 2 | Modulation of visuo-tactile processing during action execution. Bar plots (with SEM) show the modulation of the cross-modal congruency effect (CCE) as a function of action phase and object orientation. The CCE significantly increased during the Grasping-end phase only when the action was plausible (i.e., when the candy was oriented horizontally).

FIGURE 3 |

 3 FIGURE 3 | Means and standard errors of the parameters of the reaching component differing between plausible and implausible actions. Asterisks denote statistically significant differences between the actions.

Frontiers

  in Psychology | www.frontiersin.org 7 July 2019 | Volume 10 | Article 1681

TABLE 1 |

 1 Absolute reaction times (mean ± standard errors of the mean, in ms) for the different phases of the plausible (horizontal orientation) and implausible (vertical orientation) actions.

	Action phase		Plausible action	Implausible action
	Static		514 ± 18.6	517 ± 21.3
	Planning		541 ± 25.7	540 ± 25.5
	Execution		542 ± 25.7	526 ± 26.2
	Grasping end		477 ± 27.8	479 ± 27.8
	Bringing		476 ± 28.2	480 ± 21.2
	9000	160
				Plausible
	8000	*		Implausible
	7000
	mm/s 2	ms
	6000
	5000
	4000
	Acceleration	Acceleration Peak
			(latency)

ACKNOWLEDGMENTS

We are grateful to Nunzia Franceschini for helping with data collection and data processing, and Olivier Sillan for technical support.

FUNDING This work was supported by the following grants: IHU CeSaMe ANR-10-IBHU-0003, FRC (Fédération pour la Recherche sur le Cerveau, Neurodon), ANR-16-CE28-0015, and the James S. McDonnell Scholar Award to AF. This work was performed within the framework of the LABEX CORTEX (ANR-11-LABX-0042) of Université de Lyon. IS was supported by the Deutsche Forschungsgemeinschaft (DFG) DIP-Grant ER 542/3-1. LC was supported by the MINDED Program -Marie Skłodowska-Curie grant agreement No 754490. CB was supported by a grant from the Swedish Research Council(2015-01717) and ANR-JC (ANR-16-CE28-0008-01).

AUTHOR CONTRIBUTIONS

AF, CB, and IS designed the experiment. IS and LC analyzed the data. IS, LC, CB, and AF wrote the paper.

Conflict of Interest Statement:

The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.


domain: info math

text:
Nicolas Aragon

Magali Bardet

Loïc Bidoux

Jesús-Javier Chi-Domínguez

Victor Dyseryn

Thibauld Feneuil

Philippe Gaborit

Antoine Joux

Matthieu Rivain

Jean-Pierre Tillich

Adrien Vinçotte

RYDE specifications

Table of Contents 1 Introduction

This document specifies the RYDE digital signature scheme. It is a quantum-resistant signature, based on zero-knowledge proofs, and symmetric functions, such as hash functions. We present a high-level description of the scheme and the MPC-in-the-Head paradigm (it allows to transform MPC protocols in proofs of knowledge) on which the signatures are based. The security of the signature relies on the Rank Syndrome Decoding problem: thanks to the previous process we can transform a proof of knowledge of a witness to a Rank-SD instance [START_REF] Feneuil | Building MPCitH-based Signatures from MQ, MinRank, Rank SD and PKP[END_REF] to obtain a signature scheme. We apply then the Fiat-Shamir transform to obtain signature schemes.

We present a signature scheme, of which we have designed two variants, both based on the transformation of an additive MPC protocol optimized with the hypercube technique [AMGH + 22]. The difference of these variants is the number of parties we use in the underlying MPC protocol: taking less parties increases the size of the signature, but induces a faster one. We refer to the design document [BCDF + 23] for the proofs of the security statements.

Background and notations

To understand the mathematical background to the problem, we begin by recalling a few fundamental definitions and fixing some notations.

Let F q m be the finite field of size q m . We fix a F q -basis B = (b 1 , ..., b m ) of F q m . Let us consider a vector x = (x 1 , ..., x n ) ∈ F n q m . Each coordinate x i can be associated with a vector (x i,1 , ..., x i,m ) ∈ F m q such that

x i = m j=1
x i,j b j .

The matrix M (x) = (x i,j ) (i,j)∈[1,n]×[1,m] is called matrix associated to the vector x.

We then define the following notions:

the rank weight W R (x) of a vector x is defined as the rank of the associated matrix: W R (x) := Rank(M (x)).

the distance between two vectors x and y is then given by d(x, y) := W R (x -y).

the support of a vector x is the linear subspace of F q m generated by its coordinates:

Supp(x) = x 1 , ..., x n .
Now that we have defined the mathematical background, we can define the Rank Syndrome Decoding problem, on which the security of the signature RYDE is based:

Rank Syndrome Decoding problem: Let (n, k, r) positive integers such that k ≤ n. The Rank Syndrome Decoding (Rank-SD) problem with parameters (q, m, n, k, r) is the following one:

Let H, x and y such that:

• H is uniformly sampled from F

(n-k)×k q m

, and H = (I | H ) ∈ F

(n-k)×n q m

• x is uniformly sampled from {x ∈ F n q m , W R (x) ≤ r}

• y = Hx
From the public data (H, y), find x.

In the RYDE signature scheme, the public key is an instance (H, y) of the Rank-SD problem, and the secret key is the corresponding solution x. The principle of the signature is based on a transformation of a proof of knowledge into a non-interactive protocol thanks to the Fiat-Shamir transform [START_REF] Fiat | How to Prove Yourself: Practical Solutions to Identification and Signature Problems[END_REF]. Iterating this process multiple times gives the verifier high assurance that the prover knows x.

The interactive proof relies on a prover which simulates a multiparty computation (MPC) protocol, where each party has a share of the secret witness x. One details here the formalism proposed by [START_REF] Feneuil | Threshold Linear Secret Sharing to the Rescue of MPC-in-the-Head[END_REF]. The sharing of a secret value s into N parties is denoted (s[1], ..., s[N ]), where s[i] is the share of index i for i ∈ [1, N ], and s[J] = (s[i]) i∈J is the subset of shares for J ⊂ [1, N ].

Let F a finite field and an integer ∈ [1, N ]. A ( , N )-threshold Linear Secret Sharing Scheme is a method to share a secret s ∈ F into N shares s[1, N ] = (s[1], ..., s[N ]) ∈ F N such that the secret can be rebuilt from any subset of + 1 shares, while the knowledge of any subset of shares (or less) gives no information on s.

Formally, a ( + 1, N )-threshold LSSS is a pair of algorithms:

Share : F × R → F N Reconstruct J : F → F
where R denotes some randomness space, and Reconstruct J is indexed by a subset J ⊂ [1, N ] of + 1 elements. These algorithms must verify the following properties:

-Correctness: Reconstruct allows to retrieve s if it has any subset of + 1 shares as input;

-Perfect -privacy: The distribution of the outputs of Share on two different secrets are perfectly indistinguishable;

-Linearity: for every v, v ∈ F l , α ∈ F and subset J ⊂ [1, N ] of + 1 elements:

Reconstruct J (αv + v ) = αReconstruct J (v) + Reconstruct J (v )
We present below the additive secret sharing, that we use in the signature scheme:

Additive secret sharing: An additive secret sharing over a finite field F is an (N, N )-threshold LSSS where R = F N -1 . The Share algorithm is defined as:

Share : (s, (r 1 , ..., r N -1 )) → s[1, N ] = r 1 , ..., r N -1 , s - N -1 i=1 r i
The Reconstruct [1,N ] outputs the sum of all the shares.

3 High level description of the signature scheme

As mentioned below, the security of the signature scheme relies on the hardness to solve the Rank-SD problem. The instance (H, y) is the public key of the signature, and the associated witness x is the secret key. In order to sign a message, we must:

-Build an interactive zero-knowledge proof of the knowledge of x;

-Use the Fiat-Shamir transform to obtain a non-interactive proof

The proof relies on an MPC protocol, and we use the MPC-in-the-Head paradigm to transform it in a zero-knowledge proof.

MPC protocol

A multi-party computation protocol is an interactive protocol involving several parties whose objective is to jointly compute a function f on the shares x[•] they received at the begin of the protocol, so that they obtained the shares f (x)[•] at the end of the protocol. At each step, the parties can perform one of the following actions:

-Receiving elements: it can be randomness sent by a random oracle, or the share of a hint which depends on the witness ω and the previous elements sent;

-Computing: since the sharing is linear, the parties can perform linear transformations on their shares;

-Broadcasting: it is sometimes necessary to open some shared values (which give no information about the witness ω) to execute the protocol.

Due to application to zero-knowledge proofs that we will do below, we suppose here that all parties are honest: they compute and share only correct values.

The interactive proof relies on the application of the the MPC-in-the-Head (MPCitH) paradigm [START_REF] Ishai | Zero-Knowledge from Secure Multiparty Computation[END_REF]: the prover simulates a MPC protocol, where each party has a share of the secret witness x. Informally, an MPC protocol takes place as follows:

each party takes a share of the witness;

they jointly compute (some operations are locally calculated, others are performed together) a Boolean value indicating whether x is right the witness associated to (H, y) (in other words, the MPC protocol compute the function f which verifies that x is the correct solution of the instance (H, y)); -In the case of the additive sharing, the view of all parties except one gives no information about x.

We formally describe the MPC protocol [START_REF] Feneuil | Building MPCitH-based Signatures from MQ, MinRank, Rank SD and PKP[END_REF] used for the RYDE scheme in Figure 1. Compared to its original version, the protocol of Figure 1 integrates an optimization: it relies on the fact that L(1) = 0 to save one field element in the communication cost. We refer to [BCDF + 23] for the proof of correctness and the false positive rate.

Public values. An instance of a Rank-SD problem:

H = (I H ) ∈ F (n-k)×n q m
and y ∈ F n-k q m . Inputs. Each party takes a share of x B [•] where x ∈ F n q m . Let U a Fq-linear subspace of F q m of dimension r which contains x 1 , . . . , xn and has for annihilator polynomial L = u∈U (X -u). Each party takes a share of the following sharing as inputs :

L[•] = r-1 i=1 β i [•](X q i -X) + (X q r -X), a[•] where a is uniformly sampled from F r q m•η and c[•] such that c = -β, a .
MPC Protocol:

1. The parties sample uniformly random: (γ 1 , ..., γn, ε)

$ ←-F n+1 q m•η . 2. The parties locally compute x A [•] = y -H x B [•] and x[•] = (x A [•] || x B [•]).

The parties locally compute z

[•] = -n j=1 γ j (x j [•] q r -x j [•]).
4. The parties locally compute for all k from 1 to r -1 :

ω k [•] = n j=1 γ j (x j [•] q k -x j [•]). 5. The parties locally compute α[•] = ε • ω[•] + a[•].

6.

The parties open α.

The parties locally compute

v[•] = ε • z[•] -α, β[•] -c[•].

The parties open v.

9. The parties output ACCEPT if v = 0, and reject otherwise.

Application of the MPCitH paradigm

The MPC-in-the-Head paradigm, introduced by [START_REF] Ishai | Zero-Knowledge from Secure Multiparty Computation[END_REF], is a framework enabling to convert an MPC protocol into a zero-knowledge proof. The RYDE signature scheme has two trade-offs, induced by the same proof of knowledge. Both use an additive MPC protocol turned into zero-knowledge proof thanks to the MPC-in-the-Head paradigm, but with different numbers of parties.

We start by presenting the main idea of the hypercube optimization [AMGH + 22]: splitting a secret in N = 2 D additive shares, and arranging them in a geometrical structure. Let us consider an hypercube of dimension D, each dimension having 2 slots. These 2 D shares are called "leafs". Since we use an additive secret sharing, one can intertwine several executions where each party (what we will call a "main party") can be the sum of a subset of leafs, such that these subsets form a partition of the leafs. The main parties' shares of a secret s are denoted ŝ. We build here D intertwined protocols, and each of them has 2 main parties (an interested reader can find more details in [BCDF + 23]).

The proof of knowledge in the additive case works as follows:

the prover builds the inputs of the MPC protocol, i.e, he generates the states of N parties;

he then commits the states of the parties, and receives a first challenge corresponding to some random values. This challenge consists in the random values (γ 1 , ..., γ n , ε) to be used in the MPC protocol;

the prover runs one MPC protocol per dimension of hypercube. For each of the D dimensions, he builds two main parties, each of them being the sum of the leafs whose has the same coordinate for this dimension. The prover hashes the shares of α and v;

thanks to this challenge, he simulates the MPC protocol on the main parties, and hashes the results of the computations;

he receives a second challenge, which is a subset of N -1 parties, and reveals their views. (In practice, he receives only a subset of 1 party, and reveals the views of every party except this one). He also reveals one specific share of data for the party whose views are not revealed;

the verifier can verify that the computation of the MPC protocol was done honestly.

From the interactive proof of knowledge, we can easily build a non-interactive proof/signature, using the Fiat-Shamir transform [START_REF] Fiat | How to Prove Yourself: Practical Solutions to Identification and Signature Problems[END_REF].

Detailed algorithmic description

This section is dedicated to a low-level algorithmic description of the three algorithms of our scheme: RYDE_Keygen, RYDE_Sign and RYDE_Verify. Before that, we introduce low-level notation in Section 4.1, and detail subroutines of our main algorithmis in Sections 4.2-4.8.

The MPC protocol from Figure 1 is characterized by a degree η of extension of F q m in which the computations are done. The signature size is minimized for η = 1, as presented in Section 5. The rest of this section assumes η = 1 for simplification purposes.

Algorithmic notation

For an integer x ∈ [0, 2 D -1] and δ ∈ [D], we denote bit(x, δ) the δ-th least significant bit of the binary repesentation of x. For example, let x = 35 = 100011 2 , then bit(x, 2) = 1 and bit(x, 3) = 0. Field elements, vectors and matrices:

Indexes: i [1, N ] Index of
H F (n-k)×n q m Public matrix. x F n q m
Secret vector of small rank weight.

β F r-1 q m
Annulator polynomial of the support of x. y

F n-k q m Public syndrome. a F r-1 q m
Vector used in the MPC rank checking protocol.

w F r-1 q m
Vector used in the MPC rank checking protocol.

γ F n q m
Vector from the first challenge. c Fqm Element used in the MPC rank checking protocol. z Fqm Element used in the MPC rank checking protocol.

Fqm

Element from the first challenge.

The leaf shares of the above vectors and elements are noted with an array index i (for example a[i]).

The main shares of the above vectors and elements are noted with an hat and an array index δ (for example â[δ]).

Table 1: Description of low level notation used in our scheme

Operations on finite field elements

Representation of finite field elements

In this document we always have F q m = F 2 m . We define F q m as F 2 [X]/ P where P is a sparse irreducible polynomial of degree m. Table 2 describes the chosen polynomials.

m P 31 X 31 + X 3 + 1 37 X 37 + X 6 + X 4 + X + 1 43 X 43 + X 6 + X 4 + X 3 + 1 Table 2: Polynomials used to define the field F q m .
Elements of F q m are represented in the polynomial basis. An array of l = m 8 bytes [b 1 , . . . , b l ] is used to store an element u of F q m . Each byte b i can be converted into a bitstring β 1 , . . . , β 8 where

β j = (b i >> j) & 0x1.
Let β 1 , . . . , β 8l be the bitstring stored in the byte array [b 1 , . . . , b l ], then:

u = m i=1 β i X i-1

Converting a byte stream into an element of F q m

When sampling randomness, we want to convert a byte stream into elements of F q m . Sampling an element u is done is the following way:

-Obtain l = m 8 bytes from the stream. Let β 1 , . . . , β 8l be the obtained bitstring.

-

Set u = m i=1 β i X i-1 .
To sample an array of F q m elements of length n we simply repeat this process n times, requiring n× m 8 bytes b of randomness. We refer to this process as FqmArrayFromBytes(b). To convert an array y of n elements in F q m into a byte array, we simply revert this process, writing the values of the bits β 1 , . . . , β 8l for each element of F q m and repeating the process n times. We refer to this process as FqmArrayToBytes(y).

Compacting arrays of F q m elements

In order to obtain a more compact representation (for values that will be sent over the network for example), we want to use a more compact representation for arrays of F q m elements.

Let y be an array of n F q m elements. Instead of representing each F q m element in a fixed number of bytes, we concatenate the n bitstring obtained from the y i into a bitstring of bytes instead of n × m 8 for representing the whole array.

We refer to these subroutines as FqmArrayToString(y) and FqmArrayFromString(str) respectively.

Computing the weight of an array of F q m elements The following algorithm computes the rank weight of an F q m -vector.

Algorithm 1 GetRankWeight

Input: A vector x ∈ F n q m of length n Output: Its rank weight r ∈ N 1: Initialize a new zero matrix M ∈ F m×n q . 2: for j ∈ [n] do 3:
Fill the j-th column of M with the coefficients of x[j] seen as a polynomial.

x

[j] = m i=1 M [i][j]X i-1 4: return Rank(M )

Computing an annihilator polynomial

We use the procedure from [Loi07, Ch. 3, Sec. 2.4] to compute the coefficients of a linearized polynomial given its roots.

Algorithm 2 ComputeAnnihilatorPolynomial

Input: Support supp ∈ F r q m of rank r Output: Annihilator polynomial P ∈ Fqm [X] such that for all u ∈ supp , P (u) = 0

P1 = X q -supp[0] q-1 for i from 1 to r do T = P q i eval = Pi(supp[i]) Pi+1 = eval q-1 Pi + T return Pr+1

Randomness generators and hash functions

-RandomBytes( ) is instanciated using the NIST provided randombytes function, it returns bytes from system entropy;

-PRG is a psuedorandom generator instanciated using SHAKE-128 for security category 1 and SHAKE-256 otherwise. It offers two invokable functions:

• PRG.Init(seed) initializes the internal state of the generator with a seed,

• PRG.GetBytes( ) outputs bytes from the generator and updates its internal state.

-Hash functions are instanciated using SHA3-256, SHA3-384 or SHA3-512 for security categories 1, 3 and 5 respectively.

Sampling routines

The routines presented in this subsection sample from a seed some set of elements needed in the scheme.

Algorithm 3 SampleFqmVector

Input: Length n, a seed seed Output: x ∈ F n q m PRG.Init(seed) xbytes = PRG.GetBytes(n × m 8 ) x = FqmArrayFromBytes(xbytes) return x Algorithm 4 SampleFqmMatrix Input: Dimensions k × n, a seed seed Output: A ∈ F k×n q m PRG.Init(seed) for i ∈ [k] do xbytes = PRG.GetBytes(n × m 8 ) Ai, * = FqmArrayFromBytes(xbytes) return A
The following algorithm samples a support of rank weight r, represented by a basis supp ∈ F r q m . The support always contain the element 1 ∈ F q m , as explained in Section 3. The algorithm further samples a vector x of support supp.

Algorithm 5 SampleFqmVectorAndSupport

Input: Length n, rank weight r, a seed seed Output: x ∈ F n q m of rank weight r and its support supp ∈ F r q m 1: PRG.Init(seed)

2: r_bytes = r m 8 3: repeat 4: supp[1] = 1
The support always contains one 5:

supp[2, r] = FqmArrayFromBytes(PRG.GetBytes(r_bytes)) Sampling the rest of the support 6: until GetRankWeight(supp) = r 7: x = (0, . . . , 0)

Initialize x with zeros 8: repeat 9:

rand =PRG.GetBytes( nr 8 ) 10:

Convert rand into a bitstring randbits of length 8 nr Algorithm 7 SampleShares

Input: A seed seed Output: A set of shares (xB, β, a, c) ∈ F k q m × F r-1 q m × F r-1 q m × Fqm PRG.Init(seed) xbytes = PRG.GetBytes(k × m 8 ) xB = FqmArrayFromBytes(xbytes) bbytes = PRG.GetBytes((r -1) × m 8 ) β = FqmArrayFromBytes(bbytes) abytes = PRG.GetBytes((r -1) × m 8 ) a = FqmArrayFromBytes(abytes) cbytes = PRG.GetBytes(1 × m 8 ) c = FqmArrayFromBytes(cbytes)[0] return x Algorithm 8 SampleFirstChallenge Input: A seed seed Output: A set of first challenges (γ (e) , (e) ) e∈[τ ] ∈ (F n q m × Fqm ) τ PRG.Init(seed) for e ∈ [τ ] do xbytes = PRG.GetBytes((n + 1) × m 8 ) γ (e) = FqmArrayFromBytes(xbytes[..n]) (e) = FqmArrayFromBytes(xbytes[n+1])[0] return (γ (e) , (e) ) e∈[τ ]
Algorithm 9 SampleSecondChallenge

Input: A seed seed Output: A set of second challenges (i * (e) ) e∈[τ ] ∈ [N ] τ PRG.Init(seed) for e ∈ [τ ] do i * (e) = PRG.GetBytes(1) mod N return (i * (e) ) e∈[τ ] 4.5 MPC routines Algorithm 10 MPC-RSD.ComputeAlpha Input: -A set of shares (x, a) -A protocol challenge (γj) j∈[1,n] , Output: α 1: for s ∈ [1, r -1] do 2: w k = n j=1 γj(x q k j -xj) 3: α = • w + a 4: return α Algorithm 11 MPC-RSD.Exec Input: -A set of main shares ( xB[δ], β[δ], â[δ], ĉ[δ]) δ∈[D] -A protocol challenge (γj) j∈[1,n] ,
-A full value α -The public matrix H and the public syndrome y

Output: ( α[δ], v[δ]) δ∈[D] 1: for δ ∈ [D] do 2: xA[δ] = y -H xB[δ] 3: x[δ] = ( xA[δ] || xB[δ]) 4: α[δ] = MPC-RSD.ComputeAlpha( x[δ], â[δ], (γj) j∈[1,n] , ) 5: ẑ[δ] = -n j=1 γj( xj[δ] q r -xj[δ]) 6: v[δ] = • ẑ[δ] -α, β[δ] -ĉ[δ] 7: return ( α[δ], v[δ]) δ∈[D]

Hypercube routines

The N = 2 D leaf shares are arranged on a D-dimensional hypercube of side length 2. An index i ∈ [N ] is positioned according to the binary representation of i -1

∈ [0, 2 D -1].
The δ-th coordinate of i in the hypercube is the δ-th least significant bit of the binary repesentation of i -1, i.e. bit(i -1, δ).

A main share of index δ is the sum of all leaf shares in the hyperface of the hypercube comprising all vertices whose δ-th coordinate is zero.

Algorithm 12 Hypercube.MainShares-Compute

Input: A set of leaf shares (xB[i], β[i], a[i], c[i]) i∈[N ] where N = 2 D Output: A set of main shares ( xB[δ], β[δ], â[δ], ĉ[δ]) δ∈[D] 1: for δ ∈ [D] do 2: xB[δ] = i∈[N ] bit(i-1,δ)=0 xB[i] 3: β[δ] = i∈[N ] bit(i-1,δ)=0 β[i] 4: â[δ] = i∈[N ] bit(i-1,δ)=0 a[i] 5: ĉ[δ] = i∈[N ] bit(i-1,δ)=0 c[i]
Algorithm 13 Hypercube.MainAlphaAndV-Compute

Input: A set of leaf shares (α[i], v[i]) i∈[N ] where N = 2 D Output: A set of main shares ( α[δ], v[δ]) δ∈[D] 1: for δ ∈ [D] do 2: α[δ] = i∈[N ] bit(i-1,δ)=0 α[i] 3: v[δ] = i∈[N ] bit(i-1,δ)=0 v[i]
i ) 12:

a (e) [N ] = SampleFqmVector(seed

(e)
N , r -1) Compute final leaf shares 13:

a (e) = i∈[N ] a (e) [i] 14: x (e) B [N ] = xB -N -1 i=1 x (e) B [i] 15: β (e) [N ] = β -N -1 i=1 β (e) [i] 16: c (e) [N ] = -a (e) , β -N -1 i=1 c (e) [i] 17: cmt (e) N = Hash(DS_C, salt, e, N, seed (e) i , x (e)
B [N ], β (e) [N ], c (e) [N ]) 18: ( x(e) B [δ], β(e) [δ], â(e) [δ], ĉ(e) [δ]) δ∈[D] = Hypercube.MainShares-Compute((x (e)
B [i], β (e) [i], a (e) [i], c (e) [i]) i∈[N ] ) 19: h1 = Hash(md, pk, salt, DS_1, cmt (1) 1 , . . . , cmt (1)
N , cmt (2) 1 , . . . , cmt (τ ) 1 , • • • , cmt (τ ) N )
Commit hypercube

Step 2: First challenge 20: (γ (e) , (e) ) e∈[τ ] = SampleFirstChallenge(h1)

Step 3: First response 21: for e ∈ [τ ] do 22:

α (e) = MPC-RSD.ComputeAlpha(x, a (e) , γ (e) , (e) ) 23:

( α(e) [δ], v(e) [δ]) δ∈[D] = MPC-RSD.Exec ( x(e) B [δ], β(e) [δ], â(e) [δ], ĉ(e) [δ]) δ∈[D] , γ (e)
, (e) , α (e) , H, y 24: h2 = Hash(md, pk, salt, h1, DS_2, (α (e) , ( α(e

) [δ], v(e) [δ]) δ∈[D] ) e∈[τ ] )
Step 4: Second challenge 25:

(i * (e) ) e∈[τ ] = SampleSecondChallenge(h2)
Step 5: Second response 26: for e ∈ [τ ] do 27:

ptree (e) =PRGPartialTreeReveal(seed (e) , i * (e) )

28:

x e) ] otherwise 29:

(e) A [i * (e) ] = y -Hx (e) B [i * (e) ] if i * (e) = 1 -Hx (e) B [i * (
x (e) [i * (e) ] = (x (e)

A [i * (e) ] || x (e)
B [i * (e) ]) 30:

MPC-RSD.ComputeAlpha(x (e) [i * (e) ], a (e) [i * (e) ], γ (e) , (e) ) 31:

if i * (e) = N then 32:

rsp (e) = (ptree (e) , cmt

i * (e) , α (e) [i * (e) ], 0, 0, 0) 33: else 34:

rsp (e) = (ptree (e) , cmt

i * (e) , α (e) [i * (e) ],

x if i * (e) = N then 6:

Check that (x e) [N ]) = (0, 0, 0). If not, return Reject.

(e) B [N ], β (e) [N ], c (
Step 2: Recompute h1 7: md = Hash(DS_M, m) 8: for e ∈ [τ ] do 9:

(seed

(e) i ) i∈[N ],i =i * (e)
= PRGPartialTreeExpand(ptree (e) , N, salt, e) 10:

for i ∈ [N ], i = i * (e) do 11: if i = N then 12: (x (e) B [i], β (e) [i], a (e) [i], c (e) [i]) = SampleShares(seed (e) i ) 13: cmt (e) i
= Hash(DS_C, salt,

N , cmt (2) 1 , . . . , cmt (τ ) 1 , • • • , cmt (τ ) N )
Step 3: Recompute h2 18: for e ∈ [τ ] do 19:

for i ∈ [N ], i = i * (e) do 20: x (e) A [i] = y -Hx (e) B [i] if i = 1 -Hx (e) B [i] otherwise 21: x (e) [i] = (x (e) A [i] || x (e) B [i]) 22: z (e) [i] = -n j=1 γ (e) j (x (e) j [i] q r -x (e) j [i]) 23: α (e) [i] = MPC-RSD.ComputeAlpha(x (e) [i], a (e) [i], γ (e)
, (e) ) 24:

α (e) = i α (e) [i] 25: for i ∈ [N ], i = i * (e) do 26: v (e) [i] = (e) • z (e) [i] -α (e) , β (e) [i] -c (e) [i] 27: v (e) [i * (e) ] = -i =i * (e) v (e) [i] 28: ( α(e) [δ], v(e) [δ]) δ∈[D] = Hypercube.MainAlphaAndV-Compute((α (e) [i], v (e) [i]) i∈[N ] )
29: h2 = Hash(DS_2, md, pk, salt, h1, (α (e) , ( α(e

) [δ], v(e) [δ]) δ∈[D] ) e∈[τ ] )
Step 4: Verify commitments 30: return h1

? = h1 ∧ h2 ? = h2

Parameter Sets

The Rank Syndrome Decoding problem has the following parameters:

q ∈ N -the order of the base field; m ∈ N -the extension degree of the extension field F q m ; n ∈ N -the length of the code C; k ∈ N -the dimension of the code; r ∈ N -the rank of the vector x.

The other parameters of RYDE include:

-N ∈ N -the number of parties of the MPC protocol; τ ∈ N -the number of parallel repetitions; η ∈ N -the extension degree for the MPC protocol (checking relations on F q m•η ).

In order to choose the parameters, we need to consider:

the security of the Rank-SD instance, i.e, the complexity of the attacks on the chosen parameters;

the security of the signature scheme, i.e, the cost of a forgery;

the size of the signature.

Additive-sharing scheme

The choice of the number N ∈ N of shares in the MPC protocol is a parameter which impacts performances: the bigger N , the slower the signing and verification, but the shorter the signature. We propose here two versions of the signature scheme with different values for N : we set N = 256 for a short version of the signature, and N = 32 for a fast version.

There is also the number τ of repetitions required to reach the desired level of security, which increases the size and the signing time.

With additive sharing, we take q = 2 since it is the most efficient (and it does not impose a constraint on the number of parties unlike with threshold sharing). The choice of (q, m, n, k, r) was then made in order to have the necessary security in regards to the considered attacks. As for the choice of τ , we need to choose it such that our signature scheme resists to the forgery attack described in [START_REF] Kales | An Attack on Some Signature Schemes Constructed From Five-Pass Identification Schemes[END_REF].

We add a parameter η in the signature: the degree of the extension field on which the relations are checked in the MPC protocol. While it increases the quantity of information to transmit per round, it also increases the soundness of the zero-knowledge proof thus reducing the number of necessary repetitions τ . We choose for each set of parameters the optimal value of η with respect to the signature size.

Parameters are chosen based on the effectiveness of existing attacks on the Rank-SD problem (see section 9.2). We remind that the security levels of the signature 1, 3 and 5 correspond respectively to the security of AES-128, AES-192 and AES-256. The following table presents our different sets of secured parameters in the case of additive shares: The main difference from the theoretical sizes relies on the packing of the vector: RYDE implementation individually packs each vector in the signature instead of a single vector containing all the vector coefficients.

Instance NIST Security Level q m n k r N η τ sk pk σ RYDE-128F 1

Threshold-sharing scheme

In [BCDF + 23], two different variant of RYDE are described, using either an additive sharing scheme, or a threshold sharing scheme. The present specification contains only the additive sharing scheme, since, so far, "threshold MPCitH" does not bring a significant advantage compared to "hypercube MPCitH" for the considered protocol for the Rank-SD problem (we obtain roughly the same signature sizes while not being particularly faster with threshold techniques). This might however change in the future, in the case where threshold techniques were to improve.

Performance Analysis

This section provides performance measures of our implementations of RYDE.

Benchmark platform. The benchmarks have been performed on a machine running Ubuntu Server 22.04.2 LTS equipped with an Intel 13th Gen Intel (R) Core(TM) i9-13900K CPU running at 3000MHz and 64GB of RAM. All the experiments were performed with Hyper-Threading, Turbo Boost, and SpeedStep features disabled. The scheme has been compiled with GCC compiler (version 11.3.0) and uses the XKCP and OpenSSL (version 3.0.2) libraries.

For each parameter set, the results have been obtained by computing the mean from 25 random instances. To minimize biases from background tasks running on the benchmark platform, each instance has been repeated 25 times and averaged.

Constant time. The provided implementations have been implemented in a constant time way whenever relevant, and as such, the running time should not leak any information concerning sensitive data. For instance, all If branches depend on public data. Additionally, Valgrind (version 3.18.1) and LibVEX were used to check that there were no memory leaks on the implementation.

Reference Implementation

The performance concerning the reference implementation on the aforementioned benchmark platform are described in Table 4. The following optimization flags have been used during compilation:

-Concerning the C code: -O3 -flto.

-Concerning the ASM code (required in the XKCP library): -x assembler-with-cpp -Wa,-defsym,old_gas_syntax=1 -Wa,-defsym,no_plt=1.

Optimized Implementation

The performance concerning the optimized implementation on the aforementioned benchmark platform are described in Table 5. The following optimization flags have been used during compilation:

-Concerning the C code: -O3 -flto -mavx2 -mpclmul -msse4.2 -maes.

-Concerning the ASM code (required in the XKCP library): -x assembler-with-cpp -Wa,-defsym,old_gas_syntax=1 -Wa,-defsym,no_plt=1. Notice that one can generate the test files as mentioned above using the kat and verbose modes of the implementation, respectively. The procedure is detailed in the technical documentation (README file of the provided code).

Expected security strength

Our scheme relies on the hardness of solving a Rank-SD instance. We expect our parameters to offer the security required for each security category. For the hardness of solving a Rank-SD instance, we refer to the following section, as well as the design document [BCDF + 23], where we describe the two best attacks on the Rank-SD problem, namely, the kernel attack and the Support Minor Modeling.

For the hardness of forging the signature, we refer to the following section and the design document, which gives the complexity of the attack on the Fiat-Shamir transform described in [START_REF] Kales | An Attack on Some Signature Schemes Constructed From Five-Pass Identification Schemes[END_REF]. This is the best attack on the Fiat-Shamir signature, and as such, this allows us to choose the parameters τ and η accordingly.

As for the proof of the unforgeability of the scheme, we have the following result in the EUF-CMA model.

Theorem 1. Let the PRG used in the signature be (t, P RG )-secure and assume an adversary running in time t has advantage at most RSD against the underlying Rank-SD problem. Let H 0 , H 1 , H 2 , H 3 , and H 4 be random oracles with output length 2λ bits. Let an adversary who makes q 0 , q 1 , q 2 , q 3 , q 4 , q S queries to the random oracles and signing oracle respectively. The probability that the adversary running in time at most t in producing an existential forgery under chosen message attack (EUF-CMA) is upper-bounded as:

Pr(f orge) ≤ 3 • (q + τ • N • q S ) 2 2 • 2 λ + q S • (q S + 5q) 2 λ + q S • τ • P RG + Pr(X + Y = τ ) + RSD
where: τ is the number of rounds of the signature, X = max i∈[0,q 2 ] {X i } where X i ∼ B(τ, p), Y = max i∈[0,q 4 ] {Y i } where Y i ∼ B(τ -X, 1 N ) and q = max{q 0 , q 1 , q 2 , q 3 , q 4 }.

We refer to the design rationale document for the proof of the theorem and the formal definition of the EUF-CMA security of a signature.

To summarize, we have an EUF-CMA scheme, relying on the hardness of solving the Rank-SD scheme. The parameters are taken such that:

-Solving the Rank-SD instance chosen respects the NIST security level aimed at;

-Building the signature without knowing the secret key respects the NIST security level aimed at;

-Pairs of messages and signatures does not help an attacker to forge a signature Our signature scheme relies on the security of hash functions and commitments functions as well. In the proofs for the security of the schemes, they are modeled as random oracles.

In practice, we use SHAKE and SHA3, which are collision resistant and preimage resistant too. With Grover's algorithm, the complexity to find a preimage is of O( n 2 ) (for an hash function with an n bits output), while collisions can be found in O(2 n 3 ) with Brassard's algorithm [START_REF] Brassard | Quantum Cryptanalysis of Hash and Claw-Free Functions[END_REF]. However, this last algorithm is unlikely to perform better than O(2 n 2 ) in practice. Hence, as in many other cryptosystems, we consider here that a hash function with an output of 2 • λ bits provides a security of λ bits.

Resistance to quantum attacks

There exist two type of attacks for our problem: combinatorial and algebraic attacks.

Since combinatorial attacks rely for their exponential part on guessing special vector spaces of a whole space, they can be improved by a square root factor through the Grover algorithm, which basically means dividing by a factor 2 the exponential part of the complexity. For algebraic attacks, such an improvement cannot be obtained directly. Notice that for the type considered parameters close to the Gilbert-Varshamov bound, combinatorial and algebraic attack behave similarly. So that in practice, resistance to quantum attacks may imply roughly dividing by a factor 2 the classical security. 9 Analysis of known attacks

Kales and Zaverucha's attack against Fiat-Shamir Signatures

There are several attacks against signatures from zero-knowledge proofs obtained thanks to the Fiat-Shamir heuristic. [START_REF] Abdalla | From Identification to Signatures via the Fiat-Shamir Transform: Minimizing Assumptions for Security and Forward-Security[END_REF] propose an attack more efficient than the bruteforce one for protocols with more than one challenge, i.e. for protocols of a minimum of 5 rounds.

Kales and Zaverucha describe in [START_REF] Kales | An Attack on Some Signature Schemes Constructed From Five-Pass Identification Schemes[END_REF] an approach which consists in guessing separately the two challenge of the protocol. It results in an additive cost rather than the expected multiplicative cost. The cost associated with forging a transcript that passes the proof of knowledge relies on achieving an optimal trade-off between the work needed for passing the first step and the work needed for passing the second step. Let C 1 and C 2 the respective cardinals to the first and second challenge sets, the probability P 1 of guessing at least r of the τ first-round challenges correctly is given by the equation:

P 1 = τ k=r τ k 1 C 1 k C 1 -1 C 1 τ -k
The optimal number of repetitions to achieve the attack is:

τ = arg min 0≤τ ≤r 1 P 1 + C r-τ 2
then the number of repetitions τ must be chosen such that this number allows to achieve the desired security.

In the case of the additive case, one obtains:

cost forge = min 0≤τ ≤τ 1 τ i=τ τ i p i (1 -p) τ -i + N τ -τ (1)

Combinatorial attacks against Rank-SD problem

We describe in this section the two most efficient combinatorial attacks against Rank-SD problem.

Enumeration of basis

Chabaud and Stern proposed an algorithm in [START_REF] Chabaud | The Cryptographic Security of the Syndrome Decoding Problem for Rank Distance Codes[END_REF] which solve the problem by enumerating the possible supports for the vector x. For each of them, one must translate the equations in F q m to equations in F q as follows.

If trying all the different possible supports in Hamming metric is inefficient due to their large number (there are n ω vectors of weight ω in F n 2 ), this is a viable method in rank metric: there are approximately q (m-r)r linear subspaces in F q m of dimension r. Moreover, one can always make the assumption that 1 is in the support, since it is enough to multiply by an invertible constant in F q m to make it appear in the coefficients of x. There are approximately q (m-r)(r-1) linear subspaces in F q m which contains 1. One obtains a system that has (n -k)m independent equations and nr + m variables in F q . Thanks to the gaussian elimination, this system can be solved with O((nr + m) 3 ) operations in F q . It is deduced that the complexity of this attack is upper bounded by O((nr + m) 3 q (m-r)(r-1) ).

GRS Algorithm

This method is an adaptation of the information set decoding attack used in Hamming metric. From the syndrome y of length n -k, the algorithm consists in guessing a set of n -k coordinates which contains the support of the vector x. One obtains n -k equations and n -k unknown coordinates of x, which can be recovered by inverting an extracted matrix from H of size (n -k) × (n -k).

In order to adapt this method to coding theory in rank metric, Gaborit, Ruatta and Schrek proposed in [START_REF] Gaborit | On the complexity of the Rank Syndrome Decoding problem[END_REF] to consider a linear subspace in F q m of dimension r ≥ r, and hope that includes the support of the vector x.The probability that E of dimension r is included in E of dimension r (for r ≥ r) is q -(m-r )r .

Suppose one knows a subspace E of dimension r which contains E = Supp(x). It is possible to recover x by solving a this linear system as long as:

r n ≤ (n -k)m i.e. r ≤ (n -k)m n
Choosing the higher possible value r = (n-k)m n , one gets the probability to obtain a suitable subspace E equal to q -(m-r )r = q -r km n . As in the previous attack, one can recover x by executing gaussian elimination, which can be perform in O((n -k) 3 m 3 ) operations in F q . This attack can be achieved with an average complexity: O((n -k) 3 m 3 q r km n ).

An improvement of GRS Algorithm

The idea proposed in [START_REF] Aragon | A New Algorithm for Solving the Rank Syndrome Decoding Problem[END_REF] is, instead of consider a linear subspace in F q m which contains 1, choose a completely random subspace E . If E contains a subspace of the form αE, with α ∈ F * q m , then one can retrieve the code word as before.

At the cost of an increase in the dimension of the code (k becomes k + 1, since we multiply by an element α which does not belong to the code), we can obtain a new subspace that contains αE. This attack can be achieved with an average complexity: O((n -k) ω m ω q r (k+1)m n -m ), where ω is in practice equal to 2.

Algebraic attacks against Rank-SD problem

Algebraic attacks amount to solve the system of equations Hx = y using computer algebra techniques like Gröbner basis. Today, the best algebraic modelings for solving the Rank-SD problem are the MaxMinors modeling [BBB + 20,BBC + 20] and the Support Minors modeling [BBC + 20,BBB + 22]. They can both benefits from a classical improvement that is the hybrid approach, that consists in specializing some variables with all possible values and solving the resulting system with less variables, but the same number of equations. In certain cases, the gain in complexity for solving the specialized system compared to the original one superseeds the lost in complexity coming from the exhausive search.

Hybrid methods As shown in [BBB + 22, Section 5], solving a Rank-SD problem of parameters (q, m, n, k, r) amount to solve q ar smaller Rank-SD problems of parameters (q, m, na, k -a, r).

MaxMinors Modeling Let H, x, y be a Rank-SD problem with parameters (q, m, n, k, r), i.e. H = (I H ) ∈ F (n-k)×n q m is uniformly sampled, x ∈ F n q m has rank exactly9 r, and y = Hx.

The idea of the MaxMinors modeling from [BBB + 20] is the following: let E = (E 1 , . . . , E r ) be a basis of Supp(x), and X = (x i,j ) ∈ F r×n q a matrix representing the coordinates of x in the basis E, then x = (E 1 , . . . , E r )X. Considering the extended code C described in the previous section, and a parity-check H ∈ F (n-k-1)×n q m of this code, we have the relation :

H x = 0, i.e. (E 1 , . . . , E r )XH = 0.
This implies that the matrix XH is not full rank, and that all its maximal minors are equal to zero. By using the Cauchy-Binet formula that expresses the determinant of the product of two matrices A ∈ K r×n and B ∈ K n×r as

|AB| = T ⊂{1..n},#T =r |A| * ,T |B| T, * , (2)
each of these maximal minors can be expressed as a linear combination of the maximal minors of the matrix X. Using these minors as new variables, we obtain a system of n-k-1 r linear equations in n r variables with coefficients over F q m , that can be unfolded over F q as m n-k-1 r equations in the same number of variables (that are searched over F q ). It is possible to solve the Rank-SD problem with the MaxMinors modeling as soon as

m n-k-1 r ≥ n r -1, if the system has 1 solution, m n-k-1 r ≥ n r ,
if the system has no solution.

(3)

It is possible to improve slightly the solving by puncturing the code on p positions, as long as

m n -p -k -1 r ≥ n -p r -1. (4)
With the largest such p, the linear system has almost the same number of equations than variables. If (3) is not satisfied, then we use the hybrid approach and specialize a ∈ {0..k} columns of X. The final complexity of the MaxMinors attack is bounded by

O q ar n -a -p r ω (5)
as n → ∞, where ω is the linear algebra constant. In all our estimates, we use conservatively ω = 2, see Table 6.

We observe in Figures 3,4, 5 that this approach is efficient for small r's, and becomes equivalent or worse than the combinatorial approach for r around the Gibert-Varshamov bound, as in this case a is close to k (see Figure 2). (192,37,41,18,13), (256, 43, 47, 18, 17) with q = 2. The horizontal lines represent the value of k. The black points correspond to the selected value of r for the proposed parameters.

The Support Minors modeling The previous modeling is a linearization technique, that only works with a large hybrid parameter a for large r. An alternative method is to rely on the Support Minors modeling, which was initially introduced in [BBC + 20] to solve generic MinRank instances, and that uses a new set of variables. It has been adapted to instances coming from F q m -linear codes in [BBB + 22].

Write the received vector v = -mG + x with -mG ∈ C a codeword, and Rank(x) = r. Then, x = v + mG = (E 1 , . . . , E r )C so that any row r i of M (v + mG) ∈ F m×n q is in the row space of C. Therefore, all the maximal minors of the matrix r i C are equal to 0. This system is described and analyzed in [BBB + 22], where it is shown that it contains the previous equations from the MaxMinors modeling. + 22], based on a careful theoretical analysis of the system and some experimental heuristics, that it is possible to solve this bilinear system by linear algebra on a matrix with N rows and M columns, as soon as N ≥ M -1, with:

It is conjectured in [BBB

N = k i=1 n -i r k + b -1 -i b -1 - n -k -1 r k + b -1 b (6) -(m -1) b i=1 (-1) i+1 k + b -i -1 b -i n -k -1 r + i . ( 7
) M = k + b -1 b n r -m n -k -1 r . (8)
In this case, the final cost in F q operations is given by

O m 2 N M ω-1 ,
where ω is the linear algebra constant and where the m 2 factor comes from expressing each F q m operation involved in terms of F q operations. As previously, it is possible to use an hybrid approach to reach the constraint N ≥ M -1, or to puncture the code to get N and M of the same value. The complexity estimates for the parameters sets are ploted in Figures 3,4, 5. We can see that for q = 2, the MaxMinors modeling is (almost) always better than the Support Minors one.

10 Advantages and limitations 10.1 Advantages Difficulty of the underlying problem: the security of the signature scheme relies on the genuine problem of decoding in rank metric Rank-SD, and there exists a probabilistic reduction from a generic NP-complete problem to the Rank-SD problem [START_REF] Gaborit | On the hardness of the decoding and the minimum distance problems for rank codes[END_REF]. The Rank-SD problem has been studied for many years. In particular the security of the problem corresponds to parameters on the Rank-Gilbert-Varshamov bound, the hardest area for parameters in which recent algebraic attacks [BBC + 20] behave similarly to classical combinatorial attacks.

Size of public keys and signature: the size of our parameters remains low. When comparing to Dilithium level 1, the sum of public key and signature sizes of RYDE is less than 60% higher than Dilithium (the sum for Dilithium reaches 3.7kB compared to 5.9kB for RYDE). It makes RYDE one of the shortest MPCitH signatures.

Size of the public matrix: in our case the public matrix can be generated from a random seed. Now independently of this, the properties of rank metric make the size of the public matrix very small (and this without additional cyclic structure), for instance of order 1kB for the first level of parameters: it could be an advantage if one were to choose not to generate the public matrix from a seed.

No cyclic structure of the underlying problem: our security is based on a problem which does not rely on cyclic structure for which the quantum security is not fully known.

Resilience against Rank-SD attacks: the size of the signature is composed of two parts: a part related to the MPC that only depends on the security level (seeds, hashes) and a part related to the parameters of the chosen RSD instance. Hence, increasing the size of the problem parameters has a limited impact on the total size of the signature. For example, the RYDE-128S instance features a signature size of 5.9kB using the parameters (q, m, n, k, r) = (2, 31, 29, 14, 10) for NIST security level 1. Choosing the parameters (q, m, n, k, r) = (2, 37, 38, 16, 14) would reach more than 192 bits of security for the underlying problem and result in a signature size of 6.9 kB for NIST security level 1. Thus, if one discovers an efficient attack against the Rank-SD problem that forces us to increase the problem parameters, only the problem parameter part will be impacted and the overall effect on the signature length will be mitigated, as explained in the previous example.

Limitations

Growth rate of the signature size: the size of the signature grows with a quadratic rate when increasing the security level. This comes from the fact that when the security level increases, both the parameters of the Rank-SD instance and the number of repetitions tau need to be increased. For example, going from security level 1 to 3, the number of repetitions is increased by half (20 to 30) while the quantity of data to be transmitted per turn grows as well since the parameters of the Rank-SD instance also have to be increased. Notice that this limitation is coherent with the Rank-SD resilience advantage from Section 10.1. Indeed in that case only the instance parameters need to be increased and not the number of repetitions nor the size of seeds and hashes.

Signature speed: Compared to lattice based signatures, the speed of our scheme is slower even if it compares very well with other signature schemes in general.

Fig. 1 :

 1 Fig. 1: Protocol Π η : a protocol that checks that the given input is a solution of the considered instance of Rank-SD problem

  for i ∈ [n] do 12: for j ∈ [r] do 13: xi = xi + randbits[ir + j] • supp[j] 14: until GetRankWeight(x) = r 15: return x, supp Algorithm 6 SampleSeeds Input: Length , Number of seeds τ , a seed seed Output: (seed (e) ) e∈[τ ] ∈ ({0, 1} ) τ PRG.Init(seed) for i ∈ [τ ] do seed (e) = PRG.GetBytes( ) return (seed (e) ) e∈[τ ]

4. 7 =

 7 Key parsing routines Algorithm 14 ParseSecretKey Input: Secret key sk Output: H, x, y and the annihilator polynomial β 1: (sk_seed, pk_seed) = sk 2: (x, supp) = SampleFqmVectorAndSupport(n, r, sk_seed) 3: H = SampleFqmMatrix(n -k, k, pk_seed) 4: y = (I|H)x 5: β = ComputeAnnihilatorPolynomial(supp) 6: return (H, x, y, β) Algorithm 15 ParsePublicKey Input: Public key pk Output: H, y 1: (pk_seed, y_string) = pk 2: H = SampleFqmMatrix(n -k, k, pk_seed) 3: y = FqmArrayFromString(y_string) 4: return (H, y) 4.8 PRG tree routines Algorithm 16 PRGTreeExpand Input: A root seed seed, a number of parties N = 2 D , a salt and an iteration index e Output: A family of seeds (seedi) i∈[N ] 1: if D = 0 then 2: return seed 3: else 4: (seed_left, seed_right) = Hash(DS_T, salt, e, seed) 5: (seedi) i∈[1,N/2] = PRGTreeExpand(seed_left, N/2, salt, e) 6: (seedi) i∈[N/2+1,N ] = PRGTreeExpand(seed_right, N/2, salt, e) 7: return (seedi) i∈[N ] Algorithm 17 PRGPartialTreeReveal Input: A root seed seed, a number of parties N = 2 D , a salt and an iteration index e, a hidden index i * Output: A partial tree, i.e. a family of seeds (seedi) i∈[D]1: (seed_left, seed_right) = Hash(DS_T, salt, e, seed)2: if D = 1 then 3: if i * = 1 then 4if i * ≤ N/2 then 9: (seedi) i∈[1,D-1] = PRGPartialTreeReveal(seed_left, N/2, salt, e, i * ) 10: seedD = seed_right 11: else 12: seed1 = seed_left 13: (seedi) i∈[2,D] = PRGPartialTreeReveal(seed_right, N/2, salt, e, i * -N/2) 14: return (seedi) i∈[D] Algorithm 18 PRGPartialTreeExpand Input: A partial tree, i.e. a family of seeds (seedi) i∈[D] , a salt and an iteration index e, a hidden index i * Output: All seeds but one (seedi) i∈[N ],i =i * 1: Let N = 2 D 2: if i * ≤ N/2 then 3: (seedi) i∈[N/2],i =i * = PRGPartialTreeExpand((seedi) i∈[D-1] ) 4: (seedi) i∈[N/2+1,N ] = PRGTreeExpand(seedD, N/2, salt, e) 5: else 6: (seedi) i∈[N/2] = PRGTreeExpand(seed1, N/2, salt, e) 7: (seedi) i∈[N/2+1,N ],i =i * = PRGPartialTreeExpand((seedi) i∈[2,D] ) 8: return (seedi) i∈[N ],i =i * 4.9 Protocol specification Algorithm 19 RYDE_Keygen Input: Security level λ Output: Secret key sk, public key pk 1: sk_seed = RandomBytes(λ) 2: pk_seed = RandomBytes(λ) 3: (x, _) = SampleFqmVectorAndSupport(n, r, sk_seed) 4: H = SampleFqmMatrix(n -k, k, pk_seed) 5: y = (I|H)x 6: pk = pk_seed || FqmArrayToString(y) 7: sk = sk_seed || pk_seed 8: return sk, pk Algorithm 20 RYDE_Sign Input: Secret key sk, public key pk, message m ∈ {0, 1} * Output: Signature σ ∈ {0, 1} * Step 0: Parse keys 1: (H, x, y, β) = ParseSecretKey(sk) 2: Define xB as the last k coordinates of x. Step 1: Commitment 3: salt = RandomBytes(2λ) 4: mseed = RandomBytes(λ) 5: md = Hash(DS_M, m) 6: (seed (e) ) e∈[τ ] = SampleSeeds(λ, τ , mseed) 7: for e ∈ [τ ] do 8: (seed (e) i ) i∈[N ] = PRGTreeExpand(seed (e) , N, salt, e) 9: for i ∈ [N -1] do Compute leaf shares 10: (x (e) B [i], β (e) [i], a (e) [i], c (e) [i]) = SampleShares(seed Hash(DS_C, salt, e, i, seed

B

  [N ], β(e) [N ], c(e) [N ])Step 6: Signature 35: return σ = (salt, h1, h2, (rsp (e) ) e∈[τ ] ) Algorithm 21 RYDE_Verify Input: Public key pk, message m ∈ {0, 1} * , signature σ ∈ {0, 1} * Output: Accept or Reject Step 0: Parse keys 1: (H, y) = ParsePublicKey(pk) Step 1: Parse challenges 2: (γ (e) , (e) ) e∈[τ ] = SampleFirstChallenge(h1) 3: (i * (e) ) e∈[τ ] = SampleSecondChallenge(h2) 4: for e ∈ [τ ] do 5:

B

  [N ], β (e) [N ], c (e) [N ]) 17: h1 = Hash(DS_1, md, pk, salt, cmt

Fig. 2 :

 2 Fig.2: Values of a for the MaxMinors modeling, in terms of r ∈ {0..r GV } below the Gibert-Varshamov bound. The values are given for the three proposed parameter sets (λ, m, n, k, r) equal to (128, 31, 33, 15, 10), (192, 37, 41, 18, 13),(256, 43, 47, 18, 17) with q = 2. The horizontal lines represent the value of k. The black points correspond to the selected value of r for the proposed parameters.

Fig. 3 :

 3 Fig. 3: Comparison of the MaxMinors complexity and the combinatorial attacks for the parameters λ = 128, (2, 31, 33, 15) and r ∈ {2..10}. Only the values of the complexities with a < k are ploted.

Fig. 4 :

 4 Fig. 4: Comparison of the MaxMinors complexity and the combinatorial attacks for the parameters λ = 192, (2, 37, 41, 18) and r ∈ {1..13}. Only the values of the complexities with a < k are ploted.

Fig. 5 :

 5 Fig. 5: Comparison of the MaxMinors complexity and the combinatorial attacks for the parameters λ = 256, (2, 43, 47, 18) and r ∈ {1..17}. Only the values of the complexities with a < k are ploted.

Table 3 :

 3 Parameters for RYDE with additive sharing, fast and short signatures We refer to the design document for the computation of the theoretical sizes [BCDF + 23].

Table 4 :

 4 Thousand (K) and Million (M) of CPU cycles of RYDE reference implementation.

Table 5 :

 5 Thousand (K) and Million (M) of CPU cycles of RYDE optimized implementation.7 Known Answer Test ValuesKnown Answer Test (KAT) values have been generated using the script provided by the NIST and can be retrieved in the KATs/ folder. Both reference and optimized implementations generate the same KATs. In addition, examples with intermediate values have also been provided in these folders. The intermediate values correspond with one execution calling the NIST-provided randombytes function seeded with zero.

Table 6 :

 6 Complexity of the algebraic attacks for the proposed parameters. a is the hybrid parameter, p the number of columns on which the code is punctured. The complexities are given in log 2 bit operations. We use ω = 2.-For the 256 bits of security parameters, the SM attack does not work: as it needs a = k, it amounts to a combinatorial attack

	NIST security level q m n k	r	combi	a p C M M b a p C SM +
	1	2 31 33 15 10	148	12 2	153	1 11 0	155
	3	2 37 41 18 13	217	15 2	238	2 14 0	241
	5	2 43 47 18 17	284	15 2	308	---	317

We assume the rank r is known. Otherwise, we can try to solve for r = 1, r = 2, . . . until we find the good r.

length nm. This process thus requires nm Complex implementation: this scheme is relatively complex to implement. Although it has potential to perform well on hardware, its implementation could be difficult in embedded systems.