Modulated string searching Apostolico, Alberto; Erdős, Péter L.; Miklós, István ...
Theoretical computer science,
03/2014, Letnik:
525
Journal Article
Recenzirano
Odprti dostop
In his 1987 paper entitled Generalized String Matching Abrahamson introduced the concept of pattern matching with character classes and provided the first efficient algorithm to solve this problem. ...The best known solution to date is due to Linhart and Shamir (2009).
Another broad yet comparatively less intensively studied class of string matching problems is numerical string searching, such as for instance “less-than” or L1-norm string searching. The best known solutions for problems in this class are based on FFT convolution after some suitable re-encoding.
The present paper introduces modulated string searching as a unified framework for string matching problems where the numerical conditions can be combined with some Boolean/numerical decision conditions on the character classes. One example problem in this class is the locally boundedL1-norm matching problem with parameters b and τ: here the pattern “matches” a text of same length if their L1-distance is at most b and if furthermore there is no position where the text element and pattern element differ by more than the local bound τ. A more general setup is that where the pattern positions contain character classes and/or each position has its own private local bound. While the first variant can clearly be handled by adaptation of the classic FFT method, the second one is far too complicated for this treatment. The algorithm we propose in this paper can solve all such problems efficiently.
The proposed framework contains two nested procedures. The first one, based on Karatsuba's fast multiplication algorithm, solves pattern matching with character classes within time O(nm0.585), where n and m are the text and pattern length respectively (under some reasonable conventions). This is slightly better than the complexity of Abrahamson's algorithm for generalized string matching but worse than algorithms based on FFT. The second procedure, which works as a plug-in within the first one and is tailored to the specific problem variant at hand, solves the numerical and/or Boolean matching problem with high efficiency. Some of the previously known constructions can be adapted to match or outperform several (but not all) problem variations handled by the construction proposed here. The latter aims to be a general tool that provides a unified solution for all problems of this kind.
•A new class of complex string matching.•The fit may depend on the string elements and on their positions within the pattern.•Common generalization of Abrahamson's “Generalized String Matching” and several numerical kind matching problems.•The method is based on Karatsuba's fast multiplication algorithm.
Simple power attack (SPA) is a type of side-channel attack (SCA). In the literature, many SPA-resistant scalar multiplication algorithms have been proposed, but most are inefficient and not ...interoperable with other coding methods. To prevent SPA, Chevallier-Mames et al. proposed a technique called side-channel atomicity for pure binary number systems. Using their method, extra costs for preventing SPA can be limited. Even though many researchers have extended this technique to other number systems, their algorithms are for specific cases and few provide implementation results. In this paper, we generalize the atomicity technique to protect nearly all existing fast coding methods/number systems. Our general framework provides security and flexibility while its efficiency is coupled to that of the coding methods. Moreover, we utilize our framework to protect the known fastest scalar multiplications by exploring application on the GLV method for GLS curves. Proof of concept programs are written in the C language along with assembly for fast field operations and run on AMD Athlon X2 245-based hardware.
PDF
