Cryptology ePrint Archive: Report 2008/357

A protocol for K-multiple substring matching

Vadym Fedyukovych and Vitaliy Sharapov

Abstract: A protocol is introduced to show $K$ copies of a pattern string are embedded is a host string. Commitments to both strings, and to offsets of copies of the pattern in the host is input of Verifier. Protocol does not leak useful information about strings, and is zero knowledge.

Category / Keywords: cryptographic protocols / Substring matching, argument protocol, Schwartz-Zippel lemma, zero knowledge

Publication Info: Extended abstract of ITaS'08 report.

Date: received 17 Aug 2008

Contact author: vf at unity net

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20080818:184719 (All versions of this report)

Discussion forum: Show discussion | Start new discussion