Claire André

PhD Stéphane Rehel

MSc Elizabeth Kuhn

MSc Brigitte Landeau

MSc Inès Moulinet

MSc Edelweiss Touron

MSc Valentin Ourry

MSc Gwendoline Le Du

MSc Florence Mézenge

Clémence Tomadesso

PhD Robin De Flores

PhD Alexandre Bejanin

PhD Siya Sherif

PhD Nicolas Delcroix

PhD Alain Manrique

PhD Ahmed Abbas

PharmD Natalie L Marchant

PhD Antoine Lutz

PhD Olga M Klimecki

PhD Fabienne Collette

PhD; Eider M Arenaza-Urquijo

PhD Géraldine Poisnel

PhD; Denis Vivien

PhD Françoise Bertran

MD Vincent De La Sayette

MD Gaël Chételat
email: chetelat@cyceron.fr

PhD Géraldine Rauchs

Association of sleep-disordered breathing with Alzheimer's disease biomarkers in community-dwelling older adults A Secondary Analysis of a Randomized Clinical Trial

 Question: Which brain changes are associated with sleep-disordered breathing (SDB) in aging?

 Findings: In this cross-sectional study of 127 cognitively unimpaired communitydwelling older individuals, the presence of SDB was associated with greater amyloid burden, gray matter volume, metabolism, and perfusion in the posterior cingulate cortex and precuneus. There was no association with cognitive performance, selfreported cognitive or sleep difficulties, nor excessive daytime sleepiness.

 Meaning: SDB-related changes include amyloid deposition in brain regions typically involved in Alzheimer's disease (AD), which might explain why SDB is associated with an increased risk for developing Alzheimer's clinical syndrome at a younger age.

(T=4.62; P FWE-corrected =.001; Cohen's d=0.86) and metabolism (T=4.63; P FWE-corrected =.001; Cohen's d=1.04) overlapping mainly over the posterior cingulate cortex and precuneus. No association was found with cognition, self-reported cognitive and sleep difficulties, or excessive daytime sleepiness symptoms.

Conclusions and relevance: SDB-related brain changes in cognitively unimpaired older adults include greater amyloid deposition and neuronal activity in AD-sensitive brain regions, notably the posterior cingulate cortex and precuneus. These results support the need to screen and treat for SDB, especially in asymptomatic older populations, in order to reduce AD risk.

Manuscript text 1. Introduction

Sleep-disordered breathing (SDB) is a respiratory disorder characterized by recurrent upper airway collapse during sleep, associated with intermittent hypoxia and sleep fragmentation 1,[START_REF] Malhotra | Obstructive sleep apnoea[END_REF] .

It affects 30 to 80% of cognitively unimpaired older adults, depending on SDB definition criteria [START_REF] Ancoli-Israel | Comparisons of Home Sleep Recordings and Polysomnograms in Older Adults with Sleep Disorders[END_REF][START_REF] Senaratna | Prevalence of obstructive sleep apnea in the general population: A systematic review[END_REF] . Patients with a clinical diagnosis of Alzheimer's disease (AD) are even more likely to suffer from SDB [START_REF] Emamian | The Association Between Obstructive Sleep Apnea and Alzheimer's Disease: A Meta-Analysis Perspective[END_REF] , and untreated SDB is associated with cognitive decline and conversion to Alzheimer's clinical syndrome at a younger age [START_REF] Yaffe | Sleep-Disordered Breathing, Hypoxia, and Risk of Mild Cognitive Impairment and Dementia in Older Women[END_REF][START_REF] Leng | Association of Sleep-Disordered Breathing With Cognitive Function and Risk of Cognitive Impairment: A Systematic Review and Meta-analysis[END_REF][START_REF] Osorio | Sleep-disordered breathing advances cognitive decline in the elderly[END_REF] .

In order to clarify the mechanisms underlying the association between SDB and dementia risk, growing efforts have been deployed to better characterize the brain changes associated with SDB. Yet, previous studies have provided heterogeneous results, showing both SDBrelated decreases [START_REF] Huang | Structural and functional brain alterations in obstructive sleep apnea: a multimodal meta-analysis[END_REF][START_REF] Shi | A Meta-analysis of Voxel-based Brain Morphometry Studies in Obstructive Sleep Apnea[END_REF][START_REF] Tahmasian | Structural and functional neural adaptations in obstructive sleep apnea: An activation likelihood estimation metaanalysis[END_REF] and increases [START_REF] Baril | Gray Matter Hypertrophy and Thickening with Obstructive Sleep Apnea in Middle-aged and Older Adults[END_REF][START_REF] Rosenzweig | Hippocampal Hypertrophy and Sleep Apnea: A Role for the Ischemic Preconditioning? Annunziato L[END_REF] in gray matter (GM) volume or cortical thickness in various brain areas including frontal, temporal and parietal regions. Similarly, both decreased [START_REF] Innes | Decreased Regional Cerebral Perfusion in Moderate-Severe Obstructive Sleep Apnoea during Wakefulness[END_REF][START_REF] Baril | Regional Cerebral Blood Flow during Wakeful Rest in Older Subjects with Mild to Severe Obstructive Sleep Apnea[END_REF][START_REF] Kim | Effect of continuous positive airway pressure on regional cerebral blood flow in patients with severe obstructive sleep apnea syndrome[END_REF] and increased [START_REF] Baril | Regional Cerebral Blood Flow during Wakeful Rest in Older Subjects with Mild to Severe Obstructive Sleep Apnea[END_REF][START_REF] Nie | Resting cerebral blood flow alteration in severe obstructive sleep apnoea: an arterial spin labelling perfusion fMRI study[END_REF] perfusion has been reported in SDB patients compared to controls. Finally, SDB has been related to increased amyloid and tau levels in the blood and cerebrospinal fluid (CSF), both cross-sectionally and longitudinally [START_REF] Bu | Serum amyloid-beta levels are increased in patients with obstructive sleep apnea syndrome[END_REF][START_REF] Bubu | Obstructive sleep apnea and longitudinal Alzheimer's disease biomarker changes[END_REF][START_REF] Liguori | Obstructive Sleep Apnea is Associated With Early but Possibly Modifiable Alzheimer's Disease Biomarkers Changes[END_REF][START_REF] Sharma | Obstructive Sleep Apnea Severity Affects Amyloid Burden in Cognitively Normal Elderly. A Longitudinal Study[END_REF] . However, crosssectional PET studies have reported inconsistent results, some showing greater amyloid burden in association with SDB [START_REF] Elias | Risk of Alzheimer's Disease in Obstructive Sleep Apnea Syndrome: Amyloid-β and Tau Imaging[END_REF][START_REF] Yun | Amyloid Burden in Obstructive Sleep Apnea[END_REF] , while others do not report significant associations [START_REF] Sharma | Obstructive Sleep Apnea Severity Affects Amyloid Burden in Cognitively Normal Elderly. A Longitudinal Study[END_REF][START_REF] Spira | Objectively Measured Sleep and β-amyloid Burden in Older Adults: A Pilot Study[END_REF] .

These discrepancies may be explained by the characteristics of SDB patients (e.g., recruited from sleep clinics versus from the community, differences in age and disease duration), the scoring criteria of respiratory events, sample sizes, and/or the lack of control for possibly biasing covariates.

To our knowledge, no previous study has used a multimodal neuroimaging approach to highlight early brain changes associated with the presence of untreated SDB within a large sample of cognitively unimpaired older participants recruited from the community, with no or few symptoms. Therefore, our main objective was to provide a comprehensive picture of structural, functional and molecular brain changes associated with untreated SDB in aging, in order to provide significant advances in our understanding of early brain mechanisms underlying the relationships between SDB and AD. Secondary objectives aimed at identifying which aspect of SDB severity (i.e., sleep fragmentation, hypoxia severity or the frequency of respiratory events), is most associated to brain changes. Lastly, we investigated the associations between SDB severity and/or SDB-related brain changes and cognitive performance, self-reported cognitive and sleep difficulties, or symptoms of sleepiness.

Materials & Methods.

Participants

We included 127 cognitively unimpaired older adults from the baseline visit of the Age-Well randomized controlled trial (RCT) of the Medit-Ageing European project [START_REF] Poisnel | The Age-Well randomized controlled trial of the Medit-Ageing European project: Effect of meditation or foreign language training on brain and mental health in older adults. Alzheimer's[END_REF] Participants meeting inclusion criteria performed a detailed cognitive assessment, a polysomnography, structural MRI, [START_REF] Bu | Serum amyloid-beta levels are increased in patients with obstructive sleep apnea syndrome[END_REF] F-Florbetapir and [START_REF] Bu | Serum amyloid-beta levels are increased in patients with obstructive sleep apnea syndrome[END_REF] F-fluorodeoxyglucose (FDG) PET scans and Apolipoprotein E 4 (APOE4) genotyping within a maximum period of 3 months.

(flow diagram in

All participants gave their written informed consent prior to the examinations, and the Age-Well RCT was approved by the ethics committee (CPP Nord-Ouest III, Caen; trial registration number: EudraCT: 2016-002441-36; IDRCB: 2016-A01767-44; ClinicalTrials.gov Identifier: NCT02977819).

Cognitive and behavioral assessment

The detailed neuropsychological evaluation encompassed global cognitive functioning, processing speed, attention, working memory, executive functions, and episodic memory [START_REF] Poisnel | The Age-Well randomized controlled trial of the Medit-Ageing European project: Effect of meditation or foreign language training on brain and mental health in older adults. Alzheimer's[END_REF] .

For each cognitive domain, a composite score was computed (see eAppendix1 in the Supplement for further details). In addition, self-reported cognitive difficulties were assessed using the Cognitive Difficulties Scale [START_REF] Mcnair | Assessment in Geriatric Psychopharmacology[END_REF] . Moreover, self-reported sleep quality was assessed using the Pittsburgh Sleep Quality Index (PSQI) [START_REF] Buysse | The Pittsburgh Sleep Quality Index: a new instrument for psychiatric practice and research[END_REF] , and excessive daytime sleepiness symptoms were measured using the Epworth Sleepiness Scale (ESS) [START_REF] Johns | A new method for measuring daytime sleepiness: the Epworth sleepiness scale[END_REF] .

Neuroimaging examinations

All participants underwent a high-resolution T1-weighted anatomical image to measure GM volume, and a Florbetapir-PET scan, with a 10 min early acquisition, beginning immediately after the intravenous injection, reflecting brain perfusion, and a 10 min late acquisition (beginning 50 mn after injection) reflecting amyloid burden. A subset of participants (n=87) also underwent an [START_REF] Bu | Serum amyloid-beta levels are increased in patients with obstructive sleep apnea syndrome[END_REF] F-fluorodeoxyglucose (FDG)-PET scan, to measure brain glucose metabolism. All participants were scanned at Cyceron Center (Caen, France) on the same MRI (Philips Achieva 3.0T) and PET (Discovery RX VCT 64 PET-CT, General Electric Healthcare) scanners. The detailed acquisition and pre-processing procedures are available in the eAppendix1 in the Supplement (see also [START_REF] Poisnel | The Age-Well randomized controlled trial of the Medit-Ageing European project: Effect of meditation or foreign language training on brain and mental health in older adults. Alzheimer's[END_REF] ). PET analyses were performed on images corrected for partial volume effects (PVE) using the three-compartmental voxel-wise Müller-Gartner method [START_REF] Müller-Gärtner | Measurement of radiotracer concentration in brain gray matter using positron emission tomography: MRI-based correction for partial volume effects[END_REF] .

SDB characterization

Participants underwent a polysomnography (PSG) using a portable home device (Siesta®, Compumedics, Australia). Acquisition parameters are described in the eAppendix1 in the Supplement. Sixty-eight percent of the participants (n=86 over 127) underwent two PSG recordings, including a habituation night which was not included in the analyses. The remaining 39 participants only had one PSG recording. Recordings were visually scored in 30-s epochs following the recommended standard criteria of the American Academy of Sleep Medicine 1 . Sleep apnea was defined by a 90% drop of nasal pressure for at least 10 seconds, whereas sleep hypopnea was characterized by a 30% drop of nasal pressure for a minimum of 10 seconds, associated with an arousal or a 3% oxygen desaturation.

Based on the apnea-hypopnea index (AHI) (i.e., the sum of apneas and hypopneas per hour of sleep), participants were classified into two groups with a cut-off value of 15, independently of clinical symptoms, in accordance with the recommendations of the 3 rd edition of the International Classification of Sleep Disorders [START_REF] Sateia | International classification of sleep disorders-third edition highlights and modifications[END_REF] . Thus, we obtained a SDB-group (AHI<15; n=31) and a SDB+ group (AHI≥15; n=96) [START_REF] Yaffe | Sleep-Disordered Breathing, Hypoxia, and Risk of Mild Cognitive Impairment and Dementia in Older Women[END_REF][START_REF] Liguori | Obstructive Sleep Apnea is Associated With Early but Possibly Modifiable Alzheimer's Disease Biomarkers Changes[END_REF][START_REF] Ju | Obstructive sleep apnea decreases central nervous system-derived proteins in the cerebrospinal fluid[END_REF][START_REF] Osorio | The interaction between sleep-disordered breathing and apolipoprotein E genotype on cerebrospinal fluid biomarkers for Alzheimer's disease in cognitively normal elderly individuals[END_REF] . The sub-sample of 87 participants who also had a FDG-PET scan was composed of 69 SDB+ and 18 SDB-participants, who did not differ from the main sample regarding the proportion of SDB+ versus SDB-participants (χ 2 =0.26, P=.61), demographic, sleep and cognitive variables (data not shown).

Lastly, to address secondary objectives, we computed two composite scores reflecting sleep fragmentation and hypoxia severity. This composite score approach, also used in a previous study [START_REF] Baril | Gray Matter Hypertrophy and Thickening with Obstructive Sleep Apnea in Middle-aged and Older Adults[END_REF] , was preferred to a single-item approach, in order to minimize the issue of multiple statistical testing. The sleep fragmentation composite score corresponded to the average of the Z-scores of the respiratory arousal index, the number of shifts to non-REM sleep stage 1 per hour, and the number of nocturnal awakenings per hour. The hypoxia composite score corresponded to the average of the Z-scores of the oxygen desaturation index, the proportion of total sleep time with oxygen desaturation ≤90%, and the minimal oxygen saturation.

Statistical analyses 2.5.1. Between-group differences

Between-group differences for demographical, behavioral, sleep, and cognitive variables were assessed using Student t-tests for continuous variables, and chi-square statistics for categorical variables, with statistical significance set to P<.05.

Voxel-wise group differences in amyloid burden, GM volume, perfusion and glucose metabolism were explored using ANCOVAs in SPM12, controlling for age, sex, education, body mass index (BMI), sleep medication use, and ApoE4 status. Voxel-wise analyses were performed using MRI and PVE-corrected PET data, and considered significant at a voxellevel P<.005 (uncorrected) threshold and a cluster-level threshold of P<.05 corrected for family-wise errors (FWE).

Stepwise regression analyses

As a second step, we aimed at further assessing which aspect of SDB severity (i.e., the frequency of respiratory disturbances, associated sleep fragmentation and/or hypoxia severity) was more specifically involved in the SDB-related brain changes highlighted in the previous analysis. For this purpose, amyloid burden, GM volume, perfusion and glucose metabolism signal values were extracted from the significant clusters obtained in the voxel-wise group comparisons described above. Then, stepwise regression analyses were performed on the whole sample of participants with nine measures entered in the model as independent variables (i.e., the AHI, the sleep fragmentation composite score, the hypoxia composite score, age, sex, education, body mass index (BMI), sleep medication use and the ApoE4 status), while dependent variables were neuroimaging signal values, each modality being tested separately.

Partial correlation analyses

Finally, partial correlations were performed on the whole sample of participants in order to assess potential associations between (i) the three measures of SDB severity, and (ii) SDBrelated brain changes, with cognitive and behavioral variables. These analyses were controlled for age, sex, education, BMI, sleep medication use and ApoE4 status, and considered significant at a P<.05 threshold, after applying a Bonferroni correction for multiple comparisons. Thus, the statistical threshold for significance was set to P≤(.05/number of comparisons).

Results

Participants' characteristics

Participants' characteristics, including demographical and behavioral variables, neuropsychological scores, sleep parameters, as well as corresponding between-group differences, are provided in Table 1. SDB+ and SDB-participants did not differ for age, sex, education, depression and anxiety scores, current use of sleep medication, and the proportion of ApoE4 carriers. As expected, SDB+ participants presented significantly higher BMI (t=2.25; mean difference=1.96; 95% CI, 0.23 to 3.69; P=.03), AHI (t=8.64; mean difference=20.91; 95% CI, 16.12 to 25.70; P<.001), levels of sleep fragmentation (t=5.96; mean difference=0.90; 95% CI, 0.60 to 1.20; P<.001), and hypoxia (t=3.68; mean difference=0.59; 95% CI, 0.27 to 0.91; P<.001). Interestingly, no between-group difference was observed for subjective sleep quality, daytime sleepiness symptoms, objectivelymeasured total sleep time, sleep efficiency, and sleep onset latency on the PSG night.

Moreover, cognitive performance and self-reported cognitive difficulties were comparable between the two groups. Cohen's d=1.04). Additionally, we further compared brain changes between participants with moderate SDB (i.e., 15≤AHI<30) versus severe SDB (AHI≥30), and found no significant differences at the p<.005 level, combined with a FWE cluster-level correction (data not shown). This suggests that brain changes associated with SDB are detectable from the moderate stage, and are not exacerbated in participants with severe SDB.

Brain changes associated with the presence of SDB

Results of between-group comparisons for MRI and PVE-corrected PET data are presented in

Interestingly, there was an overlap between brain changes observed in all four neuroimaging modalities over the posterior cingulate cortex, the precuneus and the cuneus (Figure 3).

Perfusion, metabolism and GM volume signal values extracted from significant clusters

showed strong inter-correlations, and amyloid deposition significantly correlated with GM volume and perfusion (eTable 2 in the Supplement).

Lastly, for the sake of completeness, region of interest (ROI)-based complementary analyses were performed. The signal was extracted from PVE-corrected and uncorrected FDG, early and late Florbetapir PET images, in ROIs from the AAL atlas [START_REF] Tzourio-Mazoyer | Automated anatomical labeling of activations in SPM using a macroscopic anatomical parcellation of the MNI MRI single-subject brain[END_REF] overlapping with the significant clusters obtained in the voxel-wise analyses. The results are summarized in the eTable 3 in the Supplement, and are overall consistent with the findings from the voxel-wise analyses. Only results obtained with PVE-uncorrected amyloid PET images were less significant, which likely reflect the between-group differences in GM volume highlighted in the main analyses.

Links between SDB-related brain changes and measures of SDB severity.

Forward stepwise regressions were then performed in order to determine which aspect of SDB severity is the most predictive of SDB-related brain changes (Table 2). The best predictors of amyloid burden were the hypoxia composite score, explaining 8% of the variance (unstandardized β=.06; 95% CI, .02 to .10; P=.002), followed by the ApoE4 status, explaining 4% of the variance (unstandardized β=.07; 95% CI, .001 to .14; P=.05). No other variable entered the model. The AHI was the only predictive variable of GM volume, explaining 4% of the variance (unstandardized β=.01; P=.04). No variable significantly predicted brain perfusion or metabolism.

To ensure that these findings were not biased by a possible circularity issue, we replicated stepwise regression analyses with neuroimaging values that were independent from the previous between-group comparison. For this purpose, amyloid deposition was more globally measured through the global neocortical SUVr, and GM volume was extracted from the composite ROI of posterior regions of the AAL atlas described above (eTable 4 in the Supplement). Briefly, results were similar for amyloid burden, with hypoxia severity being the best predictor of the global neocortical amyloid SUVr (unstandardized β=.06; 95% CI, .01 to .11; P=.01), followed by the APOE4 status (unstandardized β=.09; 95% CI, .01 to .17; P=.04). Moreover, the AHI was still the best SDB-related predictor of GM volume, although it was preceded by the BMI, sex and age.

Links with cognition, self-reported cognitive and sleep difficulties

Lastly, we aimed at exploring the cognitive and behavioral correlates of SDB severity and associated brain changes. No association survived the Bonferroni correction for multiple comparisons (eTable 5 in the Supplement), such that neither measures of SDB severity, nor SDB-related brain changes, were related to cognitive performance, self-reported cognitive and sleep difficulties or symptoms of sleepiness.

Discussion

The main goal of the present study was to provide a comprehensive overview of brain changes associated with untreated SDB in community-dwelling older participants with few symptoms. Our results show that SDB+ participants presented greater amyloid burden, GM volume, metabolism, and perfusion in parieto-occipital regions, including the precuneus and posterior cingulate cortex. Interestingly, greater amyloid burden was robustly associated with the severity of hypoxia. Neither SDB severity, nor SDB-related brain changes, were associated with cognitive performance, self-reported cognitive and sleep difficulties, and symptoms of sleepiness.

The association between SDB and greater amyloid deposition is in line with previous studies

showing that SDB is associated with lower serum and CSF amyloid levels [START_REF] Bu | Serum amyloid-beta levels are increased in patients with obstructive sleep apnea syndrome[END_REF][START_REF] Liguori | Obstructive Sleep Apnea is Associated With Early but Possibly Modifiable Alzheimer's Disease Biomarkers Changes[END_REF] . Furthermore, our results characterize the regional pattern of amyloid deposition in cognitively unimpaired individuals with SDB, extending the findings of Yun and colleagues [START_REF] Yun | Amyloid Burden in Obstructive Sleep Apnea[END_REF] to a larger and older sample of individuals. The association between amyloid deposition and hypoxia severity is also consistent with animal studies, showing that hypoxia promotes the cleavage of the amyloid precursor protein by the β-and γ-secretases, leading to increased Aβ levels [START_REF] Sun | Hypoxia facilitates Alzheimer's disease pathogenesis by up-regulating BACE1 gene expression[END_REF][START_REF] Li | Hypoxia increases Abeta generation by altering beta-and gamma-cleavage of APP[END_REF][START_REF] Shiota | Chronic intermittent hypoxia/reoxygenation facilitate amyloid-β generation in mice[END_REF] .

Moreover, it may partly explain why this specific aspect of SDB, rather than the AHI or sleep fragmentation, significantly predicts cognitive decline and conversion to Alzheimer's clinical syndrome in older adults [START_REF] Yaffe | Sleep-Disordered Breathing, Hypoxia, and Risk of Mild Cognitive Impairment and Dementia in Older Women[END_REF][START_REF] Blackwell | Associations between sleep-disordered breathing, nocturnal hypoxemia, and subsequent cognitive decline in older communitydwelling men: the Osteoporotic Fractures in Men Sleep Study[END_REF] .

Interestingly, SDB+ participants also presented greater GM volume, perfusion, and metabolism, in line with the findings of several other studies [START_REF] Baril | Gray Matter Hypertrophy and Thickening with Obstructive Sleep Apnea in Middle-aged and Older Adults[END_REF][START_REF] Baril | Regional Cerebral Blood Flow during Wakeful Rest in Older Subjects with Mild to Severe Obstructive Sleep Apnea[END_REF][START_REF] Nie | Resting cerebral blood flow alteration in severe obstructive sleep apnoea: an arterial spin labelling perfusion fMRI study[END_REF][START_REF] Rosenzweig | The impact of sleep and hypoxia on the brain: potential mechanisms for the effects of obstructive sleep apnea[END_REF][START_REF] Cross | Structural brain correlates of obstructive sleep apnoea in older adults at risk for dementia[END_REF] . Nevertheless, other groups have also reported GM atrophy, hypoperfusion and hypometabolism in participants with SDB [START_REF] Huang | Structural and functional brain alterations in obstructive sleep apnea: a multimodal meta-analysis[END_REF][START_REF] Shi | A Meta-analysis of Voxel-based Brain Morphometry Studies in Obstructive Sleep Apnea[END_REF][START_REF] Tahmasian | Structural and functional neural adaptations in obstructive sleep apnea: An activation likelihood estimation metaanalysis[END_REF][START_REF] Innes | Decreased Regional Cerebral Perfusion in Moderate-Severe Obstructive Sleep Apnoea during Wakefulness[END_REF][START_REF] Kim | Effect of continuous positive airway pressure on regional cerebral blood flow in patients with severe obstructive sleep apnea syndrome[END_REF] . Discrepancies across studies may be due, at least in part, to methodological differences, as most studies have been performed on smaller samples of young and middleaged participants with severe SDB (AHI>30). Alternatively, it is possible that studies including participants with less severe SDB (i.e., from the moderate stage, corresponding to an AHI>15) and few symptoms, as in the present study and in others [START_REF] Baril | Gray Matter Hypertrophy and Thickening with Obstructive Sleep Apnea in Middle-aged and Older Adults[END_REF][START_REF] Baril | Regional Cerebral Blood Flow during Wakeful Rest in Older Subjects with Mild to Severe Obstructive Sleep Apnea[END_REF] , may be more able to capture earlier brain changes associated with the presence of SDB.

Greater GM volume, perfusion and metabolism observed in SDB+ participants could result from astrogliosis, microgliosis, and neuro-inflammatory processes [START_REF] Rosenzweig | The impact of sleep and hypoxia on the brain: potential mechanisms for the effects of obstructive sleep apnea[END_REF][START_REF] Aviles-Reyes | Intermittent hypoxia during sleep induces reactive gliosis and limited neuronal death in rats: implications for sleep apnea[END_REF][START_REF] Li | Association between Serum Homocysteine Level and Obstructive Sleep Apnea: A Meta-Analysis[END_REF][START_REF] Daulatzai | Death by a Thousand Cuts in Alzheimer's Disease: Hypoxia-The Prodrome[END_REF] . Importantly, our results show for the first time, in vivo, that greater amyloid burden co-localize with greater GM volume, perfusion, and metabolism in cognitively unimpaired older participants with SDB. We believe that these overlapping patterns reinforce the likelihood of common underlying mechanisms. Indeed, it has been demonstrated that higher neuronal activity is associated with increased Aβ production [START_REF] Bero | Neuronal activity regulates the regional vulnerability to amyloid-β deposition[END_REF][START_REF] Raichle | A default mode of brain function[END_REF][START_REF] Buckner | Cortical Hubs Revealed by Intrinsic Functional Connectivity: Mapping, Assessment of Stability, and Relation to Alzheimer's Disease[END_REF][START_REF] Cirrito | Synaptic Activity Regulates Interstitial Fluid Amyloid-β Levels In Vivo[END_REF] . In addition, several studies have shown that neuro-inflammatory processes play a central role in AD progression, and are associated with higher levels of amyloid deposition [START_REF] Kinney | Inflammation as a central mechanism in Alzheimer's disease. Alzheimer's[END_REF] . Thus, SDB-related neuro-inflammatory processes and associated neuronal hyperactivity are likely to promote amyloid deposition in the same area.

Furthermore, greater GM volume, perfusion and metabolism co-localizing with amyloid deposition may precede the development of neuronal injury, such as hypometabolism, and atrophy [START_REF] Fortea | Cerebrospinal fluid β-amyloid and phospho-tau biomarker interactions affecting brain structure in preclinical Alzheimer disease[END_REF][START_REF] Pegueroles | Longitudinal brain structural changes in preclinical Alzheimer's disease[END_REF] . Alternatively, greater GM volume, perfusion and metabolism could also reflect higher brain reserve [START_REF] Stern | Whitepaper: Defining and investigating cognitive reserve, brain reserve, and brain maintenance[END_REF] , helping to cope with amyloid pathology and maintain cognitive performance.

In our study, SDB-related brain changes were not associated with cognitive performance, selfreported cognitive and sleep difficulties, or symptoms of excessive daytime sleepiness. We believe that this finding indicates that greater amyloid deposition, GM volume, perfusion, and metabolism may represent early and asymptomatic brain changes associated with SDB.

Studies exploring the associations between SDB and cognitive performance using crosssectional designs have provided mixed results [START_REF] Leng | Association of Sleep-Disordered Breathing With Cognitive Function and Risk of Cognitive Impairment: A Systematic Review and Meta-analysis[END_REF][START_REF] Olaithe | Cognitive deficits in obstructive sleep apnea: Insights from a meta-review and comparison with deficits observed in COPD, insomnia, and sleep deprivation[END_REF][START_REF] Boland | Measures of cognitive function in persons with varying degrees of sleep-disordered breathing: the Sleep Heart Health Study[END_REF][START_REF] Sforza | Cognitive Function and Sleep Related Breathing Disorders in a Healthy Elderly Population: the Synapse Study[END_REF] , but longitudinal studies showed that SDB is associated with conversion to Alzheimer's clinical syndrome, and with cognitive decline over time [START_REF] Yaffe | Sleep-Disordered Breathing, Hypoxia, and Risk of Mild Cognitive Impairment and Dementia in Older Women[END_REF][START_REF] Leng | Association of Sleep-Disordered Breathing With Cognitive Function and Risk of Cognitive Impairment: A Systematic Review and Meta-analysis[END_REF][START_REF] Osorio | Sleep-disordered breathing advances cognitive decline in the elderly[END_REF] . Therefore, older adults with SDB may exhibit silent brain changes, including increased amyloid deposition, which may propagate with time and explain why they are more at risk of developing Alzheimer's clinical syndrome.

The main strengths of the present study are the multimodal assessment of brain integrity, allowing to reveal the overlap of brain changes, and the detailed cognitive assessment, on a large sample of cognitively unimpaired older individuals. However, the cross-sectional design of the analyses does not allow for the assessment of the causal relationships between SDB and brain changes, and longitudinal studies are needed to investigate whether these early SDBrelated brain changes will progress to neurodegeneration and cognitive deficits.

Taken together, community-dwelling older individuals with untreated SDB presented greater amyloid deposition, GM volume, perfusion and metabolism mainly over the posterior cingulate, cuneus and precuneus areas, typically altered in AD. However, no association with cognitive performance, self-reported cognitive or sleep difficulties, or sleepiness symptoms was observed. Early neuro-inflammatory and neuronal hyperactivity processes promoting amyloid deposition could represent the underlying mechanisms increasing the susceptibility to AD at an asymptomatic stage of SDB. Our findings highlight the need to treat sleep disorders in the older population, even in the absence of cognitive or behavioral manifestations.

Acknowledgements

The authors are grateful to Alison Mary, Franck Doidy, Sébastien Polvent, Nicolas Oulhaj, Aurélia Cognet, Clarisse Gaubert, and the Cyceron MRI-PET staff for their help with recruitment and data acquisition or administrative support, as well as Caitlin Ware for editing the final draft. We acknowledge the members of the Medit-Ageing Research Group, Euclid team, the sponsor (Pôle de Recherche Clinique at Inserm), and all the participants of the study for their contribution. Abbreviations: FWE, family-wise error; GM, gray matter.

Representation of the overlap between SDB-related patterns of greater perfusion (blue) and amyloid deposition (pink), obtained at a P<.005 (uncorrected) threshold combined with a FWE cluster-level correction.

Tables. Results are expressed as means (SD), unless otherwise specified.

a Between-group differences were assessed using Student t-tests for continuous variables, and chi-square statistics for categorical variables. Statistical significance was set to P<.05.

b Use of sleep medication on a regular basis (>1/week), excluding phytotherapy and homeopathy.

c n=30 controls with valid Florbetapir-PET scan. The threshold for amyloid positivity was defined as >.99, and corresponded to the 99.9 th percentile of the neocortical SUVr distribution among 45 healthy young individuals, aged <40 years.

d n=30 SDB-and 88 SDB+ participants with valid data related to oxygen saturation.

eReferences.

This supplementary material has been provided by the authors to give readers additional information about their work.

Florbetapir-and FDG-PET scans were acquired in two separate sessions with a resolution of 3.76 × 3.76 × 4.9 mm 3 (field of view = 157 mm). Forty-seven planes were obtained with a voxel size of 1.95 × 1.95 × 3.27 mm 3 . A transmission scan was performed for attenuation correction before the PET acquisition.

For the Florbetapir-PET scan, each participant underwent a 10 min PET scan beginning at the intravenous injection of ~4MBq/Kg of Florbetapir, and a 10 min PET scan beginning 50 min after the intravenous injection.

Early Florbetapir-PET, reflecting brain perfusion, was reconstructed from 1 to 6 min. Late-Florbetapir acquisition reflected brain amyloid burden.

For the FDG-PET scan, participants (n=87) were fasted for at least 6 hours before scanning. After a 30-min resting period in a quiet and dark environment, 180 MBq of 18 F-fluorodeoxyglucose were intravenously injected as a bolus. A 10-min PET acquisition scan began 50 min after injection. PET images were coregistered on their corresponding anatomical MRI, voxel-wise corrected for partial volume effects using the three-compartmental voxel-wise Müller-Gärtner method 1 , and were then normalized to the MNI template using deformation parameters derived from the anatomical MRI. Resulting images were scaled using cerebellar grey matter as a reference. A smoothing kernel of 10 mm Gaussian filter was applied and images were masked to exclude non-grey matter voxels from the analyses. PVE-corrected normalized and scaled Florbetapir-PET images were also used to extract the individual global cortical amyloid standard uptake value ratio (SUVr) using a predetermined neocortical mask including the entire grey matter, except the cerebellum, occipital and sensory motor cortices, hippocampi, amygdala and basal nuclei 2 . The threshold for amyloid positivity was defined as >0.99, and corresponded to the 99.9 th percentile of the neocortical SUVr distribution among 45 healthy young individuals, aged <40 years.

Polysomnography recording

Twenty EEG electrodes were placed over the scalp (Fp1, Fp2, F3, F4, F7, F8, Fz, C3, C4, Cz, T3, T4, P3, P4, Pz, O1, O2, vertex ground, and a bi-mastoid reference) according to the international 10-20 system, with impedances kept below 5 kΩ.

Figure 1 )

 1 Figure 1), sponsored by the French National Institute of Health and Medical Research

Figure 2 ,

 2 Figure 2, and cluster peak statistics and coordinates are detailed in eTable 1 in the

  The Age-Well RCT is part of the Medit-Ageing project funded through the European Union's Horizon 2020 research and innovation program (grant agreement N °667696), INSERM, Région Normandie, and Fondation d'entreprise MMA des Entrepreneurs du Futur. CA was funded by INSERM, Région Normandie, and the Fonds Européen de Développement

Figures.

  Figures.

Figure 1 :

 1 Figure 1: Flow diagram of the inclusion process. Abbreviations: APOE, Apolipoprotein E; FDG, 18 F-fluorodeoxyglucose; MRI, Magnetic

Figure 2 :

 2 Figure 2: Neuroimaging pattern of the significant differences between SDB+ and SDB-

Figure 3 :

 3 Figure 3: Overlap of SDB-related brain changes in SDB+ compared to SDB-

Table 1 : Participant characteristics and between-group differences.

 1 SDB, sleep-disordered breathing; STAI-B, State-Trait Inventory form B; SUVr, Standard Uptake Value ratio; TST, Total Sleep Time.

	SDB-	SDB+	Between-group
	(n=31)	(n=96)	differences a

Mattis Dementia Rating Scale; MMSE, Mini Mental State Examination; NREM-1: non-rapid eye movement sleep stage 1; ns, non-significant; PSQI, Pittsburgh Sleep Quality Index; SD, standard deviation;

Table 2 : Forward stepwise regressions predicting SDB-related brain changes.

 2 Results of partial correlation analyses between SDB parameters and SDBrelated brain changes with cognitive and behavioural scores.

	Dependent variable	Model	Predictor	Unstandardized coefficient	Standardized coefficient	95% CI	R²	P-value
	Amyloid burden	1	(intercept)	0.88		[0.85 -0.91]		<.001
			Hypoxia composite	0.06	0.28	[0.02 -0.10]	0.08	.002
		2	(intercept)	0.86		[0.82 -0.90]		<.001
			Hypoxia composite	0.06	0.26	[0.02 -0.10]		.004
			APOE4 status	0.07	0.18	[0.001 -0.14]	0.11	.05
		Full model					0.16	.02
	GM volume	1	(intercept)	0.77		[0.76 -0.78]		<.001
			AHI	0.01	0.19	[ 5.718×10 -4 -0.02]	0.04	.04
		Full model					0.11	.20
	Abbreviations: AHI, apnea-hypopnea index; APOE; apolipoprotein E; GM, gray matter.

Results of between-group comparisons using a ROI approach for PET data.

  Participants also underwent an electrooculogram, electrocardiogram, and chin electromyogram. Respiratory movements, airflow, and oxygen saturation were recorded respectively with thoracic and abdominal belts, nasal and oral thermistors, and a finger pulse oximeter. The EEG signal was digitalized at a sampling rate of 256 Hz. High-pass and low-pass filters were applied, respectively at 0.3Hz and 35Hz. : AAL, Automated Anatomical Labelling; FDG,[START_REF] Bu | Serum amyloid-beta levels are increased in patients with obstructive sleep apnea syndrome[END_REF] F-fluorodeoxyglucose, L, left; PCC, posterior cingulate cortex; PVE, partial volume effect; R, right; ROI, region of interest. Results of between-group comparisons (SDB+>SDB-) for amyloid burden (late Florbetapir-PET, n=125), brain perfusion (early Florbetapir-PET, n=124) and glucose metabolism (FDG-PET, n=87) data, extracted from PVE-corrected and uncorrected PET images in standardized ROIs of the AAL Atlas overlapping with the significant clusters obtained in the voxel-wise analyses. The "composite" ROI is a meta-ROI comprising all the individual AAL ROIs listed below (i.e., left and right PCC, cuneus, precuneus, lingual and calcarine regions). The statistical threshold for significance was set to p<0.05, and significant results are indicated in bold.

	Cluster extent voxels mm 3 Lingual R Calcarine L Calcarine R Composite Region of Interest coordinates MNI x y z 3.22 9.05 4.13 5.04 F PCC L 7.78 829 2 798 0 -63 20 Precuneus L 4.03 4 699 15 859 -10 -78 6 Cuneus R 4.21 Cuneus L 3.58 PCC R 1.59 PCC L 1.94 4 295 14 496 -3 -68 12 Late Florbetapir-PET (uncorrected Brain areas FDG-PET (uncorrected for PVE) eTable 3. Imaging modality MRI B precuneus, posterior cingulate Early Florbetapir-PET L calcarine, L lingual, B precuneus, B posterior and B calcarine, B lingual, B L calcarine, L precuneus, L posterior cingulate, L cuneus Late Florbetapir-PET cingulate for PVE) precuneus, B posterior Composite 3.85 Calcarine R 3.45 FDG-PET Calcarine L 8.81 middle cingulate 3 946 13 318 -6 -76 6 Late Florbetapir-PET (PVE-corrected) Composite 4.77 PCC R 8.48 PCC L 4.88 Cuneus L 4.69 PCC R 4.62 Cuneus R 4.62 Cuneus L 7.07 Precuneus L 4.01 Cuneus R 5.35 Precuneus R 5.03 Precuneus L 4.23 Lingual L 3.56 Precuneus R 4.17 Lingual R 2.68 Lingual L 5.38 Calcarine L 5.62 Lingual R 0.66 Calcarine R 3.66	T-value .08 .004 .05 .03 p Partial eta-squared p FWE-corrected 0.04 0.10 0.05 0.06 .007 0.09 Effect size (Cohen's d) 4.12 .04 .75 .05 0.03 4.51 .04 .04 0.04 .83 .06 0.03 .21 0.01 .17 0.02 4.63 .001 .05 0.03 1.04 .07 0.03 .004 0.07 4.62 .001 .86 .03 .005 0.10 0.04 .03 .03 0.06 0.04 .03 .04 0.06 0.04 .01 .05 0.05 0.06 .02 .03 0.06 0.04 .04 .06 0.04 0.04 .04 .10 0.03 0.03 .02 .02 0.07 0.04 .42 0.01 .06 0.04
		Precuneus R	3.85	.05	0.03
		Lingual L	4.26	.04	0.04
		Lingual R	2.61	.11	0.02
		Calcarine L	3.68	.06	0.03
		Calcarine R	3.59	.06	0.03
	Early Florbetapir-PET (PVE-	Composite	9.12	.003	0.07
	corrected)	PCC L	8.90	.004	0.07
		PCC R	10.55 .002	0.08
		Cuneus L	4.88	.03	0.04
		Cuneus R	3.00	.09	0.03
		Precuneus L	6.34	.01	0.05
		Precuneus R	7.98	.01	0.06
		Lingual L	8.00	.01	0.06
		Lingual R	5.35	.02	0.04
		Calcarine L	12.50 .001	0.10
		Calcarine R	4.05	.05	0.03
	Early Florbetapir-PET	Composite	6.74	.01	0.06
	(uncorrected for PVE)	PCC L	7.41	.01	0.06
		PCC R	9.12	.003	0.07
		Cuneus L	3.52	.06	0.03
		Cuneus R	2.90	.09	0.02
		Precuneus L	5.23	.02	0.04
		Precuneus R	6.17	.01	0.05
		Lingual L	7.27	.01	0.06
		Lingual R	5.27	.02	0.04
		Calcarine L	8.58	.004	0.07
		Calcarine R	4.17	.04	0.04
	FDG-PET (PVE-corrected)	Composite	6.98	.01	0.08
		PCC L	9.39	.003	0.11
		PCC R	10.31 .002	0.12
		Cuneus L	5.99	.02	0.07
		Cuneus R	5.28	.02	0.06
		Precuneus L	4.60	.04	0.06
		Precuneus R	5.70	.02	0.07
		Lingual L	4.90	.03	0.06

eTable 1. Detailed statistics of significant neuroimaging clusters. Abbreviations: B, bilateral; FDG, 18 F-fluorodeoxyglucose, L, left; MNI, Montreal Neurological Institute; MRI: magnetic resonance imaging. Results were obtained at a p<0.005 (uncorrected) threshold and only clusters surviving a FWE cluster-level correction are reported. AbbreviationseTable 4.

Results of complementary forward stepwise regression analyses.

  : AAL, Automated Anatomical Labelling; ROI, Region of Interest; SUVr, Standard Uptake Value ratio.

	Imaging	Model Predicto	Unstandardize	Standardize	R²	p	Lower	Upper
	modalit		r	d coefficient	d coefficient			95%	95% CI
	y							CI
	Neocorti	1	(Intercep	0.97			<.001	0.94	1.01
	cal		t)
	amyloid		Hypoxia	0.06	0.23	0.0	.01	0.01	0.11
	SUVr		composit			5
			e
		2	(Intercep	0.95			<.001	0.91	0.99
			t)
			Hypoxia	0.06	0.22		.02	0.01	0.10
			composit
			e
			ApoE4	0.09	0.19	0.0	.04	0.01	0.17
			status			9
		Full				0.1	.07
		model				3
	GM	1	(Intercep	0.72			< .001	0.68	0.76
	volume		t)
	extracte		BMI	-0.003	-0.32	0.1	< .001 -0.004	-0.001
	d from					0
	the	2	(Intercep	0.72			< .001	0.69	0.76
	composit		t)
	e AAL		BMI	-0.002	-0.31		< .001 -0.004	-0.001
	ROI		Sex	-0.02	-0.24	0.1	.01	-0.03	-0.005
						5
		3	(Intercep	0.83			< .001	0.72	0.94
			t)
			BMI	-0.003	-0.32		< .001 -0.004	-0.001
			Sex	-0.02	-0.23		.01	-0.03	-0.005
			Age	-0.002	-0.17	0.1	.05	-0.003 -6.404e -6
						9
		4	(Intercep	0.85			< .001	0.73	0.96
			t)
			BMI	-0.003	-0.34		< .001 -0.004	-0.001
			Sex	-0.02	-0.26		.002	-0.03	-0.007
			Age	-0.002	-0.19		.03	-0.003 -1.975e -4
			AHI	0.007	0.19	0.2	.03	6.235e	0.01
						2		-4
		Full				0.2	<.001
		model				5

Abbreviations

Régional (FEDER). Complementary funding sources were obtained from the Fondation LECMA-Vaincre Alzheimer (grant n°13732) and the Fondation Thérèse et René Planiol.

Funding sources were not involved in the design and conduct of the study; collection, management, analysis and interpretation of the data; preparation, review, or approval of the manuscript; and decision to submit the manuscript for publication. Drs Chételat and Rauchs had full access to all the data in the study and take responsibility for the integrity of the data and the accuracy of the data analysis.

eAppendix. Methods

Neuropsychological scores

To obtain robust proxies of cognitive abilities and minimize the issue of multiple statistical testing, composite scores were used for each cognitive domain, instead of multiple (sub)tests. For that purpose, performance on various cognitive tests were z-transformed and averaged as follows. Please note that before averaging, Z-scores derived from reaction times and percentages/number of error were reversed so that increasing values always indicated better performance.

Neuroimaging procedure

All participants were scanned at the Cyceron Center (Caen, France) on the same MRI (Philips Achieva 3.0T scanner) and PET (Discovery RX VCT 64 PET-CT scanner, General Electric Healthcare) cameras. During the MRI session, subjects were equipped with earplugs and their head was stabilized with foam pads in order to minimize head motion.

Structural MRI

A high-resolution T1-weighted anatomical image was acquired using a 3D fast-field echo sequence (3D-T1-FFE sagittal, repetition time =7.1 ms, echo time = 3.3 ms, flip angle = 6°, 180 slices with no gap, slice thickness = 1mm, field of view = 256x256 mm², in-plane resolution= 1x1x1 mm 3 ). T1-weighted images were segmented using FLAIR images (3D-IR sagittal, TR/TE/TI = 4800/272/1650 ms ; flip angle = 40°; 180 slices with no gap; slice thickness = 1 mm; field of view = 250x250 mm 2 ; in-plane resolution = 0.98x0.98 mm 2 ), spatially normalized to the Montreal Neurological Institute (MNI) template, modulated using the SPM12 segmentation procedure (http://www.fil.ion.ucl.ac.uk) and smoothed with an 8 mm full-width at half-maximum (FWHM) Gaussian filter. Images were then masked to exclude non-grey matter voxels from the analyses.

PET imaging eTable Results of inter-modality correlations.

Neuroimaging modality Brain perfusion

Amyloid

Glucose metabolism

GM volume

Brain perfusion

Pearson


Aurélie Bauer
email: aurelie.bauer@ssi.gouv.fr

Damien Vergnaud

Practical Key Recovery for Discrete-Logarithm Based Authentication Schemes from Random Nonce Bits

Keywords: Schnorr identification, Girault-Poupard-Stern identification, Girault-Poupard-Stern signatures, statistical cryptanalysis

We propose statistical cryptanalysis of discrete-logarithm based authentication schemes such as Schnorr identification scheme or Girault-Poupard-Stern identification and signature schemes. We consider two scenarios where an adversary is given some information on the nonces used during the signature generation process or during some identification sessions. In the first scenario, we assume that some bits of the nonces are known exactly by the adversary, while no information is provided about the other bits. We show, for instance, that the GPS scheme with 128-bit security can be broken using only 710 signatures assuming that the adversary knows (on average) one bit per nonce. In the second scenario, we assume that all bits of the nonces are obtained from the correct ones by independent bit flipping with some small probability. A detailed heuristic analysis is provided, supported by extensive experiments.

Introduction

Since the introduction of the ElGamal signature scheme [START_REF] Elgamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF], many works have been devoted to design digital signatures and identification schemes, based on the discrete logarithm problem in a finite cyclic group G of order q (e.g. [START_REF] Horster | Meta-El-Gamal signature schemes[END_REF]). After Schnorr's proof of knowledge for discrete logarithms in groups of known prime order [START_REF] Schnorr | Efficient signature generation by smart cards[END_REF] (that can be used as an interactive identification scheme or be converted into a digital signature scheme using the Fiat-Shamir paradigm [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF]), many other signature schemes have been designed, including the standard DSA [START_REF]FIPS PUB 186-2: Digital Signature Standard (DSS)[END_REF]. Another variant, proposed by Girault [START_REF] Girault | Self-certified public keys[END_REF] and further analysed by Poupard and Stern [START_REF] Poupard | On the fly signatures based on factoring[END_REF][START_REF] Girault | On the fly authentication and signature schemes based on groups of unknown order[END_REF] -called GPS -allows to use groups of unknown order.

All these signature and identification schemes perform randomized authentication: they use a nonce (or ephemeral key) r in {0, 1, . . . , q -1} for each message (or identification session) and compute g r with g some generator of G. These random nonces can be generated using either a (true) random number generator or a pseudo-random one. Obviously extreme care is required in sampling such nonces since a predictable (or reused) output of the (pseudo)random generator may lead to a total break of the scheme. As an example, Bellare, Goldwasser and Micciancio mounted [START_REF] Bellare | pseudo-random" number generation within cryptographic algorithms: The DDS case[END_REF] a polynomial time key-recovery attack against the DSA signature scheme when the random nonces are generated using a (truncated) linear congruential generator. In [START_REF] Bleichenbacher | On the generation of one-time keys in dl signature schemes[END_REF], Bleichenbacher found a bias in the original DSA pseudorandom number generator specification, that could reveal the signer's private key and this attack was made practical recently [START_REF] Mulder | Using Bleichenbacher's solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA[END_REF]. .

Using side-channel attacks, partial information can be obtained on the nonce r from the run of the algorithm that computes g r . In [START_REF] Kuwakado | On the security of the elgamal-type signature scheme with small parameters[END_REF], Kuwakado and Tanaka proposed a polynomial-time algorithm that recovers the signer's private key given only two signatures with nonces smaller than √ q or where half of the nonces' bits are known to the adversary. Nguyen and Shparlinski [START_REF] Phong | The insecurity of the digital signature algorithm with partially known nonces[END_REF] presented a polynomialtime algorithm that recovers the secret key of the signer when a few consecutive bits of the nonces are known for several signatures. Their algorithm runs in polynomial time when approximately √ log q bits are known for a number of signatures in O(log q). Note that in practice, side-channel attacks will not generally reveal consecutive bits of the nonces used. Moreover, if countermeasures are used, only noisy information on the secrets may leak through power consumption (or other side-channel attacks) and an adversary may obtain partial information on the nonces (but not with perfect certainty).

In [START_REF] Halderman | Lest we remember: Cold boot attacks on encryption keys[END_REF], it was reported that memory persistence times can be increased with simple cooling techniques and that an attacker with physical access to a machine may be able to recover some random part of cryptographic key information. Motivated by this work, Heninger and Shacham presented in [START_REF] Heninger | Reconstructing RSA private keys from random key bits[END_REF] a new method for recovering RSA private keys given a fraction of private data (see also [START_REF] Percival | Cache missing for fun and profit[END_REF]). Their method succeeds with good probability in quadratic time if a fraction of at least 0.27 of the private key bits are known with certainty. In [START_REF] Henecka | Correcting errors in RSA private keys[END_REF], Henecka, May and Meurer addressed the situation where no RSA private key bits are known with certainty but where a candidate for each secret key bit is known to the adversary in such a way that most bits are correct but some of them (unknown to the adversary) are flipped (in a symmetric way). In [START_REF] Kenneth | A codingtheoretic approach to recovering noisy RSA keys[END_REF], Paterson, Polychroniadou and Sibborn brought a coding-theoretic viewpoint to bear on this problem. In particular, they highlighted the fact that the papers [START_REF] Heninger | Reconstructing RSA private keys from random key bits[END_REF] and [START_REF] Henecka | Correcting errors in RSA private keys[END_REF] considered the problem of error-correcting noisy RSA private keys in the binary erasure channel and the binary symmetric channel (respectively). This coding-theoretic viewpoint enabled them to design a new algorithm in another channel model more relevant for the so-called "cold-boot attacks" from [START_REF] Halderman | Lest we remember: Cold boot attacks on encryption keys[END_REF] and to derive bounds on the performance of the proposed algorithms.

Contributions of the paper. We propose attacks on discrete-logarithm based authentication schemes where an adversary has some information on the nonces used in the signature generation or in some identification sessions. This information may come from the use of a biased (pseudo)random generator, a side-channel attack or a cold-boot attack. Using the coding-theoretic viewpoint from [START_REF] Kenneth | A codingtheoretic approach to recovering noisy RSA keys[END_REF], we consider the following two scenarios:

erasure correction scenario: we assume that some bits of the nonces are known exactly by the adversary, while no information at all is known about the other bits. This is defined in terms of a parameter δ representing the fraction of erasures. In standard coding terminology, this corresponds to an erasure model for errors, and an erasure channel. error correction scenario: we assume that all bits of the nonces are obtained from the correct ones by independent bit flipping with probability defined by a parameter also denoted δ. In coding-theoretic terms, this corresponds to a (memoryless) binary symmetric channel with crossover probability δ.

Our attacks apply to discrete-logarithm based authentication schemes where the "authentication relation" holds over the integers (instead of modulo the group order q). In particular, they can be applied readily to the GPS identification and the GPS signature schemes. However, they can also be mounted against Schnorr identification protocol if the adversary is first allowed to interact with the prover in a "dishonest" way before trying to impersonate her. In this active attack model [START_REF] Feige | Zero-knowledge proofs of identity[END_REF][START_REF] Bellare | GQ and Schnorr identification schemes: Proofs of security against impersonation under active and concurrent attacks[END_REF], which is the standard de facto security notion, an adversary can simply choose small challenges in the identification session in order to obtain an authentication relation that holds over the integers (after a small brute force search of the size of the chosen challenge).

In the erasure correction scenario, we provide an algorithm that, given t signatures or identification sessions (with t ≥ 2) and partial information on the corresponding nonces with a fraction of erasures δ ln(2)/t, recovers the corresponding secret key in (heuristic) quadratic time. The algorithm recovers the nonces bit-by-bit, starting from the least significant bit to the most significant one, by growing a search tree and pruning it to remove partial solutions which do not match the known key bits. The algorithm is similar to the one proposed in [START_REF] Heninger | Reconstructing RSA private keys from random key bits[END_REF] but works for any t ≥ 2 and requires a more complex analysis. We implemented it and performed extensive experiments; in particular, we attack a 128-bit security level instantiation of GPS signature scheme that uses 512-bit nonces [START_REF] Poupard | On the fly signatures based on factoring[END_REF][START_REF] Girault | On the fly authentication and signature schemes based on groups of unknown order[END_REF] with δ 1/512 (i.e. with on average only one nonce bit known for each signature). Our analysis guarantees that the private key can be recovered given only 710 signatures and a very naive implementation actually gives the secret key in a few minutes. In the error correction scenario, we provide an algorithm that, given t signatures or identification sessions (with t ≥ 2) and partial information on the corresponding nonces with a fraction of errors δ 1/2 -ln(2)/2t, recovers the corresponding secret key in (heuristic) quadratic time. We implemented our algorithm and performed extensive experiments using it. The attack analysis is simpler and follows closely the one presented in [START_REF] Henecka | Correcting errors in RSA private keys[END_REF].

Preliminaries

Schnorr Identification. Let G = g be a group of (known) prime order q and P and V denote a prover and a verifier. By engaging in the protocol, P proves to V that she knows the discrete logarithm x of a public group element y = g x . The protocol has three simple moves:

Commitment P selects a random r ∈ {0, 1, . . . , q -1} and sends k = g r to V . Challenge V picks a random c ∈ {0, 1, . . . , q -1} and sends c to P . Response P computes and sends s = r + cx mod q to V .

Eventually, V checks that g s • y -c = k and recognizes that P knows x if the equality holds. Schnorr's scheme is one of the most important ingredients in the design of cryptographic protocols and proofs of knowledge. It readily gives rise to an identification scheme where P proves her knowledge of the discrete logarithm of her public key.

The strongest form of attack against an identification scheme is an active attack, where the adversary (that wants to impersonate P ) interacts with P , posing as V , but not necessarily following V 's protocol. Since active attacks are quite feasible in practice, this model has become the standard de facto security notion for identification scheme. In [START_REF] Bellare | GQ and Schnorr identification schemes: Proofs of security against impersonation under active and concurrent attacks[END_REF], Bellare and Palacio proved that Schnorr identification scheme is secure against active attacks assuming the one-more discrete logarithm assumption in G (see [START_REF] Bellare | The one-more-RSA-inversion problems and the security of Chaum's blind signature scheme[END_REF]).

GPS Identification and Signature scheme. The GPS schemes were proposed by Girault in [START_REF] Girault | Self-certified public keys[END_REF] and further analysed by Poupard and Stern [START_REF] Poupard | On the fly signatures based on factoring[END_REF][START_REF] Girault | On the fly authentication and signature schemes based on groups of unknown order[END_REF]. The schemes are similar to Schnorr's but allow to use groups of unknown order. Given a group G = g generated by g, of (possibly) unknown order and three parameters R, S, C ∈ N, the protocol has three simple moves to prove the knowledge of x ∈ {0, . . . , S} such that y = g x : Commitment P selects a random r ∈ {0, 1, . . . , R} and sends k = g r to V . Challenge V picks a random c ∈ {0, 1, . . . , C} and sends c to P . Response P computes and sends s = r + cx to V .

Eventually, V checks that g s = ky c and recognizes that P knows x if the equality holds and s ∈ {0, 1, . . . , R + CS}. GPS signature scheme is derived from the identification scheme using the Fiat-Shamir heuristic [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF]: to sign a message m ∈ {0, 1} * , the signer selects a random r ∈ {0, 1, . . . , R}, computes k = g r , computes c = H(m, k) where H : {0, 1} * -→ {0, 1, . . . , C} is a cryptographic hash function and outputs the pair (s, c) where s = r + cx as the signature of the message m. The security of the signature scheme against existential forgeries under chosen message attacks was proven (when H is modelled as a random oracle) in [START_REF] Girault | On the fly authentication and signature schemes based on groups of unknown order[END_REF] under the assumption that computing discrete logarithms in G with exponents in {0, 1, . . . , S} is hard. For a k-bit security level, the analysis requires to use S 2 2k , C 2 k and R 2 4k . Authentication relation. In the following, we call the authentication relation of a discrete-logarithm based authentication scheme, the relation used in the Response phase of the three-move identification scheme (or in the signature generation protocol). Our attacks apply to all discrete-logarithm based authentication scheme for which this authentication relation holds over the integers. This is obviously the case for GPS identification and signature schemes. However, our attack also applies to Schnorr identification if one considers an adversary allowed to mount an active attack and that has access to partial information on the nonce bits used in the different identification sessions. Such an adversary posing as V can indeed pick small challenges c (e.g. always c = 1). Since we have s = r + cx mod q in Schnorr identification scheme, we obtain s = r + cx + αq, where α ∈ Z -and |α| ≤ c. By performing an exhaustive search on the small set of values for α (e.g. α ∈ {-1, 0} when c = 1), the adversary obtains an authentication relation that holds over the integers.

Note that for all these discrete-logarithm based schemes, the knowledge of the random values generated during the signature process/identification session provides precious information on the signer's secret key. In particular, if an adversary is given access to a valid signature/identification transcript σ = (s, c) (possibly for some message m), and to the nonce r such that g s = g r y c then he can retrieve the value of the signer's secret key x in polynomial time. Therefore, in the following, we will focus on attacks that aim to recover a complete nonce from partial information on nonces used in several signatures/identification sessions.

Erasure correction scenario

In this section, we focus on the erasure correction scenario described in the introduction where part of the bits of the random value r generated during the signature process are revealed to the attacker. To be more precise, we denote the binary decomposition of r as r 0 + r 1 2 1 + • • • + r n-1 2 n-1 and we introduce a parameter δ, with 0 ≤ δ ≤ 1, to define the probability that, at a given position i ∈ {0, . . . , n -1}, the bit r i is known to the adversary (and probability (1 -δ) that bit r i is unknown).

Assuming that t signatures have been processed, we determine a lower-bound on δ allowing the attacker to fully recover the secret key x in (heuristic) polynomial time. We focus on the particular case of the GPS signature scheme, but as explained previously any other signature or identification scheme using authentication relations defined over the integers can be attacked similarly. In the following we first focus on the simple case of two signatures, and then generalize the study for a higher number of signatures.

The Attack Knowing Two Signatures

We assume that the adversary is given access to two valid signatures σ 1 = (s 1 , c 1 ) and σ 2 = (s 2 , c 2 ), respectively related to the messages m 1 and m 2 . According to the description of the GPS scheme, provided in Section 2, the following relations hold:

s 1 = r 1 + c 1 x and s 2 = r 2 + c 2 x (1)
where r 1 and r 2 are nonces generated during the signature process and c i = H(m i , g ri ) (for i ∈ {1, 2}). Eliminating the unknown x in (1), we get:

C = r 1 c 2 -r 2 c 1 (2)
where C = s 1 c 2 -s 2 c 1 . Our algorithm will construct all pairs (ϑ 1 , ϑ 2 ) that satisfy (2) and the match the known partial information on (r 1 , r 2 ) -in the sequel we denote as L the list of such elements -and eventually, select, among them, the one that verifies the relations (1).

General Idea. Following [START_REF] Heninger | Reconstructing RSA private keys from random key bits[END_REF], our method to construct the set L consists in performing an exhaustive search on all pairs (ϑ 1 , ϑ 2 ) satisfying Equation ( 2), guessing each of their bits from the least significant one to the most significant, and detecting invalid candidates during the process. Given a pair (ϑ 1 , ϑ 2 ) for which the relation ( 2) holds, if we denote ϑ

(i) α = ϑ α,0 + 2ϑ α,1 + • • • + ϑ α,i 2 i where ϑ (i) α = ϑ α mod 2 i+1
and ϑ α,j ∈ {0, 1} for α ∈ {1, 2} and j ∈ {0, . . . , i}, we get:

         C = ϑ 1,0 c 2 -ϑ 2,0 c 1 mod 2 C = (ϑ 1,0 + 2ϑ 1,1 )c 2 -(ϑ 2,0 + 2ϑ 2,1 )c 1 mod 2 2 . . . C = ( n-1 i=0 ϑ 1,i 2 i )c 2 -( n-1 i=0 ϑ 2,i 2 i )c 1 mod 2 n (3)
Thus one can verify, at each step of the bit generations of ϑ 1,i and ϑ 2,i , for i from 0 to (n -1), whether the equation modulo 2 i+1 of System (3) holds for the pair. If not, the corresponding bit-values for (ϑ 1,i , ϑ 2,i ) are not kept as valid ones in the sequel of the bit-generations of (ϑ 1,j , ϑ 2,j ) for j going from (i + 1) to (n -1). This technique allows to reduce the size of the list L containing all final potential candidates (ϑ 1 , ϑ 2 ). In the following, we show that, in fact, this method leads to a polynomial time algorithm.

Description of the Technique. Let us now explain how to construct the list L. In the analysis that follows, we use the notation L (k) to refer to the state of list L at step k of the Algorithm. Such a list will be defined as containing elements (ϑ 1 , ϑ 2 ) that are reduced modulo 2 k+1 . The basic principle of the algorithm can be sum up that way: the list L (0) is first initialized with all pairs of bits (ϑ 1,0 , ϑ 2,0 ) that satisfy Equation 1of System (3) modulo 2 and that coincide with the bit-values preliminary known by the adversary on r 1 and r 2 . All pairs (ϑ 1,0 , ϑ 2,0 ) in L (0) are then lifted to construct values modulo 2 2 . To do so, one has to generate all possible values for pairs of bits (ϑ 1,1 , ϑ 2,1 ) (which again coincide with the bits known by the adversary on r 1,1 and r 2,1 ) and to construct ϑ 2 respectively as ϑ 1,0 +2ϑ 1,1 and ϑ 2,0 +2ϑ 2,1 . From now the obtained values (ϑ

(1) 1 , ϑ (1)
2 ) are checked to determine whether they satisfy Equation 2of System (3) modulo 2 2 . In case of an invalid answer, the corresponding bit-values for (ϑ 1,1 , ϑ 2,1 ) are evicted and all remaining valid pairs (ϑ

(1) 1 , ϑ (1)
2 ) are put in L (1) . The process then continues from a bit-position i to the following one, taking all pairs (ϑ

(i) 1 , ϑ (i)
2 ) belonging to L (i) at step i, lifting them by generating all possible bit-pairs (ϑ 1,i+1 , ϑ 2,i+1 ) that coincide with the known bits on r 1,i+1 and r 2,i+1 and by creating new values ϑ

(i+1) 1 = ϑ (i) 1 +2 i+1 ϑ 1,i+1 and ϑ (i+1) 2 = ϑ (i) 2 + 2 i+1 ϑ 2,i+1
, and checking whether Equation (i + 2) of System (3) is satisfied modulo 2 i+2 . Again, invalid solutions are evicted and the remaining pairs constitute the set L (i+1) . The algorithm finally stops when i equals n. A description of the whole process is provided in Algorithm 1.

Algorithm 1 Generic Attack on Two Signatures

Require: c1, c2, C and δ : partial bit information on r1 and r2 Ensure: L a list of pairs (ϑ1, ϑ2) possible candidates for (r1, r2)

1: L (0) = {} 2:
--/* Initialisation -Case i = 0 */--3: Generate all bit pairs for (ϑ1,0, ϑ2,0): E = (0, 0), (1, 0), (0, 1), (1, 1) 4: for each element (ϑ1,0, ϑ2,0) ∈ E do 5:

if (ϑ1,0, ϑ2,0) coincides with knowledge of (r1,0, r2,0) then

6:

if (ϑ1,0, ϑ2,0) satisfies Equation (1) of System (3) modulo 2 then

7:

Add element (ϑ1,0, ϑ2,0) to L (0)

8:

--/* Main loop for i from 1 to n -1 */--9: for i from 1 to n -1 do 10:

L (i) = {}

11:

Generate all bit pairs for (ϑ1,i, ϑ2,i): E = (0, 0), (0, 1), (1, 0), (1, 1)

12:

for each element (ϑ1,i, ϑ2,i) ∈ E do

13:

if (ϑ1,i, ϑ2,i) coincides with knowledge of (r1,i, r2,i) then

14:

for each element (ϑ

(i-1) 1 , ϑ (i-1) 2 ) ∈ L (i-1) do 15: Lift ϑ (i) 1 = ϑ (i-1) 1 + 2 i ϑ1,i and Lift ϑ (i) 2 = ϑ (i-1) 2 + 2 i ϑ2,i 16: if (ϑ (i) 1 , ϑ (i) 2 ) satisfies Equation (i + 1) of System (3) modulo 2 i+1 then 17: Add (ϑ (i) 1 , ϑ (i) 2 ) to L (i) 18: return L (n-1)
Complexity Analysis. Estimating the overall complexity of Algorithm 1 can be reduced to the cost of constructing the list L (n-1) . Since this list has been built recursively from the previous ones L (n-2) , L (n-3) , . . . , L (0) , we have to evaluate the expected cardinal of all L (i) for i going from 0 to (n -1) (denoted N (i) ).

Let us first count the number of elements belonging to L (0) . By definition, this list contains all bit pairs (ϑ 1,0 , ϑ 2,0 ) coinciding with the (possible) knowledge of (r 1,0 , r 2,0 ) and satisfying Equation (1) of System (3). In fact, the number of solutions to that equation strongly relies on the parity of both c 1 and c 2 . Indeed, two even values would give four pairs of solutions (in the general case) opposed to only two for odd values c 1 and c 2 . For this reason, we have to split the analysis that follows in two scenarios, depending on the 2-adic valuation 1 of both c 1 and c 2 . In the sequel, we denote as 1 (resp. 2 ) the 2-adic valuation of c 1 (resp. c 2 ).

• First analysis when 1 = 2 Before coming back to the evaluation of the cardinality of the list L (0) , let us first see how the relation 1 = 2 impacts the shape of the equations belonging to System (3). When 1 and 2 are equal, Equation (2) can be simplified by dividing both sides of the equality by 2 1 . Indeed as this can be done for c 1 and c 2 , this is obviously also the case for C. Thus, the shape of the relation does not change and the new obtained constants c 1 /2 1 and c 2 /2 1 are odd. In the following, for the sake of simplicity (and as this does not change the analysis, at the cost of renaming the variables), we still work with Equation (2) (and thus with System ( 3)) but assuming that the constants c 1 and c 2 are odd.

From now on, one can easily describe the elements that belong to L (0) as bit-values of the form (ϑ 1,0 , ϑ 2,0 ) satisfying C = ϑ 1,0 + ϑ 2,0 mod 2, and such that (ϑ 1,0 , ϑ 2,0 ) coincide with possible knowledge of (r 1,0 , r 2,0 ). This description allows to evaluate N (0) , see Lemma 1 (a proof can be found in the full version of the paper [START_REF] Bauer | Practical key recovery for discrete-logarithm based authentication schemes from random nonce bits[END_REF]).

Lemma 1. We have

N (0) = δ 2 -2δ + 2.
We now have to find, for a fixed i between 1 and (n -1), an expression of N (i) in function of N (i-1) . By definition L (i) can be described as the set of elements (ϑ

(i) 1 , ϑ (i)
2 ) defined as ϑ

(i) 1 = ϑ (i-1) 1 + 2 i ϑ 1,i and ϑ (i) 2 = ϑ (i-1) 2 + 2 i ϑ 2,i with (ϑ (i-1) 1 , ϑ (i-1) 2
) ∈ L (i-1) , (ϑ 1,i , ϑ 2,i ) ∈ {0, 1} 2 and satisfying Equation (i+1) of System (3), namely:

C = (ϑ (i-1) 1 + 2 i ϑ 1,i )c 2 -(ϑ (i-1) 2 + 2 i ϑ 2,i )c 1 mod 2 i+1 (4)
Moreover, the pairs (ϑ 1,i , ϑ 2,i ) should coincide with possible information on (r 1,i , r 2,i ). Knowing that (ϑ

(i -1) 1 , ϑ (i-1) 2
) belong to L (i-1) , the relation

C = ϑ (i-1) 1 c 2 -ϑ (i-1) 2
c 1 mod 2 i necessarily holds. As a consequence, there exists an integer k ∈ Z such that C = ϑ

(i-1) 1 c 2 -ϑ (i-1) 2 c 1 + k2 i .
Putting this relation into Equation (4) and simplifying the whole expression allows to reach the following new condition:

k = ϑ 1,i + ϑ 2,i mod 2 (5)
The choice of (ϑ 1,i , ϑ 2,i ) solutions to [START_REF] Bleichenbacher | On the generation of one-time keys in dl signature schemes[END_REF] and coinciding with possible information on (r 1,i , r 2,i ), strongly depends on whether (ϑ

(i-1) 1 , ϑ (i-1) 2
) equals (r

(i-1) 1 , r (i-1) 2
) or not. Indeed, if these values are equal, namely (ϑ

(i-1) 1 , ϑ (i-1) 2
) is the beginning of the right solution, then when r 1,i and r 2,i are known, Equation (5) necessarily holds (obviously as this is the searched solution). In that case, one will choose (ϑ 1,i , ϑ 2,i ) = (r 1,i , r 2,i ). To the contrary, when (ϑ

(i-1) 1 , ϑ (i-1) 2 ) = (r (i-1) 1 , r (i-1) 2
), a value is fixed for k and the knowledge of (r 1,i , r 2,i ) does not necessarily make Equation (5) be satisfied. In that case, the choice (r 1,i , r 2,i ) will not be maintained. As we cannot determine whether Equation ( 5) would be satisfied or not, we introduce a new parameter γ ∈ [0, 1], which is only defined when (ϑ

(i-1) 1 , ϑ (i-1) 2 ) = (r (i-1) 1 , r (i-1) 2
), corresponding to the probability that Equation (5) holds. A detailed discussion on the value of γ is given in Section 3.3 (see also the full version of the paper [START_REF] Bauer | Practical key recovery for discrete-logarithm based authentication schemes from random nonce bits[END_REF]).

We can finally express the number of elements belonging to L (i) in function of those of L (i-1) , as claimed by the following lemma.

Lemma 2. Under our heuristic, we have

N (i) = N (i-1) (γδ 2 -2δ+2)+δ 2 (1-γ).
A proof of this lemma can be found in the full version of the paper, see [START_REF] Bauer | Practical key recovery for discrete-logarithm based authentication schemes from random nonce bits[END_REF]. Combining Lemmas 1 and 2, we obtain:

N (n-1) = N (n-2) (γδ 2 -2δ + 2) + δ 2 (1 -γ) . . . = (γδ 2 -2δ + 2) n-1 (δ 2 -2δ + 2) + δ 2 (1-γ) 2δ-γδ 2 -1 (1 -(γδ 2 -2δ + 2) n-1 )
The goal of the adversary being to construct the set L (n-1) in polynomial time, this attack will only be made practical if the quantity (γδ 2 -2δ + 2) is strictly smaller than 1. In that case, the cardinality of the list L (n-1) will not grow too fast when n tends toward infinity. Since γ is unknown, we have to evaluate it in order to reach some necessary condition on δ. Setting γ to 1/2 seems to be a reasonable choice, see Section 3.3. We finally reach the condition 1 2 δ 2 -2δ+2 < 1, which is satisfied for δ > 2 -√ 2 0.59. By taking this value as a lower bound on δ, we are able to determine the expected size of the set L (n-1) , namely (3 -2 √

2)n + 1. Knowing that n refers to the bit-size of the random values generated during the signature process, we thus obtain a polynomial time complexity for our attack.

Theorem 1 (Two Signatures and 1 = 2 ). An adversary able to learn a proportion of δ = (2 -√ 2) bits of the random nonces used during the generation of two known signatures can (heuristically) break the scheme in polynomial time. In that case, the expected space required for performing the attack is (3-2 √ 2)n 2 + 1 0.17n 2 + 1.

• Second analysis when

1 = 2 .
The study is a bit more tedious here, but the analysis can be adapted to prove Theorem 2. The entire proof is provided in the full version of the paper [START_REF] Bauer | Practical key recovery for discrete-logarithm based authentication schemes from random nonce bits[END_REF].

Theorem 2 (Two Signatures and 1 < 2 ). An adversary, able to learn a proportion of δ = (2 -√ 2) bits of the random nonces used during the generation of two known signatures, can (heuristically) break the scheme in polynomial time. In that case, the expected space required for performing the attack is ( √ 2-1)n 2 + 1 0.41n 2 + 1.

When comparing Theorem 1 and Theorem 2, one notices that the lower bound on δ is the same for both cases " 1 = 2 " and " 1 < 2 ". However the space required to construct the sets L (i) is higher when 1 = 2 than in the other case. This actually impacts the efficiency of the attack since the number of constructed solutions is larger.

The Attack Knowing t Signatures

Let us now consider the case of an adversary that is given access to t signatures σ 1 , . . . , σ t corresponding to known messages m 1 , . . . , m t . We denote σ i = (s i , c i ) the signatures and r i the nonces used in their generation (s.t. c i = H(m i , g ri )) for i in {1, . . . , t}. We denote r i,j the j-th bit of r i for each j in {1, . . . , n} and i in {1, . . . , t}. We have s i = r i + c i • x for i ∈ {1, . . . , t} and we obtain:

     C 1,2 = r 1 c 2 -r 2 c 1 . . . C 1,t = r 1 c t -r t c 1 (6)
where C 1,j = s 1 c j -s j c 1 for j ∈ {2, . . . , t}. As above, our algorithm retrieves the nonces r 1 , . . . , r t by collecting all tuples (ϑ 1 , . . . , ϑ t ) satisfying System (6) and coinciding with possible knowledge on the bits r i,j . As previously, L denotes the set containing such elements2 . The complexity of the attack can thus be reduced to the cost of constructing L.

General Idea. As for the "two-signature case", a way to retrieve (r 1 , . . . , r t ) would consist in performing an exhaustive search on all bit-values r i,j , for i going from 1 to t and j from 0 to (n -1), using some possible additional information on the bits r i,j , and to detect the invalid candidates during the process. The technique consists in generating all tuples (ϑ

t ) satisfying System (6) modulo 2 k+1 and to select among them, the one that can be lifted to solutions modulo 2 k+2 . Of course, these operations should be consistent with the possible knowledge on some bits of the r i 's. In this algorithm, parameter k will vary from 0 to (n -1). At the end of the procedure, the set L (n-1) containing all elements (ϑ (n-1) 1 , . . . , ϑ (n-1) t

) satisfying System (6) modulo 2 n and coinciding with known information on the bits r i,j , is in fact the desired one: L. A precise description of the whole method is provided in Algorithm 2.

Complexity Analysis. Let us now determine the number of elements belonging to L by evaluating the expected cardinal of all L (i) for i going from 0 to (n -1) (denoted N (i) ). We start with L (0) which, by definition, contains all tuples (ϑ 1,0 , . . . , ϑ t,0 ) in {0, 1} t coinciding with possible knowledge on bits (r 1,0 . . . , r t,0 ) and verifying System (6) modulo 2. One notices that the number of such solutions strongly depends on the 2-adic valuations of c 1 , . . . , c t . For this reason, and similarly to the "two signatures case", we split the analysis in two configurations depending on whether the 2-adic valuations of c 1 , . . . , c t are all equal or not. In the rest of the paper, we denote as i the 2-adic valuation of c i (for i ∈ {1, . . . , t}).

• First analysis with

1 = 2 = • • • = t
When the 2-adic valuations are all equal, System (6) can be simplified by dividing each equation by 2 1 . One thus reaches a new system involving simpler equations, Denoting as A(γ, δ) the quantity 1 γ (γδ + 1 -δ) t + (2 -1 γ )(1 -δ) t and using the formula obtained for N (0) , we reach:

N (n-1) = (1 + (1 -δ) t )A(γ, δ) n-1 + 1 -1 γ (γδ + 1 -δ) t + ( 1 γ -1)(1 -δ) t i=0...n-2 A(γ, δ) i
The goal of the adversary being to construct the set L (n-1) in polynomial time, this attack will only be made practical if the quantity A(γ, δ) is strictly smaller than 1. In that case, the size of the list L (n-1) will not grow too fast when n tends toward infinity. Setting γ to 1/2 (see Section 3.3 for experimental results on that point) leads to the condition 2(1 -δ 2 ) t < 1, which is satisfied for δ > 2 -2 1-1/t . By taking this value as a lower bound on δ, we are able to determine the expected maximum size of the set L (n-1) , namely (2 1-1 t -1) t n + 1.

Theorem 3 (t signatures and 1 = • • • = t ). An adversary able to learn a proportion of δ = 2-2 1-1/t bits of the random nonces used in the generation of t known signatures can (heuristically) break the scheme in polynomial time. In that case, the expected space required for performing the attack is (2 1-1 t -1) t n 2 + 1.

• Second analysis when some of the i 's are different.

The analysis is more tedious here but can still be adapted to the case when some of the i 's are different, see Theorem 4 below (the proof is provided in the full version of the paper [START_REF] Bauer | Practical key recovery for discrete-logarithm based authentication schemes from random nonce bits[END_REF]).

Theorem 4 (t signatures with i different). An adversary able to learn a proportion of δ = 2-2 1-1/t bits of the random nonces used in the generation of t known signatures can (heuristically) break the scheme in polynomial time. In that case, the expected space required for performing the attack is (2 1-1 t -1) e n 2 + 1.

Remark 1. Using the coding viewpoint from [START_REF] Kenneth | A codingtheoretic approach to recovering noisy RSA keys[END_REF], one can obtain limits on the performance of any algorithm for selecting candidate nonces in the erasure correction scenario. Their argument is based on the converse to Shannon's noisychannel coding theorem 5 . The underlying code is made of the 2 n words on tn bits obtain by the naive algorithm without pruning (i.e. with code rate 1/t) so simple variants of our algorithm cannot be efficient for δ < 1/t and our algorithm is optimal up to the multiplicative constant ln(2).

Experimental Results

To confirm the validity of the attack and of our heuristic, extensive experiments have been performed for various values of t and δ. For each pair (t, δ), the attack has been launched and its complexity has been measured by counting the sum of the cardinality of the sets L (i) for i in {0, . . . , n}. The obtained results are analysed below.

With 32 and 64 signatures. We performed experiments using 32 and 64 signatures (using a security parameter κ equal to 128). Since the experiments were time-consuming, we performed 1000 experiments for each pair (t, δ). The results for t = 32 are provided on Figure 1, for values of δ varying from 0.04 to 0.06 and the ones for t = 64 are illustrated on Figure 2, for values of δ between 0.02 and 0.04 (namely from 2% to 4%). These experiments show that it works better in practice than what was predicted. Indeed, the bounds below which the attack begins to become unpractical are approximately 0.04 for t = 32 signatures and 0.02 for t = 64. These values are better than the ones reached by the theoretical analysis, say 2 -2 1-1/32 0.043 and 2 -2 1-1/64 0.022. With 710 signatures. We finally considered the case where the adversary knows (on average) only one bit per nonce r i (i.e. δ = 1/512). For a security parameter κ equals to 128, our theoretical analysis claims that an attacker will be able to break the scheme knowing 710 signatures. In this case, our attack by bit but we compare larger blocks of bits. More precisely, we grow subtrees of depth T (for some parameter T ) for each t-tuple of nonce candidate. We will see that this results in 2 T new candidates which we all compare with our noisy nonce material. If the Hamming distance with this material in these T bits is above some threshold parameter d we keep the candidate, otherwise we discard it. The only difficulty here consists in estimating these parameters T and d:

the parameter T cannot be chosen too large since in each iteration the search tree grow by a factor 2 T ; the parameter T has to be sufficiently large in order to guarantee that the actual t-tuple of nonces has a small Hamming distance with the noisy nonce material (in each block of successive T bits) but incorrect t-tuples of nonces are separable by the threshold parameter d ; the threshold parameter d has to be large enough to guarantee that with probability close to 1 the actual t-tuple of nonces will never be discarded during the execution of the algorithm ; the parameter d cannot be chosen too large since otherwise we obtain too many faulty t-tuples candidates for the next iteration.

• First analysis with

1 = 2 = • • • = t .
As above, one can assume we are using odd values c i . We have to determine the size N (k) of the sets L (k) . For k = 0, since none of the r i,0 is known for sure by the adversary, there are two possible values for the bit ϑ 1,0 and each of them fixes the other bits ϑ 2,0 , . . . , ϑ t,0 (using System [START_REF] Feige | Zero-knowledge proofs of identity[END_REF]). Therefore, we obtain N (0) = 2. Similarly, using System (9), one can see that if there is no pruning at the depth k then N (k) is simply equal to 2N (k-1) .

• Second analysis when some of the i 's are different.

In this case, we can still show that N (0) = 2 and that we have, before pruning, N (T -1) = 2 T at iteration T6 (see [START_REF] Bauer | Practical key recovery for discrete-logarithm based authentication schemes from random nonce bits[END_REF] for a complete proof of this result).

We now consider the pruning phase. Let us define a random variable X c for the number of matching bits between the actual t-tuple of nonces and the noisy nonce material in a block of T consecutive bits. Clearly X c is the binomial distribution with parameters tT and probability

(1 -δ): Pr[X c = m] = tT m (1 - δ) m δ tT -m for m in {0, . . . , tT }.
Considering an incorrect partial solution for the t-tuple of nonces, we denote X b for the number of matching bits between the expansion of this incorrect solution by T bits and the noisy nonce material in the corresponding block of T consecutive bits. We make use of the following heuristic assumption Heuristic 1 Every solution generated by applying the expansion phase to an incorrect partial solution is an ensemble of T randomly chosen bit slices.

Therefore every expansion of an incorrect candidate in the expansion phase results in tT uniformly random bits. We verified the validity of this heuristic experimentally. Under this assumption, we obtain Pr[X b = m] = tT m (2) -tT for m ∈ {0, . . . , tT }.

Henecka, May and Meurer proved in [START_REF] Henecka | Correcting errors in RSA private keys[END_REF]Main Theorem 7] that these conditions are sufficient to insure the existence of an expansion parameter T and a threshold parameter d such that the two distributions are sufficiently separated and the growing factor 2 T in the expansion phase is polynomial.

Theorem 5 ([12]). Under the previous heuristic, for every > 0, the following holds: let n, t ≥ 2 be two integers, let T = ln(n) t 2 , γ = (1 + 1/T ) ln (2) 2t , and d = tT 1 2 + γ . An adversary able to learn (in the error correction scenario) the individual bits of random nonces of t known signatures of length n with probability δ < 1 2 -γ -can recover the nonces (and therefore the secret key) in expected time O(n 2+ln(2)/t 2 ) with success probability at least 1 -(m 2 / ln(n) + 1/n).

Remark 2. The following table gives the limit crossover probability δ (i.e. with -→ 0 and T -→ +∞) in the error correction scenario depending on the number of signatures/identification sessions available t known to the adversary: 2 (1 -1/t) The value δ * corresponds to the optimal value of δ one can derive from the converse to Shannon's noisy-channel coding theorem as in Remark 1 using the fact that the channel capacity of (memoryless) binary symmetric channel with crossover probability δ is 1-H 2 (δ) where H 2 (δ) = -δ log 2 (δ)-(1-δ) log 2 (1-δ) is the entropy function. For a 128-bit security level, with nonces of binary length 512, each signature provides only one bit of information for δ 1/2 -10 -4 and one needs in theory around 70 • 10 6 signatures in order to recover the secret key.

Conclusion

We proposed attacks on discrete-logarithm based authentication schemes where an adversary has some information on the nonces used in the signature generation or in some identification sessions. We considered the erasure correction scenario and the error correction scenario and the following table gives the limit crossover probability δ in the two scenarios depending on the number N r of signatures/identification sessions known to the adversary: Our methods can be generalized to the Z-channel considered in [START_REF] Kenneth | A codingtheoretic approach to recovering noisy RSA keys[END_REF].

Fig. 1 .Fig. 2 .

 12 Fig. 1. Total number of constructed (ϑ1, . . . , ϑ32) in function of δ (t = 32 and κ = 128).

  084 0.160 0.205 0.237 0.260 0.277 0.292 0.303 1/2 -ln(2)/2t δ * 0.110 0.174 0.214 0.243 0.264 0.281 0.295 0.306 H -1

  correction) 0.586 0.413 0.318 0.259 0.218 0.188 ln(2)/t δ (error correction) 0.084 0.160 0.205 0.237 0.260 0.277 1/2 -ln(2)/2t

We remind that the

2-adic valuation of a number c denotes the largest power of 2 dividing c.

Obviously once (r1, . . . , rt) has been retrieved, the signers' secret key x can easily be recovered. Theoretically only one of the ri's is really necessary to retrieve x, but we see in the following that recovering one such element requires in fact to retrieve all ris simultaneously.

This theorem states that no combination of code and decoding procedure can jointly achieve arbitrarily reliable decoding when the code rate exceeds the capacity of the channel

In particular, in both cases, one gets before pruning N (T -1) = 2 T at iteration T (instead of N (T -1) = 2 tT for a naive approach).

Acknowledgments. The authors are supported in part by the French ANR JCJC ROMAnTIC project (ANR-12-JS02-0004).

Algorithm 2 Generic Attack on t Signatures

Require: (c1, . . . , ct), (C1,1, . . . , C1,t), δ and partial bit information on (r1, . . . , rt) Ensure: L a list of tuples (ϑ1, . . . , ϑt) possible candidates for (r1, . . . , rt)

1: L (0) = {} 2:

--/* Initialisation -Case k = 0 */--3: Generate all bit tuples for (ϑ1,0, . . . , ϑt,0), say E = {0, 1} t 4: for each element (ϑ1,0, . . . , ϑt,0) ∈ E do 5:

if (ϑ1,0, . . . , ϑt,0) coincides with knowledge of (r1,0, . . . , rt,0) then

6:

if (ϑ1,0, . . . , ϑt,0) satisfies System (6) modulo 2 then

7:

Add element (ϑ1,0, . . . , ϑt,0) to L (0)

8:

--/* Main loop for k from 1 to n -1 */--9: for k from 1 to n -1 do 10:

11:

Generate all bit tuples for (ϑ 1,k , . . . , ϑ t,k ), say E = {0, 1} t

12:

for each element (ϑ 1,k , . . . , ϑ t,k ) ∈ E do 13: if (ϑ 1,k , . . . , ϑ t,k ) coincides with knowledge of (r 1,k , . . . , r t,k ) then 14:

for each element (ϑ

. . .

17:

Lift ϑ is known to the attacker. To simplify the analysis that follows -and since it does not change anything but renaming the variables -we assume that we keep working with System (6) but using odd values c i . Now if we come back to our analysis on the set L (0) , namely considering System (6) modulo 2, we reach the following new system:

It now becomes easy to count the number of elements belonging to L (0) . Indeed, either none of the r i,0 is known by the adversary, and in that case there are two possible values for ϑ 1,0 , say 0 or 1 and each of them fixes the rest for ϑ 2,0 , . . . , ϑ t,0 . In the second configuration, when there is at least one of the r i,0 which is known by the attacker (say r 1,0 for instance 3 ), the value ϑ 1,0 is fixed to r 1,0 and thus the other values ϑ 2,0 , . . . , ϑ t,0 are fixed too (see System [START_REF] Feige | Zero-knowledge proofs of identity[END_REF]). As a consequence, there is unique solution for the uple (ϑ 1,0 , . . . , ϑ t,0 ). The construction of the whole set L (0) is summed up in Algorithm 2-a, which can be seen as an adaptation of the initialisation phase of Algorithm 2 when all i are equal (process to a replacement of lines 3-7 of Algorithm 2 by the following ones). The expected cardinal N (0) of the list L (0) can thus be expressed easily:

when none of the r i,0 's is known, which holds with probability (1 -δ) t , there are two candidates for (ϑ 1,0 , . . . , ϑ 1,t ).

Algorithm 2-a Init. phase of Algorithm 2 when

if (None of the ri,0's is known) then Add {(0, C1,2 mod 2, . . . , C1,t mod 2), (1, C1,2 + 1 mod 2, . . . , C1,t + 1 mod 2)} to L (0) else /*At least one of the ri,0's is known, say for instance r1,0*/ Add (r1,0, C1,2 + r1,0 mod 2, . . . , C1,t + r1,0 mod 2) to L (0)

when at least one of the r i,0 is known, what happens with probability 1 -(1 -δ) t , there is a unique solution for (ϑ 1,0 , . . . , r t,0 ).

One can thus reach

We will now determine by induction the expected size N (k) from N (k-1) for k ∈ {1, . . . , n-1}, knowing that it contains all elements of the form (ϑ

t ) coinciding with possible knowledge on (r 1,k , . . . , r t,k ) and satisfying:

Putting such expressions inside System (8) finally leads to the following new relations:

Now it is easier to determine the number of solutions (ϑ 1,k , . . . , ϑ t,k ) that will be chosen to lift elements (ϑ

) from L (k-1) to L (k) . Nevertheless one should be careful during this analysis, since it strongly depends on whether the chosen element (ϑ

) or not. Indeed when this condition is not satisfied, the choice of an element (ϑ

) fixes all integers k 1 , . . . , k t implying some possible invalid restrictions on the values ϑ 1,k , . . . , ϑ t,k . As a consequence, when some of the r i,k 's are known (precisely more than two), the corresponding equalities in [START_REF] Girault | Self-certified public keys[END_REF] are not necessarily satisfied. Since we do not know in advance when it happens, we assume each equation in [START_REF] Girault | Self-certified public keys[END_REF] holds independently with some fixed probability γ ∈ [0, 1] during the whole run of our Algorithm 4 . In the other case, namely when the r i,k 's are unknown or when the element (ϑ

) corresponds to the right solution, the lifting process behaves as usual, see the "two signatures case". Taking all these considerations into account, one can finally determine the size of the set L (k) , see Algorithm 2b for a precise description (this algorithm can be seen as an adaptation of the main loop of Algorithm 2, lines 10 -19). From now on, we are able to deduce the size N (k) of the set L (k) , knowing that:

when the adversary does not know any of the r i,k , what holds with probability (1 -δ) t , there are 2N (k-1) solutions; when exactly one of the r i,k is known, which happens with probability tδ(1δ) t-1 , there are N (k-1) solutions; 4 We remind that γ is only defined when (ϑ

in the other case, this number depends on the chosen element (ϑ

). When this element is equal to (r

) (this is the right candidate), there is a unique solution. In the other case, there are γ(N (k-1) -1) solutions when exactly two r i,k are known, what holds with probability t 2 δ 2 (1 -δ) (t-2) ; there are γ 2 (N (k-1) -1) solutions when exactly three r i,k are known, which holds with probability t 3 δ 3 (1 -δ) (t-3) ; and so on; there are γ t-1 (N (k-1) -1) solutions when all the r i,k are known, what happens with probability t t δ t .

Algorithm 2b Main loop of Algorithm 2 when 1 = • • • = t (lines 10 -19)

Add element (ϑ

t ) in L (k) else if there exists a unique i such that r i,k is known /*say for instance r 1,k */ then for each element (ϑ

Compute ϑ j,k = ϑ 1,k + kj mod 2 ; construct ϑ

Add element (ϑ

/*two or more r i,k are known, assume r 1,k is concerned*/ for each element (ϑ

) ∈ L (k-1) do for each index j in {1, . . . , t} do Compute kj such that kj

) coincide with possible knowledge on (r 1,k , . . . , r t,k ) then for each index j in {1, . . . , t} do Compute ϑ

Add element (ϑ

By combining all these results, we obtain the following formula for N (k) :

Evaluating the quantity inside the summation leads to the following relation:

succeeded in a few minutes (using a very naive implementation) with a total size of generated elements equal to 2437. To go further, we also tried to launch the attack for a smaller number of signatures, but still keeping δ = 1/512. The cases t = 650 and t = 600 were also successful. The time required for the last case was approximately a few hours and the total sum of elements was 53770 (again using a very naive implementation).

Impact of γ. The formula obtained in Section 3.1 and 3.2 strongly depend on the value of the parameter γ. In our theoretical analysis, we decided to take γ = 1/2. In practice, several tests have been launched to determine whether this assumption is correct. In every experiments we performed, the observed value for γ was very near from 1/2, what confirms our initial assumption.

Error correction scenario

In the erasure correction scenario (see previous sections), we compared each nonce candidate with its given fragmentary version in order to determine the nonce uniquely with overwhelming probability. In this section, the error correction scenario, we proceed similarly: we assume an adversary obtain some error-prone nonces in a discrete-logarithm based authentication scheme which are derived from the actual nonces by flipping each bit individually with some fixed probability δ ∈ [0, 1/2). Intuitively, if δ is below 1/2, then among all nonce candidates, the Hamming distance between the least significant bits of the actual nonces and the nonces with noise should be minimal. The analysis is simpler than in the previous section and relies on the technique proposed by Henecka, May and Meurer in [START_REF] Henecka | Correcting errors in RSA private keys[END_REF]. We consider the case of an adversary that is given access to t signatures (or authentication sessions) σ 1 , . . . , σ t corresponding to known messages m 1 , . . . , m t . Again, each signature σ i is defined as a pair (s i , c i ) where s i = r i +c i x and x is the signers' secret key. Moreover we assume that each bit of each nonce r i is known with some error: to formalize this model we denote by δ the probability that for each nonce r i , its j-th bit r i,j is flipped (for j in {1, . . . , n}). By definition, the bit r i,j is correct with probability (1 -δ).

Making the quantity x disappear from all the expressions, one reaches the simple system of equations [START_REF] Elgamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF]. The adversary can retrieve the nonces r 1 , . . . , r t by collecting all tuples (ϑ 1 , . . . , ϑ t ) satisfying System (6) and minimizing the Hamming distance with the bits r i,j . The algorithm performs a clever exhaustive search, consisting in generating all tuples (ϑ (k) 1 , . . . , ϑ (k) t ) satisfying System (6) modulo 2 k+1 and then selecting among them, those that can be lifted to solutions modulo 2 k+2 . These operations should minimize the distance with the knowledge on some bits of the r i 's.

Contrary to the erasure correction scenario, one cannot easily prune partial solutions that do not coincide with the known secret key bits. Indeed this process may discard the correct solution, since this solution does not fully agree with the noisy nonce material. Thus, in this scenario, we do no longer compare bit