Computationaly hard detokenization algorithm for credit card numbers I am designing a vault that tokenizes credit card numbers (a plaintext that consists of 16 decimal digits), with the following requirements:


Given some plaintext, the vault returns an index.
   If the plaintext does not exist it returns a new index.
   If it does exist it returns the same index it had returned before for that plaintext.
The vault allows detokenization (given index return the plaintext),
   however this is quite rare (once a month) and involves authentication procedure.
The vault stores the plaintext encrypted using an algorithm so that detokenization 
   of one index is computationally possible but hard.
   Let the costs of detokenization be X per entry.
An attacker that got access to the vault should find it too computationally expensive 
   to detokenize the entire vault. 
A variation: the attacker may have access to a limited list of (index, plaintext)
   pairs that they injected into the vault before they compromised it.
   Let the length of this list be Y.


What is the encryption algorithm that should be used for this use case? Can it be designed so that X is configurable (given Y=0)? Can detokenizing the entire vault be computationally hard regardless of Y, or must we assume Y = 0?

Edit:

I've modified the original question. Instead of tokenizing a 6 decimal digit plaintext, the question is now about tokenizing a 16 decimal digit credit card number.

Both a legitimate user and a very skilled attacker has access to partial credit card numbers. A partial credit card number consists of the first 6 plaintext digits, the last 4 plaintext digits, and the index received from the vault. In order to find the remaining middle 6 digits the legitimate user would authenticate and detokenize, while the skilled attacker would have three options:


Perform a limited number of tokenizing operations without compromizing the vault.
Compromise the vault and perform 50,000 tokenizing operations per plaintext. 
Compromise the vault and perform one detokenization per plaintext. 


Additional information:


Many credit cards share the same first 6 digits.
Werther the plaintext is the complete 16 digits number or only the middle 6 digit number is part of the design. 
The index length is part of the design
Once the vault is compromised the attacker has access to the vault storage/memory which contains everything except one-time keys that were properly erased. The same attacker has also compromised the detokenizer's private key stored elsewhere if there are such keys.


Edit 2:


Removed the requirement that the index is random. It just need not to be some hash of the plaintext to avoid brute forcing the index without compromizing the vault.
Changed brute force tokenization per plaintext from 100,000 to 50,000 
Obviously the plaintext could be encrypted with a public key, and assume that only the authorized detokenizer has the private key. Alas, if a skilled attacker has enough resources to compromise the vault (by hacking into the vault machine) , the attacker has enough resources to compromise the private key (by hacking into the machine containing the private key).
 Assuming the hack is discovered in timely fashion, the cards would be canceled before the hacker sold the Cards in the black market. 
 For that purpose, the detokenization of the entire vault must be so hard that it would delay the attacker for a long time, or would require vast amounts of compute resource to make it non-economical in the first place.
It is expected to make the tokenization computationally hard - so 50,000 tokenization operations per credit card number would be non-economical or would take too long (configurable)
It is expected to make the detokenization computationally harder than 1 and less than 50,000 tokenization operations (configurable).
I am assuming that the vault shall store arbitrary-length messages and associate with each message a token consisting of six decimal digits. Otherwise, as has been noted (see below), the problem is probably either impossible or trivial.

I interpret your requirements to mean that the detokenization algorithm is also available to an attacker that has gotten access to the vault, which means that the cost of detokenizing the entire vault is at most $nX$, where $n$ is the number of items stored in the vault and $X$ is the cost of detokenizing one index.

This means that the best you can do is to balance your $X$ such that $X$ is feasible, but $nX$ is economically infeasible. (Note that $n$ is very small, so it seems unlikely that $X$ cost can be feasible for you, but $nX$ cost infeasible for an attacker.)

(Note that if the vault's detokenization algorithm is not available to the attacker, your problem has a very simple solution using deterministic public key encryption: Encrypt the message using the detokenizer's public key. If you already have the ciphertext, you're done. Otherwise, pick a fresh index and store the index-ciphertext pair. The detokenizer simply decrypts the ciphertext. This is the best you can do unless the vault's tokenization algorithm also isn't available to the attacker, in which case everything is trivial.)

The system consists of an interactive algorithm $V$ and an algorithm $D$. The correctness requirement can then be stated as follows:


We can send $m$ to $V$, in which case $V$ responds with an integer $i$. As long as $V$ has been sent less than $10^6$ distinct messages, the following requirement is satisfied: For any $m'$ previously sent to $V$ to which $V$ replied with $i'$, then $i=i'$ if and only if $m=m'$.
We can send $i$ to $V$, in which case $V$ responds with $z$ or $\bot$. The response satisfies the following requirement: If $V$ previously replied with $i$ when sent message $m$, then $D$ will output $m$ on input of $z$, using expected time $X$.
We can send compromise to $V$, in which case $V$ responds with any secret keys it may have and a list $(i_1, z_1), (i_2, z_2), \dots, (i_n, z_n)$. If $V$ was sent the messages $m_1, m_2, \dots, m_k$ with replies $j_1,j_2, \dots, j_k$, then $k=n$, $i_1=j_1$, ..., $i_n=j_n$, and $D(z_i) = m_1$, $D(z_2) = m_2$, ..., $D(z_n) = m_n$.


The security requirement is the following:


If $V$ has been sent $n$ distinct messages, of which $k$ have been sent by the attacker (or can be predicted with reasonable effort) and the remaining $n-k$ are unpredictable to the attacker, then no adversary sending compromise to $V$ can recover the remaining $n-k$ messages with expected cost significantly smaller than $(n-k)X$.


The following scheme seems to satisfy these requirements. We need


a hash function $H$ (modeled as a random oracle),
a deterministic one-time symmetric encryption scheme $(\mathcal{E}, \mathcal{D})$, and
a large family of groups $\mathcal{G}$ such that we can efficiently sample a group $G$, a generator $g$ and a verifiably random element $y$ in the subgroup generated by $g$, such that $(G,g)$ are suitable for ElGamal encryption, and the best algorithm for computing logarithms smaller than $T$ in $G$ requires expected cost $\sqrt{T}$. (All reasonable assumptions.)


The interactive algorithm $V$ stores a list of tuples $(i, c, G, g, y, x, w)$:


On input of $m$ to $V$, let $K = H(m)$ and $c = \mathcal{E}(K,m)$. If $(i,c,-,-,-,-,-)$ is stored, respond with $i$ and stop. Otherwise sample fresh $i$. Sample $G$ from $\mathcal{G}$ as well as $g,y$, then choose random $r &lt; X^2$. Compute $x = g^r$, $w=y^r K$. Store $(i, c, G, g, y, x, w)$.
On input of $i$ to $V$, if $(i, c, x, w)$ is stored, respond with $z = (c, G, g, y, x, w)$.
On input of compromise, respond with the entire list of tuples.


The algorithm $D$ on input of $(c, G, g, y, x, w)$ does:


Compute the discrete logarithm of $x$ to the base $g$. (Expected cost $X$.)
Compute $K = w y^{-r}$.
Compute $m = \mathcal{D}(K, c)$.
(Optional) Verify that $H(m) = K$.


This scheme is correct, and a five-minute analysis suggests that it also satisfies the security requirement. The only minor subtlety in the scheme is that every entry must have a fresh group, otherwise algorithms for computing many discrete logarithms in one group could allow the adversary to decrypt with expected time smaller than $(n-k)X$.

I would not actually use this scheme without a proper security analysis.

A few minor notes: The families of groups can be either based on finite fields or elliptic curves, where the latter would probably involve point counting and therefore be moderately expensive. In either case, naïve ElGamal is probably not the right scheme to use, some variant of DHIES or ECIES or something would be better.

You can make tokenization cost $T$ work as follows: Let $K' = H(m)$. Use $K'$ to generate an elliptic curve of prime order $\approx T^2$ and two verifiably random points $P$ and $Q$ on the curve. Compute the discrete logarithm $U = \log_P Q$. Then let $K = H(m,U)$. Another (simpler) option (as was pointed out in another answer) is to simply use an expensive hash function such as PBKDF2 or scrypt with appropriate parameters.