Keywords:

Le paradigme de Fiat-Shamir permet la création systématique de schémas de signature à partir de protocoles d'identification. Ces derniers sont des protocoles interactifs en trois messages, entre un prouveur possédant une information secrète et un vérificateur avec une information publique corrélée. La transformation de Fiat-Shamir est simple et flexible, ce qui explique sa popularité, notamment lorsqu'elle est combinée avec des protocoles d'identification efficaces. Malheureusement, son utilisation dans le cadre de la cryptographie fondée sur les réseaux Euclidiens se révèle plus compliquée, et on lui préfère sa variante dite avec rejet. Cette thèse propose une étude de cette variante et de son utilisation en conjonction avec les réseaux Euclidiens. Nous commençons par recouvrer sa sécurité après avoir identifié des erreurs dans les précédentes preuves de sécurité proposées. On étudie aussi le temps d'exécution d'une signature ainsi que les propriétés de non-divulgation de connaissance du protocole de Lyubahsevsky, qui est le plus célèbre à reposer sur les réseaux Euclidiens.

Nous l'étudions ensuite plus en détail. Ce protocole repose sur l'échantillonnage par rejet, qui peut être utilisée avec une très grande variété de paires "proches" de distributions : on échantillonne depuis l'une pour rejeter vers l'autre. Étant donné un nombre moyen d'itérations du protocole, nous minimisons la norme Euclidienne moyenne de la signature résultante, en choisissant soigneusement la paire de distributions source et cible. Cela diminue la taille de la signature, et la rend plus résistante aux attaques, ce qui permet de réduire les paramètres pour la même sécurité.

Nous proposons ensuite HAETAE, une implémentation de la version bimodale avec des distributions uniformes sur des boules Euclidiennes de la signature de Lyubashevsky. Si nous la comparons rapidement avec les signatures réseaux sélectionnées par le NIST pour être standardisées, on s'aperçoit que nous avons des tailles de signatures près de 40% plus petite que Dilithium, même si nous signons jusqu'à 8 fois plus lentement. Cela reste pourtant plus grand en taille mais plus rapide en vitesse de signature que Falcon. De plus, notre implémentation est en temps constant et n'utilise que de l'arithmétique à virgule fixe.

Enfin, nous proposons d'éviter l'échantillonnage par rejet en utilisant à la place des convolutions de Gaussiennes discrètes. Contrairement aux autres techniques connues, cette solution semble préserver les tailles de signatures et de clés de vérification du protocole pour des paramètres concrets, et elles sont même meilleures asymptotiquement. Bien que cette technique requiert d'échantillonner à partir d'une Gaussienne discrète elliptique, celle-ci est indépendante du message. Pour corriger i cette distribution du premier message, un centre aléatoire est choisi et le résultat sera indépendant du secret, ce qui est le problème critique qui avait mené à l'introduction du rejet en premier lieu.

Résumé substantiel en Français

La cryptographie moderne a pour but de fournir un ensemble de primitives et protocoles sécurisés correspondant à n'importe quelle situation où une forme de sécurité est requise lors de communications. Parmi eux, les protocoles de signature numérique permettent à un signataire, en possession d'une clé secrète, de produire une signature pour un message quelconque. N'importe qui en possession de la clé de vérification correspondante peut vérifier la cohérence de la signature produite avec le message. De plus, il est difficile pour quelqu'un sans la clé de signature de contrefaire une signature pour un autre message de son choix en un temps raisonnable. Depuis leur introduction par Diffie et Hellman en 1976 [START_REF] Diffie | New directions in cryptography[END_REF], de nombreuses applications reposent sur les signatures numériques et il est difficile de surestimer leur importance.

Le premier cas d'usage, et peut-être le plus évident, est en tant que remplacement des signatures manuscrites. Plusieurs pays, notamment les États Unis et les membres de l'Union Européenne, accordent une valeur légale aux signatures numériques dans plusieurs situations, telles que la signature de contrat entre entreprises. Une seconde application est la prévention d'usurpation d'identité lors de la mise à jour d'un logiciel. Plus précisément, un développeur peut adjoindre une clé de vérification à un logiciel lors de sa sortie initiale. Lors de mises à jour futures, il signera celles-ci, ce qui permettra aux utilisateurs d'être convaincus quant à l'intégrité de la mise à jour qu'ils viennent de télécharger. Plus généralement, dans le contexte du chiffrement à clé publique, les signatures numériques permettent de distribuer les clés publiques nécessaires pour mettre en place un canal de communication sécurisé. En effet, lors de la transmission d'une telle clé publique, on peut démontrer son authenticité en la signant, en supposant que le destinataire possède notre clé de vérification pour la signature. C'est peut-être une fuite en avant mais il faut pourtant reconnaître que ce problème de l'échange de clé n'apparaît maintenant plus qu'une seule fois, lors de l'échange des clés de vérification. Il devient ensuite possible d'utiliser autant de clés publiques que nécessaire, notamment en cas de compromission de session. C'est d'ailleurs le rôle des autorités numériques et des certificats numériques, qui peuvent être vus comme la "carte d'identité" d'un ordinateur. En signant une clé de vérification en plus d'une adresse IP ou même physique, ces autorités certifient l'origine d'une clé de vérification, qui peut ensuite être librement utilisée ailleurs.

Un exemple crucial est la poignée de main TLS. Pendant celle-ci, un client et un serveur tentent d'établir un canal de communication sécurisé (HTTPS) en générant xi ensemble une clé symétrique. Pour commencer, ils échangent leurs certificats, avec les clés de vérifications correspondantes. Ils peuvent ensuite les utiliser pour échanger une clé publique, qui leur permettra enfin d'échanger secrètement une clé symétrique. Au total, trois signatures et deux clés de vérification sont échangées pendant ce protocole, ce qui représente de nos jours quelques kilooctets de données transmises. En perspective, le poids moyen d'une page web atteint 2,3 Mégaoctets en mai 2023 1 . Ainsi, le coût actuel de ce protocole est infime par rapport au coût du téléchargement d'une page web.

Cependant, la sécurité des standards actuels repose sur la difficulté à factoriser de très grands entiers, ou encore la difficulté à calculer le logarithme discret dans un groupe. Or, ces deux problèmes sont menacés par l'avènement du calcul quantique, car ils sont résolus en temps polynomial grâce à l'algorithme de Shor. L'institut national américain des standards et de la technologie (NIST) a lancé en 2016, comme mesure préventive, une compétition pour trouver de nouveaux standards, ceux-ci résistants aux attaques par ordinateur quantique. Ces nouveaux standards doivent allier sécurité sur le long terme, efficacité calculatoire et tailles de signature raisonnables.

Différentes familles d'hypothèses sont pour le moment supposées résister aux algorithmes quantiques. Parmi elles, les problèmes reposant sur les réseaux Euclidiens, ou sous-groupes discrets de R n , sont particulièrement remarquables par leur grande flexibilité et leurs bonnes performances, qui sont encore accrues quand on les considère dans la version "module". Les problèmes Short Integer Solution (SIS) et Learning with Errors (LWE) sont d'un intérêt particulier pour la cryptographie. Le premier consiste à trouver un petit vecteur (pour la norme Euclidienne) dans le noyau d'une matrice A sur un groupe quotient Z/qZ, tirée uniformément. Le second consiste, étant donné A et un vecteur b, à retrouver si b = As + e pour de petits s et e, ou si b a été tiré uniformément.

Certains choix de paramètres bénéficient de réductions pire cas-moyen cas, renforçant la confiance en la difficulté de ces problèmes, telles que prouvées pour la première fois dans [START_REF] Ajtai | Generating hard instances of lattice problems (extended abstract)[END_REF][START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. De plus, pour les paramètres considérés en pratique, malgré plusieurs décennies de cryptanalyse, aucun algorithme quantique n'arrive à les résoudre efficacement. Ces arguments, parmi d'autres, ont conduit le NIST à choisir deux protocoles de signature fondés sur les réseaux, parmi les trois protocoles qui seront standardisés. Le premier, Falcon [FHK + 17], découle d'une branche dénommée "Hash-and-Sign" (hacher puis signer). Le second, Dilithium [BDK + 20], est construit à partir du paradigme de Fiat-Shamir. C'est à celui-ci que nous allons nous intéresser dans cette thèse. Il a été introduit par Fiat et Shamir en 1987 [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF] et offre de multiples avantages : il est flexible, efficace et part d'une primitive plus simple conceptuellement. Nous allons maintenant brosser un bref portrait des innovations qui ont abouti à Dilithium.

Une Brève Histoire de Fiat-Shamir et des Réseaux

Le principal ingrédient de la transformation de Fiat-Shamir est un protocole d'identification. C'est un protocole interactif entre un prouveur, qui possède une information 1 https://httparchive.org/reports/page-weight?start=2023_03_01&end=latest&view= list xii secrète, et un vérificateur détenant une information publique corrélée. L'objectif du prouveur est de convaincre le vérificateur qu'il est bel et bien en possession de l'information secrète, sans la révéler. Cet objectif peut être réalisé en trois étapes. De tels protocoles peuvent être réalisés de manière simple et pourtant efficace, ce qui permettra ensuite d'obtenir une signature hautement efficace. Le protocole de Schnorr pour le logarithme discret est particulièrement intéressant dans notre cas, et nous verrons comment il est adapté au cas des réseaux.

Le Protocole de Schnorr pour le Logarithme discret

Étant donné un groupe cyclique G d'ordre p très grand, un générateur g ainsi qu'un élément quelconque du groupe g x , le problème du logarithme discret consiste à calculer x. En supposant que ce problème est difficile, on comprend qu'on peut alors cacher des informations à l'intérieur de l'exposant, tandis que la cohérence des calculs peut être vérifiée en manipulant les éléments du groupe.

Le protocole de Schnorr [START_REF] Schnorr | Efficient signature generation by smart cards[END_REF] profite de cette flexibilité pour être efficace et sécurisé. La clé publique du vérificateur est un élément du groupe g s , tandis que la clé secrète du prouveur est son logarithme discret s. L'interaction se déroule alors comme suit. D'abord, le prouveur échantillonne y ← U (Z p ) et envoie g y comme engagement. Il reçoit ensuite un défi c échantillonné uniformément sur Z p . Sa réponse est enfin z = y + sc mod p. Notons ici qu'aucune information n'est révélée sur s. En effet, comme y est caché au vérificateur (à moins qu'il ne résolve une instance du problème du logarithme discret), la réponse z est a priori uniforme et indépendante du secret. Cependant, il est convaincu que le prouveur connaît s en vérifiant la véracité de l'équation g z = g y (g s ) c .

La Transformée de Fiat-Shamir

Nous décrivons maintenant la technique utilisée par Fiat et Shamir [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF] pour transformer un protocole d'identification en une véritable signature. L'algorithme de génération de clé est exactement le générateur d'instance du protocole d'identification. L'algorithme de signature va dérouler le protocole interactif en jouant le rôle à la fois du prouveur et du vérificateur. Pour éviter qu'un adversaire ne puisse contrefaire une signature, le défi est calculé de manière déterministe en hachant l'engagement et le message. La signature est alors la retranscription complète de l'échange. Enfin, l'algorithme de vérification n'accepte que si deux conditions sont réunies. D'abord, le vérificateur doit accepter la retranscription. Ensuite, le défi doit avoir été calculé honnêtement : l'algorithme de vérification re-hache le message et l'engagement et vérifie que le haché obtenu est le même que le défi.

Heuristiquement, utiliser une fonction de hachage "force" le signataire à utiliser un défi uniforme, qui peut être vérifié publiquement, afin de l'empêcher de le modifier selon ses besoins. On peut alors prouver la sécurité de la signature dans le modèle de l'oracle aléatoire (la fonction de hachage est remplacée par une fonction dont les sorties sont tirées uniformément et qui est gérée par le challenger, l'attaquant n'ayant qu'un accès à celle-ci par "oracle"). Pour cela, il est nécessaire que le protocole d'identification satisfasse les propriétés suivantes :

• Min-entropie de l'engagement : si le protocole est utilisé à plusieurs reprises, la probabilité d'utiliser plusieurs fois le même engagement doit être négligeable. Dans le cas de Schnorr, c'est le cas comme l'ordre du groupe est grand.

• Sans Divulgation de Connaissance pour un Vérificateur Honnête (HVZK) : un vérificateur honnête ne devrait rien apprendre à propos du secret détenu par le prouveur. Cela se traduit par l'existence d'un simulateur capable de générer une retranscription, étant donné un défi, tel que la distribution de cette retranscription est proche de celle d'une vraie retranscription, conditionnée sur ce défi. Le simulateur pour Schnorr commence par échantillonner uniformément z ← U (Z p ) et pose g y = g z (g s ) -c comme engagement. On remarque alors que la distribution de cette simulation est exactement celle d'une véritable retranscription.

• Sûreté : il doit être difficile de convaincre le vérificateur pour une personne n'ayant pas le secret. Grâce à une technique dite de rembobinage, on peut montrer qu'un attaquant pouvant convaincre le vérificateur une fois peut en fait le convaincre deux fois, pour le même engagement mais deux défis différents. On obtient alors (g y , c, c ′ , z, z ′ ) tel que g y = g z (g s ) -c = g z ′ (g s ) -c ′ et on retrouve s = (z -z ′ )/(c -c ′ ) mod p.

La réduction de sécurité utilise un jeu hybride, où le challenger rend les signature indépendantes de la clé secrète en les simulant à l'aide du simulateur. Il doit aussi reprogrammer l'oracle aléatoire pour qu'il reste cohérent avec le défi qu'il aura échantillonné. Il devient donc impossible pour un adversaire d'apprendre quoi que ce soit au sujet de la clé secrète à partir de signatures. Enfin, on peut utiliser cet adversaire pour contredire la propriété de sûreté du protocole d'identification, en construisant un attaquant contre la sûreté qui joue le rôle du challenger pour le premier adversaire, sans avoir besoin de la clé secrète. Il doit par contre reprogrammer la fonction de hachage au bon endroit afin qu'il puisse utiliser la signature contrefaite pour convaincre le vérificateur.

Notons que le protocole de Schnorr satisfait une propriété supplémentaire : le recouvrement de l'engagement, ce qui sera le cas pour les autres protocoles considérés dans cette thèse. En effet, si l'on omet l'engagement de la signature, on peut le recalculer en sachant que g y = g z (g s ) -c . Cela permet de réduire considérablement la taille de la signature. La vérification va alors commencer par recouvrer l'engagement, avant de vérifier la cohérence du haché, et enfin de vérifier que la retranscription est convaincante. Dans le cas de Schnorr, on peut omettre cette dernière étape car elle sera automatiquement valide, vu la manière dont on a récupéré l'engagement.

Du Log Discret aux Réseaux Euclidiens : Introduction de l'Échantillonnage par Rejet

Un but de longue date dans la cryptographie à base de réseaux Euclidiens est de proposer une adaptation efficace du protocole de Schnorr au contexte des réseaux. Lyubashevsky en a proposé la première [START_REF] Lyubashevsky | Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures[END_REF][START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF]. Celle-ci implique une matrice publique A ∈ Z n×m q , qui remplace le générateur g et définit une instance SIS. La clé secrète est une matrice S ∈ Z m×k , dont chaque colonne a une petite norme Euclidienne, par rapport à q. En remplacement de g s , la clé de vérification est T = AS mod q.

Dans le protocole d'identification, le prouveur échantillonne un petit vecteur de masquage y ∈ Z m et calcule un engagement pseudo-uniforme w = Ay mod q. Il reçoit ensuite un défi c ∈ Z k choisi uniformément parmi les vecteurs de norme infinie bornée par un paramètre du protocole. Enfin, après un test, dont nous parlerons plus tard, il renvoie z = y + Sc si celui-ci est réussi, sinon, il faut recommencer. Étant donné une retranscription σ = (w, c, z), le vérificateur accepte si Az -Tc = w mod q, et si z est petit, ce qui est spécifique aux réseaux. Le lecteur trouvera une description détaillée en Anglais du protocole en Figure 2. 5.

Contrairement au protocole de Schnorr, la clé de signature et le masque n'appartiennent pas à un groupe fini, ce qui empêche y de complètement cacher le terme sensible Sc. Au contraire, en fournissant un effort proportionnel à la valeur moyenne de ∥y∥, des attaques statistiques génériques permettent de récupérer la clé secrète. Une possibilité (voir par exemple [START_REF] Damgård | Multiparty computation from somewhat homomorphic encryption[END_REF]) est de choisir y exponentiellement plus large que Sc en tant que fonction du paramètre de sécurité, ce qui contrecarre l'attaque précédente et permet même de prouver la sécurité. En effet, la distance statistique entre y et y + Sc devient alors négligeable. Étant donné que q doit être plus grand que y et que la petitesse de S par rapport à q impacte la sécurité, cette approche par flooding (noyade) donne de très grands paramètres. À la place, Lyubashevsky propose une notion de Fiat-Shamir avec rejet. C'est ici qu'intervient le test que passe z dans le protocole. Il sert à faire en sorte que la distribution de z ne dépende plus de Sc.

Une application classique du rejet (cf. [Dev86, Chapitre 2]) est l'échantillonnage d'une distribution P "difficile" à partir d'une distribution plus simple à échantillonner Q. Ici, le rejet est détourné de son utilité première : on part d'une distribution pré-source Q qu'on décale par Sc, ce qui donne une distribution source Q +Sc . On la rejette ensuite vers une distribution P qui ne dépend pas de Sc. L'objectif ici alors est de cacher Sc. Des choix divers ont été faits jusqu'à présent pour P et Q : uniforme dans des hypercubes [START_REF] Lyubashevsky | Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures[END_REF], gaussiennes discrètes de même écart type [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF]. L'efficacité de ces choix est contrôlée par deux paramètres : le nombre d'itérations en moyenne M , et la distance statistique ε entre le résultat du rejet et la distribution cible P . Grâce à cette flexibilité, il existe donc une myriade de possibilités pour adapter le protocole de Schnorr aux réseaux Euclidiens. Cela nous mène donc à la question suivante : Q1. Étant donné un nombre moyen d'itérations, quelle stratégie de rejet permet d'obtenir les signatures les plus compactes ?

L'équipe de Dilithium avait choisi de répondre à une autre question, leur but étant de produire une signature "facile à implémenter". Leur choix s'est alors porté sur P et Q uniformes dans des hypercubes, ce qui permet d'échantillonner chaque coordonnée indépendamment dans un intervalle. De plus, la condition de rejet consiste à simplement calculer la norme infinie de z et à le rejeter si elle est trop grande. La question Q1 reste alors ouverte.

Nous considérons aussi le cas de BLISS [START_REF] Ducas | Lattice signatures and bimodal Gaussians[END_REF], qui note que le rejet de gaussienne à gaussienne est inexact à cause des queues de celles-ci. Ses auteurs considèrent alors une Gaussienne bimodale comme distribution source, ce qui règle ce problème. C'est à dire qu'au lieu de calculer z = y + Sc, ils calculent z = y + (-1) b Sc, où b est un bit uniforme. Non seulement le rejet devient exact, mais il devient aussi plus xv efficace. Pour le même nombre moyen d'itérations, on peut prendre des écarts-type plus faibles. Malheureusement, le bit b ne peut être révélé à moins de retomber dans le cas unimodal. On change alors de module, de q à 2q, et changer la génération de clé afin que AS = qI mod 2q, pour que la vérification puisse fonctionner quelle que soit la valeur de b.

Nos Contributions

Pour conclure cette introduction, nous allons brièvement présenter les différentes contributions de chaque chapitre de cette thèse.

Chapitre 3 : Une Analyse Détaillée de Fiat-Shamir avec Rejet Dans un premier temps, nous étudions les preuves de sécurité de la transformation de Fiat-Shamir avec rejet. Les preuves de sécurité proposées, par exemple dans [Lyu12, KLS18, AFLT16], diffèrent des preuves standards pour la transformation de Fiat-Shamir. En effet, si le protocole d'identification doit être appelé à plusieurs reprises avant d'obtenir une signature, ce n'est plus la transformation de Fiat-Shamir mais une transformation différente, que nous dirons de Fiat-Shamir avec rejet. Les preuves doivent alors être modifiées pour prendre ce changement en compte. En particulier, la notion de HVZK peut être abordée de deux manières : doit-on pouvoir simuler les retranscriptions rejetées ? Les réductions précédentes considèrent que non, tandis que nous considérons que oui. Notons au passage qu'elles étudient une version modifiée de la transformation, où le protocole est appelé au plus B fois, quitte à ce que la signature échoue, ce qui ne correspond pas aux signatures utilisées en pratique.

Dans un premier temps, nous avons identifié une erreur commune à toutes les preuves précédentes. Toutes ces preuves considèrent un premier jeu hybride où un défi uniforme est échantillonné et une signature est générée, jusqu'à en avoir une nonrejetée (ou atteindre B itérations), puis l'oracle aléatoire est reprogrammé pour la signature acceptante uniquement. C'est un problème, car dans la signature originale, les itérations sont corrélées, à cause de la fonction de hachage, et ici elles ne le sont pas. Contrairement à ce qui est affirmé, on ne peut pas conclure que les deux jeux sont identiques.

Nos contributions portent alors sur trois fronts. Le premier est de corriger ces preuves en considérant que la propriété HVZK doit permettre la simulation de retranscriptions rejetées. Le second est d'étendre les réductions au cas où le nombre d'itérations n'est pas borné, comme c'est le cas en pratique. Nous identifions alors quelques difficultés dans les définitions car un contre-exemple montre les limites de celles-ci pour des questions de temps d'exécution. Enfin, nous montrons que le protocole de Lyubashevsky satisfait notre propriété plus forte de HVZK. Au final, les bornes de sécurité dans les preuves sont quasiment identiques à celles qui étaient mises en avant auparavant.

Chapitre 4 : Optimisation des Protocoles d'Identification fondés sur les Réseaux Euclidiens

Dans ce chapitre, nous étudions l'utilisation de l'échantillonnage par rejet dans les protocoles d'identification fondés sur les réseaux Euclidiens, et nous cherchons à mixvi nimiser la taille (ou compacité) d'une signature, mesurée par la norme Euclidienne moyenne d'un élément, étant donné un nombre d'itérations moyen M donné, ce qui répond à la question Q1. Dans un premier temps, nous nous intéressons à l'échantillonnage par rejet lui-même, et nous prouvons que cette procédure est optimale pour minimiser le nombre moyen d'itérations, étant donné un choix de distributions. Ensuite, nous prouvons une borne inférieure dans les cas unimodal et bimodal sur la compacité d'une signature. Pour cela, nous avons besoin de remarquer que la contrainte M sur le nombre moyen d'itérations se traduit par une condition M ≥ R ∞ (P ∥Q +Sc ) sur la divergence de Rényi entre P et n'importe quelle translatée de Q. Cette divergence est définie comme étant max x∈Supp(P ) P (x)/Q +Sc (x). En manipulant avec prudence les différentes équations que cela donne, nous trouvons ces bornes inférieures.

Ensuite, nous explorons des instanciations de P et Q afin de trouver des choix pouvant atteindre ces bornes. Nous en isolons deux. Le premier, les gaussiennes discrètes, est un choix standard en cryptographie fondée sur les réseaux. Le second, la distribution uniforme dans une boule Euclidienne, est nouveau. Bien que ces deux choix offrent la même compacité, le second choix est intéressant car la condition de rejet est plus simple : il s'agit de calculer une norme et de vérifier si la signature est suffisamment petite dans le cas unimodal. Enfin, pour les comparer plus en détail, nous proposons plusieurs jeux de paramètres concrets ainsi que des estimations de tailles, qui sont similaires pour ces deux choix de distributions. Elles sont en revanche bien meilleures que pour les distributions uniformes dans des hypercubes, comme considérées dans Dilithium : jusqu'à 40% de gains.

Chapitre 5 : HAETAE, une Nouvelle Implémentation de Fiat-Shamir avec Rejet Fondée sur les Réseaux Afin de concrétiser les résultats des deux premiers chapitres, nous proposons une implémentation, dénommée HAETAE. Celle-ci implémente la variante bimodale de la signature de Lyubashevsky qui repose sur la distribution uniforme dans des boules Euclidiennes. Dans ce chapitre, nous détaillons principalement les optimisations, largement présentes déjà dans Dilithium [BDK + 20], que nous adaptons au cas bimodal. Nous présentons aussi les différents choix qui permettent de passer d'une distribution théorique à une implémentation concrète d'un échantillonneur ainsi que d'une condition de rejet. En particulier, l'un des défis d'une telle implémentation est de permettre l'utilisation d'arithmétique à virgule fixe tout au long de la procédure de signature. Finalement, nous présentons brièvement les performances et paramètres de l'implémentation.

L'équipe de HAETAE est composée d'une dizaine de membres et les informations complémentaires du projet peuvent être trouvées sur la page web 2 . Notons que cette signature est soumise à deux concours de standardisation, l'un organisé par la Corée du Sud et l'additionnel quatrième tour des signatures post-quantiques du NIST.

Cette signature étant le résultat d'un travail d'équipe, ce chapitre se focalisera sur les parties où mon implication a été la plus forte, tout en n'en omettant aucun aspect. Il en résulte que, bien que HAETAE soit plus compliqué conceptuellement que Dilithium, le gain en terme de tailles de signature et de clé de vérification est 2 https ://kpqc.cryptolab.co.kr/haetae xvii largement en notre faveur : jusqu'à 40% de gain pour les signatures. D'un autre côté, par rapport à l'autre finaliste du NIST reposant sur les réseaux, Falcon, HAETAE reste conceptuellement plus simple, est plus rapide, mais a des tailles de signature et clé de vérification plus grandes.

Chapitre 6 : G+G, un Premier Pas vers un Fiat-Shamir Efficace Fondé sur les Réseaux Dans ce dernier chapitre, nous explorons une solution permettant d'éviter l'échantillonnage par rejet, qui consiste à utiliser une propriété de convolution des gaussiennes discrètes. On note que dans le mode bimodal, la relation vérifiée par les clés de vérification et secrète est AS = qJ mod 2q. Or, le défi c est toujours multiplié par S à gauche dans la signature, ce qui signifie que lors de la vérification, le secret est réduit modulo 2. C'est cette remarque qui permet au mode bimodal de fonctionner, en prenant un représentant de c qui est soit c soit c -2c. Si on cherche à aller encore plus loin, on peut tirer un représentant de c suivant une gaussienne discrète sur 2Z k + c sans centre de matrice de covariance s 2 I k . Maintenant, si y est échantillonné suivant une gaussienne discrète de covariance σ 2 I n -s 2 SS ⊤ , il résulte que z = y + Sc ′ suit une Gaussienne discrète sphérique sans centre.

Nous proposons alors G + G, un protocole d'identification fondé sur les réseaux Euclidiens, qui ne nécessite pas de rejet, et qui peut être transformé en une signature en utilisant la transformation de Fiat-Shamir (sans rejet). Le retrait du rejet est quelque chose qui avait déjà été exploré précédemment [START_REF] Damgård | Multiparty computation from somewhat homomorphic encryption[END_REF], mais le résultat était loin d'être pratique au vu des tailles qui en résultent. Ici, nous montrons que les tailles sont non seulement similaires à HAETAE pour des jeux de paramètres concrets, mais aussi les tailles de signature asymptotiques sont meilleures d'un facteur λ/ log(λ) par rapport aux meilleurs signatures avec rejet.

Chapter 1

Introduction

Modern cryptography aims at providing users with a toolkit of secure primitives and protocols which suits any communication setting where some form of security is desired. Among them, digital signature protocols allow a signer in possession of a secret key to produce a signature for any input message. Anyone in possession of the corresponding verification key may check the consistency of the signature with the message. Moreover, security guarantees prevent anyone from forging another signature for any message of their choice without the signing key in a reasonable time. Since their introduction by Diffie and Hellman in 1976 [START_REF] Diffie | New directions in cryptography[END_REF], digital signatures have found applications in numerous domains and it is hard to overstate their importance. The most obvious use case is as replacement for written signatures. Multiple countries, including members of the European Union and the USA, give legal value to digital signatures for contracts or other business applications. Another application is to prevent spoofing for software updating. Namely, a company bundles a verification key with a software in its initial release, and signs further updates. Users are then assured of the integrity of the update they downloaded, i.e., it has not been tampered with.

More broadly, in the context of public key encryption, digital signatures allow for secure distribution of public keys. When broadcasting a public key to someone in possession of the verification key, signing it allows to demonstrate its authenticity. Granted, this pushes back the problem one step before, as the verification key of the signature needs to be distributed beforehand. However, this problem now only happens at most once: with one verification key, one may then broadcast as many public keys as necessary. Digital authorities also use signatures to issue digital certificates. By signing an e-mail or an address, digital certificates can be seen as "identity cards" of servers and computers across the internet. They also embed a verification key to enable the previous usage. This is particularly visible during TLS handshakes. In those, a client and a server come together to exchange a symmetric key, thus enabling secure communication and HTTPS web browsing. They first exchange their certificates, with the corresponding verification keys. They use the latter to sign the further messages they send each other in order to agree on a symmetric encryption key. In total, three signatures and two verification keys are sent, which amounts to a few kilobytes of data transmission nowadays. To put it into perspective, the average website page weighs 2.3MB as of

Introduction

May 2023 1 . Thus the cost of signing is but a negligible fraction of the total cost of connecting to a website.

However, current standards rely on the hardness of factoring large integers or the hardness of computing the discrete logarithm in a group. With the ever-rising threat of quantum computing, the long term security of current standards for digital signatures is at stake, as these two problems are broken in polynomial time with Shor's algorithm. As a preventive measure, the American National Institute of Standards and Technology (NIST) launched in 2016 a competition to look for new, quantumresistant, standards that should ally long-term security, computing efficiency and reasonable signature size.

Different families of assumptions are currently assumed to resist to quantum attacks. Among them, problems based on Euclidean lattices (discrete subgroups of R n ) are particularly remarkable for the great design flexibility and good performance they offer, even more so when considered in their so-called "module" version. Of particular interest are the Short Integer Solution (SIS) problem and the Learning with Errors (LWE) problem. The former asks, given a matrix A over a finite field, to find a short (for the Euclidean norm over representatives centered around 0) element in its kernel. The latter asks to distinguish between As + e for short, random s and e and a uniform vector over the finite field, given A.

Certain settings benefit from worst-case to average-case reductions, strengthening the belief that those problems are hard to solve, as first shown in [START_REF] Ajtai | Generating hard instances of lattice problems (extended abstract)[END_REF][START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. Moreover, for settings considered in practice, despite more than a decade and a half of research, no polynomial time quantum algorithm can solve the problems yet. These arguments, among others, led the NIST to elect, out of the three winners of the competition for standardization of post-quantum digital signatures, two latticebased schemes. The first one, Falcon [FHK + 17], results from a first line of signatures, following the "Hash-and-Sign" design. The second one, whose line of work we are interested in in this thesis, is called Dilithium [BDK + 20]. It relies on a paradigm introduced by Fiat and Shamir in 1987 [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF], which offers multiple advantages: it is flexible, efficient and starts from a conceptually easier building block. We now briefly recall the results that ultimately led to Dilithium.

Brief History of Fiat-Shamir and Lattices

The main building block of the Fiat-Shamir transform is called an identification protocol. It is an interactive protocol between a prover, which holds some secret information, and a verifier, holding some related public information, where the prover tries to convince the verifier that it knows the secret information, without revealing it. The interaction is 3-round: the prover first sends a first message, the "commitment", the verifier replies with a "challenge" and the prover answers with a "response". The verifier checks the whole transcript and decides if it is convinced or not. Moreover, there is an efficient instance generator, which samples a random instance of related secret and public information. Simple yet efficient designs for such protocols arose, which in turn led to highly efficient and versatile signature schemes. We are 1.1. Brief History of Fiat-Shamir and Lattices particularly interested in Schnorr's protocol for the discrete logarithm, which is then adapted to the lattice setting.

Schnorr Protocol for Discrete Logarithm

The discrete logarithm problem asks one, given a cyclic group G of large order p, a generator g and an element of the group g x , to compute x. Based on the difficulty of solving this problem, one can hide secret information in the exponent, while the consistency of said private information can be checked through various operations over the group.

Schnorr's identification protocol [START_REF] Schnorr | Efficient signature generation by smart cards[END_REF] takes advantage of this flexibility to offer an efficient design. The prover's public verification key is simply a group element g s , whose discrete logarithm s forms the prover's secret key. The identification protocol proceeds as follows: the prover first commits to some uniform y ← U (Z p ) by sending g y to a verifier. The latter returns some uniform challenge c ∈ Z p , to which the prover replies with the response z = y + cs mod p. Here, no information about s is revealed as z is still uniform modulo p as y is hidden from the verifier. Indeed, it cannot compute the discrete logarithm of g y by assumption. However, a verifier is convinced that the prover knows s as it can verify g z = g y (g s ) c .

The Fiat-Shamir Transform

We now describe the technique Fiat and Shamir used [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF] to turn an identification protocol into a full-fledge signature scheme. The key generation algorithm is the instance generator of the identification protocol. The signing algorithm runs the interactive protocol. Instead of sampling a uniform challenge, which an attacker could maliciously choose, it hashes the commitment along with the message and obtains the challenge. The signature is comprised of the whole transcript. The verification algorithm accepts if the challenge is consistent with the hash of the commitment and the message, and if the verifier of the identification protocol accepts the transcript.

Heuristically, relying on the hash function "forces" the signer to use a uniform challenge, which can be publicly verified, to prevent it from tampering with it. The resulting signature can be proven unforgeable in the random oracle model (where the hash function is replaced with a function with uniform outputs) under the assumption that the identification protocol satisfies a few properties. Namely:

• Commitment min-entropy: if the protocol is ran multiple times, the probability of using the same commitment twice should be negligible. In the case of Schnorr's protocol, since the group order is large, g y has large min-entropy.

• Honest Verifier Zero-Knowledge (HVZK): a honest verifier should not learn anything about the secret held by prover. In particular, if the challenge is known in advance, transcripts can be simulated by someone who does not hold the secret key. The distribution of the simulation must be statistically close to the real one. Schnorr's simulator samples a uniform z ← U (Z p ) and sets g y = g z (g s ) -c , which does not require knowing the secret key. Moreover, the distribution of the transcript is exactly the same as a real one.

• Soundness: it must be hard for someone who does not hold the secret key to convince the verifier. Convincing Schnorr's verifier without knowing s implies computing the discrete logarithm of g s via rewinding techniques, which yields two accepting transcripts with the same commitment but different challenges. This gives (g y , c, c ′ , z, z ′ ) such that

g y = g z ′ (g s ) -c ′ = g z (g s ) -c . The discrete logarithm of g s is then s = (z -z ′ )/(c -c ′ ) mod p.
The security reduction uses an hybrid game, where the signatures are independent from the secret key, rendering impossible to learn the secret key by observing signatures. To do so, the challenger generates a signature using the HVZK simulator, and then reprograms the random oracle accordingly, as it manages it. From here, the unforgeability of the signature scheme is reduced to the soundness of the identification protocol.

Schnorr's identification protocol further satisfies the commitment-recoverability property, as do all other identification protocols discussed in this thesis. Given the challenge c and its answer z, one can recover the commitment g y = g z (g s ) -c . This is used to reduce the signature size by omitting the commitment from the signature. Verification is achieved by recovering it during verification and checking the consistency of the challenge with the hash function.

From Discrete Logarithm to Lattices: Introduction of Rejection Sampling

A long-standing goal in lattice-based cryptography is proposing efficient adaptations of Schnorr's protocol to lattices. Lyubashevsky proposed famous adaptations [START_REF] Lyubashevsky | Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures[END_REF][START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF] of this protocol for lattices. Lyubashevsky's scheme involves a publicly shared matrix A ∈ Z n×m q (note that other algebraic setups are possible, but this is not relevant to the present discussion), which replaces the group generator g and defines a SIS instance. The secret key is a matrix S ∈ Z m×k . It is small in the sense that all its entries have absolute values significantly smaller than q. Instead of a group element whose discrete logarithm is s, the verification key associated to S is T = AS mod q. In the identification protocol, the prover samples a small masking vector y ∈ Z m and computes a random-looking commitment w = Ay mod q. It receives a uniform c ∈ Z k challenge with small values from the verifier. Finally, if some (possibly probabilistic, later defined) test passes, it outputs z = y + Sc, and else it restarts from scratch. Given a transcript σ = (w, c, z), the verifier accepts if and only if Az -Tc = w mod q, as in Schnorr's protocol, and if z is small, which is particular to the lattice setting. We refer the reader to Figure 2.5 for a formal description.

Compared to Schnorr's signature scheme, the signing key and mask do not belong to a finite set, preventing the use of a uniform mask y to hide the sensitive term Sc. 2On the contrary, with an effort proportional to the expected value of ∥y∥, generic statistical attacks allow for key recovery. One possibility (see, e.g., [START_REF] Damgård | Multiparty computation from somewhat homomorphic encryption[END_REF]) is to sample y exponentially larger than Sc as a function of the security parameter, so that the distributions of y and y + Sc have exponentially small statistical distance.

As q must be larger than y and the smallness of S relative to q impacts security, this flooding approach leads to large parameters. Instead, Lyubashevsky [START_REF] Lyubashevsky | Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures[END_REF][START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF] put forward the notion of Fiat-Shamir with aborts. This is the reason for the test concerning z in the signing algorithm: it is so that the output signature (z, c) follows a distribution that is independent of the sensitive term Sc.

A classic application of rejection sampling (see, e.g., [Dev86, Chapter 2]) is to use a source distribution Q that is convenient to sample from, to create samples from a target distribution P . In Lyubashevsky's scheme, the purpose differs: we start from a pre-source distribution Q for y; it is shifted by Sc, leading to a distribution Q +Sc for y+Sc; the latter is the source distribution; it is rejected to a target distribution P for z that does not depend on the signing key S. The purpose of rejection sampling here is to hide the sensitive data Sc. Diverse choices of pairs of distributions have been put forward in the literature: uniform in hypercubes [START_REF] Lyubashevsky | Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures[END_REF], Gaussian with the same standard deviation while allowing for some small statistical inaccuracy in the target distribution [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF]. The efficiency of these choices is constrained by two parameters: the expected number of iterations M and the statistical distance ε between the the resulting distribution and the target one. Due to its flexibility, the rejection sampling technique allows us to adapt the Schnorr protocol to the lattice setting in multiple ways. This gives rise to the following question: Q1. Given signing runtime requirements, which rejection sampling strategy leads to the most compact signatures?

Dilithium chose to answer a different question: which rejection sampling strategy leads to the "easier to implement" signature? Their approach was to choose P and Q uniform in hypercubes, i.e. each coordinate is uniform over a centered range. This leads to a rejection condition which only depends on the infinite norm of z. Thus, obtaining randomness for the scheme can be done very efficiently as well as computing the rejection condition. An interesting observation from [START_REF] Ducas | Lattice signatures and bimodal Gaussians[END_REF] is that the statistical inaccuracy from Gaussian to Gaussian rejection sampling stems from the tails of the distributions. In particular, while one tail from the source (shifted) Gaussian behaves nicely, the other cannot be rejected correctly to the target distribution.

Then, one can consider bimodal Gaussian as the source distribution. Namely, instead of setting z = y + Sc, one sets z = y + (-1) b Sc for some uniform bit b. Now, the two tails of the source distribution behave nicely, which leads to a smaller expected number of rejections for the same standard deviation. Equivalently, given a target expected number of iterations, it is achieved with a smaller standard deviation than in the unimodal setting. However, the bit b cannot be revealed or we fall back in the unimodal setting. The key generation algorithm is then tweaked in order to produce A and S such that AS = -AS mod p for some integer p. In [DDLL13], the authors aim at setting AS = qI mod 2q, where I is the identity matrix. A careful analysis however reveals that setting AS = qJ mod 2q for any nonzero binary rectangular J is enough for the security reduction to go through.

Contributions

The findings of this thesis are part of the aforedescribed paradigm. We start by analyzing and fixing the security proofs of Fiat-Shamir with Aborts (Chapter 3) before

Introduction

carefully choosing a new pair of source and target distributions in order to minimize the expected norm of the signature (Chapter 4). We then propose an implementation and analyze its performances (Chapter 5) before proposing a rejection-free yet efficient, new lattice-based adaptation of Schnorr protocol (Chapter 6).

Chapter 3: A Detailed Analysis of Fiat-Shamir with Aborts

This chapter focuses on proving the security of Fiat-Shamir with Aborts. Indeed, previous proofs suffer from a common flaw, which we now describe.

A Flaw in Previous Proofs

An important caveat of rejection sampling is that with an aborting identification protocol, simply applying the Fiat-Shamir transform does not yield a correct signature, because of the rejection probability. However, one can adapt the transform by rerunning the signing algorithm until a non-aborting transcript is found: this is the Fiat-Shamir with aborts transform. Of course, this change of setting renders the generic security reductions of Fiat-Shamir useless in this case. This raises the question of the HVZK property needed: do we need to simulate aborting transcripts? Previous reductions [Lyu12,KLS18,AFLT16] only required to simulate non-aborting transcripts. However, those reductions only consider a specific case, where the number of aborts is bounded, for simplicity. Indeed, up to outputting ⊥, they assume that the signing algorithm is run at most B times: we call this Fiat-Shamir with Bounded Aborts (FSwBA).

An unsubstantiated intuition. We start by describing a first flaw appearing in all existing analyses. These analyses start as follows: in the genuine security experiment (denoted Game 0), all (successful or not) transcripts generated during a sign query use a challenge that is computed with the hash function. Then, a first hybrid (Game 1) changes the sign algorithm by sampling a uniformly random challenge and programming the hash function consistently with the successful proof transcript only. All proofs immediately conclude these two games are identical: the (unsubstantiated) intuition is that the adversary does not have access to the aborted transcripts, and hence programming these transcripts does not impact the adversary's view.

F1. Assume the challenger in the genuine CMA (or even CMA 1 ) security game answers a sign query µ using a sequence of commitments w 1 , w 2 , . . . . Assume that rejecting is a deterministic function of w and c (this is for example the case for Lyubashevsky's signatures with the parameters considers in [START_REF] Abdalla | Tightly secure signatures from lossy identification schemes[END_REF]).

Then, as soon as w 1 fails to produce a valid transcript, the hash value H(w 1 ∥µ) is fixed and the sign oracle can no longer return a valid signature which uses commitment w 1 . This is not the case in Game 1, since the hash value H(w 1 ∥µ) is not programmed by the failed attempt, and the sign query could return a signature (w 1 , c ′ , z ′ ) for c ′ ̸ = c.

FSwBA has been analyzed and used numerous times (we focus here on the most detailed analyses), yet the above flaw F1 appears in [Lyu12, Lemma 5.3], [Lyu16, Lemma 4.1], [KLS18, Theorem 3.2], and [Kat21, Lemma 4.6]. Moreover it appears in [START_REF] Abdalla | Tightly secure signatures from lossy identification schemes[END_REF] though not in Game 1 but in Game 0: in the proof of [AFLT16, Theorem 1], the authors directly start with the above Game 1 rather than with the correct Game 0. Finally, the difficulty with the hash function inconsistencies seems identified in [ABB + 17, Appendix B.4], but the authors do not handle the case of inconsistencies between different sign queries for the same message.

The fact that the adversary can make hash queries on superpositions of all inputs in the Quantum Random Oracle Model (QROM) makes it even more difficult to argue that the adversary cannot detect random oracle programmings, which induces additional errors.

A New, Complete Analysis of Fiat-Shamir with Aborts

Our first set of results concerns FSwBA. We assume that the identification protocol satisfies a stronger notion of HVZK, where one can simulate any transcript, even aborting ones. This notion of HVZK is closer to the standard definition in the case of non-aborting identification protocols. In particular, with this notion of HVZK, we can show that if we apply the Fiat-Shamir transform on the identification protocol, then the resulting signature may not be correct, but is at least unforgeable according to standard reductions such as [START_REF] Grilo | Tight adaptive reprogramming in the QROM[END_REF]. We can then consider the reduction which on FSwBA signature queries forwards these queries at most B times to the Fiat-Shamir signature oracle, which gives rise to a tight reduction. This is in essence what we do, except that we need to do it from scratch as the details of the reduction will help to prove the expected polynomial runtime of the signing algorithm in the case of Fiat-Shamir with Unbounded Aborts (FSwUA).

Our second set of results concerns FSwUA, i.e. the flavor of Fiat-Shamir with Aborts without an artificial bound on the number of iterations. On the negative side, we exhibit an interactive proof system such that applying FSwUA to it leads to a signature scheme such that:

• for all signing keys, with non-zero probability over the random oracle randomness, signing loops forever for all messages; in particular, the expected signing runtime is infinite;

• with overwhelming probability over the random oracle randomness, for all messages and all signing keys, the expected runtime of signing over its own randomness is below a fixed polynomial.

This suggests a modification of the signing efficiency requirement, in which the runtime expectation is not taken over the randomness of the random oracle, but should be bounded by a polynomial with overwhelming probability over the randomness of the random oracle. On the positive side, we give analyses of correctness, signing efficiency (with respect to the modified definition) and security for FSwUA in the ROM.

The main applications of these results are the Lyubashevsky and BLISS identification protocols. We show that they satisfy the stronger notion of HVZK we consider. Simulating a non-aborting transcript is done as usual: first sample z according to the target distribution, and then compute w = Az -Tc mod p, as c is given as an input of the simulator. In the case of aborting transcripts, we have to 1. Introduction compute w = Ay mod p with y sampled from the source distribution conditioned on z being rejected. We show that in usual cases, the entropy of y is sufficiently large, even with the conditioning, and the leftover hash lemma allows us to replace w with some uniform vector modulo p.

Throughout the chapter, we give an adaptation of the setting for another flavor of HVZK. We note that the simulator we exposed above can be decomposed in two parts: one part for non-aborting transcripts, and one part for aborting ones. We consider a specific case, where the simulator for non-aborting transcripts is close to real non-aborting transcripts in the sense of the Rényi divergence (aborted transcripts are still measured using the statistical distance). Given two distributions P and Q, the Rényi divergence of infinite order is the maximal ratio of their probability mass function. We recall its properties in Section 2.2.2.1. Sections pertaining to this specific case have a name starting with "Rényi Divergence Approach".

To understand its usefulness, we go back to the rejection sampling technique. We notice that for a given pair of source and target distribution, the proof that shows that the statistical distance between the rejection sampling output and the target distribution is ≤ ε also shows that their Rényi divergence of infinite order is (roughly) ≤ 1 + ε. Hence, both approaches can be applied to the Lyubashevsky identification protocol 3 . It turns out that by comparing them, we notice that the Rényi Divergence allows for larger ε, i.e. for a broader class of pairs of source and target distributions. Namely, the Rényi divergence approach gives useful reductions up to ε = O(1/Q s ), the number of signature queries, while the statistical distance approach is only meaningful up to ε = negl(λ).

While our results can be extended to the QROM, this chapter focuses on the ROM and classical adversaries, as the quantum part of this joint work was handled by a coauthor.

Chapter 4: Optimizing Lattice-based Identification Protocols

Equipped with the previous result, which gives us a class of admissible pairs of source and target distributions, we aim in this chapter at answering the question Q1. This chapter addresses it with a particular goal in mind: minimizing the expected norm of z. Indeed, as z makes up for (almost all of) the signature, minimizing its norm minimizes the signature size. Moreover, this also minimizes the verification bound, which in turns makes the signature harder to forge. To further formalize the question, we need to address how we model the expected signing time. We make the following assumptions in this chapter:

• We have a bound M ≥ 1 on the expected number of iterations under which we want to minimize the above.

• The runtime of one iteration is independent from the number of previous iterations and the choice of source and target distribution. Namely, the runtime is a linear function of M .

• The set of shifts {Sc} is modelled as a set of the form {v|∥v∥ ≤ t}, i.e. an hyperball.

On Alternative Rejection Sampling Strategies. In Section 4.2, we first investigate rejection sampling itself. Indeed, the classical rejection sampling algorithm has an expected runtime of R ∞ (P ∥Q) when rejecting from distribution Q to distribution P . If there is a way to make it faster, then we could look for even smaller distributions under the same time constraints. We consider the following setting. The goal is to sample from a distribution P given access to a sampler from a distribution Q, and we consider a sequence of samples (X i ) i≥1 from distribution Q. Any strategy is allowed as long as we output one of the X i 's. A strategy is given by a sequence of algorithms (A i ) i≥1 that take samples (X j ) j≤i as input and return either an index j ∈ [i], which corresponds to halting with output X j , or a special symbol r which corresponds to rejecting and moving to A i+1 . We restrict ourselves to the case of procedures that terminate with probability 1. Considering i * the random variable denoting the number of samples observed in a strategy, our objective is then to measure how small E(i * ) can be. We prove that for any P, Q, we have E(i * ) ≥ R ∞ (P ∥Q). This result is obtained by proving that for any x, we have P (x) ≤ E(i * ) • Q(x), leading to the former inequality by definition of R ∞ .

Lower Bounds. In Section 4.3, we prove lower bounds on achievable compactness in the case of exact rejection sampling in both unimodal and bimodal settings. These lower bounds are obtained following a similar path. In what follows, we focus on the unimodal setting.

Our lower bounds are obtained in three steps: (1) considering the same setting with continuous distributions, we first prove that we can restrict ourselves to the case of isotropic distributions over R m , where isotropic means that their densities only depend on the norm. (2) Starting with f and g isotropic, we show that E x← f (∥x∥) = µ m /µ m-1 where µ k = ∞ 0 r k f (r) dr. Our lower bound is then obtained by applying the Cauchy-Schwarz inequality |E(XY )| 2 ≤ E(X 2 )E(Y 2 ) to random variables X = ∥x∥ m/2 and Y = ∥x∥ (m-2)/2 , where x ← f . Indeed, it immediately leads to inequality µ m •µ m-2 ≥ (µ m-1 ) 2 , which results in µ m /µ m-1 ≥ µ m-1 /µ m-2 ≥ (t/M 1/(m-1) -1). (3) A similar lower bound in the discrete setting is obtained by considering the continuous density p(x) = P (⌈x⌋) with P being a discrete probability. These lower bounds provide us with a target to reach, and we can compare them with the signature size obtained when instantiating the above scheme with various distributions.

• Considering Lyubashevsky's scheme with perfect rejection sampling to the target distribution P (as in [START_REF] Lyubashevsky | Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures[END_REF]), the relevant quantity measuring the signing runtime is then given by M = max S,c R ∞ (P ∥Q +Sc ). We show (under a mild assumption discussed below) that for all P and Q such that M is finite, the expected norm

E x← P (∥x∥) is Ω((m/ log M ) • max S,c ∥Sc∥).
• In the case of perfect rejection with the accommodating arithmetic modification from [START_REF] Ducas | Lattice signatures and bimodal Gaussians[END_REF], then the relevant quantity for measuring the signing runtime is M = max S,c R ∞ (P ∥Q ±Sc ), where Q ±Sc denotes the balanced mixture of Q +Sc and Q -Sc . In this case, we show (under the same mild assumption) that for all P and Q such that M is finite, the expected norm

E x← P (∥x∥) is Ω( m/ log M • max S,c ∥Sc∥).
Usual Choices. We recall in Section 4. 4.3 results on two usual choices for source and target distributions. Namely, the uniform distribution in hypercubes and the discrete Gaussian distribution. Gaussian distributions provide better signature compactness in the bimodal and imperfect unimodal regimes, than uniforms in hypercubes in the perfect unimodal regime. In the perfect unimodal setting, our lower bound is a factor √ m lower than the hypercube result, while Gaussian distributions are incompatible with this setting. In the bimodal setting, our lower bound is actually reached (up to a constant factor) by discrete Gaussian distributions as in [START_REF] Ducas | Lattice signatures and bimodal Gaussians[END_REF].

However, uniforms in hypercubes are sometimes preferred (see, e.g., Dilithium), because they lead to a simpler implementation, which in turn makes protection against timing attacks easier.

Hyperball Uniforms. We show that (continuous) uniform distributions over hyperballs reach the signature compactness lower bound (up to constant factors) in both unimodal and bimodal settings, as shown in Section 4. 4.1. We also show that they are experimentally as good as Gaussians for imperfect rejection sampling. These results reduce to Rényi divergence computations, which involve geometric properties of hyperballs. We emphasize that while Gaussian distributions also achieve similar signature size in both unimodal and bimodal settings (but only in the case of imperfect rejection sampling with polynomial loss for the unimodal case), using uniform distributions over hyperballs makes the rejection test as simple as computing ∥z∥ in the unimodal case since it consists only in checking that z is in the hyperball of the target distribution P . In the bimodal case, the rejection test involves computing two norms and flipping a coin. In order to use this distribution in a signature, we propose a generalization of Lyubashevsky's signature that allows for continuous source and target distributions, by adding a rounding step after accepting a sample. Its security relies on the same mechanisms as the discrete case. This strategy could also benefit to Gaussian distributions, by allowing to replace discrete Gaussian sampling with possibly simpler continuous Gaussian sampling. To assess the practicality of this new choice of distributions, we propose parameters for a variant of Dilithium with uniform distributions in hyperballs. If considering the sum of bitsizes of a verification key and a signature, the gains range from ∼ 25% to ∼ 30%, depending on the security level, just like for the Gaussian variant, whose parameters we also update.

The results concerning signature compactness for unbounded (perfect and imperfect) rejection sampling are summarized in Table 1. 1. For practical estimations, we give in Table 1.2 the estimated sizes for the signatures based on unimodal Gaussian rejection sampling and unimodal hyperball rejection sampling, assuming that they integrate various standard optimizations, such as relying on polynomial modules instead of Z n , and considering compression of the signature via truncation of its lower bits.

Chapter 5: HAETAE, A New Implementation of Lattice-based Fiat-Shamir with Aborts

As a natural follow-up to the two previous chapters, we propose HAETAE4 , an implementation of the hyperball-uniform bimodal variant of Lyubashevsky's sig-

Unimodal (ε = 0) Unimodal (ε ≥ 2 -o(m) and ε = o(1/m)) Bimodal (ε = 0) Hypercube tm 3/2 log M tm 3/2 log M tm 3/2 log M Gaussian ∞ t √ m log 1 ε +log M log M t √ m √ log M Hyperball tm log M (Lemma 4.10) t √ m log 1 ε +log M log M (Lemma 4.10) t √ m √ log M (Lemma 4.11) Lower bound tm log M (Corollary 4.6) ? t √ m √ log M (Corollary 4.9)
Table 1.1: Optimal asymptotic expected Euclidean norm of z for different pairs of source and target distributions. Parameter M quantifies the expected number of iterations, ε quantifies the accuracy of the rejection sampling, m is the dimension of z and t is an upper bound on ∥Sc∥. Multiplicative constants are omitted and we assume that log M ≤ m. The last row corresponds to the lower bounds we computed. nature. This implementation features various optimizations, already present in Dilithium [BDK + 20] and which we adapt to the bimodal setting.

The HAETAE team is comprised of ten members and informations about the project can be found on the website 5 . It is a submission to the Korean post-quantum competition6 and to the fourth round of the NIST post-quantum signature competition 7 .

It implements the bimodal hyperball setting from Chapter 4. We adapted the following optimizations, which were already considered in multiple schemes, e.g., Dilithium, Kyber, Saber, to the bimodal setting for our implementation. We also adapted continuous hyperball sampling to discrete hyperball sampling in order to enable fixed-point arithmetic in the signature algorithm.

Polynomial modules. Instead of working over Z m , we rely on polynomial modules over a power-of-two cyclotomic ring, thus speeding up computations and decreasing the sizes.

Modulus and truncating the verification key. First, as we noted in the previous chapter, the bimodal hyperball setting leads to the smallest for the Euclidean norm signatures. For the same SIS security than Dilithium, we are thus able to aggressively decrease the modulus, from 23 to 16 bits. As the verification key bit-size is proportional to the logarithm of the modulus, this helps reducing it. Moreover, we adapt Dilithium's verification key truncation to our setting. However, as we already enjoy the modulus reduction, our adaptation turns out to be less efficient than Dilithium's as we only cut at most 1 bit per coordinate.

Compression techniques to lower the signature size. We use two techniques to compress the signatures. First, as the verification key A is in (almost)-HNF, we rely on the Bai-Galbraith technique [START_REF] Bai | An improved compression technique for signatures based on learning with errors[END_REF]. Namely, the second part of the signature, which is multiplied by 2Id in the challenge computation and verification algorithm, can be aggressively compressed by cutting its low bits. This requires in turn modifying the computation of the challenge c and the verification algorithm, in order 1. Introduction to account for this precision loss. Usually, this is done by keeping only the high bits of Ay in the computation of the challenge. However, as we multiply everything by 2, we do not keep the lowest bit of those high bits and keep the (overall) least significant bit instead. As in Dilithium, our decomposition of bits technique is a Euclidean division with a centered remainder, and we choose a representative range for modular integers that starts slightly below zero to further reduce the support of the high bits. The second compression technique, suggested in [START_REF] Espitau | Shorter hash-andsign lattice-based signatures[END_REF] in the context of lattice-based hash-and-sign signatures, concerns the choice of the binary representation of the signature. As the largest part of it consists in a vector that is far from being uniform, we can choose some entropic coding to obtain a signature size close to its entropy. In particular, as in [START_REF] Espitau | Shorter hash-andsign lattice-based signatures[END_REF], we choose the efficient range Asymmetric Numeral System to encode our signature, as it allows us to encode the whole signature and not lose a fraction of a bit per vector coordinate, like with Huffman coding. We can further apply the two techniques to the hint vector h, which is also a part of the signature, to reduce the signature sizes.

Fixed-point algorithm for hyperball sampling. Unlike uniform Gaussian sampling or uniform hypercube sampling, uniform hyperball sampling has not been considered in the cryptographic protocols before the suggestion of [START_REF] Devevey | On rejection sampling in lyubashevsky's signature scheme[END_REF]. To narrow the gap between the hyperball uniforms sampled in the real and the ideal world, we discretize the hyperball and bound the numerical error and their effect by analyzing their propagation. This leads to a fixed-point hyperball sampling algorithm and, therefore, the fixed-point implementation of the whole signing process.

Let us briefly compare the resulting scheme with Dilithium and Falcon.

Comparison with Dilithium. Once the design rationale was set, I was mainly involved with the parameter computations. We chose the core-SVP methodology, a conservative approach to security estimation. Our signature size is 25% to 40% smaller than Dilithium's while the verification key is 20% to 25% smaller as seen in Table 1. 2. This comes at the price of having a less efficient signature algorithm. However, we note that the hyperball sampling takes up to 80% of the total runtime, and thus any improvement on this sampler would lead to massive gains in the signing time. Finally, we note that our design is based on Dilithium-G, which appears in a preliminary version of [DKL + 18], and its design has a few subtle differences with Dilithium when it comes to the role of the hint and in the definition of the commitment, where both are optimized for hypercubes in Dilithium.

Comparison with Hash and Sign lattice signatures. In terms of ease of implementation, our scheme favorably compares to lattice signatures based on the hash and sign paradigm such as Falcon [FHK + 17] and Mitaka [EFG + 22]. HAETAE, Falcon and Mitaka all three rely on some form of Gaussian sampling, which are typically difficult to implement and protect against side-channel attacks. Falcon makes sequential calls to a Gaussian sampler over Z with arbitrary centers. Mitaka also relies on an integer Gaussian sampler with arbitrary centers, but the calls to it can be massively parallelized. It also uses a continuous Gaussian sampler, which is arguably simpler. HAETAE, however, only relies on a (zero-centered) continuous Gaussian sampler, used to sample uniformly in hyperballs. The calls to it can also be massively parallelized. This difference makes HAETAE possible to have a fixed-point signing algorithm and easier maskings. Further, in the randomized version of the signature scheme, these samples can be computed off-line as they are independent from the message to be signed. The on-line tasks are far simpler than those of Falcon and Mitaka. Finally, we note that key-generation is much simpler for HAETAE than in Falcon and Mitaka.

While HAETAE is simpler from an implementation perspective, its verification key and signature sizes are larger than Falcon's and Mitaka's. 1.2.4 Chapter 6: Towards Efficient Lattice-based Fiat-Shamir In this last chapter, we introduce a new paradigm for adapting Schnorr's identification protocol to the lattice setting. It relies on Gaussian convolution, rather than flooding or rejection sampling. Our G + G (Gaussian Plus Gaussian) identification protocol can be compiled into a signature using the Fiat-Shamir heuristic (without aborts), in the QROM.

G + G involves two Gaussian samples that are being summed. The first one is y and the second one corresponds to Sc. The first difficulty that we face is that S is fixed and c is publicly known as part of the resulting signature and hence cannot be assumed random for the sake of studying the distribution of z.

To introduce the required new randomness, we start from BLISS [START_REF] Ducas | Lattice signatures and bimodal Gaussians[END_REF]. Recall that the verification key A ∈ Z m×k 2q and the signing key S ∈ Z k×m satisfy the relation AS = qI m mod 2q. Among the variants of Lyubashevsky's signature, it is a specificity of BLISS to work modulo 2q, which is particularly useful in our case. The commitment of the prover is w = Ay mod 2q, and upon receiving c ∈ {0, 1} m , the prover replies with either z = y + Sc or z = y -Sc with probability 1/2 each. The verifier checks that z is short and Az = w + qc mod 2q. This check works for both values of z that the prover chose from. This can be explained by observing that the verification views c modulo 2, i.e., as a coset of Z m /2Z m , and negating it does not change the coset. This observation was used in [START_REF] Ducas | Accelerating bliss: the geometry of ternary polynomials[END_REF] to take negations of individual coordinates of c to minimize the Euclidean norm of Sc and hence decrease the standard deviation of y necessary to hide Sc via rejection sampling. We go further and let the prover extend the coset c sent by the verifier to a Gaussian sample with support 2Z m + c. The verification equation above still holds, and we now have our second Gaussian.

At this stage, the prover samples a Gaussian y over Z k , transmits w = Ay mod 2q, receives a uniform coset c ∈ Z m /2Z m from the verifier, produces a Gaussian sample x with support 2Z m + c and computes z = y + Sx. Equivalently, it samples k Gaussian with support 2SZ m + Sc and returns z = y + k. In order to obtain the zero-knowledge property (i.e., be able to simulate signatures without knowing the signing key), we aim to prove that the distribution of the Gaussian convolution z can be sampled from publicly. If y and k were continuous Gaussians, we would set their covariance matrices Σ y and Σ k such that Σ y + Σ k = Σ z for a known covariance matrix Σ z for z. To fix the ideas, we could set Σ z = σ 2 I for some σ > 0, i.e., the distribution of z is a spherical Gaussian, and set Σ y = σ 2 I -Σ k . If we sample x from a spherical Gaussian with standard deviation s > 0, then Σ k = s 2 SS ⊤ and Σ y = σ 2 I -s 2 SS ⊤ (by taking σ sufficiently large, the latter is indeed definite positive). This is the choice we actually make for G + G, but there is flexibility.

The above over-simplifies the situation as the Gaussians we manipulate are discrete rather than continuous. Further, their supports do not have the same dimensions. Indeed, the support of y is Z k whereas the support of k is exactly 2SZ m + Sc whose span has dimension m < k: the second Gaussian lives in a smaller dimension and its support is sparser. This is illustrated in Figure 1.1. Convolution of discrete Gaussians has been studied in [START_REF] Boneh | Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures[END_REF], but restricted to the case of full-dimensional supports. As a technical contribution, we extend their result to rank-deficient Gaussians with co-diagonalizable covariance matrices. Thanks to the above, if the covariance matrices are set appropriately, then G + G is honest-verifier zero-knowledge (HVZK). The proofs of completeness and soundness are adapted from [START_REF] Ducas | Lattice signatures and bimodal Gaussians[END_REF]. To apply the Fiat-Shamir heuristic, we also need the commitment Ay to have sufficiently high min-entropy. This is technically more complex than for Lyubashevsky's signatures as y is distributed from a skewed Gaussian. The properties satisfied by G + G allow a conversion to a secure signature scheme, using completeness and commitment-recoverability to obtain the correctness of the signature, HVZK and commitment-min-entropy to reduce security against chosenmessage attacks to security against no-message attacks, and computational soundness (resp. lossy-soundness) which implies security against no-message attacks for different parametrizations.

Comparison with BLISS. Among variants of Lyubashevsky's signatures, BLISS provides the smallest z: its expected norm can be as small as σ 1 (S)m/ √ log M (up to a constant factor), where σ 1 (S) is the largest singular value of S and M is the expected number of repetitions (see Lemma 4.16). Further, following Corollary 4.9, this is essentially optimal for Lyubashevsky's signatures, even if we allow to optimize over the choice of source and target distributions. In the case of G + G, the strongest constraint on parameters is essentially that the standard deviation σ of z be sufficiently large to "smooth out" the lattice 2SZ m . By using the variant of the HVZK property based on the Rényi divergence rather than the statistical distance defined in Definition 3.3, where we further set p = 0 as no rejection is involved, it suffices that σ be above σ 1 (S) √ log Q S , up to a constant factor, where Q S is the maximum number of signature queries that the adversary is allowed to make. As a result, the

expected norm of z in G + G is σ 1 (S) √ m log Q S .
We conclude by observing that log Q S is typically much smaller than m, and that the √ log M term from BLISS cannot grow sufficiently to compensate for the difference. More concretely, if we set M = λ Θ (1) , Q S = λ Θ (1) and m = Θ(λ), where λ is the security parameter, then the expected norms of z in BLISS and G + G respectively grow as σ 1 (S) • λ/ √ log λ and σ 1 (S) • √ λ log λ. Optimization and concrete parameters. While all key generation techniques pre- sented in [START_REF] Ducas | Lattice signatures and bimodal Gaussians[END_REF] can be used with our G + G protocol, we present alternative versions which offer more flexibility. A first improvement is that we can set AS = qJ mod 2q, where J ∈ Z m×ℓ q is only rectangular and full column-rank rather than set to the identity. Departing from the BLISS setting, when instantiating G + G with the MLWE and MSIS hardness assumptions [START_REF] Brakerski | Leveled) fully homomorphic encryption without bootstrapping[END_REF][START_REF] Langlois | Worst-case to average-case reductions for module lattices[END_REF]

over a ring R = Z[x]/(x n +1)
with n a power of 2, we take j = (x n/2 + 1, 0, . . . , 0). This allows us to replace the lattice 2sR with (x n/2 -1)sR, and to decrease the standard deviation of z by a factor √ 2. Overall, we obtain signature sizes that are between 20% and 30% smaller than those from Chapter 4, or 35% to 45% smaller than Dilithium [DKL + 18]. We recall that Table 1.2 summarizes all the different sizes for the different signatures presented in this thesis.

Other Contributions and Publications

The various results from this thesis and complimentary findings resulted in the following publications. The last chapter of this thesis, Chapter 6, is currently in review process for publication. The version presented in this thesis is already the full version and no content was omitted.

Additionally, three more publications resulted from these PhD years. They are omitted from this manuscript for consistency as they approach different topics. Consider a polynomial ring Z[x]/f (x) and a prime q. We compare the hardness of the LWE problem over this ring with the hardness of the problem where each polynomial is evaluated at q and reduced modulo f (q) before doing any operation. This allowed to prove the hardness of a variant of ThreeBears, a round 2 key-exchange mechanism submission to the NIST post-quantum competition.

[ Chapter 2

Preliminaries

We start by introducing all the notations we use and we recall the previous results we rely on and give some extensions.

Notations

Matrices are denoted in bold font and upper case letters (e.g., A), while vectors are denoted in bold font and lowercase letters (e.g., y or z 1 ). The i-th component of a vector is denoted with subscript i (e.g., y i for the i-th component of y).

Vectors are column vectors. We let (u, v) denote concatenation between matrices and/or vectors by putting the rows below and (u|v) the columns on the right.

When we consider a probability density, this is with respect to the canonical (i.e., Lebesgue or counting) measure µ over their support. We may identify the notion of probability distribution and probability density in the discrete case. Given two probability distributions F and G with densities f and g, we let x ← F denote the sampling of x according to F . We let Supp(F ) denote the smallest (for inclusion) set such that for any set X, we have F (X ∩ Supp(F )) = F (X). In particular, in the case where F is discrete, then we have Supp(F ) = {x|F (x) ̸ = 0}. Given a set S ⊆ Supp(F ), we let F S denote the distribution F cut to S, i.e., the measure F/F (S) restricted to S. We let F ⊗ G denote the distribution of (x, y) where x ← F and y ← G are independent and f ⊗g one of its density. Moreover given an element x, we let F +x (respectively F ±x ) denote the distribution with density f +x : y → f (y-x) (respectively f ±x : y → (f (y -x) + f (y + x))/2). Given a finite or measurable set S, we let U (S) denote the uniform distribution over S. We let N (µ, σ) denote the normal distribution centered at µ with standard deviation σ. By notation abuse, we use algorithm names to denote the random variable associated to their output.

Given a dimension m ≥ 1, a center c ∈ R m and a radius r > 0, we let B p m (r, c) (resp. S p m (r, c)) denote the p-norm ball (resp. sphere) of radius r and center c for

any p ∈ [1, +∞]. When p = 2 (resp. c = 0), we omit it. Let V m (r) := π m/2
Γ(m/2+1) r m denote its volume as well as S m = m • V m (1) denote the surface of the unit sphere.

Given a set and a subset S ⊆ Y we let χ S : x → {1 if x ∈ S, 0 if x ∈ Y \ S} denote the indicator function of S. Let ⌈•⌋ : R → Z be the rounding operator that maps x to the nearest integer (in case of a tie, it is rounded downwards). It is naturally extended to R n by coordinate-wise application. The notation log refers to the natural logarithm, except in Chapter 3.

For some λ going to infinity, we let negl(λ) = λ -ω (1) as well as poly(λ) = λ O (1) . Let H : D → R be a function with finite R. It is modeled as a random oracle by replacing it by a uniformly sampled function among those from D to R. We call this the random oracle model (ROM). To denote that it is reprogrammed at input x to the value y we use the notation H x →y .

For a positive integer α, we let r mod ± α denote the unique integer r ′ satisfying the relation r = r ′ mod α in the range [-α/2, α/2). We also define r mod + α as the unique integer r ′ in the range [0, α) satisfying r = r ′ mod α. We let LSB(r) denote the least significant bit of an integer r. We naturally extend this to integer polynomials and vectors, by applying it component-wise.

Probabilities

This section introduces commonly-used probability tools.

Min-Entropy and Statistical Distance

We recall the definition of min-entropy and conditional min-entropy.

H ∞ (Y |Z) p X = -log Supp(p Z ) p Z (z) max y∈Supp(p Y |Z=z )
p Y |Z=z (y) dµ(z) .

To quantify similarities between distributions, we consider the statistical distance.

Definition 2.2 (Statistical Distance). Let P, Q be two probability distributions with respective densities p, q. Their statistical distance is

∆(P, Q) := 1 2 Supp(P )∪Supp(Q) |p(x) -q(x)| dµ(x).
We recall the Leftover Hash Lemma, which we use in Chapter 3.

Lemma 2.1 (Leftover Hash Lemma). Let n, m > 0 and q be a prime and define the set H = {A ∈ Z n×m q : y → Ay}. Then for any random variable X over Z m q and ε > 0 such that H ∞ (X) ≥ log q n + 2 log(1/ε), the distributions (h, h(X)) and (h, U (Z n q )) are within statistical distance ε.

Rényi Divergence and Extension

The Rényi Divergences form a class of divergences which play a central role in this work. Indeed, in the case of lattice-based signatures, it often gives tighter security bounds than what is obtained through the use of the statistical distance. Moreover, the Rényi divergence of infinite order shares a strong link with rejection sampling, which we explicit in Section 2.2.3.

Rényi Divergence

We start by recalling the definition of the Rényi divergence of order a ∈ (1, +∞]. Definition 2.3 (Rényi divergence). Let a ∈ (1, +∞). Let P, Q be two probability distributions with P absolutely continuous with respect to Q. Their Rényi divergence of order a, assuming that it exists, is R a (P ∥Q) :=

Supp(P ) dP dQ (x) a-1 dP (x) 1 a-1 . Their Rényi divergence of infinite order is R ∞ (P ∥Q) := ess sup x∈Supp(P ) dP dQ (x).
By notation abuse, we may use random variables instead of probability densities as arguments, for the notions defined above.

The following lemma lists standard properties of the Rényi divergence.

Lemma 2.2 ( [vEH14]

). Let X and Y be two random variables with probability distributions P X and P Y such that Supp(P X ) ⊆ Supp(P Y ). The following holds for any order a ∈ (1, +∞].

• Log. Positivity: R a (P X ∥P Y ) ≥ R a (P X ∥P X ) = 1.

• Data Processing Inequality:

R a (P f (X) ∥P f (Y ) ) ≤ R a (P ∥Q) (2.1)
for any map f , where P f (Z) denotes the distribution of f (Z) for Z = X or Y .

• Multiplicativity:

Let X = (X 1 , X 2 ) and Y = (Y 1 , Y 2 ). Let P X 1 and P Y 1 denote the probability distribution of X 1 and Y 1 . Let P X 2 |X 1 =x and P Y 2 |Y 1 =x denote the distribution of X 2 conditioned on X 1 = x as well as Y 2 conditioned on Y 1 = x. If X 1 and X 2 are independent and Y 1 and Y 2 are independent, then R a (P X ∥P Y ) = R a (P X 1 ∥P Y 1 )R a (P X 2 ∥P Y 2 ). Otherwise R a (P X ∥P Y ) ≤ R ∞ (P X 1 ∥P Y 1 ) • max x∈Supp(P X 1 ) R a (P X 2 |X 1 =x ∥P Y 2 |Y 1 =x ).
• Probability Preservation: For any event E ⊆ Supp(P Y ),

P Y (E) ≥ P X (E) a a-1 R a (P X ∥P Y ) . ( 2

.2)

The Rényi divergence is non-decreasing and continuous as a function of a ∈ [1, +∞], as long as it is finite.

The following result is used in Chapter 6. Lemma 2.3. Let ε < 1. Let P and Q be two random variables taking values in some countable set Ω. Let c ∈ R be a constant such that

∀a ∈ Ω : Pr[Q = a] = c(1 -δ(a)) Pr[P = a] ,
for some function δ : Ω → [0, ε]. Then it holds that:

R ∞ (P ∥Q) ≤ 1 1 -ε , R ∞ (Q∥P ) ≤ 1 1 -ε and ∆(P, Q) ≤ ε 1 -ε .
Proof. Let us first note that (1 -ε)c ≤ 1 ≤ c, by summing the above equality over all a ∈ Ω and applying the bounds on δ(a). Then we have

R ∞ (P ∥Q) = sup a∈Ω Pr[P = a] Pr[Q = a] = sup a∈Ω 1 c(1 -δ(a)) ≤ 1 1 -ε .
We also have

R ∞ (Q∥P ) = sup a∈Ω Pr[Q = a] Pr[P = a] = sup a∈Ω c(1 -δ(a)) ≤ c ≤ 1 1 -ε .
Finally, we refer to [BF11, Lemma A.2] for the third bound.

Smooth Rényi Divergence

We introduce a relaxed version of the Rényi divergence, termed the smooth Rényi divergence, where one is able to remove a few problematic points from the support, including those that may lie in Supp(p) \ Supp(q). Doing so, we can compare a wider set of probability distributions. For instance, while the Rényi divergence of infinite order between the discrete Gaussian distributions D Z m ,σ and D Z m ,σ,v (as defined in Section 2.3) is infinite when v ̸ = 0, their smooth divergence is finite, as we show in Lemma 4.15 and is implicit in [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF]. We could give this definition for any order a ∈ [1, +∞]. However, only the case a = +∞ is relevant for this work. This definition is useful to link previous works on rejection sampling and the Rényi divergence. A similar quantity has been previously defined in the quantum information literature [START_REF] Renner | Security of quantum key distribution[END_REF][START_REF] Datta | Min-and max-relative entropies and a new entanglement monotone[END_REF], though the specific notion of smoothing we consider here is slightly different. Definition 2.4 (Smooth Rényi Divergence). Let ε ≥ 0. Let p, q be two probability densities such that Supp(q) p(x)

dµ(x) ≥ 1 -ε. Their ε-smooth Rényi divergence of infinite order is R ε ∞ (p∥q) := inf S⊆Supp(q) S p(x) dµ(x)≥1-ε ess sup x∈S p(x) q(x) .
This definition is equivalent to

R ε ∞ (p∥q) := inf{M > 0 | Pr x← p (p(x) ≤ M q(x)) ≥ 1 -ε}. By convention, if Supp(q) p(x) dµ(x) < 1 -ε, we define R ε ∞ (p∥q) = +∞.
We first prove that the two definitions of Definition 2.4 are indeed equivalent.

Proof. Let R ε ∞ (p∥q) be the first quantity and R ε ∞ (p∥q) be the second one. Let S ⊆ Supp(q) such that S p(x) dµ(x) ≥ 1 -ε. Let M = sup x∈S p(x) q(x) , i.e.

Pr x← p [p(x) ≤ M q(x)] ≥ S p(x) dµ(x) ≥ 1 -ε. Then R ε ∞ (p∥q) ≤ M . By definition of R ε ∞ (p∥q), this implies the first inequality R ε ∞ (p∥q) ≤ R ε ∞ (p∥q). Now let M > 0 such that Pr x← p (p(x) ≤ M q(x)) ≥ 1 -ε. Define S := x ∈ Supp(p) ∪ Supp(q) | p(x) ≤ M q(x) .
Then S p(x) dµ(x) ≥ 1 -ε by definition. Note that if we choose S ′ = S ∩ Supp(p) we have S ′ p(x) dµ(x) = S p(x) dµ(x) as we only removed elements that were not in the support of p. Moreover, assume that there exists x ∈ S ′ such that x ̸ ∈ Supp(q). We would have p(x) ≤ M • 0 = 0, contradicting the fact that x ∈ Supp(p). Then it holds that S ′ = {x ∈ Supp(q)|p(x) ≤ M q(x)}. We have

M ≥ sup x∈S ′ p(x) q(x) , S ′ p(x) dµ(x) ≥ 1 -ε and S ′ ⊆ Supp(q).
This implies, by definition of

R ε ∞ (p∥q) that M ≥ R ε ∞ (p∥q)
. By definition of the second quantity, we have the inequality R ε ∞ (p∥q) ≤ R ε ∞ (p∥q), thus completing the proof of the equality.

We now give a few properties of the smooth Rényi divergence. The probability preservation and multiplicativity properties are used in the security proof of our signature variant with a bounded number of rejection steps as we define in Chapter 4. The comparison to the Rényi divergence is used to bound the smooth Rényi divergence between Gaussian distributions.

We start by proving a probability preservation property.

Lemma 2.4 (Probability Preservation). Let P, Q be two distributions. For any ε ≥ 0 such that R ε ∞ (P ∥Q) is finite, the following holds.

∀E ⊆ Supp(P ), P (E) ≤ R ε ∞ (P ∥Q) • Q(E) + ε. Proof. Let S := {x ∈ Supp(P )|P (x) ≤ R ε ∞ (P ∥Q)•Q(x)}.
We decompose the event E into the disjoint union (E ∩ S) ∪ (E \ S). The following holds:

• P (E ∩ S) ≤ R ε ∞ (P ∥Q) • Q(E ∩ S) ≤ R ε ∞ (P ∥Q) • Q(E)
, by definition of S,

• P (E \ S) ≤ ε, by definition of R ε ∞ (P ∥Q).
Combining both inequalities yields the result.

In the case of Fiat-Shamir signatures, the security loss bound may depend on the number of signing queries. The following result then proves useful.

Lemma 2.5 (Multiplicativity). Let (X 1 , X 2 ) (resp. (Y 1 , Y 2 )) be a random variable with probability density p X 1 X 2 (resp. p Y 1 Y 2 ). Let p X 1 (resp. p Y 1 ) be the density of X 1 (resp. Y 1 ). For any x, let p X 2 |X 1 =x (resp. p Y 2 |Y 1 =x ) denote the probability density of X 2 (resp. Y 2 ) conditioned on X 1 = x (resp. Y 1 = x). For any ε 1 , ε 2 ≥ 0 it then holds that R ε 1 +ε 2 ∞ (p X 1 X 2 ∥p Y 1 Y 2 ) ≤ R ε 1 ∞ (p X 1 ∥p Y 1 ) • sup x∈Supp(p X 1 ) ∩Supp(p Y 1 ) R ε 2 ∞ (p X 2 |X 1 =x ∥p Y 2 |Y 1 =x ). Proof. Let R 1 = R ε 1 ∞ (p X 1 ∥p Y 1 ) and R 2 = sup x∈S 1 R ε 2 ∞ (p X 2 |X 1 =x ∥p Y 2 |Y 1 =x ), where we let S 1 = Supp(p X 1 ) ∩ Supp(p Y 1 ). If R 1 = +∞, the statement is vacuously true. Assuming that this is not the case, we now define R = R 1 • R 2 and S = (x, y) ∈ Supp(p X 1 X 2 ) | p X 1 X 2 (x, y) > R • p Y 1 Y 2 (x, y) . Any pair (x, y) ∈ S satisfies p X 1 (x)p X 2 |X 1 =x (y) > Rp Y 1 (x)p Y 2 |Y 1 =x (y) or it holds that x ̸ ∈ Supp(P Y 1 ). This implies that it either holds that p X 1 (x) > R 1 • p Y 1 (x) or p X 2 |X 1 =x (y) > R 2 p Y 2 |Y 1 =x (y).
We then have, using the union bound,

S p X 1 X 2 (x) dx ≤ Pr x← p X 1 [p X 1 (x) > R 1 • p Y 1 (x)] + x∈S 1 p X 1 (x) • Pr y← p X 2 |X 1 =x p X 2 |X 1 =x (y) > R 2 • p Y 2 |Y 1 =x (y) ≤ ε 1 + x∈S 1 p X 1 (x)ε 2 ≤ ε 1 + ε 2 .
Define the set

S := Supp(p Y 1 Y 2 ) \ S = {(x, y) ∈ Supp(p Y 1 Y 2 )|p X 1 X 2 (x, y) ≤ R • p Y 1 Y 2 (x, y)}.
We have S = (Supp(p

X 1 X 2 ) ∪ Supp(p Y 1 Y 2 )) \ S, as Supp(p X 1 X 2 ) \ Supp(p Y 1 Y 2 ) ⊆ S. Then it satisfies S p X 1 X 2 (x) dx ≥ 1 -ε 1 -ε 2 .
The first definition of the smooth divergence provides the result.

Noticing that R a (P ∥Q) a-1 = E x← P ((p(x)/q(x)) a-1 ), we can apply concentration inequalities to compare the smooth divergence and the Rényi divergence, as was done in [START_REF] Renner | Smooth Rényi entropy and applications[END_REF] for entropies. We however recall that the smooth Rényi divergence may be finite for pairs of random variables for which the Rényi divergence is infinite, in which case our bound is trivial.

Lemma 2.6. Let X, Y be two discrete random variable with probability distributions P X and P Y . For any ε ≥ 0 and order a ∈ (1, +∞) it holds

R ε ∞ (P X ∥P Y ) ≤ R a (P X ∥P Y ) ε 1/(a-1) and R ε ∞ (P X ∥P Y ) ≤ R ∞ (P X ∥P Y ).
Proof. Markov's inequality gives that for any t > 0,

Pr x← P X P X (x) P Y (x) a-1 ≥ t ≤ R a (P X ∥P Y ) a-1 t .
Algorithm A real :

1: x ← p s with probability min pt(x) M •ps(x) , 1 , 2: return x 3: return ⊥ Algorithm B real ∞ : 1: z ←⊥ 2: while z =⊥ do 3: z ← A real 4: end while 5: return z Algorithm A ideal : 1: x ← p t with probability 1 M , 2: return x 3: return ⊥ Algorithm B ideal ∞ : 1: z ←⊥ 2: while z =⊥ do 3:
z ← A ideal 4: end while 5: return z Setting t 0 such that R a (P X ∥P Y ) a-1 /t 0 = ε, we have:

Pr x← P X [P X (x) ≥ t 1/(a-1) 0 • P Y (x)] ≤ ε. By the second definition of R ε ∞ (P X ∥P Y ), this shows R ε ∞ (P X ∥P Y ) ≤ t 1/(a-1) 0 = R a (P X ∥P Y ) ε 1 a-1 .
To conclude the proof, recall that the Rényi divergence is continuous as a function of a. Taking the limit of this upper bound when a tends to +∞ gives the second result.

Rejection Sampling

Given two close enough densities p t and p s , either both continuous or both discrete, rejection sampling is a way to generate samples from p t given access to samples from p s , as explained for instance in [START_REF] Devroye | Non-Uniform random variate generation[END_REF]. It was used mainly to generate samples from complex distributions that were "close" to easier-to-sample distributions. However, in cryptography and particularly in the line of works started with [START_REF] Lyubashevsky | Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures[END_REF], it found a peculiar use that diverged from its primary use. Given a family of densities (p

(v)
s ), rejection sampling can be used to hide the parameter v given a density p t that is close to every density in this family. It was later observed in [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF] that an "imperfect" rejection procedure is sufficient for this use and leads to smaller parameters, notably standard deviation of p s .

We consider the following algorithms from Figure 2.1, which take some M ≥ 1 as a parameter. Algorithm B real ∞ is the rejection sampling algorithm and A real is one iteration. Algorithm B ideal ∞ is the target distribution, which we break down for analysis. The following lemma, phrased here in full genericity and in terms of smooth Rényi divergence, expresses the closeness of the outputs of the algorithms both in terms of statistical distance and Rényi divergence.

Preliminaries

(p t (z) ≤ M • p s (z)) ≥ 1 -ε,
which can be rewritten in terms of smooth Rényi divergence as R ε ∞ (p t ∥p s ) ≤ M . Then the probability A real (⊥) that A real aborts is such that

M -1 M ≤ A real (⊥) ≤ M -1 + ε M .
We have

∆(A real , A ideal ) ≤ ε/M and ∆(B real ∞ , B ideal ∞ ) ≤ ε as well as R ∞ (A real ∥A ideal ) ≤ 1 + ε M -1 and R ∞ (B real ∞ ∥B ideal ∞ ) ≤ 1 1 -ε .
Proof. Let S = Supp(p t ) ∪ Supp(p s ). Let us write for any x ∈ Supp(p s ):

min p t (x) M p s (x) , 1 = 1 C • min (p t (x), M • p s (x)) M C • p s (x)
, where C is normalization constant defined as

C = Supp(ps) min (p t (x), M • p s (x)) dx.
Notably, we have

1 ≥ C ≥ 1 -ε,
A real (⊥) = 1 - C M ∈ M -1 M , M -1 + ε M ,
and the density of

A real is x → (1 -A real (⊥)) • p ′ t (x) = min(p t (x)/M, p s (x)).
Let us then bound the statistical distance.

∆(A real , A ideal ) = 1 2 S p t (x) M -min p t (x) M , p s (x) dx + 1 2 A real (⊥) - M -1 M ≤ 1 2 S max 0, p t (x) M -p s (x) dx + ε 2M ≤ 1 2 {x∈S|ps(x)≤pt(x)/M } p t (x) M -p s (x) dx + ε 2M ≤ ε 2M + ε 2M ,
by assumption on p s and p t .

To bound the statistical distance between B real ∞ and B ideal ∞ , we first note that their distributions actually correspond to the distributions of A real and A ideal conditioned on the fact that they do not abort. Let a = 2(1 -A real (⊥)). We have

∆(B real ∞ , B ideal ∞ ) = 1 2 Supp(pt) p t (x) - 1 1 -A real (⊥) min p t (x) M , p s (x) dx = 1 a Supp(pt) (1 -A real (⊥))p t (x) -min p t (x) M , p s (x) dx = 1 a Supp(pt) ps(x)≥pt(x)/M 1 -A real (⊥) - 1 M p t (x) dx + Supp(pt) ps(x)<pt(x)/M (1 -A real (⊥))P t (x) -P s (x) dx .
Given the upper and lower bounds on A real (⊥), the first integral is bounded with:

x∈Supp(pt) ps(x)≥pt(x)/M 1 -A real (⊥) - 1 M p t (x) dx ≤ ε M x∈Supp(pt) ps(x)≥pt(x)/M p t (x) dx.
We now observe that:

1 -A real (⊥) ≥ {x∈Supp(Pt)|Ps(x)≥Pt(x)/M } p t (x) dx M .
Then, when we multiply the left integral by 1/a, we obtain:

1 a x∈Supp(pt) ps(x)≥pt(x)/M 1 -A real (⊥) - 1 M p t (x) dx ≤ ε 2 .
Next, we study the right integral. Note that since ε ≤ 1/2, it holds that

0 ≤ p s (x) ≤ p t (x) M ≤ 2(1 -A real (⊥))p t (x), as 1 -A real (⊥) ≥ (1 -ε)/M ≥ 1/(2M ).
Hence the right integral satisfies

x∈Supp(pt) ps(x)<pt(x)/M (1 -A real (⊥))p t (x) -p s (x) dx ≤ (1 -A real (⊥))ε.
Finally, when divided by 2(1 -A real (⊥)), we get ε/2 as an upper bound.

We move on to studying the divergences. We move on to bounding the second divergence. For any x ∈ Supp(p s ):

R a (A real ∥A ideal ) a-1 =   Supp(ps) p s (x) min pt(x) M •ps(x) , 1 a (p t (x)/M ) a-1 dx   + (A real (⊥)) a (A ideal (⊥)) a-1 ≤ Supp(ps) p s (x) pt(x) M •ps(x) a (p t (x)/M ) a-1 dx + (1 -(1 -ε)/M ) a (1 -1/M ) a-1 = Supp(ps) p t (x) M dx + M -1 + ε M • M -1 + ε M -1 a-1 ≤ 1 M + M -1 + ε M • 1 + ε M -1 a-1 . Game Reprogram b : 1: H 0 ← U (Y X 1 ×X 2 ) 2: H 1 := H 0 3: b ′ ← A H b , Reprogram(•) return b ′ Reprogram(x 2 ) : 1: (x 1 , x ′ ) ← D 2: y ← U (Y ) 3: H 1 := H (x 1 ,x 2 ) →y 1 return (x 1 , x ′ )
B real ∞ (x) = A real (x) 1 -A real (⊥)
.

This also holds for B ideal ∞ with A ideal instead of A real . We obtain:

R a (B real ∞ ∥B ideal ∞ ) a-1 = Supp(ps) 1 M a-1 • p s (x) min pt(x) M •ps(x) , 1 a (A real (⊥)) a (p t (x)/M ) a-1 ≤ M (1 -ε) a Supp(ps) p s (x) min pt(x) M •ps(x) , 1 a (p t (x)/M ) a-1 .
This sum was already computed just above and is at most 1/M . The continuity of a → R a (P t ∥P s ) at a = +∞ gives the last bounds.

Reprogramming the Random Oracle

We state the classical variant of [GHHM21, Proposition 2], used in Chapter 3.

Lemma 2.8 (Classical Adaptive Reprogramming). Let X 1 , X 2 , X ′ and Y be finite sets, and let D be a distribution on X 1 × X ′ . Let A be a distinguisher playing in the reprogramming game in Figure 2.2 and making q classical queries to the random oracle and r classical queries to the Reprogram function. Then

Pr[1 ⇐ Reprogram A 0 ] -Pr[1 ⇐ Reprogram A 1 ] ≤ rq • 2 -α ,
where α is the min-entropy of the first component of D.

Proof. Note that the adversary makes q random oracle queries, implying that at most q input-output pairs of the random oracle are being revealed. If a reprogramming query does not coincide with these values, then the view of the adversary is identical for b = 0 and b = 1. For each reprogramming query, the probability of having a collision with the known random oracle values is at most q • 2 -α since the input min-entropy of each reprogramming call is α. One can complete the proof by using the union bound.

Gaussian Distributions and Smoothing Parameter

We recall properties of the discrete Gaussian distribution, a widely used distribution in lattice-based cryptography.

ρ σ : x → exp -C ∥x∥ 2 σ 2 .
The discrete Gaussian distribution with standard deviation parameter σ and center parameter v is defined as

D Z m ,σ,v : z → ρ σ (z -v) ρ σ,v (Z m ) ,
where we let ρ σ,v (Z m ) denote x∈Z m ρ σ (x-v). If v = 0, we omit it in the subscript.

The divergence between two discrete Gaussian distributions is well-known (see, e.g., [LSS14, Lemma 4.2] for a = 2). We give a formulation that includes every order ≥ 1, while restricting our case to the Z m lattice. It is proven by adapting their proof.

Lemma 2.9. Let m ≥ 1, σ > 0 and v ∈ Z m . Then for any a ∈ [1, +∞):

R a (D Z m ,σ ∥D Z m ,σ,v ) = exp aC ∥v∥ 2 σ 2 .
We also have

R ∞ (D Z m ,σ ∥D Z m ,σ,v ) = +∞ if v ̸ = 0.
We also consider bimodal Gaussian distributions in Chapter 4.

BD Z m ,σ,v : z → 1 2 (D Z m ,σ,v (z) + D Z m ,σ,-v (z)) .
In particular, since ρ σ,v (Z m ) = ρ σ,-v (Z m ) (which can be seen by reordering the sum), we can write

BD Z m ,σ,v (z) = 1 ρ σ,v (Z m ) exp -∥z∥ 2 -∥v∥ 2 2σ 2 cosh |⟨z, v⟩| σ 2 .
For spherical Gaussians, the upper and lower part of a vector are statistically independent. This is not the case anymore for general covariance matrices. The following lemma give the conditional distribution of the lower part of a Gaussian vector, given the upper part. The proof is adapted from the continuous setting. where

c 1 ∈ R k-m and Σ 11 ∈ R (k-m)×(k-m) . Let (Y ⊤ 1 |Y ⊤ 2 ) ← D Z k ,Σ,c , where Y 1 takes values in Z k-m . Given any y 1 ∈ Z k-m , the conditional distribution of Y 2 conditioned on Y 1 = y 1 is D Z m ,Σ,c , where c = c 2 + Σ 21 Σ -1 11 (y 1 -c 1 ) and Σ = Σ 22 -Σ 21 Σ -1 11 Σ 12 .
Proof. As Σ is symmetric and positive-definite, both Σ 11 and Σ 22 are also symmetric and positive-definite and thus invertible. This is shown by considering vectors of the form

(x ⊤ |(0 m ) ⊤ ) ⊤ or ((0 k-m ) ⊤ |y ⊤ ) ⊤ .
Let us write the block inverse of Σ as follows:

Σ -1 = Σ -1 11 + Σ -1 11 Σ -1 12 Σ -1 Σ 21 Σ -1 11 -Σ -1 11 Σ -1 12 Σ -1 -Σ -1 Σ 21 Σ -1 11 Σ -1 = S 11 S 12 S 21 S 22 .
This formula also ensures that Σ is invertible, as it is a diagonal block of the positive definite symmetric matrix

Σ -1 . Let y 2 ∈ Z m . The probability that Y 2 = y 2 conditioned on Y 1 = y 1 is ρ Σ,c y 1 y 2 y∈Z m ρ Σ,c y 1 y .
Let us then study ρ Σ,c ((y ⊤ 1 |y ⊤ ) ⊤ ) by expanding it and completing the square.

ρ Σ,c y 1 y ∼ exp -π (y -c) ⊤ S 22 (y -c) = ρ Σ,c (y),
where the notation ∼ hides terms that do not depend on y. Using the fact that the probability mass sums to 1, we obtain that the distribution of

Y 2 conditioned on Y 1 = y 1 is D Z m ,Σ,c .
As showed in [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF], Gaussian distributions can be sampled from by using Klein's algorithm [START_REF] Klein | Finding the closest lattice vector when it's unusually close[END_REF]. We will rely on the following variant.

3]).

There is a ppt algorithm that, given a basis B = (b 1 , . . . , b ℓ ) of a full-rank ℓ-dimensional lattice Λ, a positive definite symmetric matrix Σ and c ∈ R ℓ returns a sample from D Λ,Σ,c , assuming that ln(2ℓ + 4)/π

• max i ∥Σ -1/2 b i ∥ ≤ 1.
Given a lattice Λ ⊆ R k and ε > 0, the smoothing parameter η ε (Λ) of the lattice Λ is defined as the smallest σ such that ρ 1/σ (Λ * \ {0}) ≤ ε. The smoothing parameter satisfies the following two properties.

η ε (Λ) ≤ ln(k -1 + 2k/ε) π • max i≤k ∥b i ∥ .

Lemma 2.13 ( [MR07]

). Let Λ be a k-dimensional full-rank lattice. Let ε > 0 and Σ ∈ R k×k be a definite positive symmetric matrix with all singular values larger than η ε (Λ) and c ∈ R k . We have

ρ Σ,c (Λ) ∈ √ det Σ det Λ • [1 -ε, 1 + ε] and ρ Σ,c (Λ) ρ Σ (Λ) ∈ 1 -ε 1 + ε , 1 .
The following lemma (adapted from [MKMS22, Lemma 1]) is at the core of Chapter 6. While [START_REF] Mera | Efficient lattice-based inner-product functional encryption[END_REF] does not give explicit statistical bounds, we note that Lemma 2.13 above, which is applied at the end of the proof from [START_REF] Mera | Efficient lattice-based inner-product functional encryption[END_REF], allows us to do so when combined with Lemma 2. 3. A further adaptation is the use of the smoothing parameter bound from Lemma 2.12. In their setting of rank-deficient Gaussian distributions, we note that Lemma 2.13 is extended by using the lattice rank in the bound instead of the dimension, by considering an appropriate rotation of the lattice, contrary to [MKMS22, Lemma 4], which considers undefined quantities as

ρ Σ (Z n ) is infinite if Σ is not full rank. Lemma 2.14 (Gaussian decomposition, [MKMS22, Lemma 1]). Let k ≥ ℓ, ε ∈ (0, 1) and S ∈ Z k×ℓ . Let s ≥ 8 ln(ℓ -1 + 2ℓ/ε)/π and σ ≥ √ 2σ 1 (S) • s. Define Σ(S) = σ 2 I k -s 2 SS ⊤ ,
and let y ← D Z k ,Σ(S) and k ← D Z ℓ ,s,-c/2 for any c ∈ Z ℓ . Then Σ(S) is positive definite and the distribution

P z of z = y + S(2k + c) satisfies R ∞ (P z ∥D Z k ,σ ) ≤ 1 + ε 1 -ε and ∆(P z , D Z k ,σ ) ≤ 2ε 1 -ε .
Note that the matrix Σ(S) is positive definite since σ ≥ √ 2σ 1 (S) • s ensures that all singular values of σ 2 I k are larger than those of s 2 SS ⊤ .

Cryptographic Primitives

We recall the definitions of the cryptographic primitives of interest in this work. Namely, digital signatures and Σ-protocols, which are turned into signatures via the Fiat-Shamir transform, which we also recall.

Signatures

Here we briefly recall the formalism of digital signatures. Definition 2.7 (Digital Signature). A signature scheme is a tuple of PPT algorithms (KeyGen, Sign, Verify) with the following specifications:

• KeyGen : 1 λ → (vk, sk) outputs a verification key vk and a signing key sk;

• Sign : (sk, µ) → σ takes as inputs a signing key sk and a message µ and outputs a signature σ;

• Verify : (vk, µ, σ) → b ∈ {0, 1} is deterministic, takes as inputs a verification key vk, a message µ, and a signature σ and outputs a bit b ∈ {0, 1}.

Let γ > 0. We say that it is γ-correct if for any pair (vk, sk) in the range of KeyGen and µ, Pr[Verify(vk, µ, Sign(sk, µ)

) = 1] ≥ γ,
where the probability is taken over the random coins of the signing algorithm. We say that it is correct in the ROM if the above holds when the probability is also taken over the randomness of the random oracle modeling the hash function used in the scheme.

We also recall the definition of existential unforgeability against chosen message attacks (UF-CMA).

Definition 2.8 (Security). Let T, δ ≥ 0. A signature scheme (KeyGen, Sign, Verify) is said to be (T, δ)-UF-CMA secure in the ROM if for any PPT adversary A with runtime ≤ T given access to a signing oracle and random oracle H, it holds that

Pr (vk,sk)←KeyGen(1 λ ) [Verify(vk, µ * , σ * ) = 1|(µ * , σ * ) ← A H,Sign (vk)] ≤ δ,
where the randomness is also taken over the random coins of A. The adversary should also not have issued a sign query for m * . The above probability of forging a signature is called the advantage of A and denoted by Adv UF-CMA SIG (A). If A does not output anything, then it automatically fails.

If we allow the adversary to forge a new signature for a previously queried message, the security is called strong existential unforgeability against chosen message attack (sUF-CMA). Existential unforgeability against one-per-message (resp. nomessage) chosen message attack, denoted by UF-CMA 1 (resp. UF-NMA) is defined similarly except that the adversary is allowed to query at most one (resp. not allowed to query any) signature per message. Further, one can similarly define sUF-CMA 1 by taking the conjunction of sUF-CMA and UF-CMA 1 .

Note that for deterministic signatures, the UF-CMA 1 and UF-CMA security notions coincide.

Σ-Protocols and Identification Protocol

We start by recalling various definitions pertaining to identification protocols. Definition 2.9 (Σ-Protocol with Aborts). Let X , Y be two finite sets. A Σ-protocol for a relation R ⊆ X × Y with commitment set W, challenge set C and response set Z is a 3-round interactive proof system between a prover written as P = (P 1 , P 2 ) and a verifier V = (V 1 , V 2 ) with the following specifications:

• P 1 : (x, y) → (w, st) is a PPT algorithm that takes as input a pair of strings in X × Y and outputs a commitment w ∈ W and a state st ∈ {0, 1} * ;

• V 1 : (x, w) → c is a PPT algorithm that takes as inputs a string x ∈ X and a commitment w ∈ W and outputs a challenge c ← U (C) independent of its input;

• P 2 : (x, y, w, c, st) → z is a PPT algorithm that takes as inputs a pair of strings in X × Y, a commitment w ∈ W, a challenge c ∈ C, and a state st and outputs a response z ∈ Z ∪ {⊥} (we say that P 2 aborts if it outputs ⊥);

• V 2 : (x, w, c, z) → b ∈ {0, 1} is a deterministic polynomial-time algorithm that takes as inputs a string x ∈ X , a commitment w ∈ W, a challenge c ∈ C, and a response z ∈ Z and outputs a bit b which represents acceptance or rejection; in the case that z = ⊥, it returns 0.

A Σ-protocol is said to be public-coin if V 1 outputs a challenge string c that is uniformly sampled from the challenge space C, independently from its input.

Note that the above definition (and the following ones) is implicitly parameterized by the security parameter λ, that we omit for the sake of simplicity.

For cryptographic purposes, we must be able to efficiently generate the statement and the witness. This is captured in the following definition. An identification protocol ID = (IGen, (P

1 , P 2 ), (V 1 , V 2 )) is (γ, β)-correct if for ev- ery (vk, sk) ← IGen(1 λ ) the following holds.
• If the response of the prover is not ⊥, the verifier accepts with probability at least γ:

Pr   V 2 (vk, w, c, z) = 1 (w, st) ← P 1 (vk, sk), c ← V 1 (vk, w), z ← P 2 (vk, sk, w, c, st), z ̸ = ⊥   ≥ γ.
• The probability that the prover aborts is bounded by β:

Pr z = ⊥ (w, st) ← P 1 (vk, sk), c ← V 1 (vk, w), z ← P 2 (vk, sk, w, c, st) ≤ β.
The scheme satisfies commitment-recoverability if for any public key vk, challenge c ∈ C, and answer z, there is at most one commitment w such that the transcript (w, c, z) is valid, and there is a PPT algorithm Rec such that w = Rec(vk, c, z).

We let β denote the probability of aborting and we omit it if it is 0. We are interested in the regime of parameters in which γ ≥ 1-λ -ω (1) and β ≤ 1-1/poly(λ). Note that by repeating the protocol poly(λ) times, the parameter β is pushed toward 0, whereas γ stays close to 1.

We refer to the following definition as the one that is usually used in the literature of Fiat-Shamir with aborts. We however do not use it and we discuss our modifications in Section 3.4.1.

Definition 2.12 (No-Abort Statistical Honest-Verifier Zero-Knowledge). Let ε zk > 0 and T ≥ 0. An identification protocol is (ε zk , T )-naHVZK if there exists a simulator Sim with runtime at most T , that given x, outputs a transcript (w, c, z) such that the distribution of (w, c, z) has statistical distance at most ε zk from a honestly generated transcript (w ′ , c ′ , z ′ ) produced by the interaction conditioned on z ̸ = ⊥.

We then recall the definitions of honest-verifier zero-knowledge in the case of nonaborting identification protocols, which allow to reduce EU-CMA security of FS[ID, H] to its EU-NMA security. Definition 2.13 (HVZK). An identification scheme ID = (IGen, P, V) is Honest-Verifier Zero-Knowledge if there exists a PPT simulator Sim such that one of the following holds for (vk, sk) ← IGen(1 λ ):

• ∆((w, c, z) ← (P(sk, vk) ↔ V(vk)) , Sim(c, vk)) ≤ ε. In this case, we say that ID is ε-HVZK.

• R ∞ ((w, c, z) ← (P(sk, vk) ↔ V(vk)) ∥ Sim(c, vk)) ≤ 1 + ε. In this case, we say that ID is (1 + ε)-divergence HVZK.

The challenge c can be sampled uniformly from the challenge space C and passed over as input to the simulator Sim.

A necessary statistical property of an identification protocol is the min-entropy of the commitments. Definition 2.14 (Commitment Min-Entropy). Let α > 0. An identification scheme ID = (IGen, P, V) satisfies α-Min-Entropy or has α bits of commitment min-entropy if for any (vk, sk) in the range of IGen:

H ∞ w|(w, c, z) ← (P(sk, vk) ↔ V(vk)) ≥ α .
Note that we could accommodate our results to schemes for which the above holds only with overwhelming probability over the randomness of IGen.

Additional properties for non-aborting Identification Schemes

Finally, we recall the notions of lossiness and lossy-soundness, which allow to prove EU-NMA security of FS[ID, H] in the QROM. Definition 2.15 (Lossiness and lossy-soundness). An identification scheme ID = (IGen, P, V) is lossy and ε ls -lossy sound for some ε ls > 0 if there exists a PPT lossy key generation algorithm LossyIGen that, on input a security parameter, outputs a verification key vk ls such that vk ls is indistinguishable from a verification key vk generated by IGen.

Moreover, for any (unbounded) P * interacting with V, we have:

Pr V(vk ls , (w, c, z)) = 1 | (w, c, z) ← (P * (vk ls ) ↔ V(vk ls )) ≤ ε ls .
If we only consider classical adversaries, EU-NMA security of FS[ID, H] can be argued by relying on the simpler notion of special soundness. Definition 2.16 (Special soundness). Let ID = (IGen, P, V) be an identification scheme. It is special sound if for any PPT adversary A, the quantity

Pr V(vk, (w, c 0 , z 0 )) = 1 ∧ V(vk, (w, c 1 , z 1 )) = 1 | (w, c 0 , z 0 , c 1 , z 1 ) ← A(vk)
is negl(λ), where the probability is over the randomness of (vk, sk) ← IGen(1 λ ) and A.

KeyGen(1 λ ):

1: (x, y) ← IGen(1 λ ) 2:
(vk, sk) = (x, (x, y)) 3: return (vk, sk) Sign(sk, µ):

1: κ := 1 2: while z = ⊥ and κ ≤ B 3: (w, st) ← P 1 (sk) 4: c = H(w∥µ) 5: z ← P 2 (sk, w, c, st) 6: κ := κ + 1 7: if z = ⊥ return ⊥ 8: return σ = (w, z)
Ver(vk, µ, σ):

1: Parse σ = (w, z) 2: c = H(w∥µ) 3: return V 2 (vk, w, c, z) Figure 2.3: Signatures SIG B = FS B [ID, H] and SIG ∞ = FS ∞ [ID, H].
Signature SIG B uses blocks highlighted with the blue color, whereas SIG ∞ does not.

Fiat-Shamir Transforms

In this section, we recall the Fiat-Shamir transform, which allows to transform an identification scheme into a digital signature. It removes interaction by sampling the challenge as a hash function evaluation H(w, µ) with w being the prover's commitment and µ the signed message. The hash function is then modeled as a random oracle in the analysis. The signature is the pair (w, z), which is verified by checking validity of the transcript (w, H(w, µ), z).

As the challenge c being typically much shorter than w, it is desirable to replace w by c in the signature. This is possible if the underlying identification scheme is commitment-recoverable (see Definition 2.11). Verification simply starts by recovering w ← Rec(vk, c, z). Our protocols satisfy this property, thus we describe the signature obtained applying this version of the Fiat-Shamir transform.

The Fiat-Shamir with Aborts Transform

Let ID = (IGen, (P 1 , P 2 ), (V 1 , V 2 )) be an identification protocol for a binary relation R. Further, let H : {0, 1} * → C be a hash function where C is the challenge space of ID. Then, for every positive integer B, one can construct a signature scheme SIG B = FS B [ID, H] by applying the Fiat-Shamir transform with bounded aborts (FSwBA) as in Figure 2. 3. We are particularly interested in applying the Fiat-Shamir transform without imposing a bound on the number of iterations in the rejection sampling as it is the case for Dilithium [DKL + 18], among other schemes. One can define the unbounded version SIG ∞ = FS ∞ [ID, H] of the Fiat-Shamir transform as in Figure 2. 3. Note that the signing algorithm of SIG ∞ may not be PPT as required in Definition 2.7. Ideally, it would still be expected polynomial-time.

Chapter 3 is dedicated to proving the properties that a signature resulting from a Fiat-Shamir with aborts transform inherits from its underlying identification protocol. For more details, we refer the reader to prior works (e.g., [Lyu09,Lyu12,AFLT16, DFMS19]).

• In [AFLT16, KLS18], the authors consider lossy identification schemes They reduce UF-NMA security of a signature based on the Fiat-Shamir transform to the ε ls -soundness of the underlying identification scheme and the indistinguishability of the outputs of IGen and IGen ls .

Preliminaries

KeyGen(1 λ ) :

1: (vk, sk) ← IGen(1 λ ) 2: return vk and sk Sign(sk, µ) :

1: (w, st) ← P 1 (sk) 2: c ← H(w, µ) 3: z ← P 2 (sk, st, w, c) 4: return (c, z)
Verify(vk, (c, z), µ) :

1: w ← Rec(vk, c, z) 2: if c ̸ = H(w, µ) then 3:
return 0 4: end if 5: return V(vk, (w, c, z)) • In [START_REF] Don | Security of the Fiat-Shamir transformation in the quantum random-oracle model[END_REF] and implicitly in [START_REF] Lyubashevsky | Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures[END_REF][START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF], the authors reduce UF-NMA security of a signature based on the Fiat-Shamir transform to the proof of knowledge property of the underlying identification protocol. Their reduction is less tight than the one of [KLS18].

The Fiat-Shamir Transform

We now describe the Fiat-Shamir with aborts when the identification protocol has probability 0 of aborting as well as its known properties.

For the sake of completeness, we state the following lemma arguing correctness of the signature scheme FS[ID, H], which immediately follows from the completeness and commitment-recoverability of the underlying identification scheme. Lemma 2.15. Let ID = (IGen, P, V) denote an identification scheme. Further assume that ID is ε-complete and commitment-recoverable. Then the signature scheme FS[ID, H] described in Figure 2.4 is ε-correct in the ROM.

Security of FS[ID, H

] can be proven by successive claims. First, one can reduce EU-CMA security of FS[ID, H] to its EU-NMA security assuming ID has large commitment min-entropy and is honest-verifier zero-knowledge (see Definition 2.13). This can be shown by relying on the following theorem.

Theorem 2.16 (Adapted from [GHHM21, Theorem 3]). Let ID be an identification scheme which has α-min-entropy and satisfies ε-statistical HVZK. Let H a hash function modeled as a random oracle. Then, for any (possibly quantum) adversary A against the EU-CMA security of FS[ID, H] making at most Q S (classical) sign queries and at most Q H (possibly quantum) hash queries, there exists an adversary B against the EU-NMA security of FS[ID, H] such that:

Adv EU-CMA (A) ≤ Adv EU-NMA (B) + Q s ε + 3 Q S 2 • (Q H + Q S + 1) • 2 -α .
Furthermore, if ID is (1 + ε)-divergence HVZK, the following bound applies:

Adv EU-CMA (A) ≤ (1 + ε) Qs Adv EU-NMA (B) + 3Q S /2 • (Q H + Q S + 1) • 2 -α .
The result can be adapted to sEU-CMA security by adding Q S 2 -α to the bounds.

It remains to prove EU-NMA-security. It can be argued via the following statement for lossy identification schemes (see Definition 2.15). Theorem 2.17 ( [KLS18, Theorem 3.4]). Let ID be a lossy identification scheme satisfying ε ls -lossy soundness for some ε ls > 0. Let H a hash function modeled as a random oracle. For any (possibly quantum) adversary A against the EU-NMA security of FS[ID, H] making at most Q H (possibly quantum) hash queries, there exists a quantum adversary B against the lossiness of ID such that

Adv(A) ≤ Adv(B) + 8(Q H + 1) 2 • ε ls .
Finally, we describe a reduction in the (classical) ROM which relies on weaker properties compared to the above QROM reduction. Various folklore reductions are known in this setting, and we consider a variant based on special soundness (see Definition 2.16), which is first reduced to the soundness as recalled below.

Definition 2.17 (Soundness). Let ID = (IGen, P, V) be an identification scheme. It is sound if for any PPT adversary A, the quantity

Pr V(vk, (w, c, z)) = 1 | (w, c, z) ← A(vk)
is negl(λ), where the probability is over the choice of vk and the coins of A.

We recall the Reset Lemma, which is a reduction from special soundness to soundness.

Lemma 2.18 (Reset Lemma [BP02]

). Let ID = (IGen, P, V) be an identification scheme. Given any adversary A against the soundness of ID, there exists an adversary B against the special soundness of ID such that

Adv special-sound (B) ≥ Adv sound (A) - 1 |C| 2 .
And we show that special soundness implies EU-NMA security in the ROM.

Lemma 2.19. Let ID be an identification scheme and H a hash function modeled as a random oracle. For any adversary A against the EU-NMA security of FS[ID, H] making Q H classical hash queries, there exists an adversary B against the special soundness of ID such that:

Adv EU-NMA (A) ≤ Q H • Adv special-sound (B) + 2 |C| .
Proof. We first reduce the soundness of ID to the EU-NMA security of FS[ID, H]. First, if A outputs a forgery (µ * , (c * , z * )) such that H(Rec(vk, c * , z * ), µ * ) was never queried, it has probability at most 1/|C| of outputting a valid forgery.

The reduction B ′ guesses the hash query H(w * , µ * ) made by A which is used in A's forgery. When this query is made, B ′ answers it by running sending w * as commitments to its challenger. The latter replies with a challenge c * and B ′ programs H(w * , µ * ) as c * . With probability 1/Q H , B ′ 's guess is correct and the adversary A halts with a forgery (µ * , (c * , z * )) with Rec(vk, c * , z * ) = w * . We then have

Adv sound (B ′ ) ≥ 1 Q H • Adv EU-NMA (A) -1/|C| .
Finally, Lemma 2.18 gives an adversary B against the special soundness such that

Adv special-sound (B) ≥ Adv sound (B ′ ) - 1 |C| 2 ,
which completes the proof.

Lattice-based Security Assumptions

The Learning With Errors (LWE) and Short Integer Solution (SIS) problems serve as security foundation of Lyubashevsky's signature schemes. In the parameter instantiation section, we will use their module counterparts (see [START_REF] Langlois | Worst-case to average-case reductions for module lattices[END_REF]).

Definition 2.18 (SIS). Let m ≥ n ≥ 1, q ≥ 2 and β > 0. The SIS problem with parameters m, n, q, β is as follows: given as input A ← U (Z n×m q

), the goal is to find x ∈ Z m such that Ax = 0 mod q and 0 < ∥x∥ ≤ β.

Definition 2.19 (LWE).

Let m ≥ n ≥ 1, q ≥ 2 and χ a distribution over Z q . The LWE problem with parameters m, n, q, χ consists in distinguishing between the distributions (A, As + e) and (A, u), where A ← U (Z m×n q ), u ← U (Z n q ), s ← χ n and e ← χ m .

The Lyubashevsky and BLISS Σ-protocols

All the following parameters are functions of a security parameter λ. Let k, m, n ≥ 1 and q ≥ 2 specify matrix spaces over Z q , with m > n. The distribution P S over Z m×k is for signing keys and has support S = Supp(P S ). Let M be the message space. Let C ⊂ Z k finite and H : Z n q × M → C a hash function, which is modeled as a random oracle in the signature scheme analysis. The parameter γ > 0 is used in the verification algorithm to quantify the smallness of the answer. To obtain a 2 λ security against known attacks, one typically sets m, n, k = Ω(λ) and γ, q = poly(λ).

Let ε ≥ 0 and M ≥ 1 be parameters related to rejection sampling, for a source distribution Q and a target distribution P over Z m . Most works directly instantiate these distributions. For example, uniform distributions in well-chosen hypercubes are used in [START_REF] Lyubashevsky | Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures[END_REF] and P = Q Gaussian are used in [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF][START_REF] Ducas | Lattice signatures and bimodal Gaussians[END_REF]. We assume that the support of Q is contained in (-q/2, q/2] m .

We consider the Σ-protocols presented in Figure 2.5 borrowed from both [Lyu09] and [START_REF] Ducas | Lattice signatures and bimodal Gaussians[END_REF] with the aforementioned rejection sampling generalization. For simplicity, we assume that the verification key A ∈ Z n×m q is in Hermite normal form, i.e., we have A = (B|I n ) for some matrix B and with I n ∈ Z n×n q denoting the identity matrix. Up to mild conditions on k, n, m, q, this is without loss of generality.

For Lyubashevsky's and BLISS [DDLL13] Σ-protocols, the public key is T = AS and A. In the case of BLISS, it holds that T = -T mod q, which is usually achieved by setting q = 2q ′ with q ′ > 2 a prime and generating A, S such that T = qId. Correctness of the Fiat-Shamir with aborts transform follows from the lemma below.

Lemma 2.20 (Correctness). Let ε ≥ 0 and M ≥ 1. Let P and Q such that it holds that max (S,c)∈S×C R ε ∞ (P ∥Q +Sc ) ≤ M . Let (y ⊤ 0 |y ⊤ 1 ) ⊤ ← Q, where y 0 takes value

P(A, S) V(A, T) y ← Q w ← Ay w --→ c ← -- c ← U (C) z ← y+Sc w.p. P (z) M •Q(y) z --→ Accept if else Az = w+Tc abort and ∥z∥ ≤ γ P(A, S) V(A, T) y ← Q w ← Ay w --→ c ← -- c ← U (C) b ← U ({-1, 1}) z ← y + bSc w.p. P (z) M Q ±Sc (z) z --→ Accept if else Az = w+Tc abort
and ∥z∥ ≤ γ in Z n . Further assume that 2 -H∞(y 0 |y 1 ) Q ≤ negl(λ), ε ≤ negl(λ) and the probability that Sign terminates is ≥ 1 -negl(λ). Then, in the ROM, Lyubashevsky's signature is correct if γ ≥ γ P with γ P such that Pr z← P (∥z∥ ≥ γ P ) ≤ negl(λ).

The statement holds for BLISS by replacing Q +Sc with Q ±Sc . Runtime and security are studied in Chapter 3.

Chapter 3

Security Analysis of Fiat-Shamir with Aborts

While many different proofs of the Fiat-Shamir with Aborts (FSwA) paradigm have been proposed, we found that many of them were flawed. This chapter proposes a way to fix them. In this chapter, we use the notations FSwBA (Fiat-Shamir with Bounded Aborts) when there is a bound B on the number of iterations of the signature algorithm. If this threshold is reached, then the signature algorithm fails. When there is no such bound, we use the notation FSwUA (Fiat-Shamir with Unbounded Aborts).

As we discussed in the introduction, Definition 2.12 is not sufficient for our purposes. Instead we consider the following statistical HVZK definition, which benefits from a simulator even for aborting transcripts of the Σ-protocol. One can see this modification as a return to the classic definition in the literature of the zeroknowledge interactive proof systems. Definition 3.1 (Statistical Honest-Verifier Zero-Knowledge). Let ε zk , T ≥ 0. A Σprotocol is (ε zk , T )-HVZK if there exists a simulator Sim with runtime at most T , that given x, outputs a transcript (w, c, z) such that the distribution of (w, c, z) has statistical distance at most ε zk from a honestly generated transcript (w ′ , c ′ , z ′ ) produced by the interaction. This includes aborting transcripts, i.e., those for which z = ⊥.

The challenge c can be sampled uniformly from the challenge space C and passed over as input to the simulator Sim.

We give a corrected analysis of FSwBA in Section 3.1. We extend this result to FSwUA with a tweak in the runtime definition in Section 3.3, as we also show that the usual definition may not be satisfied in Section 3.2. Finally, we show that the Lyubahsevsky and BLISS identification protocols satisfy Definition 3.1 in Section 3. 4. In parallel, we study the benefits of a Rényi divergence-based approach in Sections 3.1.2 and 3. 4.1.3. This chapter focuses on the ROM analysis of the transform. However, further results concerning the QROM analyses can be found in [START_REF] Devevey | A detailed analysis of fiat-shamir with aborts[END_REF].

ROM Analysis of FSwBA

In this section we discuss the security of the Fiat-Shamir transform with bounded aborts. We prove the UF-CMA security of the signature in the ROM based on the adaptive reprogramming technique from [START_REF] Grilo | Tight adaptive reprogramming in the QROM[END_REF].

We also propose a tweak of the analysis which relies on the Rényi divergence instead of the statistical distance, as we show that in the case of Lyubashevsky's signature, this leads to increased performances.

The Adaptive Reprogramming Approach

We show how to reduce UF-CMA security and sUF-CMA security of the signature to UF-NMA security in the ROM. We use the framework for adaptive reprogramming (Lemma 2.8). Also, we note that our proof is crucially based on our new zeroknowledge simulator.

Theorem 3.1. Let ε zk , α, T Sim ≥ 0, B ≥ 0 and H a hash function modeled as a random oracle. Assume that Σ = ((P 1 , P 2 ), (V 1 , V 2 )) is a (ε zk , T Sim )-HVZK publiccoin identification protocol and that the commitment message of the prover has minentropy α. Let A be a ppt adversary against UF-CMA security of SIG B = FS B [Σ, H] that issues at most Q H queries to the random oracle H and Q S queries to the signing oracle. Let X ∈ {UF, sUF}; we define ∆ X as follows:

∆ UF = 0 and ∆ sUF = BQ S •2 -α .
In the ROM, there exists an adversary B against UF-NMA security of SIG B with runtime Time(A)

+ O((T Sim • B • Q S + Q H ) log(B • Q S + Q H )) such that Adv X-CMA SIG B (A) ≤ Adv UF-NMA SIG B (B) + 2 -α • B • Q S • (B • Q S + Q H + 1) + ε zk • B • Q S + ∆ X .
The result also holds if we replace HVZK by sc-HVZK and assume ε zk to be negligible in the security parameter.

Proof. The proof is based on a sequence of hybrid games. Game G 0 . The first game is the UF-CMA security game (Figure 3.

1).

Game G 1 . In this game, the challenges of the transcripts are not computed by the random oracle anymore, but sampled independently and uniformly each time. Then, the random oracle is reprogrammed according to the new challenges as in Figure 3. 2. To bound the distance between Game 0 and Game 1 , we construct a wrapper D around A that uses A to solve a reprogramming game. It works as in Figure 3. 3.

Note that if b = 0 in Figure 3.3, then D perfectly simulates G 0 , and otherwise it perfectly simulates G 1 . Therefore,

Pr[1 ⇐ G A 0 ] -Pr[1 ⇐ G A 1 ] ≤ Pr[1 ⇐ Reprogram D 0 ] -Pr[1 ⇐ Reprogram D 1 ] .
During the game, distinguisher D makes B • Q S reprogramming queries and B • Q S + Q H + 1 random oracle queries. In the ROM, Lemma 2.8 bounds the advantage of

D by B • Q S • (B • Q S + Q H + 1)2 -α . Game G 2 .
Let Sim be the zero-knowledge simulator for Σ. In this game we modify GetTrans such that the transcripts are now produced by Sim and without the secret key. See Figure 3. 4. Game :

1: M := ∅ 2: (vk, sk) ← KeyGen(1 λ ) 3: (µ * , σ * ) ← A H, Sign(sk,•) (vk) 4: Parse σ * = (w * , z * ) 5: c * := H(w * ∥µ * ) 6: return [[µ * ̸ ∈ M]] ∧ V 2 (vk, w * , c * , z * )
Sign(sk, µ) :

1: M := M ∪ {µ} 2: (w, c, z) ← GetTrans(µ) 3: if z = ⊥ return ⊥ 4: return σ = (w, z)

GetTrans(µ) :

1: κ := 0 2: while z = ⊥ and κ ≤ B 3: (w, st) ← P 1 (sk) 4: c := H(w∥µ) 5: z ← P 2 (sk, w, c, st) 6: κ := κ + 1 7: return (w, c, z)

Figure 3.1: Game G 0 Game : 1: M := ∅ 2: (vk, sk) ← KeyGen(1 λ ) 3: (µ * , σ * ) ← A H, Sign(sk,•) (vk) 4: Parse σ * = (w * , z * ) 5: c * := H(w * ∥µ * ) 6: return [[µ * ̸ ∈ M]] ∧ V 2 (vk, w * , c * , z * )
Sign(sk, µ) :

1: M := M ∪ {µ} 2: (w, c, z) ← GetTrans(µ) 3: if z = ⊥ return ⊥ 4: return σ = (w, z)

GetTrans(µ) :

1: κ := 0 2: while z = ⊥ and κ ≤ B 3: (w, st) ← P 1 (sk) 4: c ← U (C) 5: z ← P 2 (sk, w, c, st) 6: H = H w∥µ →c 7: κ := κ + 1 8: return (w, c, z)

Figure 3.2: Game G 1 . The difference from G 0 is highlighted in blue.
We would like to bound the distance between games G 1 and G 2 using the zeroknowledge property. Suppose that we are given a B • Q S transcripts that are either sampled honestly or sampled by the simulator. We use them to simulate G 1 or G 2 , respectively, by simulating H with the lazy sampling technique. Note that in both games, after each transcript, the random oracle is reprogrammed according to the transcript. In order to simulate the reprogrammed random oracle perfectly, we keep track of a list D of the values in which the random oracle must be reprogrammed. We describe the details in Figure 3. 5.

Note that C can perfectly simulate G 1 or G 2 with its respective transcripts. Furthermore, it is given B • Q S transcripts. By the statistical HVZK property of the Σ-protocol, it follows that

Pr[1 ⇐ G A 1 ] -Pr[1 ⇐ G A 2 ] ≤ B • Q S • ε zk .
Game G 3 . In this game, we add one more statement to the winning conditions. Let (µ * , (w * , z * )) be the forgery. If the value w * ∥µ * has been programmed in the D H b ,Reprogram :

1: M := ∅ 2: (vk, sk) ← KeyGen(1 λ ) 3: (µ * , σ * ) ← A H b , Sign(sk,•) (vk) 4: Parse σ * = (w * , z * ) 5: c * := H b (w * ∥µ * ) 6: return [[µ * ̸ ∈ M]] ∧ V 2 (vk, w * , c * , z * )
Reprogram(µ, sk) :

1: (w, st) ← P 1 (sk) 2: c ← U (C) 3: H 1 := H (w∥µ) →c 1
4: return (w, st)

Sign(sk, µ) : Game :

1: M := ∅ 2: (vk, sk) ← KeyGen(1 λ ) 3: (µ * , σ * ) ← A H, Sign(sk,•) (vk) 4: Parse σ * = (w * , z * ) 5: c * := H(w * ∥µ * ) 6: return [[µ * ̸ ∈ M]] ∧ V 2 (vk, w * , c * , z * )
Sign(sk, µ) :

1: M := M ∪ {µ} 2: (w, c, z) ← GetTrans(µ) 3: if z = ⊥ return ⊥ 4: return σ = (w, z)
GetTrans(µ) : random oracle H during the game, then we abort. The value w * ∥µ * would be programmed during the game if the adversary has made a sign query with µ * . As the winning condition in the UF-CMA game already requires a forgery for a message that has not been queried before, the adversary's view is identical to that of the previous one.

It remains to reduce G 3 to UF-NMA security. The signing algorithm does not use the signing key anymore and uses the zero-knowldege simulator to answer the sign queries. The last remaining technicality lies in how to simulate the random oracle.

In the ROM, we use the lazy sampling method. At each query to the random oracle, we return a match if there exists any in the database, otherwise we return a fresh sampled element from the range of H and add it in the database.

Strong Unforgeability. For the sUF-CMA security, we modify the above games. Now, the challenger maintains the list M of message-signature pairs that were queried by the adversary via the signature oracle. Each game, at its final step, also checks

C |H ′ ⟩ ({w i,κ , c i,κ , z i,κ } i∈[Q S ],κ∈[B] ) : 1: M := ∅ 2: i := 0 3: D := ∅ 4: (vk, sk) ← KeyGen(1 λ ) 5: (µ * , σ * ) ← A |H⟩, Sign(sk,•) (vk) 6: Parse σ * = (w * , z * ) 7: c * := H b (w * ∥µ * ) 8: return [[µ * ̸ ∈ M]] ∧ V 2 (vk, w * , c * , z * ) H(w∥µ) : 1: if ∃c such that (w, µ, c) ∈ D 2: return c 3: return H ′ (w∥µ)
Sign(sk, µ) : whether the forgery (µ * , (w * , z * )) belongs to this list or not, and if it is it returns 0. With these modifications, everything remains the same up to Game G 2 . The last two games G 2 and G 3 behave differently only if we have the following conditions: (µ * , (w * , z * )) ̸ ∈ M, the random oracle has been reprogrammed on input w * ∥µ * , and V 2 (vk, w * , c * , z * ) = 1. The input w * ∥µ * has been reprogrammed only if the adversary has made a sign query on µ * . The probability of w * appearing in any given loop iteration of the rejection sampling of Sign(sk, µ * ) is bounded by 2 -α . In total, there are at most B iterations per sign query, and the adversary makes at most Q S queries. By the union bound, the probability that w * ∥µ * has been reprogrammed is bounded by BQ S • 2 -α . The reduction from G 3 to the UF-NMA game works as before.

1: M := M ∪ {µ} 2: i := i + 1 3: κ := 0 4: while z = ⊥ and κ ≤ B 5: (w, c, z) = (w i,κ , c i,κ , z i,κ ) 6: if ∃c ′ such that (w, µ, c ′ ) ∈ D 7: D := D \ (w, µ, c ′ ) 8: D := D ∪ (w, µ, c) 9: κ := κ + 1 10: if z = ⊥ return ⊥ 11: return σ = (w, z)
Runtime. In the ROM, each sign query requires to run the zero-knowledge simulator up to B times. For each hash (resp. sign) query, the reduction performs 1 (resp. up to B) programming operation. It maintains a sorted data structure D in order to search and insert in O(log

(B • Q S + Q H )) steps. The runtime of the reduction is of order Time(A) + O(T Sim • (B • Q S + Q H ) • log(B • Q S + Q H )).

Rényi Divergence Approach: FSwBA Security Analysis

In this section, we start the Rényi divergence-based analysis of Fiat-Shamir with Aborts. This allows us to achieve smaller signature sizes in Section 4. 4.5. We note however that the Rényi divergence is useful for non-aborting transcripts, meanwhile for aborting transcripts the statistical distance analysis is sufficient. To take this into account, we introduce the following definition. Definition 3.2 (Decomposable Simulator). Let p ∈ [0, 1]. Let Sim be a zeroknowledge simulator for a Σ-protocol. We say that Sim admits a p-decomposition if there exist two algorithms Sim ⊥ and Sim ̸ ⊥ such that the former only outputs transcripts with z = ⊥, the latter only outputs transcripts with z ̸ = ⊥, and Sim can be defined as in Figure 3. With this formalism, we are able to extend the HVZK definition to the Rényi divergence.

Definition 3.3 (Decomposable Divergence HVZK). Let R zk ≥ 1, ε zk > 0, p ∈ [0, 1] and T ⊥ , T ̸ ⊥ ≥ 0. A Σ-protocol is said to be (ε zk , T ⊥ , R zk , T ̸ ⊥ )-DDHVZK if there exists a p-decomposable simulator Sim = (Sim ⊥ , Sim ̸ ⊥ ) such that • algorithm Sim ⊥ is (ε zk , T ⊥ )-HVZK (or sc-HVZK) simulator for the Σ-protocol transcript (w ′ , c ′ , z ′ ) conditioned on z ′ = ⊥,
• algorithm Sim ̸ ⊥ has runtime T ̸ ⊥ , and given x outputs a transcript (w, c, z) such that its distribution and the one of a transcript (w

′ , c ′ , z ′ ) of the Σ-protocol conditioned on z ′ ̸ = ⊥ are such that R ∞ (w, c, z)∥(w ′ , c ′ , z ′ ) ≤ R zk .
Note that p can possibly differ from β, but we are interested in the case where their difference is negligible (as in the following theorem). We adapt Theorem 3.1 and its proof to this new setting.

Theorem 3.2. Let R zk ≥ 1, ε zk , T ⊥ , T ̸ ⊥ ≥ 0, p ∈ [0, 1]
and H a hash function modeled as a random oracle. If Σ = ((P 1 , P 2 ), (V 1 , V 2 )) is an (ε zk , T ⊥ , R zk , T ̸ ⊥ )-DDHVZK public-coin identification protocol with a p-decomposable simulator and probability of aborting β, then we have the following updates on Theorem 3.1. In the ROM, there exists an adversary B against UF-NMA security of SIG B with runtime Time

(A) + O((T ⊥ (B -1)Q S + T ̸ ⊥ Q S ) log(B • Q S + Q H )) such that Adv X-CMA SIG B (A) ≤ R Q S zk • (Adv UF-NMA SIG B (B) + (ε zk + |p -β|) • B • Q S + ∆ X ) + 2 -α • B • Q S • (B • Q S + Q H + 1) .
Proof. The proof is almost identical to the one of Theorem 3.1. We replace Game G 2 with three different games G 2.1 , G 2.2 and G 2. 3 . The other changes between games remain similar. Let Sim = (Sim ⊥ , Sim ̸ ⊥ ) be the decomposition of the zero-knowledge simulator. We proceed as follows.

Game G 1 . It is the same as in the proof of Theorem 3.1. Game G 2.1 In this game, we change the signing algorithm. As soon as a transcript (w, c, z) with z ̸ = ⊥ is being sampled during the rejection sampling loop, we discard it and replace it with a transcript generated by Sim ̸ ⊥ . The multiplicativity of the Rényi divergence implies that

Pr[1 ⇐ G A 1 ] ≤ (1 + ε zk ) Q S • Pr[1 ⇐ G A 2.1 ].
Game G 2. 2 . We modify the signing algorithm one step further. Let Bernoulli(β) denote the Bernoulli distribution with parameter β (i.e., the probability of sampling 1 is β). We replace the honestly generated transcripts with the following distribution.

ε zk • (B -1) • Q S .
Game G 2. 3 . We replace Bernoulli(β) with Bernoulli(p). The distinguishing advantage of the adversary between G 2.2 and G 2.3 would be less than |p -β|

• (B -1) • Q S .
The rest of the proof is similar to that of Theorem 3.1.

Concrete Analysis of FSwUA: Negative Result

In the two last sections of this chapter, we focus on analyzing formally signatures constructed from combining an identification protocol with the Fiat-Shamir with unbounded aborts paradigm. To the best of our knowledge, this is the first complete analysis of FSwUA.

In this first section, we exhibit a signature constructed using FS ∞ for which the signing runtime is infinite for an instantiation of the hash function H. Therefore, the expected runtime is also infinite and the standard definition of runtime must be changed. We propose minor updates to the signature definitions so that they support such pathological behaviors. Note that FSwUA is the main paradigm used in practice: there is no reason to add a bound for the number of loop iterations in the code if the algorithm never reaches it except with negligible probability, but the latter statement thus needs to be proven.

In Section 3.3, we prove Fiat-Shamir with unbounded aborts does yield signatures which satisfy all correctness, runtime, and security requirements. Correctness of FSwBA is also addressed in Section 3.3 as a corollary of our analysis.

Infinite Signing Runtime in the Worst Case of FSwUA

In this section, we aim to prove the following theorem.

Theorem 3. 3. There exists a parametrization of dk-LWE m,n,q,Q such that the following holds assuming the hardness of dk-LWE m,n,q,Q . There exists a public-coin identification protocol Σ with instance generator IGen such that, with overwhelming probability over the randomness of IGen, there exists a hash function H bad such that the signing algorithm of SIG ∞ := FS ∞ [Σ, H bad ] on inputs the signing key and any message does not halt.

The proof relies on constructing the appropriate identification protocol, and then identifying a specific bad instantiation for the hash function. The main idea is to instantiate Lyubashevsky's signature scheme with source distribution Q being the uniform distribution over a ball B and target distribution being the uniform distribution over a corona C, as illustrated in Figure 3.7. For a keypair A, S, a loop iteration samples y ← U (B), defines a commitment w ← Ay mod q, and returns y + Sc with c ← H(Ay mod q∥µ), if and only if y + Sc ∈ C.

The cornerstone of our proof is to show that there exists a hash function H bad such that, for every message µ and every y, the challenge c = H(Ay mod q∥µ) is such that y + Sc / ∈ C. This implies that the signing algorithm of FS ∞ [Σ, H bad ] never halts on any input message.

Theorem 3. 3. We instantiate Lyubashevsky's signature in the low-density regime. We first construct the identification protocol, and then explain how to instantiate H bad to obtain the result.

We use the following parameters:

• dimensions n > 0 and m = 2n ≥ 14;

• a challenge bound τ > 24 √ m;

• a good conditioning parameter d = 300;

• a crust width t = dτ and a corona width

t ′ = dτ /3 -(d + 1) √ m;
• a radius r = m(t + t ′ );

• a prime modulus q ≤ poly(n) that satisfies q ≥ 16(r + √ m) 4 .

We define the following relation R:

R := ((A, AS), S) | A ∈ Z n×m q , S = 2 3 dI m + E ∈ Z m×m , σ 1 (E) ≤ d 3 ,
where σ 1 (E) denotes the largest singular value of E (when viewed as a real-valued matrix). Note that d is a multiple of 3 so that S is indeed integral.

Our choice of matrix S makes it so that σ 1 (S) ≤ d and S is full-rank (note that this is a real-valued matrix). We have S -1 = (2d/3) -1 k≥0 (-(2d/3) -1 E) k , which satisfies σ 1 (S -1 ) ≤ 3/d. The matrix S is the relation witness. We now consider the challenge space C. We set:

C := {c ∈ Z m |∥c∥ ≤ τ }.
As t = dτ , we have t ≥ ∥Sc∥ for all c ∈ C and all S ∈ Z m×m with σ 1 (S) ≤ d.

We further define the ball B and corona C as follows.

B := B m (r) and C := B m (r -t) \ B m (r -t -t ′ ) .
A graphical representation is given in Figure 3.7.

We instantiate Lyubashevsky's signature scheme as recalled in Section 3. 4.1, with the source distribution Q set as the uniform distribution over Z m ∩ B and the target distributions P set as the uniform distribution over Z m ∩ C. The norm bound check of the verification algorithm is instantiated to ∥z∥ ≤ r, where z is the vector output by the prover. Finally, the rejection parameter M is set to M = 100.

Lemma 3. 4. The identification protocol Σ obtained by instantiating Figure 2.5 as described above is (1, 1/M )-correct. Under the dk-LWE m,n,q,Q hardness assumption, it is sc-HVZK. Proof. We prove each property as follows: Correctness. The perfect correctness (γ = 1) follows from the fact that if the prover outputs something, it is by definition a rounding of an element belonging to C and satisfies the relation that the verifier checks. By design, the probability that the verifier outputs some z ̸ = ⊥ is 1/M . Zero-Knowledge. We now aim at using Theorem 3.15 to argue the zero-knowledge of the protocol. It suffices to show that for all c ∈ C and all z ∈ Z m ∩ C, we have that

P (z) ≤ M • Q(z -Sc).
Note first that for the considered S's and c's, if z belongs to the support of P , then z -Sc belongs to the support of Q. For such a z, we have:

Q(z -Sc) P (z) = |Z m ∩ C| |Z m ∩ B| ≥ Vol(B(r -t - √ m)) -Vol(B(r -t -t ′ + √ m)) Vol(B(r + √ m)) = 1 - t + 2 √ m r + √ m m -1 - t + t ′ r + √ m m .
By expanding the difference of powers, we then obtain:

Q(z -Sc) P (z) = t ′ -2 √ m r + √ m • m-1 k=0 1 - t + 2 √ m r + √ m m-1-k 1 - t + t ′ r + √ m k ≥ t ′ -2 √ m r + √ m • m • 1 - t + t ′ r + √ m m-1 ≥ t ′ -2 √ m t + t ′ + 1 • 1 - 1 2m m .
In the last inequality, we use the fact that r = m(t + t ′ ). Now, using the definitions of t and t ′ , we obtain that the latter is ≥ 1/100.

Let us now consider the probability β that some answer is output by P 2 . Note that our choice of t is such that for any S and challenge c, it holds that

C ⊆ B + Sc.
Therefore, the probability that a uniform element from B + Sc belongs to C is:

β = Vol(C) Vol(B) = 1 - t r m -1 - t + t ′ r m = 1 - t r -1 + t + t ′ r • m-1 k=0 1 - t r m-1-k 1 - t + t ′ r k ≥ t ′ r • m • 1 - t + t ′ r m-1 ≥ t ′ t + t ′ • 1 - 1 m m .
For the last inequality, we used the fact that r = m(t + t ′ ) and 1 -1/m < 1. By using the definitions of t and t ′ , we obtain:

β ≥ t ′ 4(t + t ′ ) ≥ 1 4 • τ -3(1 + 1/d) √ m 4τ -3(1 + 1/d) √ m .
We claim that the latter is ≥ 1/20. Indeed, having this inequality is equivalent to

τ ≥ 12(1 + 1/d) √ m, which is satisfied when τ ≥ 24 √ m.
We then show that, for any choice of A, S such that ((A, AS), S) ∈ R, there exists a hash function H such that, using H to instantiate FWsUA, the signing algorithm of FS ∞ [Σ, H] never halts on any input message. That is, for every message µ and every y, the challenge c = H(Ay mod q∥µ) is such that y + Sc / ∈ C. Fix the matrices A and S. We now show how to instantiate the hash function H so that the above holds. A first important observation is that multiplication by A of a short integer vector is injective. Note that Ay = Ay ′ mod q for some y ̸ = y ′ ∈ B implies that there exists an integer vector x ∈ Z m (namely yy ′ ) such that Ax = 0 mod q and 0 < ∥x∥ ≤ 2r. Applying the following lemma with B = 2r, it holds that with probability at least 1-2 -Ω(n) over the random choice of A, such a vector x does not exist, by our choices of m and q. Lemma 3.5. Let m, n > 0 and q a prime. Let B < q. Then:

Pr A∈Z n×m q λ 1 (Λ ⊥ q (A)) < B ≤ Vol(B m (1)) (B + √ m/2) m q n .
Proof. The following relations follow from a union bound, the statistical independence of the rows of A and the fact that every short enough integer vector is non-zero modulo q.

Pr A← U (Z n×m q ) (λ 1 (Λ ⊥ q (A)) < B) ≤ y∈Z m 0<∥y∥≤B Pr A← U (Z n×m q ) (Ay = 0 mod q) = y∈Z m 0<∥y∥≤B Pr a← U (Z m q ) (a ⊤ y = 0 mod q) n = y∈Z m 0<∥y∥≤B 1 q n .
Finally, we note that the volume of the m-dimensional hyperball of center 0 and radius B + √ m/2 is an upper bound on the number of summands.

As a consequence, we can define H as a function of y as Ay uniquely determines y. Based on the protocol, it suffices to find a challenge c ∈ C for each y ∈ Z m ∩ B, it holds that y + Sc ̸ ∈ C. We then set H(Ay mod q, µ) to be this c for all messages µ.

First, note that if y ̸ ∈ C, then setting c := 0 leads to y + Sc being rejected. Thus, we focus on the other case. Let Λ(S) be the full-rank lattice generated by the matrix S (recall that S is full-rank). Define the scaling λ = t ′ /∥y∥ and note that ∥λy∥ = t ′ . Let x ∈ Λ(S) be such that λx ∈ y + P(S), where P(S) = S • [0, 1] n denotes the (closed) fundamental parallelepiped spanned by S. In particular there exists a lattice point e ∈ x + P(S) such that ⟨e -λy, λy⟩ ≥ 0 ,

since otherwise there would exist an affine hyperplane separating λy ∈ x + P(S) from λy, which would contradict the definition of x. Note that ∥e -λy∥ ≤ d √ m: indeed, when written in the basis S, all of its coordinates belong to [-1, 1], and we have σ 1 (S) ≤ d. Since e ∈ Λ(S), there exists k ∈ Z n such that e = Sk. We set the challenge c as k. To conclude, we prove the following statements.

∥c∥ = ∥S -1 e∥ ≤ σ 1 (S -1 )[∥e -λy∥ + ∥λy∥] ≤ 3 d (d √ m + t ′ + √ m) = τ .
By using Equation (3.1), we obtain the following.

∥y + e∥ 2 = ∥λy + y + (e -λy)∥ 2 = ∥λy∥ 2 + ∥y∥ 2 + ∥e -λy∥ 2 + 2⟨λy, y⟩ + 2⟨λy, e -λy⟩ + 2⟨e -λy, y⟩

≥ ∥λy∥ 2 + ∥y∥ 2 + 2⟨λy, y⟩ = ((λ + 1)∥y∥) 2 .
Using the definition of λ and the lower bound on ∥y∥, we obtain that

∥y + e∥ ≥ (t ′ + r -t -t ′ ) = r -t .
This completes the proof: instantiated with this hash function, the signing algorithm of the Fiat-Shamir transform of the above Σ-protocol never halts.

So far, this only exhibits a single bad choice for the hash function, while signatures based on FSwUA support messages of unbounded length. Hence, there are infinitely many possible hash functions (functions with domain W × {0, 1} * and range C, with W being the commitment space). As a consequence, it is not immediate that a single bad hash function implies an infinite expected runtime for the signature scheme in the ROM, and one could think that simply considering the runtime when H is a random oracle could be sufficient to fix it. Corollary 3.6. We have Pr H [∀w ∈ W, H(w∥µ) = H bad (w∥µ)] ≥ |C| -|W| for any message µ. Therefore, the expected runtime of Sign(sk, µ) over the choice of the random oracle H is infinite.

Our result relies on the hardness of the dk-LWE problem when the weight vector is sampled from the uniform distribution over a hyperball. This is an unusual distribution for dk-LWE. However, it can be checked that for appropriate parameters, the proof of [BLR + 18, Section 5] that decision LWE is hard for a noise distribution that is uniform in a hypercube carries over to the hyperball setting.

Updated Signature Definition

As shown in Section 3.2.1, there are instances of identification protocols that yield signature schemes with infinite expected runtime of the signing algorithm. This requires relaxing the runtime requirement in the definition to be expected polynomial time with overwhelming probability over the choice of the hash function. Yet, there is another subtlety doing so: in the security game, an adversary might make a sign query that never halts. In the case of the above construction, the challenger, which is unbounded, can still notice it as the commitment space is bounded and the rejection step is deterministic. Once all the potential commitments have failed to produce a valid signature, the challenger knows that it cannot answer the query. This is however not the case of every signature scheme. To take such event into account, we consider that an attacker automatically wins if the challenger takes more than T ′ time to answer a signature query, for some parameter T ′ . An alternative choice could be to consider that an adversary which makes a non-terminating sign query loses, since the challenger does not answer anymore. We prefer to add this parameter T ′ as this makes the definition stronger by further guaranteeing that an adversary cannot find a query which forces the signer to run for a long time, which could be desirable in practice as well.

We now state our updated definition for signatures. It is highly similar to the standard Definition 2.7 and we only highlight the differences. Definition 3.4 (Modified Digital Signature in the ROM). Let H be a random oracle to which all algorithms have oracle access. A signature scheme is a tuple (KeyGen, Sign, Verify) of algorithms with the following specifications. Everything is as in Definition 2.7, except for the runtime of Sign, which we define below, and a minor tweak in the security game.

• Sign H : (sk, µ) → σ is a probabilistic algorithm that takes as inputs a signing key sk and a message µ ∈ M and outputs a signature σ. We denote with T Sign H (sk,µ) the runtime of Sign(sk, µ).

Let γ > 0, T = poly(λ) and ε = negl(λ). We say that the signature scheme is γcorrect if for any pair (vk, sk) in the range of KeyGen and µ,

Pr[Verify(vk, µ, Sign(sk, µ)) = 1 | Sign(sk, µ) halts] ≥ γ,
and we say that it is (T, ε)-efficient if for any pair (vk, sk) in the range of KeyGen and µ, Pr

H [T Sign H (sk,µ) > T ] < ε.
where both probabilities are taken over the random coins of the two algorithms and the random oracle.

In addition, we update the security game as follows. Let T ′ be another function of λ. We define T ′ -UF-CMA security exactly as UF-CMA security in Definition 2.8, except that we further make the adversary win as soon as it makes a sign query for which the signing algorithm takes more than T ′ steps to halt. Definition 3.4 does not forbid the situation described in Subsection 3.2.1 from occurring but guarantees that it should be hard to find non-halting queries.

Concrete Analysis of FSwUA: Positive Results

Equipped with this updated definition, we prove that signatures constructed from applying FSwUA to an identification protocol yields a signature scheme that satisfies all three correctness, runtime, and security requirements. This result extends to prove that FSwBA signatures satisfy correctness.

Theorem 3.7 (Runtime). Let γ > 0, β ∈ (0, 1) and H a hash function modeled as a random oracle. Let Σ = ((P 1 , P 2 ), (V 1 , V 2 )) be an identification protocol that is (γ, β)-correct and has commitment min-entropy α.

Let SIG ∞ = FS ∞ [Σ, H].
Let M be the message space and I Sign H (sk, µ) denote the random variable counting the number of iterations of the signing algorithm on input (sk, µ) using a random oracle H where µ ∈ M. It holds that for any (vk, sk) ← KeyGen(1 λ ), any message µ ∈ M, and any integer i:

Pr H (I Sign H (sk, µ) > i) ≤ β i + 2 -α (1 -β) 3 .
Proof. Let us start by introducing the random variables (w i , c i , z i , acc i ) i≥1 . It denotes an infinite sequence of transcripts, where acc i is the random variable denoting whether the transcript is accepted or not. It takes value in {0, 1}, where 0 denotes rejection and 1 acceptance. For the sake of the proof, let the sequence continue regardless of whether a prior transcript was accepted or not. Let N = I Sign H (sk,µ) . It denotes the index of the first accepting transcript, i.e., N = argmin i ({acc i = 1}). Let us denote by M the index of the first collision, i.e., M = min{i|∃j < i, w j = w i }.

Note that once H is fixed, a transcript is a deterministic function of w i .

Let i ≥ 1. Let us decompose:

Pr H (N > i) = Pr H (N < M ) • Pr H (N > i|N < M ) + Pr H (N ≥ M ) • Pr H (N > i|N ≥ M ) ≤ 1 • Pr H (N > i|N < M ) + Pr H (N ≥ M ) • 1.
We now focus on studying each of these probabilities. The second one can be rewritten as

Pr H (N ≥ M ) = ∞ k=2 Pr H (M = k) • Pr H (N ≥ M |M = k).
Let us first focus on Pr H (M = k). The random variable M only depends on the w i 's, which are i.i.d.: we can bound the collision probability with their minentropy:

Pr H (M = k) ≤ k 2 • 2 -α-1 .
Next, as long as no collision occurred, all c i 's can be seen as "fresh" randomness, i.e., all c i 's are uniform over the challenge space and most importantly, they are independent. Hence conditioned on M = k, we know that the probability of rejecting the first k -1 samples is β k-1 . Then

Pr H (N ≥ M ) ≤ ∞ k=2 k 2 • 2 -α-1 • β k-1 = 2 -α-1 • β + 1 -(1 -β) 3 (1 -β) 3 ≤ 2 -α • 1 (1 -β) 3 ,
where the equality comes from the fact that k≥1 k 2 •β k-1 = (β+1)/(1-β) 3 . Now, as we previously stated, conditioned on N < M , the distribution of N is geometric with parameter 1 -β. Hence, we have Pr H (N > i|N < M ) = β i . Plugging everything together, we obtain

Pr H (N > i) ≤ β i + 2 -α (1 -β) 3 .
Assume that α = ω(log(λ)). Setting i = ω(log(λ)/ log(1/β)) ensures that with overwhelming probability over the choice of H, signing runs in polynomial time. We note that this bound does not contradict the previous (negative) result. Indeed, it does not imply any statement on the finiteness of the expected value of T Sign H , which is infinite in the previous section.

We move on to checking that FSwUA satisfies the new γ-correctness property, assuming that the underlying identification protocol is (γ, β)-correct.

Theorem 3.8. Let γ > 0, β ∈ (0, 1) and let H denote a hash function modeled as a random oracle. Let Σ = ((P 1 , P 2 ), (V 1 , V 2 )) be an identification protocol that is (γ, β)-correct. Let T denote the runtime of one interaction in the worst-case. Let α > 0 be its commitment min-entropy. Let SIG ∞ = FS ∞ [Σ, H]. Then for any i = ω(log(λ)/ log(1/β)), it is γ-correct as well as (iT,

β i +2 -α /(1-β) 3 )-efficient.
Proof. Let (sk, vk) ← KeyGen and µ ∈ M. Conditioned on Sign(sk, µ) halting, the output transcript follows the same distribution as a transcript from the identification protocol conditioned on not being ⊥. In particular, the challenge is uniform over C, as it is a hash that comes from the random oracle. Only its marginal distribution is important here, as well as the fact that it is independent from the first and last message of the prover. Hence, this transcript is accepted with probability γ over the random coins of Sign and the random oracle.

With FSwBA, the problem is reversed: bounding the runtime becomes easy, whereas proving the correctness becomes mildly more tedious, as one needs to check that ⊥ is not output too often. Theorem 3.9. Let γ > 0, β ∈ (0, 1) and B > 0. Let H be a hash function modeled a random oracle. Let Σ = ((P 1 , P 2 ), (V 1 , V 2 )) be an identification protocol that is (γ, β)correct and has commitment min-entropy α. Let SIG B = FS B [Σ, H]. Then, for any (vk, sk) ← KeyGen(1 λ ) and any message µ ∈ M, we have

Pr[Verify(vk, µ, Sign(sk, µ)) = 1] ≥ γ • 1 -β B - 2 -α (1 -β) 3 , identical.
It follows that the mixed state of the adversary remains identical in both games.

Let R G 0 ,A be an algorithm that runs G 0 with A as a subroutine, records the sign queries of A, and wins if one of them is answered by ⊥. We have

Pr[1 ⇐ G A 1 ] -Pr[1 ⇐ G A 0 ] ≤ Pr[win(R G 0 ,A )].
We aim at bounding the winning probability of R. Remember G 1 from Figure 3.2, which we rename G ′ 0 in this proof. In Theorem 3.1, we proved that

Pr[1 ⇐ G A 0 ] -Pr[1 ⇐ G ′A 0 ] ≤ 2 -α • B • Q S • (B • Q S + Q H + 1),
in the ROM. It follows that we can replace Game G 0 in Pr[win(R G 0 ,A )] with G ′ 0 and only lose the above terms in their corresponding random oracle models.

Finally, using the union bound and the β-correctness of the identification protocol, the winning probability of the algorithm R relative to

G ′ 0 is bounded by Q S • β B . Game G 2
. This is the genuine T ′ -UF-CMA game. The distinguishing advantage of A is bounded by the probability that A makes a sign query that takes more than T ′ steps to halt. Theorem 3.7 implies that this probability is bounded by 3 . This completes the proof.

β T ′ /T + 2 -α /(1 -β) 3 ≥ β B + 2 -α /(1 -β)

Application to Lyubashevsky's Σ-Protocol

While we consider in this chapter generic Σ-protocols, our central application of the Fiat-Shamir with aborts paradigm is Lyubashevsky's signature scheme [START_REF] Lyubashevsky | Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures[END_REF][START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF]. We show here that the underlying Σ-protocol satisfies the zero-knowledge property of Definition 3.1, i.e., admits an efficient simulator for all transcripts including the aborting ones.

A Simulator for Lyubashevsky's Σ-protocol

We consider the simulator Sim described in Figure 3.8 for the underlying Σ-protocol of Section 2.6. For the rest of this section, we drop the runtime considerations, and note that the simulator runs in roughly the time necessary to sample from P and compute two matrix multiplications in the non-aborting case or the time necessary to sample a uniform w in the aborting case.

Sim(T, c) :

with probability 1/M 1: z ← P 2: w := Az -Tc else 3: w ← U (Z n q ) 4: z := ⊥ 5: return (w, z) The proof that the simulation is correct in the non-aborting case is quite standard and derives from the rejection sampling. For the aborting case, our proof relies on the leftover hash lemma and requires the source distribution Q to have high min-entropy. The case of low min-entropy source distributions Q is handled later on.

High Min-Entropy Source Distributions

We first consider the case where Q has high min-entropy. In that case, we obtain statistical zero-knowledge as per Definition 3.1.

Theorem 3.11. Let m ≥ n, k > 0, q prime, ε, β SIS > 0 and η ∈ [0, 1 2 ]. Assume that

H ∞ (Q) ≥ n log q + log 1 - 1 -η M + 2 log 1 ε . Let (S, T) ∈ R m,n,k,q,β SIS (A) for some A ← U (Z n×m q ). Assume that ∀c ∈ C : R ε ∞ (P ∥Q +Sc ) ≤ M. Then Lyubashevsky's Σ-protocol satisfies the ε + η(1 + 1/M )-HVZK property.
Observe that c ← U (C) in both genuine and simulated transcripts. It hence suffices to study the distribution of the rest of the transcript conditioned on the value of c.

The first part of the following result derives from Lemma 2.7, and the second part derives from the description of Sim. The claim ensures that the probabilities of the event z = ⊥ in the genuine and simulated transcripts are close-by. Lemma 3.12. For all c output by V 1 , the probability (over the random coins of P 1 and P 2 ) that P 2 outputs ⊥ belongs to [1-1/M, 1-(1-η)/M ]. For all c, the probability (over its random coins) that the last component of Sim is equal to ⊥ is 1 -1/M .

We now consider the transcript distribution conditioned on the event z ̸ = ⊥. Lemma 3.13. Conditioned on z ̸ = ⊥, the distribution of the transcript (w, c, z) generated by (P, V) is within statistical distance η from the simulated distribution.

Proof. For all c and conditioned on z ̸ = ⊥, the distribution of z output by P 2 is within statistical distance η from P (see Lemma 2.7). The latter is exactly the distribution of z conditioned on z ̸ = ⊥.

To complete the proof of Lemma 3.13, we argue that when z ̸ = ⊥, the first coefficient of the triple is fully determined by the two others, and equal to Az -Tc in both transcript and simulation.

Finally, we consider the statistical distance of the distributions conditioned on z = ⊥.

Lemma 3.14. Conditioned on z = ⊥, the distribution of the transcript (w, c, z) generated by (P, V) is within statistical distance ε from the simulated distribution.

Proof. It suffices to prove that for all c and conditioned on z = ⊥, the distribution of w in the transcript generated by (P, V) is statistically close to uniform over Z n q . Thanks to the first claim above, we have:

H ∞ [y|c ∧ z = ⊥] ≥ H ∞ [y] -log Pr[z = ⊥|c] ≥ H ∞ [y] -log 1 - 1 -η M .

Rényi Divergence Approach: DDHVZK Property

As a conclusion to Section 3.1.2, we prove the following statement.

Theorem 3.18. Let m ≥ n, k > 0, q prime, η, β SIS > 0 and ε ∈ [0, 1 2 ]. Assume that

H ∞ (Q) ≥ n log q + log 1 - 1 -ε M + 2 log 1 η . Let (S, T) ∈ R m,n,k,q,β SIS (A) for some A ← U (Z n×m q ). Assume that ∀c ∈ C : R ε ∞ (P ∥Q +Sc ) ≤ M.
Then Lyubashevsky's Σ-protocol satisfies the (η, 1/(1 -ε))-DDHVZK property.

Proof. We use the same simulator from Figure 3.8 and we note that by construction, it is decomposable. The analysis in the aborting case is already done in Lemma 3.14, while we change the proof of Lemma 3.13, where we use the Rényi divergence bounds from Lemma 2.7 in the non-aborting case.

In conclusion, while the two approaches lead to similar bounds, we note that the reductions are stateful when ε = negl(λ) in the statistical distance analysis, while the Rényi divergence approach allows for ε = O(1/Q s ).

Chapter 4 Optimized Use of Rejection Sampling in Fiat-Shamir with Aborts

This chapter takes a theoretical approach on the use of rejection sampling in Lyubashevsky's and BLISS signatures. Namely, we study the expected number of iterations and show that it is optimal in the "perfect" setting (Section 4.2). We then look for a choice of source and target distributions minimizing the expected Euclidean norm of the signature. To do so, we first give lower bounds on the compactness of the signature for a fixed target number of rejections (Section 4.3). Finally, we compare three choices of distributions: discrete gaussians, hypercube-uniform and hyperballuniform, both in theory and for practical parameters (Section 4.4). Further results, in particular a bounded rejection technique, can be found in [DFPS22].

Preliminaries: Beta Function and Hyperspherical Cap

The beta function is a special function related to the gamma function. Its link with hyperballs is necessary when considering imperfect rejection sampling, as seen in Lemma 4.10. The function x → I x (a, b) and its inverse are useful when we consider the area of a hyperspherical cap, as defined below.

Definition 4.1 (Regularized Incomplete Beta Function). The incomplete beta func- tion is defined over [0, 1] × R + × R + as B : (x; a, b) → x 0 t a-1 (1 -t) b-1 dt. When x = 1,
V η = V n (1) 2 • I 1-1 η 2 n + 1 2 , 1 2 and A η = S n 2 • I 1-1 η 2 n -1 2 , 1 2 .
From [MV10, Lemma 4.1], by placing an appropriate cone in the hyperspherical cap:

I 1-1 η 2 n + 1 2 , 1 2 > 1 - 1 η 2 n-1 2 • 1 -1 η n .
By placing the hyperspherical cap into a cylinder of 1-dimensional height 1 -1/η:

I 1-1 η 2 n + 1 2 , 1 2 < 1 - 1 η 2 n-1 • n • 1 - 1 η .
Letting

ε denote I 1-1/η 2 ( n+1 2 , 1
2 ), we obtain the following consequence of the above two inequalities, which we use to estimate the smooth Rényi divergence between uniform distributions in hyperballs:

1 -(2nε) 1 n+1/2 < 1 η 2 < 1 - ε n 1 n-1 .
For ε = 2 -c•n for a constant c > 0, we obtain that 1/η 2 tends to 1 -2 -c when n goes to infinity. For ε satisfying ε ≥ 2 -o(n) and ε = o(1/n) with n going to infinity, we obtain that 1/η 2 ∼ -ln(ε)/n.

Optimality of Generic Rejection Sampling

This section focuses on rejection sampling itself, before instantiating it in the case of Lyubashevsky's signature. We show the optimality of its expected runtime. We first recall another designs for rejection sampling, namely the greedy technique described in [START_REF] Harsha | The communication complexity of correlation[END_REF], which optimizes the expected value of the logarithm of number of iterations. However, when we want to minimize the expected number of iterations, we show that rejection sampling as described in Section 2.2.3 is optimal.

Another Rejection Sampling Algorithm

In this section, we study the rejection sampling procedure described in [START_REF] Harsha | The communication complexity of correlation[END_REF]. Let m > 0, P t and P s two probability distributions over Z m with R 1 (P t ∥P s ) < ∞. Let p 0 (z) = 0 for any z ∈ Z m and recursively define the following:

     α i (z) = min(P t (z) -p i-1 (z), (1 -p * i-1 )P s (z)), p i (z) = p i-1 (z) + α i (z), p * i = (z)∈Z m p i (z). Finally, define β i (z) = min Pt(z)-p i-1 (z) (1-p * i-1 )Ps(z) , 1 .

Optimality of Generic Rejection Sampling

A:

1: i ← 1 2: z ← P s 3: u ← [0, 1] 4: if u ≤ β i (z) then 5:
return z 6: else For any i > 0 and z ∈ Z m , let r(i, z) be the probability that A returns z after exactly i iterations. Then it holds that r(i, z) = α i (z) and ∞ j=1 r(j, z) = P t (z). Put differently, the statistical distance between the distribution of the output of A and A ′ is 0.

7: i ← i + 1 8: go to 2 9: end if A ′ : 1: Sample z ← P t . 2: Return z.
Proof. The probability that (i, z) is output is P s (z)p i-1 • β i (z)
, where pi-1 denotes the probability that the i -1 first values are rejected. We then show by induction that pi = 1 -p * i for any i ∈ N. In the case i = 0, we have p0 = 1 = 1 -p * 0 . Let us now assume that this holds for some i ∈ N. By induction, let us compute pi+1 = pi • z∈Z m (1 -β i+1 (z))P s (z). We have:

pi+1 = (1 -p * i ) z∈Z m (1 -β i+1 (z))P s (z) = 1 -p * i - z∈Z m min(P t (z) -p i (z), P s (z)(1 -p * i )) = 1 -p * i - z∈Z m α i+1 (z) = 1 -p * i+1 . Then ∀z ∈ Z m , ∀i ∈ N, r(i, z) = α i (z). As p i (z) = i j=1 α i (z),
we study these partial sums and show that they indeed converge to P t (z). To do so, we recall the proof from [HJMR07, Claim IV.1]. We reproduce it here for completeness.

Let us first show that α i (z) ≥ (P t (z) -p i-1 (z))P s (z). We have

1 -p * i-1 = z∈Z m (P t (z) -p i-1 (z)) ≥ P t (z) -p i-1 (z).
The above holds by definition of α i (z): both P t (z) -p -1 (z) and (1 -p * i-1 )P s (z) are ≥ (P t (z) -p i-1 (z))P s (z). From that, we find that

P t (z) -p i (z) ≤ (P t (z) -p i-1 (z))(1 -P s (z)),
and a straightforward induction show that this is ≤ P t (z)(1 -P s (z)) i . Finally, by definition of p i-1 (z), it holds that P t (z) -p i (z) ≥ 0.

Lower Bounds for Perfect Rejection Sampling

We start by studying the case of perfect rejection sampling, which corresponds to the setting of [START_REF] Lyubashevsky | Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures[END_REF][START_REF] Ducas | Lattice signatures and bimodal Gaussians[END_REF]. That is, we set ε = 0 in the formalism of Section 2.6. We prove two lower bounds: (1) regarding signature size in both unimodal and bimodal settings (Sections 4.3.1 and 4. 3.2), and (2) regarding the expected number of iterations of the rejection step (Section 4. 2.2).

First, we analyze to which extent the expected norm of a distribution P can be decreased, under the constraint that we can reject to it using shifted samples from Q, where the Euclidean norm of the shift is bounded from above. This gives lower bounds on the norm of the signature vector z in Lyubashevsky's signature scheme, as recalled in Section 2.6. We start by studying the easier case of continuous distributions, and then provide a way to discretize the results.

Second, we prove than the classical rejection sampling strategy described above is optimal if one aims to minimize the expected number of iterations of the rejection step in the case of perfect rejection sampling from P to Q. Specifically, the expected number of iterations of any strategy is at least R ∞ (P ∥Q), which is reached by classical rejection sampling.

Optimal Compactness in the Unimodal Setting

The main result of this subsection is the following. Theorem 4. 4. Let m > 1, t > 0, V = B m (t) and M > 1. Let f, g : R m → [0, 1] be two probability densities over R m such that sup v∈V R ∞ (f ∥g +v ) ≤ M . Then we have:

E x← f (∥x∥) ≥ t M 1/(m-1) -1 .
Note that we place ourselves in a setup where shifts belong to a hyperball. In the context of Lyubashevsky's signature scheme, the shift is Sc, where S is the signing key and c is the challenge (which is part of the signature). As S is unknown, replacing the set of Sc's by a hyperball seems to be a reasonable approach. Refining this approximation would lead to significant difficulties in the proof, with unlikely gains.

We now discuss the parameters M and m. As we exhibit later in Lemma 3.7, the variable M is related to the rejection probability. The smaller M , the faster we expect signing to be. To obtain a signing algorithm that terminates in polynomial time with overwhelming probability, we are interested in M ≤ poly(λ). Recall that m = Ω(λ). In this parameter regime, we have t/(M 1/(m-1) -1) ≈ t(m -1)/ log M .

The role of distribution g in Theorem 4.4 may seem puzzling, as it does not appear in the result. It acts as a control of the discrepancy of f : distribution f must be sufficiently wide to hide (in the Rényi divergence sense) a version of V that is blurred by g. This forces E x← f (∥x∥) to be rather large. The proof proceeds in two steps. The first one consists in showing that there is no point favoring any direction and that we can restrict the study to isotropic distributions, i.e., distributions whose density is a function of the norm of the vector. The proof proceeds by averaging on shells. Theorem 4.4 is then obtained by integrating the local constraint sup v∈V R ∞ (f ∥g +v ) ≤ M over the whole support, with appropriate scaling. Lemma 4.5. Let m ≥ 1, t > 0 and V = B m (t). Let f, g : R m → [0, 1] be two probability densities over R m and define M = sup v∈V R ∞ (f ∥g +v ). Then there exist two probability densities f * , g * that satisfy

• sup v∈V R ∞ (f * ∥g * +v ) ≤ M , • ∥x∥ = ∥y∥ =⇒ g * (x) = g * (y) and f * (x) = f * (y), • E z← f (∥z∥) = E z← f * (∥z∥).
Proof. Let us first take care of the m = 1 case. Define g * : x → (g(x) + g(-x))/2 as well as

f * : x → (f (x) + f (-x))/2. First, for any x ∈ R and v ∈ [-t, t], we have f (x) ≤ M • g(x -v) as well as f (-x) ≤ M • g(-x + v). This implies that R ∞ (f * ∥g * ) ≤ M . Now
, by construction, these two functions are even. Moreover, they are normalized and are thus probability densities. Finally, we have the equality

E x← f * (|x|) = (E x← f (|x|) + E x← f (|-x|))/2 = E x← f (|x|).
In the following, we assume that m ≥ 2. To define f * and g * , we switch from Cartesian to hyperspherical coordinates. Let (x 1 , . . . , x m ) and (ρ, θ 1 , . . . , θ m-1 ) both representing x in respectively Cartesian and hyperspherical coordinates. They satisfy the relations

∥x∥ = ρ x 1 = ρ cos(θ 1 )
x 2 = ρ sin(θ 1 ) cos(θ 2 )

. . . = . . .

x m-1 = ρ i≤m-2 sin(θ i ) cos(θ m-1 ) x m = ρ i≤m-1 sin(θ i ) .
Let ⃗ θ = (θ 1 , . . . , θ m-1 ) and x(ρ, ⃗ θ) be the vector whose coordinates are defined as above. Notice that the absolute value of the determinant of the variable change Jacobian is of the form ρ m-1 D( ⃗ θ) for some D : [0, π) m-2 × [0, 2π) → R ≥0 , as all columns except the first one are of the form ρ • y i ( ⃗ θ), and the first column does not depend on ρ. It then holds that

1 = R m f (x) dx = ∞ 0 ρ m-1 [0,π] m-2 ×[0,2π] f (x(ρ, ⃗ θ))D( ⃗ θ) d ⃗ θ dρ.
We then define:

f * : z → [0,π] m-2 ×[0,2π] f (x(∥z∥, ⃗ θ))D( ⃗ θ) d ⃗ θ [0,π] m-2 ×[0,2π] D( ⃗ θ) d ⃗ θ .
This is a probability density, as it is integrable and R m f * (x) dx = 1. The latter can be seen by switching once more to hyperspherical coordinates. By construction, it is isotropic. We also have E z← f (∥z∥) = E z← f * (∥z∥), which is also seen by applying the same change of variables. We define g * in the same way. It remains to prove that sup v∈V R ∞ (f * ∥g * +v ) ≤ M . Let z ∈ R m and v ∈ V . Let λ = ∥z-v∥/∥z∥. We consider the scaling s : y → λ•y.

For any y ∈ S m (∥z∥) (i.e., any y ∈ R m with ∥y∥ = ∥z∥), we have f (y) ≤ M • g(s(y)) as s(y) can be written as yv ′ , where v ′ ∈ V . Indeed, using the triangle inequality:

∥s(y) -y∥ = |λ -1|∥z∥ = |∥z -v∥ -∥z∥| ≤ ∥v∥ ≤ t.
Decomposing every element y ∈ S m (∥z∥) in hyperspherical coordinates as above with ρ = ∥z∥ for unique (θ 1 , . . . , θ m-1 ) ∈ [0, π] m-2 × [0, 2π], we multiply both sides by D( ⃗ θ), which is nonnegative, and we integrate over [0, π] m-2 × [0, 2π] to get:

[0,π] m-2 ×[0,2π] f (x(∥z∥, ⃗ θ))D( ⃗ θ) d ⃗ θ ≤ M [0,π] m-2 ×[0,2π] g(λx(∥z∥, ⃗ θ))D( ⃗ θ) d ⃗ θ.
We recall the definition of λ and divide both sides by

[0,π] m-2 ×[0,2π] D( ⃗ θ) d ⃗ θ.
We finally move on to proving Theorem 4. 4.

Theorem 4. 4. Thanks to Lemma 4.5, we can, without loss of generality, assume that both f and g are isotropic. For k ≥ 0, we define µ k = ∞ 0 r k f (r) dr, which is the k-th order moment of f . In particular, we have µ m-1 = 1/S m and µ m = E x← f (∥x∥)/S m . Indeed, using a hyperspherical variable change, we see that, for any β ∈ {0, 1}:

E x← f (∥x∥ β ) = R m ∥x∥ β f (x) dx = ∞ 0 ρ m-1+β f (ρ) [0,π] m-2 ×[0,2π] D( ⃗ θ) d ⃗ θ dρ = S m • µ m-1+β .
The above implies that E x← f (∥x∥) = µ m /µ m-1 .

For any x ≥ 0 and u ∈ [-t, t], it holds that f (x) ≤ M • g(|x -u|). In particular, for x ≥ t, we have f (x -t) ≤ M • g(x). Let us multiply both sides by x m-1 and integrate over [t, +∞). With a change of variable on the left-hand side, this gives

∞ 0 (x + t) m-1 f (x) dx ≤ M • ∞ t x m-1 g(x) dx ≤ M • ∞ 0 x m-1 g(x) dx = M • ∞ 0 x m-1 f (x) dx,
by recognizing that the right-hand side is M • µ m-1 (which is the same for f and g). Grouping everything on the same side, we have

0 ≤ ∞ 0 M x m-1 -(x + t) m-1 f (x) dx. (4.1)
Let C = t/(M 1/(m-1) -1). For m > 2, we rewrite the integrand as

M x m-1 -(x + t) m-1 = M 1 m-1 x -(x + t) • m-2 k=0 xM 1 m-1 k (x + t) m-2-k = M 1 m-1 -1 (x -C) • m-2 k=0 xM 1 m-1 k (x + t) m-2-k .
For m = 2, the above holds by replacing the sum by 1. Now, note that the inequality xM 1/(m-1) ≥ x + t holds if and only if x ≥ C. Hence the following upper bound holds for any x ≥ 0, if m > 2:

(x -C) • m-2 k=0 (xM 1 m-1 ) k (x + t) m-2-k ≤ (x -C)(m -1)M m-2 m-1 x m-2 .
When m > 2, we divide by (M 1/(m-1) -1)M (m-2)/(m-1) (m-1) > 0 in Equation (4.1):

C • ∞ 0 x m-2 f (x) dx ≤ ∞ 0 x m-1 f (x) dx.
Note that it also holds for m = 2. This can be rewritten as µ m-1 /µ m-2 ≥ C.

Observe that µ m •µ m-2 ≥ (µ m-1 ) 2 . Indeed, the Cauchy-Schwarz inequality states that for any real random variables X, Y , it holds that |E(XY

)| 2 ≤ E(X 2 )E(Y 2 ).
We instantiate it with the two (non-independent) random variables X = ∥x∥ m/2 and Y = ∥x∥ (m-2)/2 , where x ← f . Then XY = ∥x∥

m 2 + m-2 2 = ∥x∥ m-1 . To conclude, note µ m • µ m-2 ≥ (µ m-1 ) 2 implies that µ m /µ m-1 ≥ µ m-1 /µ m-2 ≥ C.
This completes the proof.

For the discrete case, given a discrete distribution P , we let f : x → P (⌈x⌋) be a probability density over R m , and we have, by the triangle inequality

E x← f (∥x∥) ≤ E x← P (∥x∥) + √ m 2 .
Theorem 4.4 can then be adapted to the discrete case, up to subtracting √ m/2 from the lower bound. In all setups considered in this work, this term is significantly smaller than t/(M 1/(m-1) -1).

Corollary 4.6. Let m, M > 1, t > 0, and V = B m (t)∩Z m . Let P and Q be two discrete probability distributions over Z m such that sup v∈V R ∞ (P ∥Q +v ) ≤ M . Then:

E x← P (∥x∥) ≥ t M 1/(m-1) -1 - √ m 2 .

Optimal Compactness in the Bimodal Setting

The following result holds in the bimodal setting, with a similar proof to Theorem 4. 4.

Theorem 4.7. Let m ≥ 3, t > 0, V = B m (t) and M > 1. Let f, g : R m → [0, 1] be two probability densities over R m such that sup v∈V R ∞ (f ∥g ±v ) ≤ M , where g ±v is the density x → 1 2 (g(x -v) + g(x + v)). Then the following holds:

E x← f (∥x∥) ≥ t M 2 m-2 -1 .
As in the unimodal case, we first radialize the densities.

Lemma 4.8. Let m ≥ 1, t > 0 and V = B m (t). Let f, g : R m → [0, 1] be two probability densities over R m and define M = sup v∈V R ∞ (f ∥g ±v ), where g ±v is as in Theorem 4.7. Then there exist two probability densities f * , g * that satisfy

• sup v∈V R ∞ (f * ∥g * ±v ) ≤ M , • ∀x, y ∈ R m , ∥x∥ = ∥y∥ =⇒ f * (x) = f * (y) and g * (x) = g * (y), • E z← f (∥z∥) = E z← f * (∥z∥).
Proof. We proceed as in the proof of Lemma 4.5 to define f * and g * , and use the same notations. Let

f * : z → [0,π] m-2 ×[0,2π] f (x(∥z∥, ⃗ θ))D( ⃗ θ) d ⃗ θ [0,π] m-2 ×[0,2π] D( ⃗ θ) d ⃗ θ .
We define g * in the same way, swapping f with g. As for Lemma 4.5, the first two claims hold. Let z ∈ R m and v ∈ V . For any y ∈ S m (∥z∥), let s y be the rotation that maps z to y. It is an isometry, so for any b ∈ {0, 1}, it holds ∥y + (-1) b s y (v)∥ = ∥z + (-1) b s y (v)∥. We also have ∥s y (v)∥ = ∥v∥, implying that s y (v) ∈ V . Then for any y ∈ S m (∥z∥):

f (s y (z)) ≤ M 2 (g(s y (z -v)) + g(s y (z + v))) .
By construction, there exist ⃗ θ 0 such that s x(∥z∥, ⃗ θ) (z) = x(∥z∥, ⃗ θ + ⃗ θ 0 ). We multiply both sides with D( ⃗ θ), which is nonnegative, and integrate over [0, π] m-2 × [0, 2π]. It yields the first claim, up to dividing by the normalisation constant.

We finally move on to proving the main result.

Theorem 4.7. Thanks to Lemma 4.8, we assume without loss of generality that both f and g are isotropic. We define the moments of f, g by µ

(ϕ) k := ∞ 0 x k • ϕ(x) dx for k ≥ 0 and ϕ ∈ {f, g}. We have µ (ϕ) m = E x← ϕ (∥x∥)/S m and µ (ϕ) m-1 = 1/S m
as in the proof of Theorem 4. 4. For any r ≥ 0, u ∈ [0, t] and θ ∈ [0, 2π), it holds that:

f (r) ≤ M 2 g r 2 + u 2 -2ru cos(θ) + g r 2 + u 2 + 2ru cos(θ) .
We will only consider θ = π/2 as it will suffice to obtain the bound. This gives for any r ≥ 0 and u ∈ [0, t]:

f (r) ≤ M g r 2 + u 2 .
Let us then multiply both sides by r √ r 2 + t 2 m-2

and integrate over R ≥0 . On the right-hand side, we use the change of variable y = √ r 2 + t 2 , which yields in turn dy = r/ √ r 2 + t 2 dr, to obtain:

∞ 0 r r 2 + t 2 m-2 f (r) dr ≤ M • ∞ t y m-1 g(y) dr.
Since y → y m-1 g(y) takes values in R ≥0 , we have that M/S m = M µ (g) m-1 is an upper bound for the right-hand side. By reordering terms, we obtain:

0 ≤ ∞ 0 r M 2 m-2 r 2 m-2 2 -r 2 + t 2 m-2 2 f (r) dr.
Now, note that for m ≥ 4, we have:

M 2 m-2 r 2 m-2 2 -r 2 + t 2 m-2 2 = M 2 m-2 r 2 -r 2 -t 2 M 1 m-1 r + √ r 2 + t 2 m-3 k=0 M 2 m-2 r 2 k 2 (r 2 + t 2 ) m-3-k 2 .
This also holds for m = 3 if replacing the sum by 1. Note that for r ≥ 0, we have M

1 m-1 r + √ r 2 + t 2 ≥ t. Let C = t/(M 2 m-2 -1) 1/2
M 2 m-2 r 2 m-2 2 -r 2 + t 2 m-2 2 ≤ (M 2 m-2 -1)(r 2 -C 2 ) m -2 t • M m-3 m-2 r m-3 .
Since all constants are positive, we obtain (including for m ≥ 3):

0 ≤ ∞ 0 (r m -C 2 r m-2 )f (r) dr.
Equivalently, µ

m ≥ C 2 µ (f ) (f )
m-2 , which we rewrite as (µ

(f ) m /µ (f ) m-1 ) • (µ (f ) m-1 /µ (f ) m-2 ) ≥ C 2 .
As we have seen in the proof of Theorem 4.4, the Cauchy-Schwarz inequality implies that µ

(f ) m-1 /µ (f ) m-2 ≤ µ (f ) m /µ (f )
m-1 . This leads to the desired lower bound. For M ≤ poly(λ) and m = Ω(λ) as in the discussion following Theorem 4.4, we have t/(M 2/(m-2) -1) 1/2 ≈ t (m -2)/(2 log M ). Similarly to the unimodal case, the lower bound can be adapted to integer distributions with limited loss (for all setups considered in this work). Corollary 4.9. Let m ≥ 3, t > 0, V = B m (t) ∩ Z m and M > 1. Let P and Q be two discrete probability distributions over Z m such that sup v∈V R ∞ (P ∥Q ±v ) ≤ M , where Q ±v is as in Theorem 4.7. Then the following holds:

E x← P (∥x∥) ≥ t M 2 m-2 -1 - √ m 2 .

Approaching the Lower Bounds with Hyperballs

We show that continuous uniform distributions in hyperballs almost reach the lower bounds in both the unimodal and bimodal perfect rejection sampling settings. We also consider the imperfect unimodal setting and find parameters that are asymptotically at least as good as the ones obtained for the Gaussian distribution (using our analysis described in Section 3.4. 1.3). As continuous hyperball uniform distributions are easier to study than their discrete counterpart, Further, we show that a slight modification of Lyubashevsky's signature allows for the target and source distributions to be continuous. We also compare this choice of distributions with the uniform distributions in hypercubes and with Gaussians, both asymptotically and with concrete parameters.

Note that the choice of r almost matches the lower bound from Theorem 4.7.

Proof. The support of U (B m (r ′ ), ±v) is exactly B m (r ′ , v) ∪ B m (r ′ , -v) and its density is z → (χ Bm(r ′ ,v) (z) + χ Bm(r ′ ,-v) (z))/(2V m (r ′ )). Thus, the divergence is finite when B m (r) ⊆ B m (r ′ , v) ∪ B m (r ′ , -v). It is the case if any x with ∥x∥ ≤ r satisfies ∥x -v∥ ≤ r ′ or ∥x + v∥ ≤ r ′ . We assume, w.l.o.g., that ∥x -v∥ ≤ ∥x + v∥. Then

∥x -v∥ = ∥x∥ 2 + ∥v∥ 2 -2⟨x, v⟩ ≤ ∥x∥ 2 + ∥v∥ 2 .
Thanks to the assumption on r and r ′ , we conclude that the divergence is finite. Now, the ratio of the densities only takes three values. If x ̸ ∈ B m (r) then the ratio is 0.

If x ∈ B m (r)∩B m (r ′ , v)∩B m (r ′ , -v) then the ratio is (r ′ /r) m . Finally, if x belongs to B m (r) ∩ B m (r ′ , v) but not to B m (r ′ , -v)
, then the ratio is 2(r ′ /r) m . This last case only occurs if B m (r) ̸ ⊆ B m (r ′ , -v). This is the case only if r ′ < r + ∥v∥. This completes the proof of the first claim.

For the second claim, note that the assumption on r and r ′ is satisfied, and that the divergence bound is indeed ≤ M .

In this bimodal case, the rejection test is as follows. One computes the norms of both z and z -2(-1) b v, where z = y + (-1) b v. If only the first one is ≤ r, then the sample is accepted. If both are ≤ r, then it is accepted and rejected with probability 1/2.

Finally, in order to use the uniform distribution in a hyperball, we verify that there is sufficient min-entropy in the first n coordinates given the remaining m -n coordinates.

Lemma 4.12. Let m ≥ 6, n ≥ 1 and r ≥ 2 √ m. Let x = (x ⊤ 0 |x ⊤ 1 ) ⊤ be a random variable over R m whose distribution is U (B m (r)), where x 0 has dimension n. It holds that

H ∞ ⌈x 0 ⌋|⌈x 1 ⌋ U (Bm(r)) ≥ log 2 1 0.85 • n .
Proof. We omit the U (B m (r)) subscripts for the min-entropies. First, note that we have H ∞ (⌈x 0 ⌋|⌈x 1 ⌋) ≥ H ∞ (⌈x 0 ⌋|x 1 ). By definition of the conditional min-entropy, we have

2 -H∞(⌈x 0 ⌋|x 1 ) = x 1 ∈B m-n (r) max x int 0 ∈Z n    x 0 ∈B ∞ n (1/2,x int 0 ) p x 0 ,x 1 (x 0 , x 1 ) dµ(x 0 )    dµ(x 1 ) ,
where the density satisfies

p (x 0 ,x 1 ) (x 0 , x 1 ) = 1 V m (r) χ <r 2 (∥x 0 ∥ 2 + ∥x 1 ∥ 2 ).
Recall that χ <r 2 (y) = 1 if y ≤ r 2 and 0 otherwise and that V m (r) is the volume of the Euclidean ball of radius r in dimension m.

The maximum is achieved when x int 0 = 0. Indeed, for any x int 0 ∈ Z m , we have

x 0 ∈B ∞ n (1/2,x int 0 ) χ <r 2 (∥x 0 ∥ 2 + ∥x 1 ∥ 2 ) dµ(x 0 ) = x 0 ∈B ∞ n (1/2,0) χ <r 2 (∥x 0 + x int 0 ∥ 2 + ∥x 1 ∥ 2 ) dµ(x 0 ) ≤ x 0 ∈B ∞ n (1/2,0) χ <r 2 (∥x 0 ∥ 2 + ∥x 1 ∥ 2 ) dµ(x 0 ) ,
where we used the fact that if ∥x 0 ∥ ∞ ≤ 1 2 and x int 0 ∈ Z n , then ∥x 0 + x int 0 ∥ ≥ ∥x 0 ∥. As a result, we can write

2 -H∞(⌈x 0 ⌋|x 1 ) = Pr ∥x 0 ∥ ∞ ≤ 1 2 .
Now we use the sub-independence of the coordinates slabs in the Euclidean ball (see [START_REF] Ball | The subindependence of coordinate slabs in ℓ n p balls[END_REF]), i.e., denoting x 0 = (x 01 , x 02 , . . . , x 0n ) T , we have

Pr ∥x 0 ∥ ∞ ≤ 1 2 ≤ n i=1 Pr |x 0i | ≤ 1 2 .
We now use Lemma As we used it in the proof above, we prove the following result. Proof. To show this, we use the fact (see [START_REF] Barthe | A probabilistic approach to the geometry of the ℓ n p -ball[END_REF]) that we can obtain samples (x 1 , . , where z is independent and has an exponential distribution (density t → exp(-t)).

With this notation, we have, for all δ > 0:

Pr x 2 1 > δ 2 m = Pr g 2 1 i≤m g 2 i + z > δ 2 m ≥ Pr   g 2 1 > 4δ 2 and i≤m g 2 i ≤ 3m and z ≤ m   ≥ Pr [|g 1 | > 2δ] -Pr   i≤m g 2 i > 3m   -Pr [z > m] ≥ Pr [|g 1 | > 2δ] -exp(-m) -exp(-m) .
For the last inequality, note that the distribution of 2 i≤m g 2 i is the chi-squared distribution of parameter m. If F denotes its cumulative density function, then we have the tail bound 1 -F (x) ≤ ((x/m) exp(1 -x/m)) m/2 for x > m, which we use with x = 6m. Taking δ = 1/2 and numerically evaluating the first term allows to complete the proof of the lemma.

Lyubashevsky's Signature with Continuous Distributions

We consider continuous distributions over hyperballs, which are not directly compatible with Lyubashevsky's signature scheme, as recalled in Section 2. 6. We argue that it is possible to extend Lyubashevsky's signature scheme to the case of continuous distributions, and that this comes with very limited complications (in the case of Gaussians, it could be simpler to use continuous Gaussians with this modified scheme, than using discrete Gaussians with the original scheme).

We use the same notations as in Section 2.6, with the source density g and the target density f being with supports over R m rather than Z m . The modified signature scheme handling continuous source and target distributions is presented in Figure 4. 2. Key generation is unchanged from Figure 2.5. Concretely, the changes compared to the construction described in Figure 2.5 are as follows: (i) y is now sampled from a continuous distribution with density g, (ii) c is now computed as H(A⌈y⌋, µ), (iii) with z still being defined as y + Sc, if the test passes, and the returned signature is now (⌈z⌋, c). Note that if f and g were actually discrete densities, then we would exactly recover the scheme from Figure 2.5. For correctness, note that

A⌈z⌋ -Tc = A⌈y + Sc⌋ -Tc = A (⌈y⌋ + Sc) -Tc = A⌈y⌋,
where the second equality holds because Sc is an integer vector.

Looking back to Chapter 3, we explain how to tweak the analysis from Section 3.4.1 to the continuous case. Having large commitment min-entropy is implied by having that H ∞ (⌈x 0 ⌋|⌈x 1 ⌋) is large, where x = (x ⊤ 0 |x ⊤ 1 ) ⊤ is a random variable over R m whose distribution is g and x 0 has dimension n. In the case of the uniform distribution in a hyperball, this is provided by Lemma 4.12. We obtain the same flavor of zero-knowledge, as the data processing inequality of the statistical distance and the Rényi divergence are used similarly.

Finally, we note that the modified scheme involves computations over real numbers. These can be securely replaced by finite precision computations, using standard techniques such as described in [START_REF] Prest | Sharper bounds in lattice-based cryptography using the Rényi divergence[END_REF] and as we apply in Chapter 5.

Sign(µ, A, S) :

1: y ← g 2: c ← H(A⌈y⌋, µ) 3: z ← y + Sc 4: u ← U ([0, 1]) 5: if u ≤ min f (z) M •g(y) ,

Comparison with other Distributions

Let t = max S,c ∥Sc∥. In Table 4.1, we summarize the expected norm of signatures (up to a constant factor) for diverse distributions P and Q, and for a target expected number of iterations M . We consider three specific pairs of distributions, two of them being previously considered distributions (Gaussians and uniforms in hypercubes), and the last one being uniform distributions in hyperballs, introduced above. We consider three different scenarios:

• unimodal distributions and perfect rejection sampling, in column ε = 0;

• unimodal distributions and imperfect rejection sampling -we use approximations specific to the choice of ε ≥ 2 -o(m) and ε = o(1/m);

• bimodal source distribution, perfect rejection sampling, in column "Bimodal". Note that the second scenario relies on our improved analysis relying on the Rényi divergence for the imperfect case (see Section 3.4.1.3). This parameter range for ε is not appropriate when using the analysis relying on the statistical distance.

In the last column, we emphasize if the rejection test is simple or not. For hyperballs, it consists in comparing the norm of the sample with the radius of the target hyperball in the unimodal case. For the bimodal case, one needs to compute two norms, and if necessary, to flip a coin (as discussed after Lemma 4.11).

The entries in the table are approximations for m → ∞, t = ω(1) and M = 2 o(m) , and for a given choice of P , we optimize the parametrization of Q (e.g., the radius in case of a hyperball) to minimize the signature norm.

The values of the table are obtained by computing the parameters for the underlying distributions (radii r, r ′ of the hypercubes or hyperballs and standard deviation σ of Gaussians) for our constraints M and t. This is done by computing their (smooth) Rényi Divergence, as done in Lemmas 4.10 and 4.11 for hyperballs. Proofs for hypercubes and Gaussians can be found in Section 4. 4.4. Given these parameters, the expected norm immediately follows (r √ m for a hypercube of radius r, σr for a Gaussian of standard deviation σ, and r for a hyperball of radius r). To conclude this section, we emphasize the following points:

• Gaussians and Hyperballs are asymptotically equivalent and reach the lower bounds in the bimodal setting; Hyperballs further reach our lower bound in

Choices for ε = 0 ε ≥ 2 -o(m) and ε = o(1/m) Bimodal Rejection P and Q Test Hypercubes tm 3/2 log M tm 3/2 log M tm 3/2 log M Simple Gaussians ∞ t √ m log 1 ε +log M log M t √ m √ log M Complex Hyperballs tm log M t √ m log 1 ε +log M log M t √ m √ log M
Simple Table 4.1: Expected norm of signatures depending on the choice of distributions and (im)perfectness of rejection sampling.

the exact unimodal setting as well;

• Hyperballs enjoy a significantly simpler rejection test compared to Gaussians;

• The bimodal setting (in both Gaussian and Hyperballs cases) leads to the most compact signatures.

Divergence of Usual Distributions

Lastly, we bound the (smooth) Rényi divergence for distributions classically used in Lyubashevsky's signatures. This lets us build Table 4.1.

Uniform Distribution in Hypercubes

For simplicity and ease of implementation, some applications rely on uniform distributions in hypercubes. The following result is implicit in [START_REF] Lyubashevsky | Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures[END_REF].

Lemma 4.14 (Rényi Divergence). Let m ≥ 1 and v ∈ Z m . Let r, r ′ ≥ 1/2 such that r ′ ≥ r + ∥v∥ ∞ . Then it holds that R ∞ U (B ∞ m (r) ∩ Z m )∥U (B ∞ m (r ′ , v) ∩ Z m ) ≤ 2r ′ + 1 2r -1 m . Let M > 1. The above is ≤ M if r ≥ ∥v∥∞+(M 1/m +1)/2 M 1/m -1 and r ′ = r + ∥v∥ ∞ .
Proof. For the divergence to be defined, we need

B ∞ m (r)∩Z m ⊆ B ∞ m (r ′ , v)∩Z m
. This is ensured by the constraint r ′ ≥ r + ∥v∥ ∞ . In that case, the divergence is the ratio of the number of elements in each support, leading to the upper bound. The second claim follows by elementary calculations.

The downside of the infinite norm is its lack of geometry: the use of the scalar product induced by the Euclidean norm is crucial to improve the bounds for the smooth divergence and the divergence with a bimodal version of the distribution, both for Gaussian distributions and uniforms in hyperballs. In contrary, these two setting do not bring significant improvements to the radius condition from Lemma 4.14 when considering the hypercube-uniform distribution.

Gaussian Distributions

By Lemma 2.9 and the fact that lim a→+∞ R a (P ∥Q) = R ∞ (P ∥Q), we see that the Rényi divergence of infinite order between two Gaussian distributions with same standard deviation but different centers is infinite. However Lemma 2.6 gives us a finite upper bound on the smooth divergence. The result is of the same flavour as [Lyu12, Lemma 4.5], but our proof clearly states the influence of ε on the bound. Lemma 4.15 (Smooth Rényi Divergence). Let m > 0, v ∈ R m , ε ∈ (0, 1) and σ > 0.

We have:

R ε ∞ D Z m ,σ ∥D Z m ,σ,v ≤ exp   ∥v∥ 2 2σ 2 + ∥v∥ 2 log 1 ε σ   , Let M > 1. The above is ≤ M if σ ≥ ∥v∥ √ 2 log(M ) log 1 ε + log 1 ε + log M .
Proof. Combining Lemmas 2.9 and 2.6, we obtain that for any a ∈ (1, +∞):

R ε ∞ (P ∥Q) ≤ exp a∥v∥ 2 2σ 2 + 1 a -1 log 1 ε .
Let a = 1 + σ ∥v∥ 2 log 1 ε , which minimizes the above quantity. This yields

R ε ∞ (P ∥Q) ≤ exp ∥v∥ 2 2σ 2 + √ 2 ∥v∥ σ log 1 ε .
To find when this is ≤ M , we take the logarithm and multiply by σ 2 on both sides. Solving a degree-2 equation in σ leads to the second claim.

The following is borrowed from [START_REF] Ducas | Lattice signatures and bimodal Gaussians[END_REF]. We prove it for the sake of completeness.

Lemma 4.16 (Rényi Divergence with a Bimodal Gaussian). Let m ≥ 1, v ∈ R m and σ > 0. Then the following holds:

R ∞ D Z m ,σ ∥BD Z m ,σ,v ≤ exp ∥v∥ 2 2σ 2 .

It is an equality if

v ∈ Z m . Let M ≥ 1. The bound is ≤ M if σ ≥ ∥v∥/(2 √ log M ).
Proof. Let z ∈ Z m . We have:

D Z m ,σ (z) BD Z m ,σ,v (z) = ρ σ,v (Z m ) ρ σ (Z m ) • exp -∥z∥ 2 2σ 2 exp -∥z∥ 2 -∥v∥ 2 2σ 2 cosh |⟨z,v⟩| σ 2 = ρ σ,v (Z m ) ρ σ (Z m ) • exp ∥v∥ 2 2σ 2 cosh |⟨z,v⟩| σ 2 ≤ ρ σ,v (Z m ) ρ σ (Z m ) • exp ∥v∥ 2 2σ 2 ,
standard deviation σ drops from 11t to 6.85t and leads to an additional saving on the signature size. When compared to Dilithium, if we consider the sum of signature and verification key sizes, we obtain up to ≈ 30% savings for the 'Recommended' parameter set, and ≈ 25% for the others. Finally, we explore the use of the continuous uniform distributions in hyperballs. We take the algorithms from Dilithium-G, which are adapted to radial distributions and replace the Gaussians with the continuous uniform distributions in hyperballs, adding coefficient-wise rounding to integers when computing commitments. To set parameters, the bound B is computed using the radius of the hyperball instead of the probabilistic upper bound on the norm of a Gaussian vector. In Table 4.3 (left side), we provide the instantiations that we obtained. We note that the signature sizes are very similar to the ones obtained with Gaussians.

Chapter 5

HAETAE: Hyperball bimodAl modulE rejecTion signAture schemE

This chapter presents HAETAE, a signature implementation relying on modules, bimodal hyperballs and Fiat-Shamir with aborts, whose complete specification can be found in [CCD + 23]. HAETAE is a candidate to the Korean post-quantum competition1 and NIST post-quantum signature competition 2 . In Section 5.2, we discuss the various optimisations we considered in the implementation. We give the full description of the scheme in Section 5.3 and discuss its performances in Section 5.4.

Additional Preliminaries

Before describing the scheme, we introduce a few additional notations.

Additional Notations

Let R = Z[x]/(x n + 1) where n is a power of 2. For any q > 0 let R q = R/qR = Z q [x]/(x n +1). We identify R 2 with the set of elements in R with binary coefficients.

Let R R = R[x]/(x n + 1). Given y = ( 0≤i<n y i x i , . . . , 0≤i<n y nk-n+i x i ) ⊤ ∈ R k R ⊃ R k ,
we define its ℓ 2 -norm as the ℓ 2 -norm of its corresponding coefficient vector, i.e. we let ∥y∥ 2 = ∥(y 0 , • • • , y nk-1 ) ⊤ ∥ 2 . For an integer η, we let the set of polynomials of degree less than n with coefficients in [-η, η] ∩ Z be denoted by S

η . Let B R,m (r, c) = {x ∈ R m R |∥x -c∥ 2 ≤ r} (resp. B (1/N )R,m (r, c) = (1/N )R m ∩ B R,m (r, c
)) denote the continuous (resp. discretized) hyperball with center c ∈ R m and radius r > 0 in dimension m > 0 (resp. for some integer N ). When c = 0, we omit the center.

High and Low Bits

An important compression technique introduced by [START_REF] Bai | An improved compression technique for signatures based on learning with errors[END_REF] and implemented by the Dilithium team [DKL + 18], consists in seding only the high bits of the lower part of

Rejection Sampling on the Key

A critical step of our scheme is bounding ∥sc∥ 2 , where s is generated as before and c ∈ R is a polynomial with coefficients in {0, 1} and has less than or equal to τ nonzero coefficients. The lower this bound is, the smaller the signature is, which in turn leads to harder forging. In the key generation algorithm, we apply the following rejection condition for some heuristic value β:

τ • m i=1 i-th max j ∥s(ω j )∥ 2 2 + r • (m+1)-th max j ∥s(ω j )∥ 2 2 ≤ nβ 2 τ ,
where m = ⌊n/τ ⌋ and r = n mod τ . We argue that the left hand side is a bound on n τ • ∥sc∥ 2 2 and that this condition leads to asserting ∥sc∥ 2 ≤ β.

Lemma 5. 4. Let n, τ > 0 and m = ⌊n/τ ⌋ and r = n mod τ . For any c ∈ {0, 1} n with hamming weight τ and any secret s ∈ S k+ℓ η , the quantity n∥cs∥ 2 2 is bounded by

τ 2 • m i=1 i-th max j ∥s(ω j )∥ 2 2 + r • τ • (m+1)-th max j ∥s(ω j )∥ 2 2 .
Proof. We first rewrite ∥sc∥ 2 as:

∥sc∥ 2 2 = i |c(ω j )| 2 • ∥s(ω j )∥ 2 2 n ,
where s(ω j ) = (s 1 (ω j ), • • • , s k+ℓ (ω j )), and ω j 's are the primitive 2n-th roots of unity.

For n = m • τ + r, let m = ⌊n/τ ⌋ and r = n mod τ . Since n j=1 |c(ω j )| 2 = nτ and

|c(ω j )| 2 = | ω j,1 + • • • + ω j,τ | 2 ≤ τ 2 ,
we bound n j=1 |c(ω j )| 2 •∥s(ω j )∥ 2 2 by rearrangement: let m = ⌊n/τ ⌋ be the maximum number of |c(ω j )| 2 's that can be τ 2 . By sorting ∥s(ω j )∥ 2 in decreasing order,

∥s(ω σ(1) )∥ 2 ≥ ∥s(ω σ(2) )∥ 2 ≥ • • • ≥ ∥s(ω σ(n) )∥ 2 ,
where σ is a permutation for the indices, we have

n j=1 |c(ω j )| 2 • ∥s(ω j )∥ 2 2 ≤ m j=1 |c(ω σ(j) )| 2 • ∥s(ω σ(j) )∥ 2 2 + n j=m+1 |c(ω σ(j) )| 2 • ∥s(ω σ(m+1) )∥ 2 2 .
Its maximum is reached when the m largest ∥s(ω j )∥ 2 2 's are multiplied with τ 2 's, i.e.

n j=1 |c(ω j )| 2 • ∥s(ω j )∥ 2 2 ≤ m j=1 τ 2 • ∥s(ω σ(j) )∥ 2 2 + n j=1 |c(ω j )| 2 -mτ 2 • ∥s(ω σ(j) )∥ 2 2 = τ 2 • m j=1 ∥s(ω σ(j) )∥ 2 2 + r • τ • ∥s(ω σ(j) )∥ 2 2 . 1: y ← U (B (1/N )R,m (r ′ )) 2: b ← U ({0, 1}) 3: z ← y + (-1) b v with probability p(z) 4: return z 5: return ⊥ B : 1: z ← U (B (1/N )R,m (r))
with probability 1/M ′ 2: return z 3: return ⊥ Then, from a continuous sample, we get a discretized one by rounding it, and slightly reducing its radius.

1: y i ← N (0, 1) for i = 0, . . . , nk + 1 2: L ← ∥(y 0 , . . . , y nk+1 ) ⊤ ∥ 2 3: y ← r ′′ /L • ( n-1 i=0 y i x i , . . . , n-1 i=0 y nk-n+i x i ) ⊤ ▷ y ∈ R k
y ← U (B (1/N )R,m (r ′ )): 1: y ← U (B R,m (N r ′ + √ mn/2)) if ∥⌊y⌉∥ 2 ≤ N r ′ 2:
return ⌊y⌉/N else

≥ √ mn 2r ′ • M 1/(mn) 0 + 1 M 1/(mn) 0 -1 .
At each iteration, the algorithm from Figure 5.4 succeeds with probability ≥ 1/M 0 . Moreover, the distribution of the output is

U (B (1/N )R,m (r ′ )).
Finally, in the complete specification of HAETAE [CCD + 23], we explain how to replace the continuous Gaussian with a discrete one as well as the necessary precision for those steps to succeed, using only fix-point arithmetic and standard techniques.

Challenge Sampling

The challenges we use are polynomials c ∈ R 2 with τ nonzero coefficients. The challenge space has size n τ . To sample them, we rely on the SampleInBall algorithm from Dilithium, which we recall in Fig. 5. 5. For the highest security, however, we require 255 bits of entropy for the challenge, which cannot be reached with 256 τ . To achieve it, we replace the challenge sampling for the parameter set with the following. Given a 256-bits hash w 0 . . . w 255 with Hamming weight w, do the following. If w < 128, return 255 i=0 w i x i . If w = 128, return 255 i=0 w i ⊗ w 0 x i . Otherwise, return 255 i=0 w i ⊗ 1x i . Exactly half of all binary polynomials are reachable this way and the challenge set has size 2 255 as desired.

SampleInBall(ρ, τ ):

Signature Encoding

A signature is comprised of three elements (h, c, z 1 ). We first split z 1 into low and high bits such that the low bits are distributed almost uniformly. The high bits however can be compressed using the range Asymmetric Numeral System from [START_REF] Duda | Asymmetric numeral systems: entropy coding combining speed of huffman coding with compression rate of arithmetic coding[END_REF], which allows for a better compression rate than Huffman coding when encoding a stream of data. Furthermore, it is possible to avoid arithmetic operations altogether and realize high-speed implementations using lookup tables (tANS). ∈ S. We define the following:

• CDF : S → Z, defined as CDF(s) = s-1 y=0 g(y). • symbol : Z → S, where symbol(y) → s such that CDF(s) ≤ y < CDF(s + 1).

• C : Z × S → Z, defined as C(x, s) = x g(s) • 2 n + (x mod + g(s)) + CDF(s).
The rANS encoding/decoding for S and frequency g/2 n is defined in Figure 5.6. Last, the cost of encoding the first symbol is ≤ n i.e. for any s ∈ S, log(C(0, s)) ≤ n.

We determine the frequency of the symbols experimentally, by executing the signature computation and collecting several million samples. Finally, we apply some rounding strategy to compute g such that the average extra cost per coordinate caused by this rounding is almost negligible. x i+1 = C(x i , s i+1 ) 3: return x m Decode(x ∈ Z):

1: y 0 = x 2: i = 0 while y i > 0 do 3: t i+1 = symbol(y i mod + 2 n ) 4: y i+1 = ⌊y i /2 n ⌋ • g(t i+1 ) + (y i mod + 2 n ) -CDF(t i+1 ) 5: i ← i + 1 6: m = i -1 7: return (t m , . . . , t 1 ) ∈ S m

Description of HAETAE

We give the description of the signature scheme HAETAE in Figure 5.7 with the following building blocks, implemented with symmetric primitives:

• Hash function H gen to generate the seeds and hashing the messages,

• Hash function H to sign, returning ρ, a seed for challenge sampling,

• Extendable output function expandA to derive a and A KeyGen from seed A ,

• Extendable output function expandS to derive (s gen , e gen ) from (seed sk , counter sk ),

• Extendable output function expandYbb to derive (y, b, b ′ ) from (seed ybb , counter), For the rest of this chapter, we let j = (1, 0, . . . , 0) ∈ R k . The parameters ρ 0 and α h refer to the size of the seed and the compression factor, respectively. The parameter β is the bound for ∥cs∥, which will be checked by bounding

f (s) := τ • m i=1 i-th max j ∥s(ω j )∥ 2 2 + r • (m+1)-th max j ∥s(ω j )∥ 2 2
by nβ 2 /τ . The parameters B, B ′ , and B ′′ refer to the radii of hyperballs. At

Step 2 of the Sign algorithm, the variable y 0 ∈ R R refers to the first component of the vector y ∈ R k+ℓ R . At Step 3 of the Sign algorithm, the vector z

∈ R k+ℓ R is decomposed as z = (z 1 , z 2 ) with z 1 ∈ R ℓ R and z 2 ∈ R k R . At
Step 4 Verify, the variable z0 ∈ R refers to the first component of the vector z ∈ R k+ℓ . We assume that α h divides 2q -1. At Step 6 of Verify, the division by 2 is over Z and well-defined as the operand is even and defined modulo 2q.

We also give a randomized signing of HAETAE in Figure 5.8. We observe that in the randomized version signing process, significant part of signing including the hyperball sampling algorithms for y can be performed "off-line", i.e., before receiving Sign(sk, M ):

1: µ = H gen (seed A , b 1 , M ) 2: seed ybb = H gen (K, µ) 3: counter = 0 4: (y, b, b ′ ) := expandYbb(seed ybb , counter) 5: w = A ⌊y⌉ 6: ρ = H(HighBits h (w), LSB(⌊y 0 ⌉), µ) 7: c = SampleInBall(ρ, τ ) 8: z = (z 1 , z 2 ) = y + (-1) b c • s 9: h = HighBits h (w) -HighBits h (w -2 ⌊z 2 ⌉) mod + 2(q-1)
α h 10: if ∥z∥ 2 ≥ B ′ , then counter++ and go to 4 11: else if ∥2z -y∥ 2 < B and b ′ = 0, then counter++ and go to 4 12: else return σ = (Encode(HighBits z1 (⌊z 1 ⌉)), LowBits z1 (⌊z 1 ⌉), Encode(h), c)

Verify(vk, M, σ = (x, v, h, c)): In the "on-line" phase of signing, we can use y and the corresponding pre-computed components by choosing them randomly among the pre-sampled list.

1: z1 ← Decode(x) • a + v and h = Decode(h) 2: (a| A KeyGen ) = expandA(seed A ) 3: A 1 = (2(a -2b 1 ) + qj| 2A KeyGen ) 4: w 1 = h + HighBits h (A 1 z1 -qcj) mod + 2(q-1) α h 5: w ′ = LSB(z 0 -c) 6: z2 = [w 1 • α h + w ′ j -(A 1 z1 -qcj)]/2 mod ± q 7: z = (z 1 , z2 ) 8: μ = H KeyGen (seed A , b 1 , M ) 9: Return (c = SampleInBall(H(w 1 , w ′ , μ), τ )) ∧ (∥z∥ < B ′′ )
Lemma 5.9. We borrow the notations from Figure 5.7. If we run Verify(vk, M, σ) on the signature σ returned by Sign(sk, M ) for an arbitrary message M and an arbitrary key-pair (sk, vk) returned by KeyGen(1 λ ), then the following relations hold:

Sign(sk, M ): // can be done off-line: using vk, make a list L of (y, w, w 1 )

1: y ← U (B (1/N )R,(k+ℓ) (B)) 2: w = A ⌊y⌉ 3: w 1 = HighBits h (w)
// can be done on-line: using sk, M and pre-computed (y, w, w 1 ) sampled from L go to 5 with resampled (y, w, w 1 ) // resample (y, w, w 1 ) ← L 13: else return σ = (Encode(HighBits z1 (⌊z 1 ⌉)), LowBits z1 (⌊z 1 ⌉), Encode(h), c) Figure 5.8: Randomized signing of HAETAE. On/offline signing can accelerate the signing process. Note that the signing can also be accelerated even if y is sampled offline alone.

4: µ = H gen (seed A , b 1 , M ) 5: b, b ′ ← {0, 1} 6: c = SampleInBall(H(w 1 , LSB(⌊y 0 ⌉), µ), τ ) 7: z = (z 1 , z 2 ) = y + (-1) b c • s 8: h = w 1 -HighBits h (w -2 ⌊z 2 ⌉) mod + 2(q-1) α h 9: if ∥z∥ 2 ≥ B ′ , then

w = HighBits

h (w), 2. w ′ j = LSB(⌊y 0 ⌉) • j = LSB(w) = LSB(w -2 ⌊z 2 ⌉). 3. 2⌊z 2 ⌉ -2z 2 = LowBits h (w) -LSB(w) assuming B ′ + α h /4 + 1 ≤ B ′′ < q/2,
Proof. Let m = 2(q -1)/α h . Let us prove the first statement. By definition of h, it holds that w 1 = HighBits h (w) mod m. However, both parts of the equality already lie in [0, m -1] by definition and Lemma 5. 3. Hence, the equality stands over Z too.

We move on to the second statement. By considering only the first component of z = y + (-1) b c • s, we obtain, modulo 2:

z0 = ⌊z 0 ⌉ = ⌊y 0 ⌉ + (-1) b c = ⌊y 0 ⌉ + c.
This yields the result. Moreover, by reducing A mod 2, we obtain that

w = A 1 ⌊z 1 ⌉ -qcj = (⌊z 0 ⌉ -c)j mod 2.
For the last statement, let us use the two preceding results. In particular, we note

w 1 • α h + w ′ j = w -LowBits h (w) + LSB(w).
We note that the last two elements have same parity, as the former one has the same parity as LowBits(w, α h ). By Lemma 5.3 their sum has infinite norm ≤ α h /2 + 2. Hence from its definition, it holds that 2z 2 = 2⌊z 2 ⌉ -LowBits h (w) + LSB(w) mod ± 2q.

Finally, this identity holds over the integers as the right-hand side has infinite norm at most 2B ′ + α h /2 + 2 < q.

Parameters and Performance Analysis

Theorem 5.10 (Completeness). Let B ′′ = B ′ + n(k + ℓ)/2 + √ nk(α h /4 + 1) < q/2. Then the signature schemes of Figures 5.7 and 5.8 are complete, i.e., for every message M and every key-pair (sk, vk) returned by KeyGen(1 λ ), we have:

Verify(vk, M, Sign(sk, M )) = 1.
Proof. We use the notations of the algorithms. We focus on the deterministic version in Fig. 5.7, since Fig. 5.8 also has almost the same proof. The two first equations from Lemma 5.9 state that ρ = ρ and thus c = SampleInBall(ρ, τ ). On the other hand, we use the last equation from Lemma 5.9 to bound the size of z. We have: ∥z∥ ≤ ∥z∥ + ∥z -⌊z⌉∥ + ∥⌊z⌉ -z∥

≤ B ′ + n(k + ℓ) • ∥z -⌊z⌉∥ ∞ + ∥⌊z 2 ⌉ -z2 ∥ ≤ B ′ + n(k + ℓ) 2 + √ nk • ∥LowBits h (w)∥ ∞ ≤ B ′ + n(k + ℓ) 2 + √ nk • α h 4 + 1 = B ′′ .

Parameters and Performance Analysis

Finally, we give our choice of parameters and the performance of the implementation.

Parameter Sets

We instantiate the HAETAE signature scheme to reach the NIST PQC security levels 2, 3, and 5. The instantiations are set to be at least as secure as the corresponding parameter sets for Dilithium and Falcon. We keep the methodology from Section 4.4.5. Namely, we set B ′′ ≪ q and use the core-SVP methodology. The parameters are provided in Table 5.

Performance Analysis

The C reference implementation of HAETAE can be found on team HAETAE website 3 . In Table 5.2, we give the performance results of the reference implementation and the sizes. All benchmarks were obtained on one core of an Intel Core i7-10700k, with TurboBoost and hyperthreading disabled. All cycle counts reported are the median and average of the cycle counts of 1,000 executions of the respective functions.

Due to the key and the signature rejection steps, the median and the average values for KeyGen and Sign differ clearly. The two values are much closer for Verify. Based on the profiling and benchmarking of subcomponents, we here discuss the most expensive parts during key generation and signing. During the key generation, the complex Fast Fourier Transformation, used for computing f (s), consumes nearly 50% of the total cycles. Among the components of the signing process, we remark that the hyperball sampling is the most significant part, using almost 80% of the total signing cost, mainly because of randomness sampling via the extendable output function.

In addition, we expect that the on/offline approach will reduce the (online) signing time by 12% to 20%, except for the time spent reading from the list.

G + G: Compact Lattice-Based Fiat-Shamir Signatures

IGen(1 λ ):

1: A 1 ← U (Z m×(k-m-ℓ) q
) 2: (S 1 , S 2 ) ← χ (k-m-ℓ)×ℓ × χ m×ℓ 3: B ← A 1 S 1 + S 2 mod q 4: A ← (qJ -2B|2A 1 |2I m ) ∈ Z m×k i.e., the verifier just samples c uniformly in the challenge space and sends it to the prover. After receiving c, the prover samples a Gaussian vector k over the lattice coset 2SZ ℓ + c. The covariance matrices of y and k are set so that the Gaussian plus Gaussian sum is statistically close to a spherical Gaussian distribution.

The first sampling that the prover has to perform is well-defined only if Σ(S) is definite positive, which we show in Lemma 2.14. The first sampling is implemented using Lemma 2.11, which requires σ 2 -s 2 σ 1 (S) 2 ≥ ln(2ℓ + 4)/π, where we let σ 1 (S) denote the largest singular value of S. The protocol can then be executed in polynomial time.

Combining this identification protocol with the Fiat-Shamir (without aborts) paradigm, we then obtain a lattice-based signature FS[G + G, H], as stated in the following Theorem. The correctness and security of the scheme are inherited from the properties of the underlying identification protocol. • ε c -correct;

• sEU-CMA-secure in the ROM under the SIS m,k,q,2γ assumption;

• sEU-CMA-secure in the QROM under the LWE k-m-ℓ,m,ℓ,χ,q assumption, assuming that 1/|C| + (|C| 2 (2γ + 1) 2k )/q m is negligible.

The proof of Theorem 6.1 follows from Corollaries 6.3, 6.5, 6.7, and 6.8, which are derived from the properties of the underlying identification protocol proved in Sections 6. 1.2, 6.1.3, and 6. 1.4, by applying the Fiat-Shamir transform.

Proof. We prove both properties separately. We start by proving HVZK, which is inherited from Lemma 2.14 and then focus on commitment min-entropy.

HVZK. The simulator on input a challenge c ∈ C and a public matrix A samples z ← D Z k , √ 2σ , sets w = Az -qJc and returns (w, c, z) as a transcript. As everything here is a function of z and c, we can rely on Lemma 2.14. The bounds from the above claim are immediately inherited from the latter lemma by applying the data processing inequalities (which we recall in Equation 2.1 for the Rényi divergence -the same inequality holds replacing the Rényi divergence by the statistical distance). This concludes the zero-knowledge analysis.

[2Y 2 = w -A 0 Y 1 mod 2q] ≤ Pr (Y 1 ,Y 2 ) [Y 2 = (w -A 0 Y 1 )ζ mod q] ,
where ζ is the modular inverse of 2 mod q. Hence, the min-entropy of the commitment is ≥ H ∞ (Y 2 mod q|Y 1 ) and we move on to bounding the latter quantity from below. Note that there exist σ ≥ σ 1 ≥ • • • ≥ σ m ≥ (σ 2 -s 2 σ 1 (S) 2 ) 1/2 and Q ∈ R m×m orthogonal such that

Σ(S) = Q    σ 2 1 . . . σ 2 m    Q ⊤ .
Let y 1 ∈ Z k-m be fixed. The distribution of Y 2 conditioned on Y 1 = y 1 is exactly D Z m ,Σ,c , as defined in Lemma 2.10 (with c = 0). Let σ 2 1 (resp. σ 2 m ) be the largest (resp. smallest) eigenvalue of Σ and c = (c 1 , . . . , c m ) ⊤ . We are interested in obtaining an upper bound on ρ Σ,c (z + qZ m )/ρ Σ,c (Z m ) for all z ∈ (-q/2, q/2] m .

As Σ -1 is the bottom right submatrix of Σ -1 of size m × m, it holds that for any y ∈ R m , we have y ⊤ Σ -1 y ∈ ∥y∥ 2 • [1/σ 2 1 , 1/σ 2 m ]. Hence all singular values σ i of Σ lie in [(σ 2 -s 2 σ 1 (S) 2 ) 1/2 , σ]. Thanks to the theorem assumptions, we obtain that all σ i 's are above η ε (Z m ). Using Lemma 2.13, it holds that

ρ Σ,c (Z m ) ≥ (1 -ε) • det Σ ≥ (1 -ε) • σ 2 -s 2 σ 1 (S) 2 m/2 .
The latter is ≥ (1 -ε) • (sσ 1 (S)) m , by assumption on σ. For the numerator, we first use Lemma 2.13 once more, to obtain: ρ Σ,c (z + qZ m ) ≤ ρ Σ (qZ m ) = 1 + ρ Σ (qZ m \ {0}) ≤ 1 + ρ σ (qZ m \ {0}) .

By assumption on q, the latter is ≤ 1 + ε. The result follows.

We then obtain the following corollary as an application of Theorem 2.16.

Corollary 6. 5. Using the same assumptions as in Theorem 6.4 the resulting signature scheme FS[G + G, H] is EU-CMA-secure (and sEU-CMA-secure) in the QROM, provided it is EU-NMA-secure.

KeyGen(1 λ ) : Second, the SIS m,k,β assumption, where β = O( √ kσ). The SIS parametrization is compatible with the reductions from worst-case lattice problems from [MR07,GPV08] when q ≥ Ω( √ kβ). Finally, the hardness of both problems is balanced out when α ≈ 1/β.

1: A 0 ← U (R m×k-m-1 q ) 2: do (s 1 , s 2 ) ← S k-m-1 η ×S m η 3: s ← (1|s ⊤ 1 |s ⊤ 2 ) ⊤ ∈ R k
The distribution of z is Gaussian with standard deviation σ = 2η ε (2SZ ℓ ), which is O(σ 1 (S) log(Q s λ)). As σ 1 (S) = O(λ), the norm of z is (almost) always at most β = O(λ 3/2 log 1/2 Q s ). Finally, we set q = Θ(λ 2 log 1/2 Q s ).

Verification keys and signatures have bit-sizes O(λ 2 log λ) and O(λ log λ).

Optimizations and Concrete Parameters

In order to decrease the sizes of a lattice-based scheme, a common approach is to replace Z with a cyclotomic polynomial ring of the form R = Z[x]/(1 + x n ), where n is a power of 2, and to rely on the intractability of the module versions of SIS and LWE [START_REF] Brakerski | Leveled) fully homomorphic encryption without bootstrapping[END_REF][START_REF] Langlois | Worst-case to average-case reductions for module lattices[END_REF]. Gaussian distributions are extended by considering the coefficients of the polynomials.

Description of the Module-Based Scheme

In this section, we propose parameters for an optimized, module version of the G + G signature, that we present in Figure 6. We let η > 0 and χ η = U ({y ∈ R| ∥y∥ ∞ ≤ η}). Given an element s ∈ R, we define rot(s) as the n × n matrix whose (i, j)-th entry is the coefficient of degree n -1 -j of x i • s mod 1 + x n . This matrix maps the coefficient embedding of a polynomial c to the coefficient embedding of sc. We extend this definition to vectors coordinate-wise and we define Σ(s) = Σ(rot(s)), where Σ is borrowed from Section 6.1. This gives rise to the signature scheme presented in Figure 6. 2. Beyond relying on polynomial rings, we consider various improvements and optimizations, which we discuss now.

KeyGen:

The key generation step includes a rejection sampling step. The threshold S will be set such that about 50% of the keys will be rejected. This helps are the lowest signatures and key sizes provided in the literature for Lyubashevsky's signatures (when using the core-SVP hardness methodology to estimate security).

We note that the resulting signature sizes are 20% to 30% lower than the ones from Chapter 4. The asymptotic gain of our signature is observable when comparing the signature sizes with Haetae, as the trade-off is first in its favor but ends up in favor of G + G for the higher security level, up to 16% of savings. However, the sum of the public key and the signature sizes is somewhat similar across the three signatures. This is due to the fact that in the non-bimodal setting, a practical optimization due to [DKL + 18] consists in truncating the low bits of the public key, at the cost of increasing the verification bound. While such a technique is also implemented in Haetae, its efficiency is relative in this setting, and we chose not to incorporate it in G + G for the sake of simplicity.

Optimized NTRU Key Generation Algorithm

We can alternatively use the NTRU-based key generation algorithm from [START_REF] Ducas | Lattice signatures and bimodal Gaussians[END_REF].

In our setting, it is possible to improve it, by relying on the aforementioned technique based on the divisibility of 2 by (1+x n/2 ). This leads to the key generation algorithm presented in Figure 6. 3. The algorithm outputs keys A and (A, s) satisfying As = ζ * q mod 2q as it holds that (q -1)hf = (q -1)(ζg +1) mod 2q since (q -1) is even. It that ζAs = 0 mod 2q, and the lattice in needs of smoothing is ζsR where ζs ⊤ = (ζf |2x n/2 g + ζ). We then propose two sets of parameters in Table 6.2, for ring dimensions 512 and 1024. The former leads to only around 90 bits of security, but the latter allows to reach NIST security level III. Focusing on the latter, while the sum |vk|+|sig| is similar to those of the other schemes, we note that the signature size is further decreased, compared to module G + G. The resulting signature is 40% smaller than in Section 4. 4.5 Chapter 7

Conclusion

In this thesis, we explored many aspects of the Fiat-Shamir (with Aborts) paradigm in the lattice setting. By a careful analysis, we discovered that the previous generic security reductions missed subtle issues, which underlines that the paradigm had yet to be fully understood. We fixed the proofs and thankfully recovered similar security loss bounds. This also let us clean up a missing link, in the sense that we proved the first reduction for the Fiat-Shamir with Unbounded Aborts transform. Moreover, our simulator for both aborting and non-aborting transcripts may prove useful for more advanced applications. In particular, any multiparty setting where multiple players have to agree during a first round on a challenge by each outputting their commitments.

In a second time, we aimed at making rejection sampling more efficient. It turned out that the generic technique is already essentially optimal in terms of expected runtime, which means that there was nothing to gain from this side. However, when we consider the specific case of the Lyubashevsky and BLISS identification protocols, we found that using uniform distributions in hyperballs led to the smallest expected norm of the answer, given a target number of repetitions, in both unimodal and bimodal setting. As a side bonus, the rejection condition consists of roughly one Euclidean norm computation and comparison. This is in stark contrast with the rejection condition for the discrete Gaussian distribution, which requires transcendental function evaluations.

However, optimized implementations such as Dilithium rely on more techniques to compress even further the signature size such as the Bai-Galbraith compression [START_REF] Bai | An improved compression technique for signatures based on learning with errors[END_REF]. For comparison, we proposed HAETAE, which relies on the above findings as well as adaptations of the standard compression techniques. It further shows that relying on hyperball-uniforms is realistic, as we implement such a sampler.

Finally, we showed how to depart from rejection sampling, while retaining similar concrete sizes and improved asymptotic sizes. The G + G signature scheme instead relies on adding randomness to the reply to the verifier's challenge, similarly to BLISS, but with more randomness involved. This paves the way for improvement of more advanced protocols, whose efficiency may have been limited due to rejection sampling. These findings raise multiple questions.

Can we improve the hyperball sampler for HAETAE?

Namely, we measured that hyperball sampling could take up to 80% of the signing process. Any improvement to the sampler would have a huge impact on the performance of HAETAE, as it clearly currently drives the signing cost. One of its downsides is its randomness consumption due to the necessary precision. Alternatively, improving the sampler could also come in the form of reducing the necessary precision, via a refined precision analysis. A third path could be to re-use randomness. Indeed, strategies exist for Dilithium that allow to reuse some part of the randomness (see, e.g. [START_REF] Sprenkels | Don't throw your nonces out with the bathwater[END_REF]). They however cannot be directly applied to our setting, as our distribution has a shape less compatible with coordinate-wise sampling, contrary to hypercubes.

What concrete performance could G + G achieve?

The main concern is the first Gaussian sampling, as the covariance matrix is skewed. Making it competitive with other schemes in terms of efficiency is far from trivial. Moreover, it has been a long standing problem to efficiently protect Gaussian sampling against side-channel attacks via masking. However, we note that if we consider an offline/online scenario, then we could sample the two Gaussian samples beforehand: we would need to sample the second gaussian twice, the first time assuming that c = 0 ℓ and the other times assuming that it is c = 1 ℓ . Indeed, we may not be aware of the challenge yet, but when we obtain it, we can compose the appropriate sample from these two samples, coordinate-wise. Moreover, the leftover randomness is not lost and it can be used for the next signature.

What impact can G + G have on advanced protocols?

The Fiat-Shamir with aborts paradigm is more versatile than just compiling identification protocols into signature schemes. More advanced cryptographic primitives have been built from Dilithium, such as multisignatures [START_REF] Damgård | Two-round n-out-of-n and multi-signatures and trapdoor commitment from lattices[END_REF], blind signatures [START_REF] Agrawal | Round-optimal lattice-based threshold signatures, revisited[END_REF], advanced proof systems [START_REF] Lyubashevsky | Lattice-based zeroknowledge proofs and applications: Shorter, simpler, and more general[END_REF], to cite a few. These proof systems rely on the unimodal setting, where one does not have to tweak the public key. Our G + G scheme is closer to the bimodal setting, for which it is not immediate to adapt these constructions. This downside is thus inherited by G + G. 4. Is there a link between G + G and hash-and-sign signatures? Hash-and-Sign is another paradigm of signatures, out of which Falcon [FHK + 17] was created. Falcon is the other winner of the NIST PQC and the hash-and-sign paradigm is also very successful in terms of further applications. It recently appeared in [START_REF] Chen | Does fiat-shamir require a cryptographic hash function[END_REF] that the first lattice based hash-and-sign signature [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] could be seen as a Fiat-Shamir signature with a very specific instantiation of the hash function. This raises the question of whether there exists an equivalent of G + G in the hashand-sign world, maybe obtained through the same hash function instantiation.

1 1 . 1 . 1 1 . 1 . 2 1 . 1 . 3

 1111112113 Brief History of Fiat-Shamir and Lattices . . . . . . . . . . . . . . . 2 Schnorr Protocol for Discrete Logarithm . . . . . . . . . . . . 3 The Fiat-Shamir Transform . . . . . . . . . . . . . . . . . . . 3 From Discrete Logarithm to Lattices: Introduction of Rejection Sampling .

Figure 1 . 1 :

 11 Figure 1.1:The sum of two Gaussians with compensating covariance matrices is a spherical Gaussian, even when the second Gaussian is rank-deficient. In the G + G identification protocol and signature, the first Gaussian corresponds to y, the second Gaussian is associated to Sc and the resulting one corresponds to z.

[

  DFPS23] A detailed Analysis of Fiat-Shamir with Aborts. J. Devevey, P. Fallahpour, A. Passelègue, D. Stehlé. Crypto 2023. This work contains additional results for Chapter 3, which includes QROM proofs as well as a fix for the [KLS18] proof. [DFPS22] On Rejection Sampling in Lyubashevsky's Signature Scheme. J. Devevey, O. Fawzi, A. Passelègue, D. Stehlé. Asiacrypt 2022. This work contains additional results for Chapter 4. It includes more details as well as a section on bounded rejection sampling strategies, which are a hybrid between rejection-free signatures and rejection sampling. [CCD + 23] HAETAE: Shorter Lattice-based Fiat-Shamir Signatures. J. H. Cheon, H. Choe, J. Devevey, T. Güneysu, D. Hong, M. Krausz, G. Land, M. Möller, D. Stehlé, and M. Yi. Preprint. This work contains additional results for Chapter 5. I played two main roles in the project. First, as I brought the bimodal hyperball idea, I worked on adapting the optimizations we will discuss next to the bimodal setting. Second, I was in charge of computing the parameter sets. The tools I used can be found on the project website or on the dedicated git repository for this thesis 8 . The full version includes the whole documentation of HAETAE, including parts where I was less involved, such as practical security assessment, longer report on performances and implementation techniques. It also includes reminders which were already present in Chapter 3 and Chapter 4. In preparation G + G: A Fiat-Shamir Lattice Signature Based on Convolved Gaussians. J. Devevey, A. Passelègue, D. Stehlé. Submitted.

[ DSSS21 ]

 DSSS21 On the Integer Polynomial Learning with Errors Problem. J. Devevey, A. Sakzad, D. Stehlé, R. Steinfeld. PKC 2021.

  DLN + 21] Non-interactive CCA2-secure Threshold Cryptosystems: Achieving Adaptive Security in the Standard Model without Pairings. J. Devevey, B. Libert, K. Nguyen, T. Peters, M. Yung. PKC 2021. This work proposes two constructions of threshold public key encryption, where the decryption key is split among multiple parties. One is based on the DCR assumption and the second one on lattice assumptions. The adaptive IND-CCA2 security model allows an adversary to adaptively corrupt parties as well as query partial decryption for non-corrupted ones. Before this work, this was not achieved in the standard model except for pairing-based constructions. [DLP22] Rational Modular Encoding in the DCR setting: Noninteractive Range Proofs and Paillier-based Naor-Yung in the Standard Model. J. Devevey, B. Libert, T. Peters. PKC 2022. This work proposes a new construction of range proofs in the standard model under the DCR assumption. As an application, we recover the security of a Naor-Yung construction of threshold encryption under the DCR setting. The previous proof contained a flaw which was fixed using our new construction of range proofs.

Definition 2 . 1 (

 21 Min-Entropy). Let X = (Y, Z) be a random variable. Let p X , p Z be the densities of X and Z, and p Y |Z=z the density of Y conditioned on Z = z. The min-entropy of Y is H ∞ (Y ) = max y∈Supp(p Y ) p Y (y). The conditional min-entropy of Y on Z is:

Figure 2 . 1 :

 21 Figure 2.1: Rejection sampling algorithms.

Lemma 2 .

 2 7 (Adapted from [Lyu12, Lemma 4.7]). Let M ≥ 1 and ε ∈ [0, 1/2] such that Pr z← pt

Figure 2 . 2 :

 22 Figure 2.2: The reprogramming game.

2. 3 .

 3 Gaussian Distributions and Smoothing Parameter Definition 2.5 (Gaussian Distribution). Let m ≥ 1, σ > 0, v ∈ R m and C = 1/2 in Chapter 4 or C = π everywhere else. Define

Definition 2 . 6 (

 26 Bimodal Gaussian Distribution). Let m ≥ 1. The bimodal Gaussian distribution BD Z m ,σ,v with parameters σ > 0 and v ∈ R m is the distribution obtained by sampling b ← U ({-1, 1}), and returning x ← D Z m ,σ,bv . It can be expressed as

Lemma 2 .= c 1 c 2

 22 10 (Conditional distribution). Let k ≥ m > 0, Σ ∈ R k×k be a symmetric positive-definite matrix and c ∈ R k . Write c and Σ = Σ 11 Σ 12 Σ 21 Σ 22 ,

Lemma 2 .

 2 11 (Adapted from [BLP + 13, Lemma 2.

Lemma 2 .

 2 12 ( [ZXZ18, Theorem 2]). Let k > 1 and ε < 0.086k. Let Λ ⊆ R k be a full-rank lattice with basis B = (b 1 , . . . , b k ). It holds that

Definition 2 .

 2 10 (Identification Protocol). An identification protocol is a Σ-protocol for an NP relation R, where the prover and verifier are dealt their statement and witness by a PPT instance generator IGen.Given a language L = {x ∈ X | ∃y ∈ Y : (x, y) ∈ R} for a relation R ⊆ X × Y, we are interested in the following properties of an identification protocol. Definition 2.11 (Completeness and commitment-recoverability). Let γ, β > 0.

Figure 2 . 4 :

 24 Figure 2.4: Fiat-Shamir Signature FS[ID, H].

Figure 2 . 5 :

 25 Figure 2.5: Left-hand side: Lyubashevsky's Σ-protocol. Right-hand side: BLISS underlying Σ-protocol. All computations are done modq.

1 :Figure 3 . 3 :

 133 Figure 3.3: The distinguisher D.

1: κ := 0 2 :Figure 3 . 4 :

 234 Figure 3.4: Game G 2 . The difference from G 1 is highlighted in blue.

Figure 3 . 5 :

 35 Figure 3.5: The distinguisher C for real and simulated transcripts of Σ based on A.

  6

1: with probability p 2 :Figure 3 . 6 :

 236 Figure 3.6: Simulator decomposition.

  Sample b ← Bernoulli(β) and c ← U (C). If b = 1 run (w, z) ← Sim ⊥ (pk, c), and if b = 0 run (w, z) ← Sim ̸ ⊥ (pk, c). Since the transcripts are being sampled independently from each other in both games G 2.1 and G 2.2 , one can bound the advantage of the distinguisher by

Figure 3 . 7 :

 37 Figure 3.7: The sets B and C in dimension 2.

  ∥c∥ ≤ τ and y + e ̸ ∈ C . The first one follows from the following (recall that t ′ = dτ /3 -(d + 1) √ m):

Figure 3 .

 3 Figure 3.8: Simulator Sim of Lyubashevsky's Σ-protocol.

  this is the Beta function, and we use the notation B(a, b) in that case. For fixed a, b, the function I • (a, b) : x → B(x; a, b)/B(a, b) is invertible.

Lemma 4 . 1 (

 41 Hyperspherical Cap). Let n > 1, η > 1 and x ∈ S n (1). Then the set {y ∈ B n (1)|⟨y, x⟩ ≥ 1/η} is the intersection of a half-space and the unit hyperball. It is called a hyperspherical cap and has volume V η and area A η satisfying

Figure 4 . 1 :

 41 Figure 4.1: Greedy rejection sampling

  843 + 2 exp(-m) ≤ 0.85 , for r ≥ 2 √ m and m ≥ 6.

Lemma 4 .

 4 13. Let (x 1 , . . . , x m ) T be uniformly chosen in the m-dimensional Euclidean ball of radius 1. Then Pr |x 1 | ≤ 1 4 √ m ≤ 0.843 + 2 exp(-m) .

  ifVerify(µ, z, c, A, T = AS) :1: if ∥z∥ ≤ γ and c = H(Az -Tc, µ) then

Figure 4 . 2 :

 42 Figure 4.2: Lyubashevsky's signature scheme with continuous distributions.

Figure 5 . 2 :

 52 Figure 5.2: Bimodal hyperball rejection sampling y ← U (B R,k (r ′′ )):

R 4 :Figure 5 . 3 :

 453 Figure 5.3: Continuous hyperball uniform sampling

Figure 5 . 4 :

 54 Figure 5.4: Discrete hyperball uniform sampling

1 : 2 :Figure 5 . 5 :

 1255 c ← c 0 c 1 . . . c 255 = 00 . . . 0 For i = 256 -τ to 255 Challenge sampling algorithm

Definition 5 . 3 (

 53 Range Asymmetric Numeral System (rANS) Coding). Let n > 0 and S ⊆ [0, 2 n -1]. Let g : [0, 2 n -1] → Z ∩ (0, 2 n ] such that x∈S g(x) ≤ 2 n and g(x) = 0 for all x /

Lemma 5 . 8 (

 58 Adapted from[START_REF] Duda | Asymmetric numeral systems: entropy coding combining speed of huffman coding with compression rate of arithmetic coding[END_REF]). The rANS coding is correct, and the size of the rANS code is asymptotically equal to Shannon entropy of the symbols. That is, for any choice of s = (s 1 , • • • , s m ) ∈ S m , Decode(Encode(s)) = s. Moreover, for any positive x and any probability distribution p over S, it holds that s∈S p(s) log(C(x, s)) ≤ log(x

5 .

 5 HAETAE: Hyperball bimodAl modulE rejecTion signAture schemE Encode((s 1 , . . . , s m ) ∈ S m ): 1: x 0 = 0 for i = 0, . . . , m -1 do 2:

Figure 5 .

 5 Figure 5.6: rANS encoding and decoding procedures

5. 3 .

 3 Description of HAETAEKeyGen(1 λ ):1: seed ← {0, 1} ρ 0 2: (seed A , seed sk , K) = H gen (seed) 3: (a| A gen ) ∈ R k×ℓ q := expandA(seed A) 4: counter sk = 0 5: (s KeyGen , e KeyGen ) := expandA(seed sk , counter sk ) 6: b = a + A gen • s gen + e gen mod q // b ∈ R k q 7: (b 0 , b 1 ) = (LowBits vk (b), HighBits vk (b)) 8: A = (2(a -b 1 ) + qj| 2A KeyGen | 2Id k ) mod 2q // A ∈ R k×(k+ℓ) 2q 9: s = (1, s gen , e gen -b 0 ) // s ∈ S k+ℓ η 10: if f (s) > nβ 2 /τ then go to 5 11: return sk = (s, K), vk = (seed A , b 1 )

Figure 5 . 7 :

 57 Figure 5.7: Deterministic version of HAETAE

  10:go to 5 with resampled (y, w, w 1 ) // resample (y, w, w 1 ) ← L 11: else if (∥2z -y∥ 2 < B) ∧ (b ′ = 0), then 12:

1 .

 1 The figures between parentheses are for the strong unforgeability security in the case of the randomized signing version of HAETAE (in the deterministic version, strong and weak unforgeability are the same). More details on the practical attacks and theoretical security reduction are provided in the complete specification [CCD + 23]. They are similar to the ones from Dilithium [BDK + 20] and the reduction from Chapter 3.

2q 5 :Figure 6 . 1 :

 561 Figure 6.1: The G + G Identification Protocol.

Theorem 6. 1 .

 1 Let m ≥ ℓ > 0, k > m + ℓ, ε ∈ (0, 1/2], s ≥ 8 ln(ℓ -1 + 2ℓ/ε)/π and σ ≥ √ 2σ 1 (S) • s for all S ∈ Z k×ℓ in the range of IGen. Let γ and ε c be such that Pr z← D Z k ,σ [∥z∥ > γ] ≤ ε c /3. Let q > max(2γ, σ • η ε (Z m)) be an odd modulus. Then the signature scheme FS[G + G, H] is:

  Commitment Min-Entropy. Let w ∈ Z m 2q and (Y ⊤ 1 , Y ⊤ 2 ) ⊤ ← D Z k ,Σ(S) , where Y 1 takes values in Z k-m . Given a matrix A = (A 0 |2I m ) ∈ Z m×k 2q , it holds that Pr (Y 1 ,Y 2 ) [A 0 Y 1 + 2Y 2 = w mod 2q] = Pr (Y 1 ,Y 2 )

2q 4 :Figure 6 . 2 :

 462 Figure 6.2: The Module G + G Signature Scheme.

2 .

 2 As in Section 6.1, let m > 0, k > m + 1 and ℓ = 1. Let j = (ζ * , 0, . . . , 0) ∈ R m , where ζ = 1 + x n/2 and ζ * = x n/2 -1 satisfy ζ * ζ = 2 mod 1 + x n . The challenge space is R/ζ * R.

Figure 6 . 3 :

 63 Figure 6.3: NTRU KeyGen for G + G

Table 1 .

 1 2: Signature sizes in bytes from across this thesis and Dilithium for comparison. All results can be reproduced using the scripts found in their respective folder at https://github.com/jdevevey/thesis and are all modifications of https://github.com/pq-crystals/security-estimates.

		1.3. Other Contributions and Publications
	Bit Security	120		160		260
	NIST Level	II		III		V
	Size	sig.	vk	sig.	vk	sig.	vk
	Dilithium	2420 1312 3293 1952 4595 2592
	Chapter 4 (Unimodal Gaussian)	1921 800	2462 1056 3553 1760
	Chapter 4 (Unimodal Hyperball) 1903 800	2473 1056 3461 1760
	Chapter 5 (Bimodal Hyperball)	1463 992	2337 1472 2908 2080
	Chapter 6 (Rejection-free)	1542 1120 2033 1568 2518 2336

  Then algorithm A real is a perfect rejection sampling algorithm with target density p ′ t and source density p s . The output density of B real is exactly p ′ t , as explained in [Dev86, Chapter II.3] (see in particular [Dev86, Theorems 3.1 and 3.2]). Moreover, the probability that A real outputs nothing is

by giving p t (x) as an upper bound of the integrand in the first inequality, and by keeping only the set of x's such that p t (x) ≤ M p s (x) in the second inequality. We have that the function p ′ t : x → min(p t (x), M p s (x))/C is a probability density satisfying R ∞ (p ′ t ∥p s ) ≤ M/C.

  . Note that r 2 +t 2 ≤ M 2 m-2 r 2 holds if and only if r ≥ C. Then for r ≥ 0 and m ≥ 4, we have

  . . , x m ) T by first sampling m independent Gaussian variables g 1 , . . . , g m with densities t → ρ 1/ , . . . , x m ) T = (g 1 ,...,gm) T

	√	2 (t)/	√ π and then setting (x 1 i≤m g 2 i +z

Table 5 .

 5 1: Parameter choices for 120, 180, 260 bits of core-SVP hardness

	Parameter set	HAETAE-120 HAETAE-180 HAETAE-260
	NIST Security level		2	3	5
	q		64513	64513	64513
	M		6.0	5.0	6.0
	Key Rate		0.1	0.25	0.1
	β		354.82	500.88	623.72
	B		9388.97	17773.21	22343.66
	B ′		9382.26	17766.15	22334.95
	B ′′		12320.79	21365.10	24441.49
	(k, ℓ)		(2,4)	(3,6)	(4,7)
	η		1	1	1
	τ		58	80	128
	α h		512	512	256
	d		1	1	0
	Forgery
	BKZ block-size b		409 (333)	617 (512)	878 (735)
	Classical hardness		119 (97)	180 (149)	256 (214)
	Quantum hardness		105 (85)	158 (131)	225 (188)
	Key-Recovery
	BKZ block-size b		428	810	988
	Classical hardness		125	236	288
	Quantum hardness		109	208	253
	Signature size		1463	2337	2908
	Public key size		992	1472	2080
	Sum		2455	3809	4988
	Private key size		1376	2080	2720
	Parameter set		KeyGen	Sign	Verify
	HAETAE-120	med ave	1,384,274 1,832,973	6,253,166 8,903,852	387,594 388,377
	HAETAE-180	med ave	2,333,614 3,464,004	9,472,724 11,763,246	718,010 719,400
	HAETAE-260	med ave	1,693,776 2,129,737	8,989,980 12,459,046	913,378 914,336

Table 5 .

 5 2: Median and average cycle counts of 1000 executions for HAETAE.

Table 6 .

 6 and 55% smaller than Dilithium. 2: Parameter Sets for NTRU G + G.

	Target Security	90	180
	n	512	1024
	q	32257	45569
	S	43.73	36.11
	KeyGen acceptance rate	0.25	0.5
	s	14.32	14.42
	σ	626.49	520.75
	B	21719.152 40218.387
	η	2	1
	α	256	2048
	BKZ block-size b to break SIS	314 (238) (622)
	Best Known Classical bit-cost	91 (69) (181)
	Best Known Quantum bit-cost	80 (61) (159)
	BKZ block-size b to break LWE	305	616
	Best Known Classical bit-cost	89	180
	Best Known Quantum bit-cost	78	158
	Signature size with rANS	974	1497
	Expected public key size	992	2080
	Sum	1966	3577

https://httparchive.org/reports/page-weight?start=2023_03_01&end=latest&view= list

If we view y and S over Zq rather than Z, then they do belong to a finite set; but for security, the masking should preserve smallness relative to q, which the uniform distribution modulo q does not achieve.

We could also apply it for BLISS, but it turns out that ε = 0 in this case.

The haetae is a mythical Korean lion-like creature with the innate ability to distinguish right from wrong.

https://kpqc.cryptolab.co.kr/haetae

https://www.kpqc.or.kr/

https://csrc.nist.gov/projects/pqc-dig-sig/

https://github.com/jdevevey/thesis

https://www.kpqc.or.kr/

https://csrc.nist.gov/projects/pqc-dig-sig

https://kpqc.cryptolab.co.kr/haetae

Remerciements Acknowledgements

where the randomness is taken over H as well as the coins of Sign.

Proof. The result follows from Theorem 3.7. Indeed, assuming that Sign did not output ⊥, then the final challenge that it outputs is uniform over the challenge space C. It may not be independent from previous executions of the identification protocol, but nonetheless its marginal distribution is uniform over C. Hence, assuming that Sign did not output ⊥, it outputs a signature that is accepted by Verify with probability at least γ, by correctness of the identification protocol. In the case where Sign outputs ⊥, this signature is of course rejected by Verify. Hence, by the law of total probabilities we have 3 .

We finally prove the security of the unbounded version of the Fiat-Shamir transform in the ROM. We reduce the T ′ -UF-CMA security of the unbounded signature scheme to the UF-CMA security of the bounded one in the ROM.

Theorem 3.10. Let α ≥ 0, β ∈ (0, 1), and let H be a hash function modeled as a random oracle. Assume that Σ = ((P 1 , P 2 ), (V 1 , V 2 )) is a (γ, β)-correct identification protocol, and that the commitment message of P 1 has min-entropy α. Let T denote the runtime of one iteration of the protocol with the hash function. Let T ′ > BT . For any arbitrary adversary A against T ′ -UF-CMA security of SIG ∞ = FS ∞ [Σ, H] that issues at most Q H queries to the random oracle H and Q S classical queries to the signing oracle and for any fixed integer B, the same adversary A against UF-CMA security of SIG B = FS B [Σ, H] is such that |Adv T ′ -UF-CMA SIG∞ (A) -Adv UF-CMA SIG B (A)| is bounded as

This also holds replacing UF-CMA with UF-CMA 1 or sUF-CMA security.

Proof. We proceed with three hybrid games.

Game G 0 . We define Game G 0 as the UF-CMA security of SIG B .

Game G 1 . Let Game G 1 be game T ′ -UF-CMA in which the adversary is promised to not make any sign query that takes more than T ′ steps to halt. In the ROM, if the advantage of the adversary A to distinguish these games is non-zero, then A must have queried a message µ such that Sign(sk, µ) = ⊥ in Game G 0 . Note that we cannot assume A is a purified quantum circuit since the queries to the signing oracle must be classical and cannot be purified. Nevertheless, we can purify A between the sign queries (the random oracle queries are quantum and would cause no problem for purification). This is equivalent to saying that after the i-th sign query µ i , and receiving σ i as the outcome, the adversary applies U i , where U i comes from a distribution derived from {σ j } j≤i , and then measures one of its registers to obtain µ i+1 . It repeats this process Q S times. By doing so, we can prove the above statement. As long as Sign(sk, µ i ) ̸ = ⊥, the distributions of σ i and thus U i are

We conclude by using the leftover hash lemma (Lemma 2.1).

Theorem 3.11 follows from the above lemmas by term collection.

Low Min-Entropy Source Distributions

The above handles many settings of Lyubashevsky's signature, as the source distribution Q is often chosen to have high min-entropy so that the map y → Ay mod q is (very) surjective. In some cases, however, it is chosen of lower entropy and the map y → Ay mod q is very far from surjective. For example, this allows to avoid the forking lemma in the security proof [START_REF] Abdalla | Tightly secure signatures from lossy identification schemes[END_REF], which both leads to a tight security proof and facilitates unforgeability proofs in the QROM. Our pathological construction from Section 3.2.1 also relies on this regime. We explain how this can be handled, for some distributions. First, we consider computational zero-knowledge rather than statistical zero-knowledge. As one needs to be able to replace real transcripts of (many) sign queries by simulated ones in the security proof, we consider a strong notion of computational zero-knowledge: computational indistinguishability is required to hold even when the distinguisher is given the witness (of course, the simulator does not use the witness). This definition is compatible with our Fiat-Shamir with aborts analyses. In the analysis based on adaptive reprogramming (Section 3. 1.1), transcripts can be replaced one at a time by simulated ones using a hybrid argument, since the witness allows to generate real signatures. In particular, our definition implies the notion of computational HVZK for multiple transcripts used in [GHHM21, Definition 2], which they use to argue that all transcripts can be replaced by simulated ones in a single step. In our reduction, when using the zero-knowledge property, the witness x is available to the challenger. Definition 3.5 (Strong Computational HVZK). Let ε zk , T ≥ 0 with ε zk a negligible function of the security parameter. A Σ-protocol ((P 1 , P 2 ), (V 1 , V 2 )) for a relation R is (ε zk , T )-sc-HVZK if there exists a simulator Sim with runtime at most T such that for all polynomial-time algorithm A and all (x, y) ∈ R, the following is ≤ ε zk :

One may consider classical or quantum adversaries A.

As in the statistical case, if the Σ-protocol is public-coin, then without loss of generality, the challenge c can be sampled uniformly from the challenge space C and passed over as input to the simulator Sim. In the following, we use this formalism.

The computational assumption that we rely on is the Learning With Errors problem [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. We use its knapsack form, introduced in [MM11].

and D a distribution over Z m q . The search knapsack-LWE problem sk-LWE m,n,q,D with parameters m, n, q, D consists in recovering e from (A, Ae), where A ← U (Z n×m q

) and e ← D. The decision knapsack-LWE problem dk-LWE m,n,q,D with parameters m, n, q, D consists in distinguishing between the distributions (A, Ae) and (A, u), where A ← U (Z n×m q ), e ← D and u ← U (Z n q ).

We argue that for some distributions Q, it is possible to prove computational zero-knowledge in the sense of Definition 3.5, with the above simulator (Figure 3.8).

Theorem 3.15. Let m ≥ n and k > 0, q ≤ poly(m, n) prime and

Then the distribution of the transcript (w, c, z) generated by ⟨P(S), V(T)⟩ is computationally indistinguishable from the distribution of the triple (w, c, z) obtained by sampling c ← U (C) and (w, z) ← Sim(T, c), even if the distinguisher is given S.

The first two claims (Lemmas 3.12 and 3.13) of the proof of Theorem 3.11 still hold. It hence suffices to prove the statistical indistinguishability of the genuine and simulated transcripts (w, c, z) conditioned on z = ⊥.

We first show that the genuine distribution of y conditioned on z being rejected resembles the distribution Q of y. Lemma 3. 16. Assume that M > 1. Consider the execution ⟨P(S), V(T)⟩. Let Q ⊥ denote the distribution of y conditioned on z = ⊥. Then we have:

Proof. For all y, we have

Lemma 3.12 ensures that the denominator is at least 1 -1/M .

The following result states that if (A, Ay) is pseudo-random for y ← D, then so is it for y ← D ′ for any distribution

Proof. Note first that dk-LWE m,n,q,D reduces to sk-LWE m,n,q,D . Moreover as we have R ∞ (D ′ ∥D) ≤ poly(m, n), the probability preservation property (see Lemma 2.2) implies that sk-LWE m,n,q,D reduces to sk-LWE m,n,q,D ′ . Finally, as shown by [MM11, Theorem 3.1], sk-LWE m,n,q,D ′ reduces to dk-LWE m,n,q,D ′ . The composition of these reductions leads to the above claim. Theorem 3.15 now follows from combining Lemmas 3.16, 3.17, 3.12 and 3.13.

Optimality of the Expected Number of Iterations

We now analyze to which extent the expected number of iterations of the rejection step could be reduced in the case of exact rejection sampling from P to Q, and prove the classical strategy to be optimal. This question arises from the variety of rejection sampling techniques that have been studied in other fields.

There exist multiple variants of rejection sampling. For instance, the aforementioned procedure described in [START_REF] Harsha | The communication complexity of correlation[END_REF] takes a greedy approach to rejection sampling and differs from the one we presented up until now. We are in the setting where we have access to a sampler from distribution Q. These samples are denoted by (X i ) i≥1 with X i ∈ X for some set X and we are required to output a sample from the distribution P over X . Any design of procedure is allowed, as long as the output is one of the observed samples X i . Let i * be the random variable denoting the number of samples observed by an algorithm and we wish to determine how small E(i * ) can be. We note that the work of [START_REF] Harsha | The communication complexity of correlation[END_REF], establishes that there exists a rejection sampling algorithm achieving E(log i * ) = log R 1 (P ∥Q) up to lower order terms in R 1 (P ∥Q), and that this is optimal. Here, we show that the minimum value for E(i * ) is R ∞ (P ∥Q).

In this section, we model a rejection sampling algorithm by a family of randomized functions A i : X i → {1, . . . , i}∪{r}. At step i, it sees the new sample X i and based on X 1 , . . . , X i it computes A i (X 1 , . . . , X i ). If it is equal to r, the algorithm asks for one more sample and otherwise if A i (X 1 , . . . , X i ) ∈ {1, . . . , i}, the algorithm terminates and outputs the sample X A i (X 1 ,...,X i ) . Note that the running time of the algorithm is defined by i * = inf{i ≥ 1 : A i (X 1 , . . . , X i ) ̸ = r}. We only consider algorithms for which i * < ∞ almost surely. Define the random variable J = A i * (X 1 , . . . , X i * ) ∈ N + , note that J ≤ i * and the output of the algorithm is X J (i.e., the output sample may not be the last one that was generated).

Theorem 4. 3. Let P, Q be two discrete probability distributions. Any rejection sampling algorithm (A i ) i≥1 sampling from P satisfies E(i * ) ≥ R ∞ (P ∥Q).

Proof. We have by assumption for any x ∈ X ,

where we used the fact that the event

In the context of Lyubashevsky's signature schemes with source distribution Q ′ , target distribution P ′ , challenge set C and signing key S, we have P = P ′ ⊗ U (C) and Q would be the distribution of the pair (z, c) obtained by sampling y from Q ′ , as well as c from U (C) and defining z = y + Sc.

The above proof can be adapted in the setting where P and Q are continuous distributions by considering a sequence of balls converging to {x} instead of x.

Uniform Distributions in Hyperballs

The first step is to compute the divergence in the three settings: unimodal, either perfect or imperfect rejection sampling and bimodal perfect rejection sampling. The first case can actually be seen as a particular case of the second one, and we summarize both in the following lemma. The function I appearing in the statement is defined in Section 4.1, and comes into play when dealing with hyperspherical caps.

For ε = 0, we have η = 1. In that case, we can set r = ∥v∥/(M 1/m -1), which almost matches the lower bound from Theorem 4. 4. As seen in Section 4.1,

Proof. Assume that there exists some cut C with vol(C)/V m (r) ≤ ε such that the divergence is defined, i.e., with B m (r)\C ⊆ B m (r ′ , v). Then the divergence is (r ′ /r) m , as the ratio of densities is constant and equal to (r ′ /r) m over B m (r) \ C. To prove the first claim, it hence suffices to show that such a cut C exists.

Let C η := {x ∈ B m (r)|⟨x, v⟩ ≥ -∥v∥r/η}. This is the intersection of a ball with an affine half-space, i.e., an m-dimensional hyperspherical cap. By Lemma 4.1, its volume is Vm(r)

By assumption, the latter is no larger than r ′ , implying that x ∈ B m (r ′ , v).

Finally, by combine the condition on r and r ′ and the equality r ′ = M 1/m r, we get

which is a degree-2 inequality on r. Solving it completes the proof.

where χ <r+∥v∥ denotes the indicator function of the set {x ∈ R|x ≤ r + ∥v∥}. where the last inequality comes from the fact that cosh(x) ≥ 1 for any x ∈ R. Note that for z ∈ Z m orthogonal to v, this upper bound is reached. Finally, using [MR07, Lemma 2.9], we have that

As a side note, we observe that this result can be extended to any order and compared to standard results between two Gaussian distributions.

Corollary 4.17. Let m ≥ 1, v ∈ R m and σ > 0. Then the following holds:

Proof. The Rényi divergence is increasing in its order. Thus the upper bound from Lemma 4.16 is also an upper bound for any order a ∈ [1, +∞].

Concrete Parameters

In this section, we use the core-SVP methodology introduced in [ADPS16], a conservative security estimation method in lattice cryptography.

To study the concrete impact of the choice of distributions on signature size, we consider Dilithium. The left side of Table 4.2 shows the parameters for three security levels of the round-3 documentation of the CRYSTALS-Dilithium submission to the NIST post-quantum project [BDK + 20]. The right side of Table 4.2 gives updated parameters for Dilithium-G, which relies on Gaussian distributions whose description is available in the first version of the eprint version of [DKL + 18]. For this update, we set the value of M to 4 and aim for security levels consistent with those of Dilithium. We update the quantum costs by plugging in the improvements from [START_REF] Chailloux | Lattice sieving via quantum random walks[END_REF].

In these schemes, the verification key is a module-LWE sample Bs 1 + s 2 where s 1 and s 2 have ℓ ∞ -norms ≤ η. For each coordinate, the lowest d bits are dropped. A parameter τ is used to control the ℓ 1 -norm of any hashed value c, so that c has sufficient min-entropy. In Dilithium-G, the bound t is S √ τ , where S is the median over the key generation randomness of the largest singular value of (rot(s 1 ) ⊤ , rot(s 2 ) ⊤ ) ⊤ . A rejection step is added in KeyGen to check that the key satisfies it. The value of the SIS bound for unforgeability is computed using [BDK + 20, Equation ( 6)]. We multiply it by 2 to get the strong unforgeability bound. The security is estimated using block-size optimized BKZ to break the module-SIS or module-LWE instances.

For Dilithium, i.e., the hypercube version, we take t ∞ = τ η as a bound on the ℓ ∞ -norm of the secret key, which drives the radius of the hypercube and subsequently the unforgeability SIS bound (in ℓ ∞ -norm).

It was argued in [DKL + 18] that it seems difficult for BKZ to solve SIS with ℓ ∞norm bound close to q, i.e., ℓ 2 -norm above q. To analyze the runtime of BKZ in the case of an ℓ 2 -norm bound B ≥ q, one can remove the trivial vectors of the input basis (i.e., the vectors with coordinates in qZ) by some randomizing step. This approach was however not considered for Dilithium-G and q was chosen such that B < q, leading to bigger parameters overall. We keep this constraint, as it is difficult to analyze the effectiveness of the attack presented in [DKL + 18] when B > q for Euclidean norm.

Finally, the computation of the verification key and signature sizes (in bytes) is performed as in [BDK + 20] and [DKL + 18], respectively, with a different encoding. Namely, to compute signature sizes for the Gaussian version, we rely on a strategy explained in [ETWY22, Section 5], called range Asymmetric Numeral System, which allows one to encode the signature with an average bit-length reaching its entropy plus some constant overhead that we ignore. This technique is used to obtain the sizes in the right hand side of Table 4. 2.

Next, we apply to Dilithium-G two modifications introduced in this work and introduce the Hyperball variant. In Table 4.3 (right side), we show the improvements we obtain when the standard deviation σ is computed using our refined bound from Lemma 4.15 on the smooth Rényi divergence between two Gaussians and instantiated with ε = 2 -64 (we set Q s = 2 64 ) instead of ε = 2 -λ , as allowed by the use of Rényi divergence (as discussed in Section 3.1.2 and Section 3.4. 1.3). Keeping M = 4, the the signature vector z. Moreover, we also rely on bit decomposition to encode the signature. We first recall the Euclidean division with a centered remainder. We define our base decomposition function.

Definition 5.1 (High and low bits). Let r ∈ Z and α be a power of two. Successively define r 1 = ⌊(r + α/2)/α⌋ and r 0 = r mod ± α. Finally, define the tuple:

(LowBits(r, α), HighBits(r, α)) = (r 0 , r 1 ).

We extend these definitions to vectors by applying them component-wise. This decomposition lets us recover the original element and we bound its components. Lemma 5.2. Let α = 2 d , d > 0, q = 2 d-1 • p + 1 be a prime and r ∈ Z. It holds that r = α • HighBits(r, α) + LowBits(r, α),

Proof. By Lemma 5.1, there exists a unique representation r = ⌊(r + α/2)/α⌋α + (r mod ± α).

Identifying HighBits(r, α) and LowBits(r, α) above yields the first result.

Next, by definition of mod ± , we have that r ′ ∈ [-α/2, α/2).

For the second range, since ⌊(r + α/2)/α⌋ is a non-decreasing function, we only show that ⌊(2q -1 + α/2)/α⌋ ≤ ⌊(2q -1)/α⌋. We have (2q -1 + α/2) ≤ ⌊(2q -1)/α⌋α + α -1 by assumption on q. Dividing by α and taking the floor yields the result.

We define HighBits z1 (r) = HighBits(r, 256) and LowBits z1 (r) = LowBits(r, 256).

High and low bits for hint

To produce the hint that we send instead of the lower part of z, we could use the previous bit decomposition. However, as noted in a preliminary version of [DKL + 18, Appendix B], a modification allows to further reduce the entropy of the hint.

We pack the high bits in the range [0, 2(q -1)/α h ). This is possible if we use the range [-α h /2 -2, 0) to represent the integers that are close to 2q -1. Definition 5.2 (High and low bits for hint). Let q be a prime and α h |2(q -1) be a power of two. Let m = 2(q -1)/α h and r ∈ Z. Define r 1 = HighBits(r mod + 2q, α h ) and r 0 = LowBits(r mod + 2q, α h ).

If r 1 = m, let (r ′ 0 , r ′ 1 ) = (r 0 -2, 0). Else, (r ′ 0 , r ′ 1 ) = (r 0 , r 1 ). We define:

(LowBits h (r), HighBits h (r)) = (r ′ 0 , r ′ 1 ).

As before, we extend these definitions to vectors by applying them componentwise. This decomposition lets us recover the original element and we bound its components.

Lemma 5. 3. Let r ∈ Z. Let q be a prime, α h |2(q -1) be a power of two and define m = 2(q -1)/α h . It holds that r = α h • HighBits h (r) + LowBits h (r) mod 2q,

0 , and r ′ 1 defined as in Definition 5. 2. The equality

. By Lemma 5.2, we get the first equality.

The second property stems from the second property in Lemma 5. 2. The modifications to r 0 make r ′ 0 lie in the range [-α h /2 -2, α h /2). The last property stems from the third property in Lemma 5.2 and the fact that if r 1 = m, then we have r ′ 1 = 0.

Design Specifications

This section details all optimisations applied to HAETAE as well as the sampling algorithm used to sample y during signing.

Key Generation

The bimodal rejection sampling relies on having a key pair (A, s) ∈ R k×(k+ℓ) p × R k+ℓ p such that As = -As mod p. To generate such a pair, following [START_REF] Ducas | Lattice signatures and bimodal Gaussians[END_REF], we choose p = 2q and aim at As = qj mod 2q for j = (1, 0, . . . , 0) ⊤ .

Key Generation and Encoding

To build a key pair, we start from an MLWE sample ba = A 0 s 0 + e 0 mod q, where A 0 ← U (R

One sees that As = qj mod 2q. The verification key is comprised of b 1 and the seed that allows generating A 0 and a. The secret key is the seed used to generate s and (A 0 , a).

It remains to choose the decomposition of b, that we see as an nk-dimensional vector with coordinates in [0, q -1]. We choose b 0 with coordinates in {-1, 0, 1} such that if a coordinate of b is odd, then it is rounded to the nearest multiple of 4. We can then write b = b 0 + 2b 1 , where b 1 is encoded using ⌈log 2 (q) -1⌉ bits per coordinate. This is computed coordinate-wise with b 0 = (-1) ⌊b/2⌋ mod 2 b mod 2, i.e. one less bit than b. In all of the following, we let (LowBits vk (b), HighBits vk (b)) denote (b 0 , b 1 ). When b is uniform, we notice that the coordinates of b 0 roughly follow a (centered) binomial law with parameters (2, 1/2), which experimentally leads to smaller choices for β, which we discuss and introduce now.

Fix-point-friendly Bimodal Hyperball Rejection Sampling

Rejected values are highly sensitive data. We adapt rejection sampling in order to make that step easier to mask and implement in constant-time.

Rejection Sampling

A first step towards this goal is to use discrete hyperball samples instead of continuous ones. This allows for a removal of floating-point arithmetic in the rejection step and replace it with an exact computation of the squared norm.

Lemma 5.5 (Bimodal Hyperball Rejection Sampling). Let n be the degree of R, c > 1, r, t, m > 0, and r ′ ≥ √ r 2 + t 2 . Define M = 2(r ′ /r) mn and set

Let p : R m → {0, 1/2, 1} be defined as follows

Then there exists M ′ ≤ cM such that the output distributions of the two algorithms from Figure 5.2 are identical.

-v v The black circles have radii equal to r ′ and the pink circle has radius r. We sample a vector z uniformly inside one of the black circles (with probability 1/2 for each) and keep z if it lies inside the pink circle but not in the blue zone. We reject it if it outside the circle, and keep it with probability 1/2 if it lies in the blue zone.

Discrete Hyperball-uniform Sampling

We first explain how to get continuous hyperball-uniform samples, using a folklore technique which yields such a n-dimensional sample using only n + 2-dimensional continuous Gaussians.

Chapter 6

Fiat-Shamir Signatures

The previous chapters were focused on lattice-based Fiat-Shamir with aborts signatures. In this chapter, we propose an identification scheme based on the same lattice assumptions as before, except that it has an aborting probability of zero. While this was already achieved in previous works (see [START_REF] Agrawal | Round-optimal lattice-based threshold signatures, revisited[END_REF] for example), our work departs from these as this comes at no cost in terms of signature compactness. On the contrary, the asymptotic size of the signature is lower by a factor √ m/ √ log Q s , where m is the dimension of the vector acting as the signature. We describe the scheme in Section 6.1 and show that it can be turned into an unforgeable signature scheme. In Section 6.2, we give concrete parameters for an optimized implementation relying on modules and using the compression techniques from [BG14].

The G + G Identification Protocol

In this section, we first describe the G + G identification protocol, then prove the required properties to compile it into a signature using the Fiat-Shamir heuristic, and then discuss asymptotic parameters.

Description of the Scheme

Let us first introduce the parameters of the scheme as well as some notations. Let m ≥ ℓ > 0, k > m + ℓ and J = J m,ℓ . Let χ be a distribution over Z. Let C ⊆ Z ℓ be the challenge space, which we assume to be finite. Let σ, s ≥ 0 and define Σ :

The scheme is also parametrized by an odd modulus q and an acceptance bound γ.

The G + G identification protocol is described in Figure 6. 1. The instance generation algorithm samples a verification key A ∈ Z m×k 2q and a secret key S ∈ Z k×ℓ with small-magnitude coefficients such that A • S = qJ mod 2q. In the first phase of the interaction, the prover samples a vector y with well-crafted covariance matrix, and sends the commitment w = Ay mod 2q to the verifier. The protocol is public-coin,

Completeness and Commitment Recoverability

We first show that the G + G protocol is complete and commitment recoverable. As a corollary, we obtain that the resulting Fiat-Shamir signature scheme

• s for all S ∈ Z k×ℓ in the range of IGen. Let γ and ε c be such that

Let q > 2γ be an odd modulus. Then the G + G identification protocol is ε c -complete and achieves commitment-recoverability.

Proof. First, we note that AS = qJ mod 2q holds for any matrix pair output by IGen. Then, in order to pass the first verification step, a transcript (w, c, z) must satisfy:

In particular, this implies a commitment w = Az -qJc mod 2q, which is unique, such that (w, c, z) can be a valid transcript, and w is efficiently recoverable, by defining Rec as Rec(A, c, z) := Az -qJc mod 2q. Now, we note that a honestly generated transcript (w, c, z) always satisfies Equation 6. 1. The probability preservation property of the Rényi divergence (Equation 2.2) and Lemma 2.14 then immediately imply that the probability that a honest transcript (w, c, z) be rejected at most

We then obtain the following corollary.

Corollary 6. 3. Using the same assumptions as in Theorem 6.2, the resulting signature scheme

Note that correctness of FS[G + G, H] does not require to assume that H is modeled as a random oracle. As Lemma 2.14 holds without relying on the randomness of c. This is in contrast to Lemma 2.15 that generically considers completeness of signatures obtained using the Fiat-Shamir transform.

Honest-Verifier Zero-Knowledge and Commitment Min-Entropy

We now show that the G + G protocol is HVZK and has large commitment minentropy. As a corollary, we obtain that the signature scheme FS[G + G, H] is EU-CMA-secure provided it is EU-NMA-secure.

Theorem 6. 4. Let m ≥ ℓ > 0, k > m + ℓ, ε ∈ (0, 1/2], s ≥ 8 ln(ℓ -1 + 2ℓ/ε)/π and σ ≥ √ 2σ 1 (S) • s for all S ∈ Z k×ℓ in the range of IGen. Let q > σ • η ε (Z m ) be an odd modulus. Then the G + G identification protocol satisfies:

In addition, its commitment min-entropy is ≥ m • log(sσ 1 (S))/3).

Special Soundness and Lossy Soundness

To complete the analysis, we show that (i) G + G is special-sound, and that (ii) G + G is a lossy identification scheme with lossy-soundness. As a corollary, we obtain that the signature scheme FS[G + G, H] is EU-NMA-secure in the ROM, and in the QROM under some parameters constraint. Theorem 6. 6.

• s for all S ∈ Z k×ℓ in the range of IGen. Let γ > 0 and q > 2γ be an odd modulus. Then the G + G identification protocol is:

• special-sound, under the SIS m,k,q,2γ assumption,

• lossy, under the LWE k-m-ℓ,m,ℓ,χ,q assumption, • ε ls -lossy sound for

Proof. We first prove G + G achieves special soundness, and then explain how to set our identification scheme in lossy mode.

Special soundness. Assume there exists a PPT adversary A which, given the verification key vk = A, produces two valid transcripts (w, c 0 , z 0 ), (w, c 1 , z 1 ) with c 0 ̸ = c 1 .

It can be turned into an SIS m,k,q,2γ solver. Indeed, by definition, such transcripts satisfy A(z 0 -z 1 ) = qJ(c 1 -c 0 ) mod 2q.

Notice that we have A(z 0 -z 1 ) = 0 mod q, which implies that z 0 -z 1 is a solution to the SIS instance defined by A. In addition, when reducing modulo 2, we also have A(z 0 -z 1 ) = J(c 1 -c 0 ) mod 2, which implies that z 0 ̸ = z 1 . Finally, note that the condition on γ implies that ∥z 0 -z 1 ∥ ≤ 2γ (as transcript validity implies ∥z∥ ≤ γ), and that z 0 -z 1 ̸ = 0 mod q.

Hence, there exists an adversary B against the SIS m,k,q,2γ problem such that:

Let us now focus on lossy-soundness. We first define a lossy key generation algorithm, and then argue about lossy-soundness.

Lossiness. The lossy key generation algorithm LossyIGen only modifies the generation of B. Let us recall that in IGen, the latter is defined as

. The lossy key generation algorithm LossyIGen samples it as B ← U (Z m×ℓ q ). Lossy verification keys are computationally indistinguishable from non-lossy ones, under the LWE k-m-ℓ,m,ℓ,η,q assumption. ε ls -lossy Soundness. First note that, if the lossy verification key A is such that, for all commitment w, there exists at most one challenge c such that there exists z with (w, c, z) passing verification, then, as the challenge is sampled uniformly and independently of w, an (unbounded) prover cannot pass verification, except with probability at most 1/|C|.

We focus on proving that the above holds with overwhelming probability over the choice of the lossy key A. By contradiction, assume there exists w, c 0 , c 1 , z 0 , z 1 with ∥z 0 ∥, ∥z 1 ∥ ≤ γ and c 0 ̸ = c 1 ∈ C, such that we have both Az 0 = w+qJc 0 mod 2q and Az 1 = w + qJc 1 mod 2q. Then, we have:

Recall that A is of the form (qJ -2B|2A 1 |2I m ), with A 1 , B uniform over Z q . Hence, the matrix A mod q is of the form (B|A 1 |I m ), since q is odd. Then the above implies that (B|A 1 |I m )(z 0 -z 1 ) = 0 mod q with z 0 -z 1 ̸ = 0 mod q. This happens with probability at most 1/q m .

To conclude, note that there are at most (2γ + 1) 2k • |C| 2 choices for z 0 , z 1 , c 0 and c 1 . A union bound therefore implies that the probability over A that there is a commitment with at least two challenges permitting valid transcripts is at most |C| 2 (2γ + 1) 2k /q m . Our lossy identification scheme is then ε ls -lossy-sound, with

which completes the proof of the theorem.

We then obtain the following corollary as an application of Lemma 2.19.

Corollary 6.7. Using the same assumptions as in Theorem 6.6, the resulting signature scheme FS[G + G, H] is EU-NMA-secure, in the ROM.

We also obtain the following corollary as an application of Theorem 2.17.

Corollary 6.8. Using the same assumptions as in Theorem 6.6, and if ε ls is negligible, the signature scheme FS[G + G, H] is EU-NMA-secure, in the QROM.

To conclude this section, we introduce an additional assumption of a similar flavour as the SelfTargetMSIS assumption [START_REF] Kiltz | A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model[END_REF], which allows to directly prove EU-NMA-security of FS[G + G, H] in the QROM as it is (up to LWE) the EU-NMA security game of the resulting signature. As for SelfTargetMSIS, this problem can be related in the ROM to SIS, using the special soundness property of the scheme. Definition 6.1 (GpGSelfTargetSIS). Let m ≥ ℓ > 0, k > m+ℓ. Let γ > 0 and q > 2γ be an odd modulus. The GpGSelfTargetSIS m,k,ℓ,γ,q assumption states that given a matrix

) and B ← U (Z m×ℓ q ), and oracle access to a hash function H, it is computationally hard to find c ∈ C, z ∈ Z k and µ ∈ {0, 1} ⋆ such that H(Az-qJc, µ) = c and ∥z∥ ≤ γ.

Asymptotic Parameters Analysis

Our analysis above is applicable to the following instantiation of parameters, as a function of the security parameter λ and the number of signature queries Q S . We assume Q S to be a large polynomial in λ. We consider k, ℓ, m linear in λ. We set χ as D Z, √ k with tail-cutting to get samples in {-k, . . . , 0, . . . , k} with overwhelming probability. We let ε = 1/Q s .

We make the security of the G + G scheme rely on the following two assumptions. First, the LWE m-k-ℓ,k,ℓ,q,χ assumption, where √ k = αq. This LWE parametrization is compatible with the reduction from worst-case lattice problems from [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. controlling the upper bound on the smoothing parameter of the secret lattice.

Sign: Instead of computing z = y + (2u + c)s, we compute z = y + (ζu + c)s. Still, as As = j mod 2q, we have ζAs = 0 mod 2q by definition of j. Thus, the identity Az -qcj = Ay mod 2q still holds. The main advantage of this modification is that the secret lattice is now ζsR instead of 2sR, whose smoothing parameter is a factor √ 2 smaller.

Verify: The verification bound is set to γ = 1.01 • √ nkσ, and the signer may verify that its signature is accepted before outputting it, up to restarting in the somewhat rare event that it is not.

Concrete Parameters

We now give concrete parameters and estimates of the public key and signature sizes resulting from these optimizations in Table 6. 1. This gives rise to the following estimates. We note that the compression techniques from Chapter 5 can be used in this setting too. Namely, the high and low bits decomposition from Section 5. 1.2, which increases the verification to γ = 1.01 • √ nkσ + √ nm(1 + α/4), as well as the rANS technique described in Section 5.2. 4.

For comparison, we include in Table 6.1 a reminder on estimated sizes of optimized Lyubashevsky signatures from Table 4. 3. As far as we are aware of, these

List of Figures

List of Tables