Véronique Sébille

Alice Guilleux

Jean-Benoit Hardouin

Myriam Blanchin
email: myriam.blanchin@univ-nantes.fr

The Guttman errors as a tool for response shift detection at subgroup and item levels

Keywords: Response shift, Guttman errors, Item Response Theory, item level, individual level

come

The Guttman errors as a tool for response shift detection at subgroup and item levels

Introduction

Patient-Reported Outcomes (PRO) are increasingly used in longitudinal studies to take into account patient's perspective and experience of disease and assess perceived health changes over time. The interpretability of PRO data and of its evolution can be complex and obfuscated by several phenomena, such as response shift (RS) due to the patients' changing standards, values, or conceptualization of what the PRO is intended to measure. As a consequence of RS, observed patient's changes may reflect true perceived health changes combined with questionnaire perception changes. RS can also be viewed as an indication of a possible therapeutic benefit coming from some form of psychological adaptation or adjustment. It has been hypothesized that RS can result from three different processes: i) recalibration (changes in the patient's internal standards of measurements), ii) reprioritization (changes in the patient's values), and iii) reconceptualization (changes in the patient's definition of what is being measured) [1]. Several approaches have been proposed for RS detection and adjustment in the appraisal of change of PRO over time such as the "then-test"

[1], Structural Equation Modeling (SEM) [START_REF] Oort | Using structural equation modeling to detect response shifts and true change[END_REF], Item Response Theory (IRT) [START_REF] Guilleux | RespOnse Shift ALgorithm in Item response theory (ROSALI) for response shift detection with missing data in longitudinal patient-reported outcome studies[END_REF], or group-based trajectory analysis (latent trajectories created from the centered residuals of a random effects model to identify subgroups of the population) [START_REF] Mayo | Identifying response shift statistically at the individual level[END_REF]. Among these, the "then-test" only allows for the detection of recalibration RS while SEM and IRT allow for all types of RS detection (recalibration, reprioritization and reconceptualization), even though it seems that IRT has to date only been applied for recalibration and reprioritization RS. In contrast, group-based trajectory analysis will indicate that RS is suspected and will not allow for determining the type of RS that occurred but can give clues to the timing of RS.

Further, the "then-test" as well as the SEM and IRT approaches allow for the detection of RS at the group level, while group-based trajectory analysis can be used for identifying RS at the individual level. It has already been discussed [START_REF] Mayo | Identifying response shift statistically at the individual level[END_REF] that statistical methods for identifying RS at the individual level could be of great practical value in interpreting change in PRO data. In fact, group level based analyses may mask important meaningful differences over time.

Moreover, in order to gain more insight on the RS phenomena, RS detection at the item level could also be worthwhile investigating. Following these ideas, it might be of value to propose a method for RS detection at the individual and item levels also allowing for the identification of the different types of RS. Using IRT models could be interesting because they are formulated at item level. In the IRT framework, RS detection is based on item parameters such as their difficulties and their discrimination power. When no RS is assumed, item parameters are not supposed to vary over time. RS is suspected otherwise.

To go towards RS detection at a more individual level, we propose a method to detect RS at subgroup level. To further assess whether response patterns vary at an individual level, indices such as the number of Guttman errors [START_REF] Sijtsma | Introduction to Nonparametric Item Response Theory[END_REF] may be used to detect discrepancies in respondent's answers compared to an expected response pattern under some hypothesis (no RS for instance). Discrepancies and resulting Guttman errors at each time of measurement may help identifying patients that might perceive the questionnaire differently than the majority of the sample over time (assumed to not present RS). Such an approach could identify subgroups of patients that are more likely to present response shift.

The aim of this study was to explore the benefits of using a new method combining IRT and Guttman errors for RS detection across subpopulations at item level for estimating and interpreting observed differences in quality of life over time in a clinical study.

Material and Methods

Sample

This analysis was performed on a subsample of the SatisQoL study [START_REF] Kepka | The relationship between traits optimism and anxiety and health-related quality of life in patients hospitalized for chronic diseases: data from the SATISQOL study[END_REF]. The SatisQoL study is a French multicenter (3 centers) cohort study designed to assess the relationships between satisfaction with care and Health-Related Quality of Life (HRQL) after being hospitalized in a university hospital for a medical or surgical intervention related to a chronic disease. Patients between 18 and 75 years old, suffering from a chronic disease for less than 6 months at initial admission, and undergoing a medical or surgical intervention during hospitalization could be enrolled in the study. Patients were asked to fill in a variety of questionnaires (including HRQL measurement) shortly after admission (T0), and at 6 months after discharge (M6). In this study, we focused on patients who underwent surgery.

Main outcome

HRQL was assessed at baseline and 6 months after discharge using the SF36 v1.3 in French [7] [8]. This analysis was restricted to the General Health (GH) dimension of the SF-36 composed of 5 items having 5 answer categories (Excellent/ Very good/ Good/Fair/ Poor or Definitely true/ Mostly true/ Don't know/ Mostly false/ Definitely false): (i) item 1 "In general, would you say your health is", (ii) item 33 "I seem to get sick a little easier than other people", (iii) item 34 "I am as healthy as anybody I know", (iv) item 35 "I expect my health to get worse" and (v) item 36 "My health is excellent".

Identification of individuals with discrepancies

In a first step, individuals with observed discrepancies based on the number of Guttman errors [START_REF] Sijtsma | Introduction to Nonparametric Item Response Theory[END_REF] at each time of measurements were identified and assigned in different groups.

Guttman errors are simple to implement as no parameters need to be estimated. It only requires the rank-ordering of the response categories and the assumption that an individual perceiving the items in the same manner than the majority of the sample and answering positively to a given response category to an item will also answer positively to easier response categories (that have a lower rank). Following this assumption, Guttman errors represent the total number of incoherent combinations of responses between all the combinations of two items for each patient. They were computed by ordering all the possible response categories (of all of the answered items) from the easiest (the most prevalent) to the most difficult (the least prevalent). A Guttman error was identified as soon as a patient responded to a given response category for one item of the questionnaire and simultaneously did not respond to an easier response category to another item. In this work, the response categories are ordered using the patients' responses observed at the first time of measurement (T0 in the whole sample). The number of Guttman errors was subsequently determined for each individual at each time of measurement (T0 and M6). To determine the number of Guttman errors that define a low or high number of Guttman errors, we looked at the two histograms of the Guttman errors at times T0 and M6 respectively. A cut off was graphically determined using the distribution of individuals' number of Guttman errors in order to distinguish at each time of measurement patients with a lot of Guttman errors from the others.

Four groups of patients were subsequently defined given that they presented a lower number of Guttman errors than the cut off or not at a given time. Patients showing a small number of Guttman errors at T0 and at M6 were assumed to have the same perception of the questionnaire over time and to present no RS and were allocated in the "No discrepancy" group. The "Late discrepancies" group is composed of patients having a large number of Guttman errors at M6 only and not at T0. Hence, it corresponds to patients having the same perception of the items as the majority of the sample at T0 but a different perception at M6 which could fit with the usual definition of response shift.

The other two groups contain patients having discrepancies at T0 and could be composed of various types of discrepancies including response shift or differential item functioning (DIF) for instance. The "Early discrepancies" group is composed of patients having a large number of Guttman errors at T0 only but not at M6. The patients having a large number of Guttman errors at T0 and at M6 belong to the "Persistent discrepancies" group which could correspond to a group of patients presenting differential item functioning and other deviations from the response pattern of the majority of the sample.

Detection of the response shift

In a second step, the RespOnse Shift Algorithm in Item response theory (ROSALI) [START_REF] Guilleux | RespOnse Shift ALgorithm in Item response theory (ROSALI) for response shift detection with missing data in longitudinal patient-reported outcome studies[END_REF] was applied on the whole sample of patients and on the "No discrepancy" and "Late discrepancies" group separately. Patients in the "No discrepancy" group were assumed to present no RS given the clustering and we expected no or few response shifts detected with ROSALI in this group. On the opposite, patients in the "Late discrepancies" group were assumed to fit with the usual definition of response shift given the clustering and we expected to detect different types of response shift with ROSALI in this group. The "early discrepancies" and "persistent discrepancies" seem to be composed of various sources of deviations and the use of ROSALI would probably not be adequate in these groups. Therefore, ROSALI was not applied on the "early discrepancies" and "persistent discrepancies" groups.

ROSALI is an algorithm for RS detection at item level using IRT polytomous models, the longitudinal generalized partial credit model and the longitudinal partial credit model. This The RS is hierarchically detected as items presenting recalibration are identified first.

At the same time, the type of recalibration (uniform or non-uniform) is determined.

Then, items presenting reprioritization are identified. The statistical analyses were performed with Stata 13 MP and SAS 9.3.

Results

Sample characteristics

Table 1 summarizes characteristics of the 669 patients who underwent surgery included in this study (Selected sample -SS). The average age was 55 years old, 53% of the patients were men and 16% lived alone. They had, in average, 2.1 children and 32% of the patients had a professional activity. The 669 patients went through various surgical procedures belonging to 11 medical areas. Among these patients, 29 (4%), 118 (18%) and 23 (3%) did not completely fulfill the items related to GH dimension of the SF36 questionnaire at T0, M6 or T0 and M6 respectively.

Place Table 1 approximately here.

Table 1 presents a descriptive analysis of the 4 groups of patients. There were significant differences between the 4 groups in terms of age (p=0.03), with lower age for the group with persistent discrepancies, and a difference close to significance for the number of children (p=0.07). There were no significant differences in terms of sex (p=0.74), familial status (p=0.45), level of education (p=0.62), professional activity (p=0.28), reason for hospital admission (p=0.44), and hospitalization duration (p=0.86).

Response shift detection

Table 2 describes for the work sample and for each group with no discrepancies at T0 the types of response shift detected using ROSALI. In the work sample, reprioritization is detected on the items 33 to 36. In the group with no discrepancies, no type of response shift is detected. Many types of response shift are detected in the group with late discrepancies.

All five items of the GH scale are affected by RS. Indeed, items 33, 34, 35 and 36 are affected by reprioritization and items 1, 33, 34 and 35 are also affected by non-uniform recalibration in this group. The same items are affected by reprioritization in the work sample and in the "Late discrepancies" group but they are not affected in the same way. In the work sample, items 34 and 36 are more predictive of the latent trait level (RP parameter estimates>1) at M6 than at T0. On the opposite, items 33 and 35 are less predictive of the latent trait level at M6 than at T0. In the "Late discrepancies" group, items 33, 34, 35 and 36 are all less predictive of the latent trait level at M6 than at T0.

Place Table 2 approximately here.

In the "Late discrepancies" group, the non-uniform recalibration affecting the item 1 "In general, would you say your health is " results in a narrower distribution of the item difficulties along the latent trait continuum at M6 compared to T0. Indeed, the two most difficult item difficulties become easier at M6 and inversely, the two easiest item difficulties become more difficult at M6. For the same level of latent trait at both times of measurement, it is more difficult to endorse "fair" rather than "poor" and "good" rather than "fair" categories at M6 and it is easier to endorse "very good" rather than "good" and "excellent" rather than "very good" categories at M6 (item 1 is reversed for the analysis). For items 33, 34 and 35, three out of four item difficulties become easier at M6, including the easiest and the most difficult item difficulties of each item, leading to a global shift to the left of the latent trait continuum due to non-uniform recalibration. Recalibration is non-uniform because 1 over 4 item difficulties shift in the other way (on the right of the latent trait continuum) for each of the items 33, 34 and 35 and the shifts of the item difficulties for a given item have not the same magnitude.

Place Table 3 approximately here.

Table 3 presents the estimates of the true change parameter and its standard error in models accounting for RS or not. In the work sample and in the group with no discrepancies, no significant change is observed between T0 and M6 whether the RS is accounted for or not.

In the group with late discrepancies, the change is higher when the RS is not accounted for and the estimated change between T0 and M6 is almost significant (p=0.06). When the RS is taken into account in the model, the estimated change decreases of 0.10 and is not significantly different from 0 (p=0.46).

Discussion

This paper presents the response shift detection on the GH dimension of the SF-36 questionnaire at two times of measurement (at the end of hospitalization (T0) and 6 months later (M6)) on a subsample of the SatisQoL study using two different ways of handling response shift between these two times of measurement. A model considering response shift at the sample level (work sample) is compared to a model where the response shift is detected in 2 groups dividing individuals assuming to present response shift or not based on their individual number of Guttman errors.

As expected, types and amount of detected RS differ in the work sample and in the two groups. Reprioritization was found on four items in the work sample. In the "no discrepancies" group, no response shift was detected. The absence of response shift in the "no discrepancies" group compared to the work sample is in agreement with the assumption that the patients with few Guttman errors at T0 and M6 are supposed to present no or less RS than the remainder of the sample. On the opposite, in the "late discrepancies" group, non-uniform recalibration affected four items and reprioritization was found on four items. This group was composed of patients with few Guttman errors at T0 and many Guttman errors at M6 and so assuming to present RS at M6 following the usual definition of response shift where a change in the standards or values of patients is assumed to have occurred between the two times of measurement. Therefore, the large amount of RS detected in this group seems consistent with the clustering based on Guttman errors.

Furthermore, this study has also shown that the estimation of the true change can vary a lot whether the response shift is taken into account or not in the different groups identified according to the number of Guttman errors. In the work sample where a small amount of RS was detected, the estimated true change was not significantly different from 0 whether the response shift was taken into account or not. But, in the "late discrepancies" group, where all items were affected by different types of RS, the estimated true change is higher when RS is not accounted for and almost leads to conclude to a deterioration of the health related quality of life on the global health dimension between T0 and M6 (p=0.06). When RS is accounted for, the estimation of the true change is not significant and shows that the global health has stayed stable between T0 and M6 for the "late discrepancies" group (p=0.46). ROSALI has been previously applied on the SatisQoL dataset [START_REF] Guilleux | RespOnse Shift ALgorithm in Item response theory (ROSALI) for response shift detection with missing data in longitudinal patient-reported outcome studies[END_REF]. Results in terms of response shifts in the ROSALI paper are quite different from the results of the work sample in this study. In the ROSALI paper, non-uniform recalibration was found on item 1 and uniform recalibration was found on item 35 for IRT. Reprioritization was evidenced on all items of the GH subscale. In the work sample, reprioritization was detected on items 33, 34, 35 and 36 and no recalibration was detected. Guttman errors can only be computed if the patients answered all items at both times of measurement. Consequently, 79 patients (13.7%) of the sample included in the ROSALI paper (N=578) are not included in the work sample (N=499). Therefore, missing data seems to have an impact on the results of response shift detection.

As well as other methods for response shift detection that are quite new, the performance of the ROSALI algorithm has to be assessed through simulation studies. Simulation studies would allow validating the whole procedure to detect response shift by assessing whether the different steps correctly detect the correct type of response shift on the correct items, in case of complete or incomplete data. Such studies would also help to quantify the potential bias in parameter estimates and evaluate the impact of missing data on the response shift detection.

Finally, the separate response shift detection analyses in each group and in the work sample led to set the item parameters at T0 to different values for each group. In fact, the item parameters were automatically set to the estimated values estimated in the step 0 of ROSALI within each group. A more refined way to proceed to the response shift detection would be to set the item parameters within each group to the estimated values of the work sample to make the comparisons between each group and the work sample more sensible. In practice, the ROSALI algorithm package has not been developed with this option and this will be an important development for the future.

From a methodological point of view, this approach raises several questions. First, the choice of the reference frame (T0) to determine the order of the response categories and consequently the number of Guttman errors to identify individuals presenting discrepancies at T0 or M6 can be questioned. Then, the threshold for the number of Guttman errors (set to 5 in this analysis) to determine the groups that should be further explored in a sensitivity analysis as this cutoff can lead to more or less homogeneous groups. Furthermore, this threshold should be higher than the number of Guttman errors due to chance to ensure a meaningful clustering. In this context, the choice of the questionnaire has its importance as a questionnaire validated with IRT might produce less Guttman errors by chance and thus allows a better identification of individuals with discrepancies or not. A good way to improve the clustering of patients could be to define the groups by recursively partitioning the Guttman errors at T0 and T6 following the idea of the GetR package [START_REF] Beller | GetR: Calculate Guttman error trees in R (Version 0.1)[END_REF]. In this approach, the Guttman error tree constructed by recursive partitioning is adapted for cross-sectional designs. A Guttman error tree adapted to a longitudinal design could possibly define more homogeneous subgroups and overcome the difficulties related to the determination of the threshold. Another limit is related to the way the discrepancies were considered at each time, in a binary fashion (presence/absence) in this analysis. It could be of value to link the number of Guttman errors per patient with more than one threshold to define the subsequent groups more precisely and in a more homogeneous way. However, this would imply a greater number of groups of patients, thus increasing the complexity of the analyses and requiring large sample sizes. Finally, other indices could be considered to identify individuals presenting discrepancies. Stochastic non-parametric IRT-models has a long-standing tradition of using statistical methods to identify aberrant response patterns [START_REF] Meijer | The Number of Guttman Errors as a Simple and Powerful Person-Fit Statistic[END_REF][START_REF] Tendeiro | Detection of Invalid Test Scores: The Usefulness of Simple Nonparametric Statistics[END_REF], but most of these have been applied in educational research and/or to dichotomous items only. PRO studies are structurally different from studies in educational and psychological measurements because the number of individuals and the number of items are small compared to studies in educational measurement. The performance of the Guttman error based indices seems to have never been evaluated in the context of PRO studies. Another main difference is that PRO questionnaires are mainly composed of polytomous items. The items are not easily convertible from polytomous to dichotomous items and it is generally out of purpose to dichotomize them as a lot of information might be lost and this may distort the validity and reliability of the PRO questionnaires. Other statistical methods could provide an index with higher performance (based on indices derived from Guttman errors or on CUSUM for example) to detect deviations from an expected response pattern than the number of Guttman errors but further research on their applicability is warranted.

The "classify-analyze" strategy implemented in this study is a natural stepwise approach [START_REF] Lanza | Latent Class Analysis: An Alternative Perspective on Subgroup Analysis in Prevention and Treatment[END_REF] but pitfalls of this strategy have been documented in the latent class analysis and general growth mixture modeling literature [START_REF] Clogg | Latent Class Models[END_REF]. For instance, a study [START_REF] Van Leeuwen | Changes in life satisfaction in persons with spinal cord injury during and after inpatient rehabilitation: adaptation or measurement bias?[END_REF] where subgroups are created first, by fitting a latent class growth mixture to distinguish a number of life satisfaction trajectories, and where presence of response shift is determined thereafter, by comparative analyses between life satisfaction measures each of the subgroups, may lead to biased parameter estimates in the second step [START_REF] Mcintosh | Pitfalls in subgroup analysis based on growth mixture models: a commentary on Van Leeuwen et al[END_REF]. In this example, the second step (analysis step) assumes that all cases are perfectly assigned to a class and ignores the fact that a case could be not assigned to the correct class. The uncertainty in the class membership of the classification step has to be integrated in the secondary analysis to avoid biases results. Our study follows a "classify-analyze" strategy and results might suffer from this two-step approach. Contrary to the growth mixture modeling, the definition of groups based on Guttman errors does not bring uncertainty in class membership as the number of Guttman errors are deterministically computed from the rank-ordering of the response categories. But, the uncertainty related to the rank-ordering of the response categories based on the observed responses of the patients probably has an effect on the results of the response shift detection in the subgroups. Several research paths have to be investigated to evaluate the performance of the proposed approach and to improve it regarding its deterministic aspect in the first step (Guttman errors). Firstly, its performance and the potential bias on the results could be evaluated in a simulation study. Then, some recent developments regarding the "classify-analyze" strategy could help to improve the results obtained for the response shift detection step. Two approaches have proven to perform well to take into account the classification error: the one-step approach and the three-step approaches [START_REF] Mcintosh | Pitfalls in subgroup analysis based on growth mixture models: a commentary on Van Leeuwen et al[END_REF][START_REF] Bolck | Estimating Latent Structure Models with Categorical Variables: One-Step Versus Three-Step Estimators[END_REF][START_REF] Vermunt | Latent Class Modeling with Covariates: Two Improved Three-Step Approaches[END_REF]. A onestep approach seems attractive but complicated to implement in our case. This would lead to consider a longitudinal mixture IRT model [START_REF] Kadengye | A generalized longitudinal mixture IRT model for measuring differential growth in learning environments[END_REF] or an adaptation of the overlapping waves model [START_REF] Boom | A new visualization and conceptualization of categorical longitudinal development: measurement invariance and change[END_REF] to allow defining different latent trajectories and simultaneously defining different item response patterns. Since complex growth mixture models and complex IRT models both have convergence problems, we can hypothesize that such a model, no matter how attractive it might be, might fail to converge or that the estimation process may take a considerable time using maximum likelihood estimation. As mixture IRT models have been developed in educational measurement, their performances have been evaluated with large item sample sizes (60 to 240 items in [START_REF] Kadengye | A generalized longitudinal mixture IRT model for measuring differential growth in learning environments[END_REF]) and large person sample sizes (350 to 700 individuals in [START_REF] Kadengye | A generalized longitudinal mixture IRT model for measuring differential growth in learning environments[END_REF]). The common small number of items and of individuals in PRO studies compared to educational measurement studies raise the question of the performance of mixture IRT models in this context. Recent developments in Bayesian estimation of both growth mixture [START_REF] Lu | Bayesian Inference for Growth Mixture Models with Latent Class Dependent Missing Data[END_REF] and IRT models [START_REF] Verhagen | Longitudinal measurement in health-related surveys. A Bayesian joint growth model for multivariate ordinal responses[END_REF] could fasten the estimation process but might not solve the problem of small sample sizes in PRO studies. A Bayesian estimation of the parameters will also lead to redevelop ROSALI that was based on maximum likelihood estimation and to determine the appropriate a priori distribution of the parameters for which little is known. Apart from these technical considerations, interpretation of such models will be very difficult as each individual could have a different trajectory as well as a different growth. A clear identification of the presence of response shift and of the type of response shift will probably be difficult. However, it is clear that these models have the advantage of detecting response shift at the individual level rather than at the subgroup level and allow including covariates to describe differences between the classes.

Another adaptation could be to take account of the uncertainty of the first step in the response shift detection step such as in the three-step approach [START_REF] Bolck | Estimating Latent Structure Models with Categorical Variables: One-Step Versus Three-Step Estimators[END_REF][START_REF] Vermunt | Latent Class Modeling with Covariates: Two Improved Three-Step Approaches[END_REF]. In the mixture modeling domain, a step is added between the classification step and the secondary analysis to compute weights to be used in the secondary analysis that will correct the bias due to the uncertainty of class membership. Developing a three-step approach for response shift detection at subgroup level assumes that we would be able to quantify analytically the potential bias due to the clustering based on Guttman errors. As for a one-step approach, a three-step approach would not be straightforward and will require extended developments.

Regarding the clinical implication of this work, we only consider patients having a surgical intervention in the SatisQoL dataset (669 patients among the 1473 patients of this study -45%). By doing so, we tried to select patients that could be more likely to present response shift (since a catalyst is assumed to be required in order to present response shift [START_REF] Sprangers | Integrating response shift into healthrelated quality of life research: a theoretical model[END_REF][START_REF] Rapkin | Toward a theoretical model of quality-of-life appraisal: Implications of findings from studies of response shift[END_REF]). It can be hypothesized that results might have been different using the whole sample of the SatisQoL study. Furthermore, selecting patients who underwent surgery led to consider a very heterogeneous group of patients in term of disease and type of surgery. This might explain the fact that a large number of patients of the sample (about 33%) had a lot of Guttman errors at T0.

The interpretation of the link between discrepancies measured using Guttman errors and response shift can also be questioned. The detection of response shift could not be adequate on the two groups with discrepancies at T0, the "early discrepancies" and the "persistent discrepancies" groups. In the usual definition of response shift at sample level, the time of reference is T0 and all the individuals are assumed to display the same amount and types of response shift at M6 compared to T0. By looking at the subgroup level, Guttman errors identified patients whose perception of the questionnaire is already different from the whole sample at T0. The "early discrepancies" group presents few Guttman errors at M6 so we can assume that the perception of the questionnaire is then becoming similar to the majority of the sample. But we can wonder if this evolution can be considered as a response shift in its usual definition. Furthermore, the "persistent discrepancies" group presents also many Guttman errors at M6 but these discrepancies may not necessarily be on the same items between T0 and M6. Hence, this group may be composed of patients whose discrepancies are not on the same items at both times of measurement and for whom response shift detection and interpretation makes sense. But, this group can also contain patients whose discrepancies are on the same items at both times and these patients should rather be considered as having no response shift. As these patients have a different perception of the questionnaire compared to the whole sample at both times of measurement, differential item functioning [START_REF] Holland | Differential item functioning[END_REF][START_REF] Osterlind | Differential Item Functioning[END_REF] may occur if the discrepancies pertain to the same items over time for this subsample. So, the "persistent discrepancies" group may mix together very different patients and response shift detection assuming that all the patients of this group are affected the same way seems not adequate. The clustering of patients based on Guttman errors has to be improved to include not only the number of Guttman errors but also the items with discrepancies at each time of measurement. The identification of patients with persistent discrepancies on the same items over time or not might help to better assign patients in the "persistent discrepancies" group and to perform response shift detection wisely. The idea that patients might show various types of deviations in the groups with discrepancies at T0 is supported by the results obtained trying to apply ROSALI on these groups. For both groups, convergence problems appeared in steps 1 and 2 of ROSALI when fitting a model without true change and RS accounted for (Model 1) or when fitting a model with true change and RS not accounted for (Model 2). As a reminder, in the preliminary step of ROSALI, item difficulties are estimated at T0 and these values are then used in longitudinal models 1 and 2 to set the values of the item difficulties. As both groups present many Guttman errors at T0, patients might be very heterogeneous and item difficulties in the preliminary step might be misestimated. Hence, models 1 and 2 may be difficult to fit because item difficulties were potentially set to erroneous values. Selecting patients with a high number of Guttman errors at T0 might lead to combine together deviations due to response shift, to DIF and to violations of the model. Therefore, a parametric IRT model as models used in ROSALI might be unlikely to fit whereas patients have been selected due to their nonfitting to non parametric IRT (Guttman errors).

The "no discrepancies" group is composed of half of the patients of the sample and each of the three groups with discrepancies at T0 and/or M6 is composed of about a sixth of the patients. This distribution of the patients in the four groups argues in favor of response shift detection at the individual level in the future as it seems difficult to assume that all patients experience the same amount and the same type of response shift in the SatisQoL data.

Therefore, mixing an item-level approach and an individual approach of the response shift phenomenon seems to be an interesting path of development for the analysis of subjective concepts such as Patient-Reported Outcomes in a longitudinal framework. However, the best approach remains today unknown, and only methodological works through simulation studies for example will help determining advantages and drawbacks of the different approaches.

Compliance with ethical standards

Authors declare that they have no conflict of interest. All procedures performed in studies involving human participants were in accordance with the ethical standards of the institutional and/or national research committee and with the 1964 Helsinki declaration and its later amendments or comparable ethical standards. The SatisQoL study was approved by the national Institutional Review Board and the national committee for data protection (CCTIRS 07.212 and CNIL 1248560).

  algorithm allows non-uniform and uniform recalibration, reprioritization detection and true change estimation with these types of RS taken into consideration if appropriate. ROSALI detects and takes account of response shift following different steps: 0. Estimating the item difficulties from the data at T0 in a preliminary step 1. Establishing a measurement model (Model 1) taking into account the following types of RS: recalibration (uniform and non-uniform) and reprioritization (step 1). The measurement model assumes no true change. 2. Fitting a model with true change and no RS (model 2) and evaluating overall RS by a LR test comparing model 1 and model 2 (step 2). 3. If the LR test is significant (overall RS detected): Detecting each type of RS on each item (step 3) by releasing constraints on RS parameters one at a time starting from model 2. Each release of constraint is tested by likelihood ratio tests and the most significant is retained to update the model (model 3). The model 3 is updated iteratively until no more RS is detected. All tests for response shift detection are adjusted using Bonferroni correction for multiple comparisons.

4 .

 4 Estimating true change (step 4) in a model accounting for all types of response shifts detected in the previous steps (model 4).

  Consequently the Guttman errors of each patient could be computed for only 499 patients at the two times of measurement (Work sample -WS). The histograms (data not shown) at times T0 and M6 of the Guttman errors presented a bimodal distribution with a cutoff at about 5 errors. Four groups of patients were subsequently defined:  No discrepancy group: individuals with less than 5 Guttman errors at T0 and at M6  Late discrepancies group: individuals with less than 5 Guttman errors at T0 and at least 5 at M6  Early discrepancies group: individuals with at least 5 Guttman errors at T0 and less than 5 at M6  Persistent discrepancies group: individuals with at least 5 Guttman errors at T0 and at M6.

Bibliography 1 .

 1 Schwartz, C. E. & Sprangers, M. A. (1999). Methodological approaches for assessing response shift in longitudinal health related quality-of-life research. Social Science & Medicine, 48(11), 1531-1548.

Table 1 .

 1 Description of the samples (SS: Selected sample, WS: Work sample) and of the groups of patients

	Variable		SS	WS	No disc. Late	Early	Persistent	p-value
						disc.	disc.	disc.
	N		669	499	258	77	81	83
	Discrepancies at T0		-	-	No	No	Yes	Yes
	Discrepancies at M6		-	-	No	Yes	No	Yes
	Sex	Males	53%	53%	55%	49%	51%	52%	0.74
	Age	Mean	55.11	54.30	55.62	54.66	53.64	50.52	0.03
		Standard deviation	13.53	13.51	13.44	12.27	11.74	15.72
	Familial status	Alone	16%	17%	19%	14%	16%	12%	0.45
	Number of children	Mean	2.09	2.07	1.96	2.27	1.95	2.38	0.07
		Standard deviation	1.37	1.34	1.20	1.62	1.25	1.53
	Level of education
		Primary school	22%	22%	22%	29%	19%	17%
		Junior or senior high	45%	50%	49%	45%	57%	51%
		school
		Higher education	16%	20%	21%	22%	22%	14%	0.62
	Professional activity		32%	39%	38%	38%	37%	45%	0.28
	Reason for hospital admission
		ENT -Ophtalmology	21%	21%	25%	17%	20%	12%
		Circulatory system	15%	12%	11%	14%	16%	10%
		Gastrointestinal	18%	18%	18%	18%	19%	18%
		Rheumatology	18%	18%	17%	18%	21%	19%
		Urology -	11%	12%	11%	13%	7%	20%
		Nephrology
		Others	17%	19%	18%	19%	17%	20%	0.44
	Number of nights of hospitalization
		Mean	0.72	0.68	0.70	0.63	0.72	0.60	0.86
		Standard deviation	1.25	1.11	1.19	1.07	1.09	0.90
	disc. : discrepancies

Table 2 .

 2 Detected types of response shift for each item and corresponding estimated parameters in the work sample and the groups with no discrepancies at T0 RP parameter=1 if no RS occurred (parameter estimates not shown if no RS occurred) $ RC parameter=0 if no RS occurred (parameter estimates not shown if no RS occurred), one parameter per positive response category

	Item	Work sample	No discrepancies		Late discrepancies
	N		499		258		77
	Item 1
	In general, would you say your						NURC
	health is
	Item 33
	I seem to get sick a little easier		RP				NURC+RP
	than other people
	Item 34
	I am as healthy as anybody I		RP				NURC+RP
	know
	Item 35 I expect my health to get worse		RP				NURC+RP
	Item 36 My health is excellent		RP				RP
		RP*	RC $	RP*	RC $	RP*	RC $
	Item 1						1.17/ 1.47/ -1.84/ -1.69
	Item 33	0.80				0.10	-6.28/ 3.60/ -5.00/ -4.06
	Item 34	1.33				0.26	-0.76/ -0.40/ 0.18/ -0.85
	Item 35	0.76				0.13	-3.89/ -0.45/ 6.24/ -1.87
	Item 36	1.65				0.45

URC: Uniform Recalibration, NURC: Non uniform recalibration, RC: recalibration, RP: Reprioritization *

Table 3 .

 3 Estimated true change parameters in the work sample and the groups with no discrepancies at T0

		Work sample	No discrepancies	Late discrepancies
	N		499	258		77
	True change	Est. (s.e)	Pvalue	Est. (s.e)	pvalue	Est. (s.e)	pvalue
	RS not accounted for	-0.03 (0.04)	0.42	-0.12 (0.11)	0.27	-0.37 (0.19)	0.06
	RS accounted for	-0.01 (0.04)	0.83	-0.12* (0.11)*	0.27*	-0.27 (0.36)	0.46
	Est.: estimate, s.e.: standard error
	Pvalue: pvalue of test of nullity of the true change
	* No RS detected in this group

Acknowledgements

The authors gratefully acknowledge Frans J. Oort, Mirjam A.G. Sprangers and Mathilde G.E.

Verdam for their comments on the manuscript.

This study was supported by the Institut National du Cancer, under reference "INCA_6931".

The SatisQoL cohort project (Investigators: P Auquier, F Guillemin (PI), M Mercier) was supported by an IRESP (Institut de recherche en santé publique) grant from Inserm, and a PHRC (Programme Hospitalier de Recherche Clinique) national grant from French Ministry of Health, France.


Timo Zijlstra
email: timo.zijlstra@univ-ubs.fr

Karim Bigou
email: karim.bigou@univ-brest.fr

Arnaud Tisserand
email: arnaud.tisserand@univ-ubs.fr

FPGA Implementation and Comparison of Protections against SCAs for RLWE

Keywords: ring learning with errors, side channel attack, blinding, masking, shuffling, randomization

We present various FPGA implementations of protections against SCAs for RLWE-based PKE. We implemented the main solutions from the state of the art with improved variants. We also propose a new protection based on a redundant representation of the ring elements to randomize computations. We compare the implementation results of all these solutions.

Introduction

The algorithms currently used in public-key cryptography (PKC) in most of applications are not secure against quantum computers using Shor's algorithm [START_REF] Shor | Polynomial time algorithms for prime factorization and discrete logarithms on a quantum computer[END_REF]. Post-quantum cryptography (PQC) relies on mathematical problems for which known quantum algorithms offer no significant speed-up. Lattice problems such as learning with errors (LWE) and ring-LWE (RLWE) received a lot of attention. A standardization project for post-quantum encryption and signatures has been launched by NIST in 2016 [START_REF] Chen | Report on post-quantum cryptography[END_REF]. Its goal is to select and standardize post-quantum solutions to replace RSA and ECC. The second round started in January 2019, it includes 17 public-key encryption (PKE) submissions [START_REF] Alagic | Status report on the first round of the NIST post-quantum cryptography standardization process[END_REF], and 9 of them are based on lattice problems.

While PQC is resistant against quantum computers, its implementation must be protected against physical attacks. Side channel attacks (SCAs) exploit the leakage of secret information through the analysis of the power consumption, electromagnetic radiation or computation timings of the cryptographic device. For instance, correlation power analysis (CPA) uses a set of traces obtained by measuring the power consumption of the device for different inputs.

The secret key in RLWE based cryptosystems consists of a polynomial in a finite ring. Decryption involves a multiplication with the secret polynomial. This multiplication is the ideal target for SCAs. One way to prevent such attacks is to randomize the operands to remove the correlation between the power traces and the secret polynomial coefficients.

In this work, we implement in hardware various countermeasures from the state of the art against SCAs. We also improve some of them and propose a new one. We consider the masking scheme from [START_REF] Reparaz | A masked ring-LWE implementation[END_REF] for which we propose a new masked decoder. Our decoder is deterministic and does not add to the decryption failure probability, as opposed to the one from [START_REF] Reparaz | A masked ring-LWE implementation[END_REF]. We also implement two randomization techniques proposed by [START_REF] Saarinen | Arithmetic coding and blinding countermeasures for lattice signatures -engineering a side-channel resistant post-quantum signature scheme with compact signatures[END_REF]: blinding, shifting; and a combination of the two. To the best of our knowledge, these are the first FPGA implementations of these techniques. We also propose a new countermeasure based on a redundant representation of the ring elements to randomize the computations during the decryption algorithm. Our new protection leads to a small overhead in terms of time and area. We also propose two methods to shuffle the operations during the point-wise multiplications. Finally, we compare all those solutions implemented on the same FPGA and using the same high-level synthesis (HLS) tools for fair comparison. HLS allows us to quickly evaluate several architectures and parameters. Our results show that HLS tools lead to implementations with similar, or even better, performances than VHDL or Verilog ones from the literature but for a significantly reduced design cost.

Definitions and Notations

-For q a prime number and n a power of two, let Z q = Z/qZ and R q = Z q [x]/(x n + 1). -Lower case bold variables (e.g. a) are polynomials in R q of degree < n.

-B λ denotes the symmetric binomial distribution centered around 0 with integer parameter λ. -a $ ← -B λ (R q ) is a polynomial in R q whose coefficients are sampled from B λ .

is used for point-wise multiplication of polynomials and vectors.

3 State of the Art Analysis

Learning with Errors based PKE

The LWE problem and LWE based cryptography have been introduced by Regev in [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF], where it is shown that LWE is at least as hard as some worst case lattice problems. The introduction of RLWE by [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF] gives rise to more efficient cryptographic applications by adding an algebraic structure to the lattices. The matrices and vectors from Regev's cryptosystem are replaced by polynomials in finite rings, reducing the size of the public key and allowing fast multiplication algorithms. This speed-up has been studied by [START_REF] Göttert | On the design of hardware building blocks for modern lattice-based encryption schemes[END_REF] in hardware implementation.

The definition of RLWE we give here is a practical instantiation of the more general definition from [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF].

Definition 1 (RLWE [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF]). For some (secret key) polynomial s $ ← -B λ (R q ), a RLWE sample is generated by sampling a polynomial a from the uniform distribution over R q , and sampling e $ ← -B λ (R q ) and computing the output (a, b) where b = a • s + e. The search variant of the RLWE problem is to find s given a number of samples for s.

We describe the framework used for instance by NewHope. Other schemes may use deterministic errors ("Learning with Rounding") or Gaussian noise instead of using the binomial distribution. RLWE based submissions still present in the second round of the NIST standardization project include NewHope [START_REF] Alkim | Post-quantum key exchange -A New Hope[END_REF], LAC [START_REF] Lu | LAC: practical ring-LWE based public-key encryption with byte-level modulus[END_REF] and Round5 [START_REF] Baan | Round5: Compact and fast post-quantum public-key encryption[END_REF].

1. Key generation. Let s $ ← -B λ (R q ) be the private key. Sample a uniform random a ∈ R q and e 0 $ ← -B λ (R q ). The public key is given by the RLWE sample (a, b) where b := as + e 0 . 2. Encryption. Let the plaintext m ∈ R q be a polynomial with coefficients in the set {0, 1} only. Sample 3 polynomials e 1 , e 2 , e 3 $ ← -B λ (R q ). The ciphertext is given by (c 1 , c 2 ), where c 1 ← ae 1 + e 2 and c 2 ← be 1 + e 3 + q 2 • m. 3. Decryption. Let d ← c 2 -c 1 s. For each coefficient of d, decode to 0 if it is closer to 0 than to q 2 , else decode to 1.

Components of the Cryptosystem

Encoding/Decoding. The maps between the message space {0, 1} n and R q are called Encode and Decode. A string of bits is encoded by mapping 0 to 0 and 1 to q 2 , resulting in a polynomial with coefficients in Z q . To decode a polynomial in R q , a coefficient is mapped to 0 if it is closer to 0 than to q 2 in Z q , else it is mapped to 1. That is, if c ∈ q 4 , 3q 4 then c → 1 , else c → 0.

Binomial sampling. The B λ distribution over Z q is sampled by generating 2λ uniformly random bits a 1 , . . . , a λ , b 1 , . . . , b λ and returning λ i=1 (a i -b i ) mod q.

Polynomial multiplication and NTT. The encryption and decryption functions both rely on polynomial multiplication in R q . The polynomial multiplication is a costly operation. Hardware implementations of RLWE schemes such as [START_REF] Pöppelmann | Towards practical lattice-based public-key encryption on reconfigurable hardware[END_REF] tend to use the Number Theoretic Transform (NTT) to compute this operation.

It has also been suggested to use the schoolbook algorithm for area optimization [START_REF] Pöppelmann | Area optimization of lightweight lattice-based encryption on reconfigurable hardware[END_REF], but in general the NTT seems to yield better performance and highly areaoptimized implementations exist [START_REF] Sinha Roy | Compact Ring-LWE cryptoprocessor[END_REF].

To compute a polynomial multiplication using the NTT, the polynomials should be mapped to the NTT domain where the polynomial multiplication is a point-wise operation taking only n modular multiplications in Z q . Addition and subtraction can also be performed point-wise in the NTT domain. The inverse NTT is applied to bring the result back in the time domain.

Definition 2 (NTT).

Let ω ∈ Z q be a primitive n-th root of unity and a(x) = n-1 i=0 a i x i an element in R q . Then the image of a under the NTT is given by â = n-1 j=0 âj x j , where âj = a(ω j ). To use the NTT for multiplication in R q , the polynomials have to be preprocessed using the negative wrapped convolution (NWC) [START_REF] Lyubashevsky | SWIFFT: A modest proposal for FFT hashing[END_REF]. Let a, b, c, d ∈ R q such that a(x)b(x) = c(x)+d(x)(x n +1) in Z q [x] for some c(x) of degree smaller than n. Let φ ∈ Z q be a primitive 2n-th root of unity such that φ n = -1 mod q. Then, in Z q [x] and for i ≥ 0, one has:

a(φω i )b(φω i ) ≡ c(φω i ) + d(φω i )((φω i ) n + 1) mod q ≡ c(φω i ) + d(φω i )(-1 + 1) mod q = c(φω i )
This means that NTT(a(φx)) NTT(b(φx)) = NTT(c(φx)). In other words, one gets the reduction mod(x n + 1) for free by applying the NTT to a(φx) instead of a(x). To obtain the correct result from the polynomial multiplication, the inverse of the NWC should be applied to NTT -1 (NTT(c)). That is, each coefficient has to be multiplied by a power of φ -1 . Therefore, the values of φ i mod q have to be precomputed for 0 < i < n and -n < i < 0.

The transform is efficiently computed in log 2 (n) stages of n multiplications using the Cooley-Tukey algorithm [START_REF] Cooley | An algorithm for the machine calculation of complex fourier series[END_REF]. Several optimizations have been proposed to accelerate this computation. The multiplication by the powers of the 2n-th root of unity can be merged with the twiddle factors in the first stage or the scaling multiplication by n -1 mod q [START_REF] Sinha Roy | Compact Ring-LWE cryptoprocessor[END_REF]. Instead of precomputing n -1 and the powers of φ -1 , the values of n -1 φ -i for 0 ≤ i < n can be precomputed directly. A similar result merging the NWC with the final stage of the inverse NTT was described by [START_REF] Pöppelmann | High-performance ideal lattice-based cryptography on 8-bit ATxmega microcontrollers[END_REF]. By making clever use of the Decimation-In-Time (DIT) and Decimation-In-Frequency (DIF) transforms, [START_REF] Pöppelmann | High-performance ideal lattice-based cryptography on 8-bit ATxmega microcontrollers[END_REF] shows that the bit reversal can be avoided. The DIT NTT is used to compute the inverse transformation. The DIT NTT takes an input in bit-reversed order and returns the output in the original order. The bit-reversal resulting from the DIF forward transformation is thus automatically undone by the inverse NTT. All the operations in the NTT domain are computed on the bit-reversed coefficient vectors. The public and private keys are therefore stored in bit-reversed order in the NTT domain. To limit the amount of modular reductions during the NTT, [START_REF] Longa | Speeding up the number theoretic transform for faster ideal lattice-based cryptography[END_REF] allows variables to grow slightly larger than q.

Not counting symmetric primitives, the NTT is the most expensive operation in the scheme with a complexity of O(n log n) . To reduce the number of NTTs to be computed, the public and private keys can be stored in the NTT domain. The ciphertext part c 1 must also be sent in the NTT domain. During the encryption, 2 forward NTTs and 1 inverse NTT have to be computed and during the decryption only 1 inverse NTT is needed.

Using the constant geometry variant [START_REF] Pease | An adaptation of the fast Fourier transform for parallel processing[END_REF] of the NTT algorithm, the memory access pattern is independent of the stage. The values are not read from the same memory as the one that the updated variables are written to, therefore 2 BRAMs are needed in the implementation. At each iteration of the stage loop, 2 values are read from the memory, a butterfly operation is computed and the 2 results are written to the memory. A detailed description of the stage is given by Algorithm 1. All arithmetic operations are performed in Z q .

Algorithm 1 i-th stage of the NTT [START_REF] Pease | An adaptation of the fast Fourier transform for parallel processing[END_REF] 1: function stage(X, i) 2:

for j ← 0 to n 2 -1 do 3:

θ ← ω j 2 i •2 i
Get twiddle factor from memory 4:

(x0, x1) ← (X[2j], X[2j + 1]) Read from memory X 5: Y [j], Y [j + n 2 ] ← (x0 + x1, (x0 -x1)θ) Write to memory Y 6: return Y
Modular reduction. Modular reduction for moduli of the form q = 2 l1 -2 l2 +1 can be efficiently computed using algorithms in the style of [START_REF] Solinas | Generalized mersenne numbers[END_REF]. Using the fact that 2 l1 ≡ 2 l2 -1 mod q, a modular reduction can be computed using only bitwise shifts, additions and subtractions.

Side Channel Analysis

Power analysis attacks on cryptographic implementations have first been described by [START_REF] Kocher | Differential power analysis[END_REF]. Side channel attacks on LWE cryptography exploit vulnerabilities in Gaussian sampling algorithms [START_REF] Bruinderink | Flush, gauss, and reload -A cache attack on the BLISS lattice-based signature scheme[END_REF], [START_REF] Espitau | Side-channel attacks on BLISS lattice-based signatures: Exploiting branch tracing against strongswan and electromagnetic emanations in microcontrollers[END_REF], polynomial multiplication [START_REF] Aysu | Horizontal sidechannel vulnerabilities of post-quantum key exchange protocols[END_REF] or the NTT [START_REF] Primas | Single-trace side-channel attacks on masked lattice-based encryption[END_REF]. The decryption algorithm makes use of the secret key and is therefore vulnerable to statistical and machine learning attacks on side channels such as power consumption (for instance differential power analysis, DPA) or electromagnetic radiations (differential electromagnetic analysis, DEMA).

Protections

All the operations in the decryption handle inputs that depend on the secret key. To protect it against DPA, these inputs should be randomized at the start of each decryption. The decryption algorithm decodes the coefficients of some polynomial d where d is defined by

d = c 2 -NTT -1 (c 1 s).
It should be noted that knowledge of the coefficients of d leads to complete key recovery in the chosen plaintext attack model. Since c 1 and c 2 are known inputs and c 1 is invertible in R q with high probability, one can compute c -1

1 • (c 2 -d) = s.
To prevent SCAs on the coefficients of d, these coefficients should not be computed directly. Instead, a randomized or masked version of d is used. The decoder should therefore be able to decode randomized or masked inputs. We now present the main countermeasures from literature against statistical attacks on RLWE.

Masking. In [START_REF] Reparaz | A masked ring-LWE implementation[END_REF] the secret key is split in two shares: s = s + s for some uniformly random s at the start of each decryption. The linear part of the decryption function is computed twice: first the ciphertext is decrypted (but not decoded) using secret key s and then using secret key s , yielding two polynomials d and d . The final step consists of decoding the coefficients of d = d + d to bits. This is a non linear operation, that is, Decode(a + b) is not necessarily equal to Decode(a) + Decode(b). As an example, if a = b = q 6 , 2 × Decode q 6 = 0 but Decode 2 × q 6 = 1. This means that one cannot simply apply the decoder to the coefficients of d and d separately and then add the results in Z 2 to obtain the correct plaintext.

Because of the DPA scenario mentioned above, the two shares d and d should not be recombined before decoding to bits. Let d and d denote a coefficient (of some fixed index) of polynomials d and d respectively. A masked decoder takes as input two coefficients (d , d ) ∈ Z 2 q and computes the value of Decode(d + d ) without computing d + d . The solution from [START_REF] Reparaz | A masked ring-LWE implementation[END_REF] makes use of the fact that for some (d , d ) ∈ Z 2 q it is easy to deduce the value of Decode(d + d ). For instance, if 0 ≤ d < q 4 and q 4 ≤ d < q 2 then it must hold that q 4 ≤ (d + d ) < 3q 4 , therefore the coefficient decodes to 1. Similar "easy cases" exist, but not all (d , d ) ∈ Z 2 q can be resolved in this way. If both d and d lie between 0 and q 4 , all we know is that 0 ≤ (d +d ) < q 2 and this can decode to either 0 or 1.

The idea from [START_REF] Reparaz | A masked ring-LWE implementation[END_REF] to solve the hard cases is to reshare the two shares: for any δ ∈ Z q one has d

+ δ + d -δ = d + d = d.
It is therefore possible to add any constant to one of the shares and subtract the same constant from the other one. However, there is no guarantee that (d + δ, d -δ) is an easy case. If the new shares still do not form an easy case, the shares have to be reshared again. In [START_REF] Reparaz | A masked ring-LWE implementation[END_REF] a list of constants {δ 1 , . . . , δ 16 } is presented that is supposed to minimize the number of resharings to be performed. Their implementation refreshes the shares 16 times such that with high probability an easy case is obtained in at least one of the 16 iterations.

The computation time overhead due to the 16 iterations and the additional decoding failures are important drawbacks to this solution. [START_REF] Oder | Practical CCA2-secure and masked ring-LWE implementation[END_REF] propose an alternative masked decoding. Their method effectively decodes without additional decoding failures. The comparison that they make between this decoder and their re-implementation of the one from [START_REF] Reparaz | A masked ring-LWE implementation[END_REF] however shows only a very limited improvement in terms of performance. Their masked decryption takes over 3 times more cycles to compute than the unmasked version. The same implementation also uses a blinding countermeasure proposed by [START_REF] Saarinen | Arithmetic coding and blinding countermeasures for lattice signatures -engineering a side-channel resistant post-quantum signature scheme with compact signatures[END_REF].

Blinding. With the blinding countermeasure [START_REF] Saarinen | Arithmetic coding and blinding countermeasures for lattice signatures -engineering a side-channel resistant post-quantum signature scheme with compact signatures[END_REF] the polynomials s and c 1 are multiplied by scalars a and b in Z q respectively. The blinded polynomial multiplication is then computed: (as) • (bc 1 ) = (ab)s • c 1 . The inverse (ab) -1 should be computed to obtain s•c 1 . [START_REF] Saarinen | Arithmetic coding and blinding countermeasures for lattice signatures -engineering a side-channel resistant post-quantum signature scheme with compact signatures[END_REF] suggested to use (pre-computed) powers of ω and ω -1 as blinding factors to avoid the modular inversion. The decoding process cannot be protected from DPA with the scalar blinding method. The blinding multiplication has to be inverted before the coefficients can be decoded.

Shifting. It is also suggested in [START_REF] Saarinen | Arithmetic coding and blinding countermeasures for lattice signatures -engineering a side-channel resistant post-quantum signature scheme with compact signatures[END_REF] to apply a random anti-cyclic shift to the coefficients vector of the polynomials before multiplying. Due to the ring structure, this anti-cyclic shift corresponds to a multiplication by some power of x. For some random i, j < n, (x j s(x)) • (x i c 1 (x)) = x i+j s(x)c 1 (x) is computed and s(x)c 1 (x) can be recovered by inversing the shift.

In practice it is not possible to obtain x i s and x j c 1 by applying anti-cyclic shifts to their coefficients vectors, because they are represented in the NTT domain. To multiply by x i in the NTT domain, observe that

NTT(x i ) = (1, ω i , ω 2i , . . . , ω (n-1)i ), (1)
and NTT((φx

) i ) = φ i • NTT(x i ).
All of the coefficients of NTT(x i ) are already pre-computed, since they are exactly the n powers of ω. Multiplication by x i can thus be done by a pointwise multiplication with the powers of ω and φ i (for the NWC). This multiplication has to be performed in bit-reversed order, since s and c 1 are in the NTT domain.

Shuffling. Masking, blinding and shifting offer little to no protection against single trace attacks. The single trace attack by [START_REF] Primas | Single-trace side-channel attacks on masked lattice-based encryption[END_REF] exploits leakage from the operations performed during the NTT. In that paper, it is suggested to counter the attack by randomizing the order in which the butterfly operations are computed. During each stage, the n 2 butterfly operations can be computed in a random order. The same shuffling methods can also be applied to all the pointwise operations in the decryption.

Unprotected FPGA Implementation of RLWE

In this section, we present our implementation of the encryption and decryption algorithms described in the previous section on an Artix XC7A200 FPGA using Vivado HLS (version 2018.1). Our decryption architecture is the basis for the protected implementations proposed in the next sections. We compare our unprotected RLWE implementations with results from literature. One of our goals is to show that competitive results can be obtained using HLS from C code for a reduced design cost compared to VHDL or Verilog design.

Figure 1 presents the high-level architecture of our accelerator. For encryption, the public keys are first loaded into the local RAM, then the computations are performed by the functional units (FUs, see below). During encryption/decryption our accelerator is isolated for security reasons, it does not take any input or generate any output. After encryption/decryption, the result is sent out through the interface. In the paper, all the communications through the interface are included in our results. Depending on parameter n, the typical time spent for interfacing represents about 12% to 21% of the total encryption/decryption time. Parameters. In order to compare with literature results, we implement RLWE for the parameter sets (n, q, λ) = (1024, 12289, 8) and (256, 7681, 3). For n = 1024, we use a simplification of the CPA-secure version of NewHope1024 PKE with key reuse. We do not implement the key refreshing, ciphertext compression/decompression and key encoding/decoding in this paper. For simplicity we use the Trivium stream cipher as PRNG.

Encryption and Decryption. Following [START_REF] Pöppelmann | High-performance ideal lattice-based cryptography on 8-bit ATxmega microcontrollers[END_REF], we avoid the bit-reversal step by implementing both the DIF and DIT NTT. The stage loop is fully pipelined, such that it takes just over n 2 clock cycles to complete one stage. The complete forward transformation is computed in few more than n 2 log n cycles. The error polynomials e 1 , e 2 and e 3 are sampled from the binomial distribution B λ (R q ). The required random bits are provided by the PRNG. Since the ciphertext part c 1 = ae 1 +e 2 will be sent in the NTT domain, the NTT has to be applied to both e 1 and e 2 . The NWC must be computed for both polynomials. To compute these multiplications, we use the fact that the coefficients are sampled from B λ and therefore are bounded by -λ and λ. The multiplications can be computed using only a few shifts and additions, without using a DSP block. The NTT is then applied to e 1 and e 2 simultaneously, using two parallel NTT units each consisting of one butterfly unit and two BRAMs. The architecture for sampling e 1 (or e 2 ) and mapping it to the NTT domain is shown in Figure 2.

The architecture for decryption is shown in Figure 3. The area and timing implementation results for RLWE are shown in Table 1 with similar solutions from the literature.

Our small implementation is denoted by V1. This implementation with only 1 DSP block is comparable in size and speed to [START_REF] Pöppelmann | Towards practical lattice-based public-key encryption on reconfigurable hardware[END_REF] but is larger and 15 to 20% slower than the cryptoprocessor from [START_REF] Sinha Roy | Compact Ring-LWE cryptoprocessor[END_REF]. By computing the forward NTTs in parallel in V2, we are faster than both, but more DSP blocks are needed. For n = 1024, the key exchange implementation by [START_REF] Kuo | Post-quantum key exchange on FPGAs[END_REF] is comparable with our V3 results in terms of speed, but the V3 implementation uses 50% less DSP blocks and BRAMs. We conclude that results obtained using HLS are comparable or, in the best case, even better in terms of speed (up to 25%) and/or area (up to 50%) than results from works based on VHDL or Verilog implementations.

New Variants of State of the Art Protections

The protections proposed in this section and the next one are implemented by modifying our base architecture from Figure 3 for n = 256 and q = 7681. In real-world applications these protections should be part of an architecture implementing the CCA2-secure version of the scheme, including a re-encryption of the decrypted ciphertext and several evaluations of some hash function. In order to make this masked decoder compatible with CCA2-secure implementations, the output is also masked. Instead of returning the plaintext bit, a random bit is generated and XORed with the unmasked decoding result. The decoder returns both the mask and the masked value.

for i = 0 to w -1 do Y ← T (ai, bi, Y ) 4: return Y δ < δ ⇐⇒ (i + 1)q 4 -d < d - jq 4
⇐⇒ (j + 1)q 4 -d < d - iq 4
A total of 2 n log q = 2 3328 different masks can be obtained. The security of the masking scheme with its original decoder is experimentally evaluated by [START_REF] Reparaz | A masked ring-LWE implementation[END_REF]. They also mention the (small) possibility of horizontal DPA attacks targeting the 16 iterations of their masked decoder. Our proposed decoder does not have this vulnerability since it does not use 16 iterations.

Shifting

In [START_REF] Saarinen | Arithmetic coding and blinding countermeasures for lattice signatures -engineering a side-channel resistant post-quantum signature scheme with compact signatures[END_REF] there is no mention of any masked decoder. To secure the complete decryption function, we propose to apply the (normal) decoder to the shifted polynomial x i+j c 2 (x) -x i+j s(x)c 1 (x), meaning that c 2 (x) should be shifted separately. The plaintext can then be obtained by applying the inverse shift to the decoded polynomial. The minus sign that comes with the anti-cyclic shift does not change the value of the decoded coefficient, because ∀a ∈ Z/qZ it holds that Decode(a) = Decode(-a). The decryption procedure for a ciphertext (c 1 , c 2 ) can then be described as follows:

1. Generate random i, j < n. 2. Compute NTT(x i ) s and NTT(x j ) c 1 by multiplying s and c 1 by the powers of ω and φ in an order determined by i and j respectively. 3. Compute the pointwise product to obtain x i+j s • c 1 and apply in the inverse NTT. 4. Apply the anti-cyclic (i + j)-shift to c 2 and obtain x i+j c 2 .

Compute the subtraction x

i+j c 2 -x i+j s • c 1 = x i+j (c 2 -s • c 1 ). 6.
Decode to obtain the shifted plaintext. Shift i + j positions to the left.

Blinding

The blinding countermeasure is implemented by generating two random indices 0 ≤ i, j < n and multiplying c 1 and s by ω i and ω j respectively.

Shifting and Blinding combined

Both shifting and blinding involve multiplication by the powers of ω and φ. To shift the polynomial s(x) by i < n positions, we compute φ i •NTT(x i ) s(x). With almost no additional costs, this operation can be combined with the blinding operation by simply modifying the exponents of ω. To shift the polynomial by i positions and blind using ω -j for some j < n, we use:

ω -j φ i • NTT(x i ) s(x) = (φ i ω -j , φ i ω i-j , . . . , φ i ω (n-1)i-j ) s(x) (2)
Both s and c 1 are shifted and blinded. The combined blinding factor has to be removed before the decoding. The combination of the two countermeasures is therefore somewhat more expensive than shifting alone. The decoding is performed in the shifted order.

Both shifting and blinding use two log(n)-bit randomization factors. As pointed out by [START_REF] Saarinen | Arithmetic coding and blinding countermeasures for lattice signatures -engineering a side-channel resistant post-quantum signature scheme with compact signatures[END_REF], the total amount of added noise entropy for shifting and blinding combined is 4 log(n) bits. For n = 256 this is equal to 32.

6 New Protections

Shuffling

The first of the two shuffling methods proposed in this paper consists of replacing loop counters by linear feedback shift registers (LFSR). An LFSR is parametrized by an irreducible polynomial f ∈ F 2 [x] and its degree k. It computes x i a mod f for 0 ≤ i < 2 k -1 and some initial state a ∈ F 2 [x]/f . The computed values are exactly all the 2 k -1 invertible elements of the finite field F 2 [x]/f . The order in which they are computed is determined by the initial state a. Multiplication by x in F 2 [x]/f is very fast and can be computed using only 1 shift and a XOR on bit positions depending on f . Our second shuffling method consists of generating a random permutation using a permutation network in the style of [START_REF] Bayrak | An architectureindependent instruction shuffler to protect against side-channel attacks[END_REF].

LFSR method. Let an LFSR be parametrized by some irreducible polynomial f of degree n 2 . We let k = log 2 (n) -1 and consider the coefficients vectors of polynomials in F 2 [x]/f to be the binary representations of integers ranging from 0 to n 2 -1. The LFSR thus generates a sequence of n 2 -1 integers that will serve as indices for the loop counter in Algorithm 1. Instead of computing the i-th butterfly operation at the i-th loop iteration, we compute the butterfly operation that is on the j-th position, where j is the index corresponding to the i-th element generated by the LFSR. In other words, the normal loop counter is replaced by an LFSR. The LFSR has only 2 k -1 outputs, whereas we need 2 k for the n 2 butterfly operations. Therefore the first operation of each stage is not shuffled: it is always computed in the first loop iteration of the stage.

To obtain a meaningful permutation, we use the PRNG to generate a new initial state a at the start of each stage. Since a = 0 is not allowed as initial state, we set a = 1 as the default state in the case that the PRNG outputs 0. The initial state is thus set to default state with probability 4 n . All the other initial states appear with probability 2 n . This slight bias could be reduced by having the PRNG generate multiple initial states and selecting a non-zero state.

The 2 k -1 possible initial states determine 2 k -1 unique sequences. The operations of a complete log 2 (n) stage NTT can then be computed in (2 k -1) log 2 (n) different ways. For n = 256 and k = 7 this is more than 2 55 . With the LFSR method applied to the pointwise operations outside the NTT as well, the total number of random bits added is equal to 71. A single trace attack like [START_REF] Primas | Single-trace side-channel attacks on masked lattice-based encryption[END_REF] that requires all of the log 2 (n) stages seems unlikely to succeed on an implementation using the LFSR countermeasure as described.

We use an LFSR of degree k = log 2 (n) in a similar manner to shuffle the order of the n pointwise multiplications outside the NTT.

Drawbacks to the LFSR loop counter include a limited permutation space, a slightly biased outcome and the fact that the first element is not permuted. Permutation Network Method. We propose to use a permutation network generator in the style of [START_REF] Bayrak | An architectureindependent instruction shuffler to protect against side-channel attacks[END_REF]. Their permutation generator is designed for use in AES and is impractical for larger (N = 256) permutations. It is also biased. We simplify their permutation network to obtain a permutation generator that can generate N N/2 permutations and that is uniform on its range. In the remainder of this section, the parameter N is the size of the permutation, which is equal to n for the shuffling of the pointwise operations. To shuffle the butterfly operations during the computation of the NTT, N is substituted by n 2 . For b ∈ {0, 1}, let the operators T b : {0, . . . , N -1} → {0, . . . , N -1} be defined by the mapping x → x 2 + b N 2 . Then T 0 is a bitwise shift erasing the least significant bit (LSB), and T 1 applies the same shift and sets the MSB to 1.

The permutation network consists of k = log 2 (N ) stages and takes as input (x 0 , . . . , x N -1 ) = (0, . . . , N -1). During each stage, N 2 random bits b 1 , . . . , b N/2 are generated and for all pairs (x 2i , x 2i+1 ) the images T bi (x 2i ) and Tb i (x 2i+1 ) are computed. In other words, for each pair (x 2i , x 2i+1 ), one is sent to position i, while the other is mapped to i + N 2 . This is equivalent to writing one bit of the image of x 2i under the generated permutation and writing its complement to the image of x 2i+1 . The network is shown for N = 8 in Figure 5. It is exactly the same as the computation scheme of the constant geometry NTT, in which the butterfly operators are replaced by controlled swap operators.

For any integer 0 ≤ x < N the image of x under the generated permutation can be written as

T b1 • • • • • T b k (x)
and is equal to the value corresponding to the binary representation (b 1 , . . . , b k ) 2 . The kN 2 control bits thus determine the image of each index under the generated permutation. By uniqueness of binary representation it follows that any modification to any subset of the kN 2 control bits would modify the generated permutation as well. The permutation generator is therefore an injective map from {0, 1} N k/2 into the set of all permutations Σ N . This means that the number of possible configurations of the kN 2 control bits, which is equal to N N/2 , is exactly the number of permutations that can be generated by the network. The number of different permutations that can be obtained is 2 1024 for the pointwise operations and 2 256 for the NTT. Moreover, the output of the permutation network is uniform on its range given uniformly random input.

Since the permutation space is much larger than the one we obtain with the LFSR, we will only generate one {0, . . . , n 2 -1} → {0, . . . , n 2 -1} permutation for the NTT at the start of each decryption. Each stage is then computed in the order defined by this permutation. We also compute only one permutation of size n that will be used for all the pointwise operations during one decryption.

Randomization using Redundant Number Representation

In RSA and ECC, some exponent or scalar randomization countermeasures have been proposed against SCAs (see for instance [START_REF] Chabrier | On-the-fly multi-base recoding for ECC scalar multiplication without pre-computations[END_REF]). A secret exponent or scalar can be randomized without loss of information by adding a random multiple of the group order to it. The corresponding power traces are thus randomized, removing correlation between the side channel traces and the secret key. A similar concept can be applied to RLWE.

We can add random multiples of the modulus q to the secret key coefficients without invalidating the secret key. This is done at the start of each decryption. The PRNG is used to generate small r-bit random numbers for some integer parameter r. These numbers are multiplied by q and then added to the input and to the secret key. We then continue using arithmetic operations in Z/(2 r q)Z instead of in Z q . The fact that for all a, b ∈ Z we have that ab mod (2 r q) ≡ ab mod q, ensures us that the result is in the correct equivalence class.

The redundancy is not removed for the decoding. Instead we modify the algorithm to decode the coefficients directly from Z/(2 r q)Z to {0, 1}. The new decoder returns 0 if the input lies in the union of sets 2 r i=0 -q 4 + iq, q 4 + iq and returns 1 if the input is in 2 r i=0 q 4 + iq, 3q 4 + iq . At each execution of the algorithm, the multipliers, adders and decoder are handling different inputs. The computations (and the corresponding traces) are thus randomized. A total of 256r random bits are added to the operands. Fig. 6. Architecture with our redundant representation countermeasure. Before the decryption, small r-bit random multiples of q are added to the coefficients of c1 and s. The operations in the decryption function are performed in Z/(2 r q)Z.

Decrypt

Redundant Decoder Validation through Correlation Power Analysis Simulations. We evaluate the robustness of our countermeasure based on a redundant representation by simulating CPAs. The polynomial multiplication in the NTT domain consists of n independent multiplications in Z/qZ. They are of the form c•s mod q, where s is a coefficient of the secret key and c is a coefficient of the input ciphertext. We simulate correlation attacks on one modular multiplication of a known input coefficient c with an unknown secret key coefficient s.

We assume that the attacker observes the modular multiplication c • s mod q for a number of different (known) inputs c. For each modular multiplication she/he obtains the exact Hamming weight (HW) of the result. The attacker computes the "predictions": the HW of the value c • s mod q for all subkey candidates s ∈ Z q and for all inputs c. She/he evaluates the correlation between the observed HW and the predictions. For each subkey possibility s ∈ Z q , the Pearson's correlation coefficient between the observed HW and the predictions is computed. Without countermeasures, the highest correlation is obtained for the correct subkey guess.

The inputs are randomized by adding a multiple of q and used in computations in Z/(2 r q)Z for some redundancy parameter r. The impact of our countermeasure on the effectiveness of the CPA can be seen (for q = 7681) in Figure 7. Without redundancy (r = 0), the attacker observes the exact HW of the value c • s mod q for different values of c. These HWs coincide with the predictions for the correct subkey guess, resulting in a correlation coefficient of 1. For higher levels of redundancy, the average of the correlation coefficient for the correct subkey guess decreases.

The right side of Figure 7 shows that the maximum correlation is obtained for incorrect subkey guesses for all r ≥ 1. We refer to subkey guesses that yield to a higher correlation coefficient than the correct subkey guess as false positives. The number of these false positives increases with the redundancy level. For r = 8 and r = 9 there are on average around q 2 subkey guesses, for one coefficient of the secret key, that yield to a higher correlation coefficient than the correct key guess. Our countermeasure ensures that an exponential number of up to q 2 n guesses have to be tested to recover the complete secret key.

Comparison of all Protections

FPGA implementation results for RLWE solutions with various countermeasures are presented in Table 2. Results from [START_REF] Reparaz | A masked ring-LWE implementation[END_REF] are reported, and we also reimplemented their solution on an Artix-7 XC7A200 (denoted "A7") to provide fair comparisons. We also implemented the blinding and shifting methods from [START_REF] Saarinen | Arithmetic coding and blinding countermeasures for lattice signatures -engineering a side-channel resistant post-quantum signature scheme with compact signatures[END_REF] and our shuffling methods. To the best of our knowledge, these are the first FPGA implementations for these countermeasures. Finally, the results for masking with our new masked decoder and our redundant randomized countermeasures are reported. The amount of randomness added for each countermeasure is specified in the second column of the table .  \renewcommand4pt3pt Fig. 7. Mean correlation over 1000 simulations between the correct subkey guess and the observed HW as a function of the number of traces (left) and the number of redundant bits per coefficient (right). Right: average (1000 simulations of 100 traces each) of the maximum correlation over all subkey guesses is shown in red and the number of subkey guesses with higher correlation than the correct secret key in green. We cannot directly compare our re-implementation of the masking from [START_REF] Reparaz | A masked ring-LWE implementation[END_REF] and their original results on a Virtex-II XC2VP7 (denoted "V2"). However, it can be seen that the impact of masking on the performance of their V2 implementation is very high compared to our A7 re-implementation. The computation time for decryption is tripled. This is probably because the number of arithmetic operations in Z q is doubled while no parallelism is used. Moreover, it seems that their masked decoder is implemented sequentially. In our re-implementation of the masked decoder from [START_REF] Reparaz | A masked ring-LWE implementation[END_REF], we use parallelism to significantly reduce the performance penalty of their 16-step decoder. This increases the area.

Our new masked decoder is relatively simple and requires a small area (about 20% reduction compared to the re-implementation of the decoder from [START_REF] Reparaz | A masked ring-LWE implementation[END_REF]), with almost the performance of the unprotected implementation. Compared to the unprotected solution, we use extra DSP blocks and BRAMs to compute the decryptions of the two shares in parallel.

The blinding implementation gives a slightly slower solution. Its area overhead is smaller than for both masking techniques. However, we stress that this blinding countermeasure should be used in combination with another countermeasure (as specified in [START_REF] Oder | Practical CCA2-secure and masked ring-LWE implementation[END_REF]), since the blinding factor is removed before the decoding step. The shifting implementation yields to similar overhead (although with lower frequency) and its combination with blinding seems to be worthwhile. The permutation network is relatively costly in area. The LFSR loop counter is cheaper and slightly faster.

Finally, our redundant randomized countermeasure does not need additional DSPs or BRAMs to be implemented for small redundancy parameters (r ≤ 4) and can therefore be used as a cheap way to secure the decryption. For higher redundancy levels the multiplication cannot be computed within a single 18 × 25

Conclusion

In this work, we compared several countermeasures against SCAs for RLWE from [START_REF] Reparaz | A masked ring-LWE implementation[END_REF], [START_REF] Saarinen | Arithmetic coding and blinding countermeasures for lattice signatures -engineering a side-channel resistant post-quantum signature scheme with compact signatures[END_REF] and proposed new ones. Our first proposed countermeasure is an adaptation of [START_REF] Reparaz | A masked ring-LWE implementation[END_REF] with a new masked decoder which is deterministic. Our second one uses a redundant representation to randomize polynomial coefficients. We also implemented two different methods for shuffling. All the countermeasures (from literature and our ones) have been implemented on FPGA to evaluate the overhead compared to a common reference implementation on the same FPGA.

Our new decoder uses over 20% less slices and LUTs than the one from [START_REF] Reparaz | A masked ring-LWE implementation[END_REF]. To the best of our knowledge, we also present the first FPGA implementations for the blinding and shifting countermeasures from [START_REF] Saarinen | Arithmetic coding and blinding countermeasures for lattice signatures -engineering a side-channel resistant post-quantum signature scheme with compact signatures[END_REF], and a combination of the two. Finally, our protection based on redundancy at ring level provides a cheap randomization method with an adjustable security/overhead trade-off.

In the future, we will explore other types of architectures, operators, algorithms and countermeasures (e.g. at architecture level). We also plan to use our solutions in the context of application benchmarks and evaluate their security against SCAs using a hardware setup under development in our research group.

Fig. 1 .Fig. 2 .

 12 Fig. 1. High level architecture of our accelerator.

Fig. 3 . 27 -d and δ = d -jq 4 areAlgorithm 2 1 :

 327421 Fig. 3. Architecture for the decryption. The ciphertext is completely loaded in the RAM before starting the computations. The two pointwise operations (one before and one after the inverse NTT) in the blue region share a DSP block. RAM RAM BF 13 13

Fig. 5 .

 5 Fig. 5. Permutation network for N = 8. Each box is controlled by a random bit and swaps the inputs if this bit is equal to 1. 0 1 2 3 4 5 6 7

Table 1 .

 1 FPGA implementation results for our RLWE solutions (denoted V1, V2 and V3) and literature solutions. If specified, Encryption/Decryption and Server/Client/Server (for a 3-step key exchange) timing results are shown separately. Separate area results for Server and Client are indicated with +.

			Latency		Time	Slice, DSP,
	Source	FPGA	(clock cycles)	MHz	(µs)	LUT, BRAM
				n = 256
	[20]	XC6VLX75	6861/4404	262	26.2/16.8	1506, 1, 4549,
						12
	[26]	XC6VLX75	6300/2800	313	20.1/9.1	n.a., 1, 1349, 2
	V1	XC7A200	5039/2188	208	24.2/10.5	1624, 1, 4365, 5
	V2	XC7A200	3764/2239	250	15.1/9.0	2122, 6, 5616, 8
			n = 1024
	[13]	XC7Z020 6900/10300/2800 133/131 51.9/78.6/21.1 n.a.,	(8+8),
						(18756+20826),
						(14+14)
	[30]	XC7A035	171124/179292 125/117	1369/1532	0,	(2+2),
						(5142+4498),
						(4+4)
	V3	XC7A200	16146/9586	250	64.6/38.3	4106, 7, 11164,
						12

Table 2 .

 2 FPGA results for RLWE with various countermeasures and (q, n) = (7681, 256). The source column refers to the work in which the countermeasure was first proposed in LWE context. Timing and area results are for the decryption only. bits multiplier, as the ones hardwired in the Artix DSP blocks. A few additional DSP blocks and BRAMs are needed.

	Counter-	Entropy Src. Impl. FPGA Lat. Clk. Time Slice, LUT, DSP,
	measure added (bits)				(ns) (µs)	BRAM
	None Masking	0 3328	-[25] [25] [25]	V2	2800 8.3 23.5 7500 10 75.2	-, 1713, 1, --, 2014, 1, -
	None	0	-			2357 3.3 7.8	483, 1163, 2, 3
	Blinding	16	[27]			2768 3.8 10.6 941, 2284, 3, 4
	Shifting	16	[27]			3138 4.7 14.8 832, 2150, 3, 4
	Shift + Blind	32	[27]			3183 4.6 14.7 1063, 2781, 3, 4
	Masking	3328	[25]			2517 4.0 10.1 2187, 5500, 5, 6
	Our Mask. Permutation LFSR ctr. r = 1 r = 2 r = 3 r = 4	3328 1280 71 256 512 768 1024	this work	this work	A7	2510 4.0 10.1 1722, 4269, 5, 6 2521 4.5 11.4 3183, 7385, 2, 4 2846 3.6 10.3 1069, 2861, 2, 3 2272 3.7 8.5 629, 1599, 2, 3 2273 3.6 8.2 611, 1664, 2, 3 2333 3.8 8.9 807, 2067, 2, 3 2338 3.6 8.5 872, 2285, 2, 3
	r = 5	1280				2352 3.8 9.0 990, 2677, 2, 6
	r = 6	1536				2394 3.9 9.4 1254, 3466, 3, 6
	r = 7	1792				2410 3.9 9.4 1713, 5017, 3, 6
	r = 8	2048				2426 3.9 9.5 2544, 7837, 3, 6

(i+1)q

Acknowledgment

This work has been supported by a PhD grant from PEC/DGA/Région Bretagne.

Masking with a New Masked Decoder

We implement a variant of the masking scheme described in the state of the art [START_REF] Reparaz | A masked ring-LWE implementation[END_REF], improving the masked decoding process. We propose a simple masked decoder that does not need 16 iterations and that does not increase the decoding failure probability. Let d , d ∈ 0, q 4 , then d + d ∈ 0, q 2 . If either d or d were to be shifted by exactly the right amount (cf. 4), then we would be able to determine if either d + d ∈ -q 4 , q 4 or d + d ∈ q 4 , 3q 4 . The trick is then to find a δ ∈ -q 4 , q 4 such that d + δ changes quadrant while d -δ does not (or the other way around). Suppose that d ≥ d and let δ = 1 + min( q 4 -d , d ). Then, depending on the value of δ, there are two possibilities for the new shares d + δ and d -δ:

and d -δ is in the same interval as d . Then d + d must be in the interval q 4 , 3q 4 , therefore we decode to 1. 2. d + δ is in the same interval as d and d -δ = -1 ∈ -q 4 , 0 . Then d + d must be in the interval 0, q 4 ∪ -q 4 , 0 and therefore we decode to 0.

Similar solutions can be found for the other hard cases. Let Q i denote the interval iq 4 , (i+1)q 4 for 0 ≤ i ≤ 3, that we will refer to as "quadrants". The property that allows to solve the easy cases is the following:

In the remainder of this section, we let i and j be the quadrant indices of d and d respectively. For i + j = 1 mod 4 it follows from Property 1 that

In other words, the sum lies in the left half of Z q and therefore decodes to 1. Similarly, the (d , d ) ∈ Z 2 q for which i + j = 3 mod 4 are easy cases and decode to 0.

The hard cases are given by (d , d ) ∈ Z 2 q for which i + j = 0 mod 4 or

To reduce to an easy case, it suffices to move either (but not both) d or d to an adjacent quadrant. Then for the new pair (d + δ, d -δ) exactly 1 mod 4 is Fig. 4. Left: given that d , d ∈ 0, q 4 , there is no simple way to determine if d + d ∈ q 4 , 3q 4 , i.e. this is a hard case. Adding some δ to d while subtracting the same δ from d yields a new pair (d , d ) which is an easy case. Middle: for some hard cases, adding and subtracting a constant δ does not give a solution: the new pair (d , d ) is another hard case. Right: d is closer to q 4 than d is to 0. We therefore let δ = 1 + q 4 -d . Then by construction, d + δ changes quadrant while d -δ does not. It follows that

added to or subtracted from the sum i + j. Then for the updated i, j it holds that i + j = 1 mod 4 or i + j = 3 mod 4 and Property 1 applies. It is always possible to modify the sum i + j for the i, j corresponding to the shares by exactly 1. Assume w.l.o.g. that

, then there is a δ such that d + δ ∈ Q i+1 and d -δ ∈ Q j . If the opposite holds, then d can be moved to Q j-1 by subtracting a δ while d stays in Q i . The new pair (d + δ, d -δ) forms an easy case. This method does not work when the distance δ between d and (j-1)q 4 is equal to the distance δ between d and iq 4 . However, these are exactly the cases for which d + d is equal to either q 4 or 3q 4 . This means that even an unmasked decoder would not be able to decode these cases correctly. The parameters in LWE-based cryptoschemes are usually chosen such that such cases appear with negligible probability.

The comparison operation δ < δ has to be implemented with caution. Generally, comparisons are performed by checking the bit sign of the subtraction of its operands. Since δ -δ = -(d + d ) + kq 4 for some integer k < 4, this operation leaks information about the unmasked value of d. Instead of implementing a combinatory circuit, we have implemented successive accesses to a look-up table to perform the comparison. The implemented algorithm is described in Algorithm 2, where the bits of a and b are denoted (a 0 , . . . , a w-1 ) and (b 0 , . . . , b w-1 ) respectively. The look-up table implements the function T defined by

Note that it is not necessary to assume that d > d . Given (d , d ) and their corresponding quadrant indices (i, j) = index(d , d ), the distances δ =