Compression et décompression inconscientes de chiffrés à l'aide de codes linéaires

La compression et la décompression inconscientes de chiffrés consistent à passer d'un vecteur dense chiffré de longueur n avec ≤ t entrées non nulles à une représentation compacte chiffrée du vecteur, et vice-versa. Ces primitives interviennent dans des protocoles efficaces de recherche chiffrée, de récupération d'informations privées (Private Information Retrieval), ou de récupération inconsciente de messages (Oblivious Message Retrieval). Les schémas existants soit ne compressent pas suffisamment le vecteur, soit nécessitent des coûts de calcul élevés. Nous donnons un cadre général basé sur les codes linéaires pour obtenir
des schémas déterministes et parfaitement corrects. En choisissant soigneusement les codes utilisés, nous obtenons une compression optimale et des temps de compression et décompression quasi-linéaires. Un élément central de notre travail consiste à montrer que, pour des codes Reed-Solomon généralisés soigneusement choisis, des variantes d'algorithmes de décodage classiques combinées à des techniques algébriques efficaces permettent de récupérer le vecteur d'erreur
directement à partir du syndrome en un temps quasi linéaire par rapport à la longueur du syndrome, plutôt que par rapport à la longueur totale du bloc du code.