4
$\begingroup$

I'm reading patent application US 20120278897 A1 — “System and method of sort-order preserving tokenization”. Near the bottom they describe their token generation algorithm, which basically involves using the first few characters of a string as input to a modified order preserving Ziv-Lempel compression function described in this patent. They then prepend the output to the token and treat it as a kind of 'sort prefix' which can enable sorting.

I would like to know what (if any) security can be guaranteed for the characters of the plaintext used to generate the 'sort prefix'. More generally, how difficult is it for an adversary to distinguish two strings which have been Ziv-Lempel encoded but not encrypted?

The patent application makes this statement:

An attacker may still be able to determine the first character with some level of certainty, but since they would no longer have all of the characters encoded within the Ziv-Lempel tree, the token is no longer susceptible to a dictionary attack

Given enough samples of this compression function is it possible for an attacker to partially reconstruct the tree and guess the input for an arbitrary output value?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Can you give a self-contained description of the algorithm here? (Reading patents is absolutely miserable.) $\endgroup$
    – D.W.
    Aug 28, 2013 at 5:05
  • $\begingroup$ I'll make an edit later today; I'm trying now to see if I can answer my own question. $\endgroup$
    – pg1989
    Aug 28, 2013 at 18:20
  • 1
    $\begingroup$ Distinguishing two strings seems trivial for an adversary. If the encodings are the same then they are the same and if different then different. Also the "sort prefix" enables one to work out the orderings of the encoded values. If some corresponding decoded values are known then bounds can be put on the unknown decoded strings. So then one can guess the input values. This seems obvious enough from a cursory reading of the patent and seems to answer the question. $\endgroup$
    – Barack Obama
    Sep 16, 2014 at 23:26

1 Answer 1

Reset to default
1
$\begingroup$

Ziv-Lempel is a data compression algorithm, so in general it doesn't protect your data. As for your question:

More generally, how difficult is it for an adversary to distinguish two strings which have been Ziv-Lempel encoded but not encrypted?

An adversary just can decode two strings and compare them. Due to the fact that Ziv-Lempel is an encoding algorithm, if you send your data to somebody then you have to send the other information needed to decode your data by the receiver. So, in this case an attacker can easily get access to the transmitted data.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Actually, I believe that the patent does try to set up the Ziv-Lempel compressor in a key-dependent state (I believe by feeding it key-depending text before starting the real compression), and so it isn't quite so simple; still, it doesn't look at all difficult. $\endgroup$
    – poncho
    Mar 9, 2014 at 18:24
  • 2
    $\begingroup$ Sometimes, I would be really happy if people would read referenced papers and patent documentation before posting generalized answers that simply miss the point of the question… this may be an answer, but it’s absolutely irrelevant because it ignores the linked patent. $\endgroup$
    – e-sushi
    May 8, 2014 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.