Finding a secret cipher given the key and known plaintext?

Let $x,y,k$ be plain text, cipher text and key respectively. Also suppose $\operatorname{Enc}$ is the algorithm of encryption for block cipher with size $n$. So we have $$\operatorname{Enc}_k(x)=y$$

We know that if $x,y$ are given finding $k$ for big $n$ is so hard. Now we change the problem:

Let $k$(with size $l$) be given and $\operatorname{Enc}$ secret. We want to find the function for $\operatorname{Enc}$. At least how many $(x,y)$ are needed to find $\operatorname{Enc}$?

• Hint: assume $\operatorname{Enc}_k(x)$ is defined as $\operatorname{AES-128}_{k\oplus c}(x)$ for some unknown 128-bit constant $c$. – fgrieu Jan 26 '16 at 21:13
• @fgrieu, key is constant and I know it. Algorithm of encrypting is unknown. What is relation between your comment and my question? – Meysam Ghahramani Jan 27 '16 at 17:28
• The function that I propose is a partially unknown function, since you do not know $c$. Hence if one could solve your problem in general, (s)he could find the constant $c$ in my function. – fgrieu Jan 27 '16 at 19:11

As fgrieu hints at in the comments, it is not in general possible to find $\operatorname{Enc}$. Otherwise you would be able to break an arbitrary block cipher, because the key of any block cipher can be cast as part of the algorithm instead.
Even if you ignore the computational cost, there is no way to find $\operatorname{Enc}$ given values for only one $k$, even if you know all pairs $x, y$ for that key. There is of course a limited number of (distinct) $n$-bit block ciphers with $l$-bit keys, but the different keys can be completely independent.
For example, I could define AES' which works just like AES, except with the key value $42$ it performs the identity permutation instead. You could not know that difference from observing the outputs for any other keys.