Using pen strokes with fuzzy tolerance algorithm as encryption key

Question

How can I encrypt/decrypt with fuzzy tolerance?

I want to be able to use a Stroke on an InkCanvas as key for my encryption but when decrypting again the user should not have to draw the exact same symbol, only similar. Can this be done in .NET C#?

--- Update (9 sep) ---

What I ideally want is an encryption algorithm that would accept any key in a certain range of keys based on some base-key and a function defining the allowed differences ..

Im doing all encryption/decryption locally so I wont need to send anything over a wire safely. And I dont want to store the key used for encryption, so I wont have anything to compare with. I could come up with some method to generate the same key for every similar stroke but its not easy if a want to accept any kind of symbol (not only letters). The other option is if the encryption key somehow could accept similar keys by design, which I dont know if its possible...?

Answer 1

OK. Let's break your problem into two.

1) Fuzzy 2) Encryption

Reality is both these concepts are relatively old and their implementation have been out there for years. Each deals with the problem at hand very well but this does not mean that combining these two is a good idea. I believe you have to have your solution as a two-stage approach.

First of all encryption standards out there are great in securing the data using a SINGLE EXACT key. In your case you need symmetric encryption algos such as AES or Rijndael.

Fuzzy part of the solution is also not that hard. Like any other fuzzy recognition technique, you need to do a feature extraction and create a vector to be passed to the encryption algo. You need to build fuzziness into your features. For example, number of strokes, quadrant of the start point for each stroke, a factor of curviness for each stroke and the like. This will be enough to build a 32 bit vector to pass to the encryption algorithm.

UPDATE

I will try to make it more illustrative:

2 bits for number of strokes: 1, 2, 3, +3 which translates to 00, 01, 10 and 11

2 bits for quadrant of the start of the first stroke: TopLeft, TopRight, BottomLeft, BottomRightt encodes to 00, 01, 10 and 11

2 bits for quadrant of the end of the first stroke: ditto

2 bits for quadrant of the start of the second stroke: ditto. If no second stroke then 00.

2 bits for quadrant of the end of the second stroke: ditto. If no second stroke then 00.

2 bits for quadrant of the start of the third stroke: ditto. If no third stroke then 00.

2 bits for quadrant of the end of the second stroke: ditto. If no third stroke then 00.

2 bits for curviness of the first stroke: straight->00 ... Nice round->11. This is not going to be very easy and you might reduce the degrees of curviness to 2 and use just one bit but it is a "suck it and see".

So this is 16 bits. You can leave the rest as zero for now and try and see how it works.

Hope this helps.

Answer 2

There are a number of encryption schemes that allow fuzzy secrets. Frequently, these schemes are developed to protect secrets with biometric information (i.e. fingerprints, retina scans), but the underlying schemes are more generally applicable. One example for such a scheme is a fuzzy vault scheme proposed by Juels and Sudan.