B. Adversary, When the latter makes an RKFn-query (?, x), adversary B responds via y ? KT Fn (?, x) Return y where Fn is B's own oracle. When A halts, B halts with the same output

B. Adversary, When the latter makes an RKFn-query (?, x), adversary B responds via If x ? S then y $ ? R Else y ? KT Fn (?, x) Return y where Fn is B's own oracle. When A halts with output b

. Finally, instead of using the key-transformer KT to compute M (?(K), ·) via oracle calls to M (K, ·), we use M directly. The correctness property of the key transformer implies that Pr

N. *. Application, 1 to NR * to prove that the construction given in Section 4 is a ? aff -RKA-secure PRF. Note that this gives an alternative proof of Theorem 4.5. Let S = {0, 1} n \ ({? 1 , . . . , ? n } ? {0 n }) The only point that remains to prove is that there exists an S-uniform key-transformer KT ? aff for NR * and the class ? aff of RKD functions. This result is actually implied by Lemma 4.3. Indeed, the same key-transformer is an S-uniform key-transformer for (NR * , ? aff ) This statement is implied by the fact that games G 0 and G n?1 , defined in the proof References [BC10a] Mihir Bellare and David Cash. Pseudorandom functions and permutations provably secure against related-key attacks, LNCS, vol.5, issue.35, pp.666-684, 2008.

M. Bellare and D. Cash, Pseudorandom functions and permutations provably secure against related-key attacks. Cryptology ePrint Archive, 2010.
DOI : 10.1007/978-3-642-14623-7_36
URL : https://link.springer.com/content/pdf/10.1007%2F978-3-642-14623-7_36.pdf

M. Bellare, D. Cash, and R. Miller, Cryptography Secure against Related-Key Attacks and Tampering, ASIACRYPT 2011, pp.486-503, 2011.
DOI : 10.1007/978-3-642-25385-0_26
URL : https://link.springer.com/content/pdf/10.1007%2F978-3-642-25385-0_26.pdf

E. Biham, O. Dunkelman, and N. Keller, Related-Key Boomerang and Rectangle Attacks, LNCS, vol.3494, pp.507-525, 2005.
DOI : 10.1007/11426639_30
URL : https://link.springer.com/content/pdf/10.1007%2F11426639_30.pdf

E. Biham, O. Dunkelman, and N. Keller, A Unified Approach to Related-Key Attacks, LNCS, vol.5086, pp.73-96, 2008.
DOI : 10.1007/978-3-540-71039-4_5
URL : https://link.springer.com/content/pdf/10.1007%2F978-3-540-71039-4_5.pdf

A. Biryukov, O. Dunkelman, N. Keller, D. Khovratovich, and A. Shamir, Key Recovery Attacks of Practical Complexity on AES-256 Variants with up to 10 Rounds, LNCS, vol.6110, pp.299-319, 2010.
DOI : 10.1007/978-3-642-13190-5_15
URL : https://link.springer.com/content/pdf/10.1007%2F978-3-642-13190-5_15.pdf

E. Biham, New types of cryptoanalytic attacks using related keys (extended abstract), EUROCRYPT'93, pp.398-409, 1994.
DOI : 10.1007/3-540-48285-7_34
URL : https://link.springer.com/content/pdf/10.1007%2F3-540-48285-7_34.pdf

M. Bellare and T. Kohno, A Theoretical Treatment of Related-Key Attacks: RKA-PRPs, RKA-PRFs, and Applications, LNCS, vol.2656, pp.491-506, 2003.
DOI : 10.1007/3-540-39200-9_31
URL : http://www.cs.ucsd.edu/~mihir/papers/rka.pdf

A. Biryukov and D. Khovratovich, Related-Key Cryptanalysis of the Full AES-192 and AES-256, LNCS, vol.5912, pp.1-18, 2009.
DOI : 10.1007/978-3-642-10366-7_1
URL : https://link.springer.com/content/pdf/10.1007%2F978-3-642-10366-7_1.pdf

A. Biryukov, D. Khovratovich, and I. Nikolic, Distinguisher and Related-Key Attack on the Full AES-256, LNCS, vol.5677, pp.231-249, 2009.
DOI : 10.1007/978-3-642-03356-8_14
URL : https://link.springer.com/content/pdf/10.1007%2F978-3-642-03356-8_14.pdf

D. Boneh, K. Lewi, H. W. Montgomery, and A. Raghunathan, Key Homomorphic PRFs and Their Applications, CRYPTO 2013, pp.410-428, 2013.
DOI : 10.1007/978-3-642-40041-4_23
URL : http://crypto.stanford.edu/~klewi/papers/homprf-full.pdf

A. Banerjee and C. Peikert, New and Improved Key-Homomorphic Pseudorandom Functions, CRYPTO 2014, Part I, pp.353-370, 2014.
DOI : 10.1007/978-3-662-44371-2_20

M. Bellare, K. G. Paterson, and S. Thomson, RKA Security beyond the Linear Barrier: IBE, Encryption and Signatures, ASIACRYPT 2012, pp.331-348, 2012.
DOI : 10.1007/978-3-642-34961-4_21
URL : http://eprint.iacr.org/2012/514.pdf

M. Bellare and P. Rogaway, The Security of Triple Encryption and a Framework??for??Code-Based??Game-Playing??Proofs, LNCS, vol.28, issue.4, pp.409-426, 2006.
DOI : 10.1002/j.1538-7305.1949.tb00928.x

A. Escala, G. Herold, E. Kiltz, C. Ràfols, and J. Villar, An algebraic framework for Diffie-Hellman assumptions, CRYPTO 2013, pp.129-147, 2013.
DOI : 10.1007/978-3-642-40084-1_8
URL : https://link.springer.com/content/pdf/10.1007%2F978-3-642-40084-1_8.pdf

O. Goldreich, S. Goldwasser, and S. Micali, How to construct random functions (extended abstract), 25th FOCS, pp.464-479, 1984.
DOI : 10.1145/6490.6503
URL : http://dl.acm.org/ft_gateway.cfm?id=6503&type=pdf

V. Goyal, A. O. Neill, and V. Rao, Correlated-Input Secure Hash Functions, LNCS, vol.6597, pp.182-200, 2011.
DOI : 10.1007/978-3-642-19571-6_12
URL : https://link.springer.com/content/pdf/10.1007%2F978-3-642-19571-6_12.pdf

J. Kim, S. Hong, and B. Preneel, Related-Key Rectangle Attacks on Reduced AES-192 and AES-256, LNCS, vol.4593, pp.225-241, 2007.
DOI : 10.1007/978-3-540-74619-5_15
URL : https://link.springer.com/content/pdf/10.1007%2F978-3-540-74619-5_15.pdf

R. Lars and . Knudsen, Cryptanalysis of LOKI91, AUSCRYPT'92, pp.196-208, 1993.

S. Kiran, C. Kedlaya, and . Umans, Fast polynomial factorization and modular composition, SIAM Journal on Computing, vol.40, issue.6, pp.1767-1802, 2011.

K. Lewi, H. W. Montgomery, and A. Raghunathan, Improved Constructions of PRFs Secure Against Related-Key Attacks, LNCS, vol.14, issue.8479, pp.44-61, 2014.
DOI : 10.1007/978-3-319-07536-5_4
URL : http://crypto.stanford.edu/~klewi/papers/rka-full.pdf

M. Naor and O. Reingold, Number-theoretic constructions of efficient pseudorandom functions, 38th FOCS, pp.458-467, 1997.
DOI : 10.1109/sfcs.1997.646134
URL : http://www.wisdom.weizmann.ac.il/~reingold/publications/GDH.PS

[. Wee, Public Key Encryption against Related Key Attacks, PKC 2012, pp.262-279, 2012.
DOI : 10.1007/978-3-642-30057-8_16
URL : https://link.springer.com/content/pdf/10.1007%2F978-3-642-30057-8_16.pdf