Efficient and secure generalized pattern matching via fast fourier transform

Damien Vergnaud 1
1 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : We present simple protocols for secure two-party computation of generalized pattern matching in the presence of malicious parties. The problem is to determine all positions in a text T where a pattern P occurs (or matches with few mismatches) allowing possibly both T and P to contain single character wildcards. We propose constant-round protocols that exhibit linear communication and quasilinear computational costs with simulation-based security. Our constructions rely on a well-known technique for pattern matching proposed by Fischer and Paterson in 1974 and based on the Fast Fourier Transform. The security of the new schemes is reduced to the semantic security of the ElGamal encryption scheme.
Type de document :
Communication dans un congrès
Abderrahmane Nitaj; David Pointcheval. AFRICACRYPT'11 - Proceedings of the 4th international conference on Progress in cryptology in Africa, Jul 2011, Dakar, Senegal. Springer, 6737, pp.41-58, LNCS - Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/hal-01110047
Contributeur : Brigitte Briot <>
Soumis le : mardi 27 janvier 2015 - 13:56:59
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Identifiants

  • HAL Id : hal-01110047, version 1

Collections

Relations

Citation

Damien Vergnaud. Efficient and secure generalized pattern matching via fast fourier transform. Abderrahmane Nitaj; David Pointcheval. AFRICACRYPT'11 - Proceedings of the 4th international conference on Progress in cryptology in Africa, Jul 2011, Dakar, Senegal. Springer, 6737, pp.41-58, LNCS - Lecture Notes in Computer Science. 〈hal-01110047〉

Partager

Métriques

Consultations de la notice

188