Which functions can be used as Pseudo Random functions? Can block Ciphers be used for this purpose with our own encryption function?

Since the cloud security algorithm I am trying to implement says that for a PRF, any secure encryption algorithm or a keyed hash function can be used. The security parameter I have chosen is 15 bits while AES and SHA use a large key size than this. So which block cipher and encyption function should I use for a PRF?

• if your security parameter / key size is 15 bit long, your scheme is completely broken whatever the underlying cipher. – Geoffroy Couteau Apr 20 at 12:33
• Increasing key size would affect the computation overhead. What should be the least value of security parameter then? – Syeda Apr 20 at 12:49
• bruteforcing a 15 bit key takes perhaps milliseconds on a standard computer. Anything below 60 bits can be bruteforced in a small amount of time without investing enormous resources. 80 bits seems the bare minimum, you can perhaps go for 64 bits if you have very strong efficiency constraints, and if adversaries are very unlikely to want badly to break your scheme. But remember that even if you go for 64 bits, it can still clearly be broken by a real world adversary who is motivated to invest some time and resources in it. – Geoffroy Couteau Apr 20 at 12:53
• As a businessman, I would find it extremely difficult to promote and sell a new cloud service secured by 80 bit keys. Perception is everything in marketing. AES is not 80 bits and that will become a promotional nightmare. Your marketing 'adversary' will simply ask "Why are the keys so small?" And you'll have no crypto credible reply. You won't convincingly justify it by saying your kit is too small. AES is almost de rigueur and can squeeze into surprisingly small spaces. – Paul Uszak Apr 20 at 13:54
• I will try to write a more detailed and useful response later this weekend, but to add to the remark of Paul Uszak: key size is also not everything that matters regarding efficiency. The underlying design, and the hardware on which the block cipher is run, is of core importance - and in this respect, it is often the case that AES is more efficient than existing alternatives even when they have smaller key size. – Geoffroy Couteau Apr 20 at 14:16

Let $$f\colon \{0,1\}^b \to \{0,1\}^b$$ be a uniform random function, and $$\pi\colon \{0,1\}^b \to \{0,1\}^b$$ be a uniform random permutation. If $$A(\mathcal O)$$ is a random decision algorithm making $$q$$ queries to the oracle $$\mathcal O$$, then $$\Pr[A(\pi)] \leq \delta \cdot \Pr[A(f)], \quad \text{where} \quad \delta = (1 - (q - 1)/2^b)^{-q/2};$$ or, as more commonly but less tightly stated, $$\Pr[A(\pi)] \leq \Pr[A(f)] + \binom q 2 2^{-b}.$$ Consequently, if $$A$$ is a random decision algorithm with advantage $$\operatorname{Adv}^{\operatorname{PRP}}_{\operatorname{AES}}(A)$$ at distinguishing AES from a uniform random permutation, then $$\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{AES}}(A) \leq \delta \cdot \operatorname{Adv}^{\operatorname{PRP}}_{\operatorname{AES}}(A),$$ or $$\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{AES}}(A) \leq \operatorname{Adv}^{\operatorname{PRP}}_{\operatorname{AES}}(A) + \binom q 2 2^{-b}.$$ This is the PRF/PRP-switching lemma, and it shows that any good pseudorandom permutation is a nearly-as-good pseudorandom function, up to the birthday bound.