What is the complexity of "Crypt Kicker"?

Question

I am thinking about crypt kicker problem. I think I can solve it by brute-force trying all permutations of the letters (perhaps with some optimizations). However the worst-case complexity of this solutions looks like O(permutations of alphabet * number of words).

Is it correct? Is there a solution with less complexity in the worst case?

score 3 · Accepted Answer · answered Dec 03 '11 at 17:30

Here's a formal proof of NP-hardness of Crypt Kicker with a k-letter alphabet, by reduction from 3-dimensional matching.

For each input triple (x, y, z), put the word xyz in the dictionary. To determine whether there exists a matching of size n, request a decryption of an n-word ciphertext abc def ghi … . Clearly this reduction is poly-time. If there exists a 3-d matching (x₁, y₁, z₁), …, (x_n, y_n, z_n), then the permutation x₁→a, y₁→b, z₁→c, x₂→d, … witnesses the existence of a valid decryption. Conversely, if there exists a valid decryption permutation π, then we recover a 3-d matching (π(a), π(b), π(c)), (π(d), π(e), π(f)), … .

score 1 · Answer 2 · edited May 23 '17 at 12:07

You can solve any crypto problem by brute force, the issue is the amount of time it takes to solve. So with polyalphabetic ciphers you want to rely on the Kasiski method, which is essentially a divide and concur methodology. What you need to do is convert the ciphertext into X number of monoalphabetic ciphers. Based on the link in your question this is the significant portion:

Sample Input 6
and
dick
jane
puff
spot
yertle

bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn

If this is the case it is at most 26 permutations. Without seeing more permutations it is difficult to provide any other information. Are there any other sample input/output pairs you are aware of?

To answer your actual question about complexity I will use approximate big oh as reference

So first we look at the encrypt method:

function encrypt(Text textToEncrypt, Alphabet substitutionAlphabet)  
{  
     Alphabet textAlphabet = textToEncrypt.getAlphabet(); //O(1) should be a constant look up to get your own property  
      for(character current : textToEncrypt) //O(N) must touch all elements
      {  
         current = substitutionAlphabet.lookupChange(current, textAlphabet); //O(N) worst case map lookup
      }        
}

So it seems the encrypt function is O(N) worst case scenario, my implementation is quite contrived. And decrypt should be the same just in reverse so that would also yield O(N).

score 1 · Answer 3 · answered Dec 03 '11 at 17:01

I think there will always be some pathological cases that require backtracking.

Here is a technique that at first appears to make things easier: look for patterns of repeated letters within words. If you know the word "banana" then "xzyzyz" suggests x = b, z = a , y = n. But this technique also allows you to construct a dictionary that marks words which have banana-like suffixes, allowing you to force particular possible solutions for prefixes. For instance, the dictionary entries ADFbanana, BCFbanana, BDEbanana, in conjunction with the word PRSbanana require the user to choose P = A or B, R = C or D, S = E or F, such that exactly one of these mappings is to the first of the two possibilities.

Given these building blocks, I think you could take a boolean equation of the form (A|B|~C) & (D|~E|F) &... and encode it as a substitution problem, such that a solution to the substitution problem would produce an assignment of T/F to the variables making the equation produce true => if you could solve the substitution problem you could solve SAT => it is NP-Complete.

What is the complexity of "Crypt Kicker"?

3 Answers3