1 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF 1 2 2 2 , Goutam Paul , Mridul Nandi Nilanjan Datta , Avijit Dutta 1 Indian Institute of Technology, Kharagpur 2 Indian Statistical Institute, Kolkata. [email protected],[email protected],[email protected], [email protected] (Yasuda, CT-RSA 2010) is the first beyond birthday bound Abstract. SUM-ECBC (BBB) secure block cipher based deterministic MAC. After this work, some more PMAC_Plus (Yasuda, BBB secure deterministic MACs have been proposed, namely (Zhang et al., ASIACRYPT 2012) and 3kf9 (Naito, CRYPTO 2011), LightMAC_Plus ASIACRYPT 2017). In this paper, we have abstracted out the inherent design principle of all these BBB secure MACs and present a generic design paradigm to Double-block Hash-then- construct a BBB secure pseudo random function, namely or in short ( Sum ). A DbHtS construction, as the name implies, computes a DbHtS on the message and then the encrypted output of the two hash double block hash sum blocks. Our result renders that if the underlying hash function meets certain security requirements (namely cover-free and block-wise universal advantage is low), DbHtS 2 n/ 3 -bit security. We demonstrate the applicability of our construction provides result by instantiating all the existing beyond birthday secure deterministic MACs (e.g., , PMAC_Plus , SUM-ECBC , LightMAC_Plus ) as well as a simple two-keyed 3kf9 variant for each of them and some algebraic hash based constructions. Keywords: DbHtS · Beyond Birthday · Cover-free · Block-wise Universal · PRF · Sum of PRP. 1 Introduction Pseudo Random Function or in short PRF plays an important role in symmetric key cryptography in providing solutions for authentication and encryption of any arbitrary length message. Mostly, PRFs are realized by iterating a block cipher or a fixed length compression function in a specific mode of operation. These PRFs are called block cipher based PRF or compression function based PRF respectively. Some of the commonly CBC-MAC [ BKR00 ], PMAC [ used block cipher based PRFs are ], OMAC [ IK03 ], BR02 LightMAC [ LPTY16 ] etc. and compression function based PRFs include NI-MAC [ AB99 ], NMAC [ BCK96 ] etc. These PRFs are secure only up to the birthday bound, i.e., the mode is secure only when the total number of blocks that the mode can process does not exceed 2 n/ , where n is the block size of the underlying primitive (i.e., a block cipher for a block 2 cipher based PRF, a compression function for a compression function based PRF etc.) of n/ 2 the construction. The bound is called the birthday bound in cryptography. 2 1.1 Limitations of Birthday Bound Secure PRFs Birthday bound secure constructions are acceptable in practice, if one uses any of these constructions with a moderately large block size. For example, instantiated with PMAC 48 2 n queries (using 5 AES-128 permits roughly about 2 / 2 ] bound), when the [ NM08 `q

2 2 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF 16 2 longest message size is blocks and the success probability of breaking the scheme − 10 is restricted to 2 . However, the same construction becomes vulnerable to use if instantiated with some light weight (smaller block size) block ciphers, whose number + + 07 BKL BPP 17 ], has grown tremendously in recent years, e.g., PRESENT [ ], GIFT [ ] etc. For example, PMAC LED [ GPPR12 , when instantiated with the PRESENT block 16 2 64 queries when the longest message cipher (a bit block cipher), permits only about 16 − 10 2 2 . Therefore, size is blocks and the success probability of breaking the scheme is it becomes risky to use the birthday bound secure constructions instantiated with light 64 -bit block ciphers are still widely used primarily due to weight block ciphers. In practice legacy applications with backward compatibility e.g., financial sectors, web browsers etc uses triple DES instead of AES as using the latter one in corporate mainframe computers 64 -bit is more expensive. However, if the mode provides only birthday bound security, then block cipher does not give adequate security. Having a beyond birthday secure mode solves the issue. Many practical secure applications use standard AES. Using AES in a birthday secure 64 -bit security which is adequate enough in current days technology. mode provides -bit security may not be adequate in However, due to the technological advancement 64 future. In such situation, the better option would be to use a mode with beyond birthday security instead of replacing the cipher with larger block size. Note that, there are no standard block cipher of size higher than 128 bits. 1.2 Beyond Birthday Bound Constructions Yas10 In this line of research, Yasuda [ ] first proposed a BBB secure deterministic MAC, called , a rate- 1 / 2 sequential mode of construction with four block cipher keys SUM-ECBC 2 that offers roughly about 3 -bit security. Followed by this work, Yasuda [ Yas11 ] came n/ up with another deterministic MAC, called PMAC_Plus that also offers roughly about 2 n/ 3 -bit security. Unlike SUM-ECBC , PMAC_Plus is a rate- 1 parallel mode of construction with three block cipher keys. Zhang et al. [ ZWSW12 ] proposed another candidate of BBB 3kf9 1 sequential mode of construction with three secure deterministic MAC, called , a rate- block cipher keys that offers 2 n/ 3 -bit security. In all of these proposals security bound of q and ` , where q is the total number of queries and ` the construction is some function of is the maximum number of message blocks in any of the queried messages. LightMAC_Plus , q Nai17 ], is the first deterministic MAC which is proven to have an as proposed by Naito [ independent beyond birthday bound and hence, it effectively offers a better security ` + than that of all the earlier three proposals. In a very recent work, Datta et al. [ DDN 17 ] proposed a single-keyed variant of the PMAC_Plus that offers a better security bound than that of PMAC_Plus IM16 ] also achieves a stronger, . The MAC part of GCM-SIV2 [ 2 beyond the birthday bound (roughly 3 -bit) security. Besides block cipher based BBB n/ secure PRFs, beyond birthday secure compression function based PRFs have also been studied by Yasuda [Yas08] and Dutta et al. [DNP16]. Interestingly, all these existing beyond birthday bound secure deterministic MACs (i.e., SUM-ECBC , PMAC_Plus , 3kf9 , LightMAC_Plus ) possess a similar structural design, which is a composition of two constituent elements: (i) a double block hash function that 2 n -bit hash value of the input message and (ii) a finalization phase that generates outputs a the final tag by xor-ing the encryption (via two independent block ciphers) of two n -bit hash values. However, all these MACs follow a different way to bound the security. This observation motivates us to come up with a generic design guideline to construct a beyond birthday bound secure PRF that brings all the existing BBB secure MACs under one common roof and enables us to give a unified security proof for all of them.

3 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 3 1.3 Our Contributions The contributions of this paper are threefold: Double-block Hash-then-Sum (in 1. We introduce a generic design which we call ) paradigm, a method of designing a beyond birthday bound secure PRF DbHtS short by xor-ing the encryption of the outputs of a double block hash function. Based on the usage of the keys, we call the DbHtS construction three-keyed (resp. two-keyed), if two block cipher keys are (resp. a single block cipher key is ) used in the finalization phase along with the hash key. We would like to mention that we consider only the keyed hash functions unlike popular unkeyed hash functions (e.g., SHA-256, RIPEMD etc). We show that if the cover-free and the block-wise universal advantage (See Sect. 3.3 for the definition) of the underlying double block hash function is sufficiently low, then the two-keyed DbHtS is secure beyond the birthday bound. We also extend our generic security result from the two-keyed to the three-keyed DbHtS construction. We show the applicability of our security result for the two-keyed DbHtS 2. construc- tion by instantiating the two-keyed variants of poly-hash based construction and SUM-ECBC PMAC_Plus , existing beyond birthday secure deterministic MACs (i.e., , 3kf9 , LightMAC_Plus ). Using our generic security result for the two-keyed DbHtS 2K-ECBC_Plus , construction, we have shown that all the two-keyed variants (i.e., 2K- PMAC_Plus 2kf9 and 2K-LightMAC_Plus ) achieve beyond birthday bound security. , The bounds are given in Table 1. 3. Finally, we apply our generic security result for the three-keyed DbHtS construction to bound the PRF security of SUM-ECBC , PMAC_Plus , 3kf9 and LightMAC_Plus . Our approach not only provides a generic tool to achieve the BBB security of these constructions, but also helps us to obtain an improved bound for some of the construc- SUM-ECBC and ). Note that, a similar improvement in the tions (e.g., PMAC_Plus + by Datta et al. [ 1k-PMAC_Plus 17 ]. security bound has also been observed in DDN 3kf9 [ ZWSW12 Additionally, we have identified a flaw in the existing security proof of ] and to the best of our knowledge, this paper provides the first correct security bound 3kf9 of . A comparison of the old security bounds of the existing BBB secure MACs with the new one is depicted in Table 1. LNS18 ] have shown attacks on all these constructions with Very recently, Leurent et al. [ 3 n/ 4 query complexity. This raises an interesting future problem to study the tightness of 2 PRF security of these constructions. Organization. We develop the notations and recall the basic security definitions in Sect. 2. DbHtS In Sect. 3, we introduce the paradigm and prove its PRF security. We instantiate DbHtS with algebraic double block hash function in Sect. 4. Sect. 5 deals with the PMAC_Plus security analysis of the two-keyed variants of the parallel constructions (i.e, LightMAC_Plus ) and provides an alternative security proof for PMAC_Plus and and LightMAC_Plus . Sect. 6 deals with the security analysis of two-keyed variants of sequential constructions (i.e., and 3kf9 ) and provides an alternative security proof for SUM-ECBC SUM-ECBC and 3kf9 . Finally, we conclude the paper by discussing some open problems and difficulties in proving the PRF security of the single-keyed DbHtS in Sect. 7. 2 Preliminaries We will introduce necessary symbols and notations in Sect. 2.1 followed by the required security definitions in Sect. 2.2. We discuss the lazy sampling of permutations in Sect. 2.3.

4 4 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF #Keys denote the number of block cipher keys used in the construction. Rate Table 1: defines the average number of message blocks processed by a single execution of block q denotes the maximum number of denotes the total number of queries and cipher. ` queries. Only the dominant terms of the security bounds are listed. q message blocks in all ( ) symbolizes the ? symbolizes the new bound is improved over the existing one and ( ) † corresponding bound is incorrect. We discuss this issue at the end of Sect. 6.3. New Bound Old bound Construction (#Keys, rate) Three-keyed DbHtS 2 3 n 2 3 n 4 n 2 / 2 q` q / 2 2) + q / ` 2 1 , ( ? ) (4 SUM-ECBC / 2 2 2 3 n 3 2 3 2 n n n 2 q + 2 `/ 2 / ` + q q ` 1) / 2 , (3 ( ? ) PMAC_Plus q`/ 3 3 2 n n 3 4 2 n 2 + (3 2 q ( † ) q / ` 2 / 1) , ` 3kf9 q`/ 3 2 n 3 2 n 1) q , (3 / 2 / 2 LightMAC_Plus q Two-keyed DbHtS 2 2 3 n n 2 q` ` / 2 2) + q / 1 , / 2 (3 2K-ECBC_Plus - 3 2 n 2 2 2 n (2 q + q , ` `/ / 2 2 - 2K-PMAC_Plus 1) 3 4 2 n , (2 - / 2 q ` 2kf9 1) 3 2 n n + / 2 (2 q 1) q/ 2 , 2K-LightMAC_Plus - Sect. 2.4 briefly discusses about H-Coefficient Technique. Some basic results of linear algebra is given in Sect. 2.5, followed by the result on xor of two permutations in Sect. 2.6. 2.1 Notations S and a random variable X , we write X ← $ S to denote that X is Given a finite set S sampled uniformly at random from . n for the rest of this section. { 0 , 1 } We fix a positive integer denotes the set of all n n . A is defined as an n -bit binary string. The functions fix0 binary strings of length block take an and return -bit binary string x fix1 x with its least significant bit set to 0 n and respectively. We write 0 to denote the all zero binary string and 1 to denote the 1 and n − 1 bits are all zeros and the least significant bit is one. binary string whose first ̃ x over an index set I is denoted by ( x A tuple : i ∈I ) . For notational simplicity, we i sometimes write the tuple as x ) when the index set is understood from the context. The ( i i -th element of a tuple ̃ x is represented by x i . Length of a tuple ̃ x refers to the number of i elements in it and is denoted by | ̃ x | . An element x if of a tuple ̃ x is called a fresh value i for all 6 = i , x j 6 = x not fresh in . Otherwise, we say x or alternatively is a colliding value i j i distinct not x if each of its elements is fresh. Otherwise, we say it is ̃ . A tuple is said to be x and ̃ y is denoted by ( a fresh tuple x, ̃ y ). A tuple is said to . Concatenation of two tuples ̃ ̃ ( q ) n 1 } be a . For a set X , X block-tuple , if each of its element is a member of { denotes 0 , n n ( q ) = { 0 , 1 } the set of all distinct tuples over , then X { 0 , 1 } of length ) q . If X denotes ( the set of all block-wise distinct tuples of length . For a positive integer q , we write [ q ] to q { , 2 ,...,q } . We denote the empty set as Φ . denote the set 1 n n ,..., , } 0 as a set of integers { 0 , 1 1 2 We regard the set − 1 } by converting an n -bit { 2 − n 1 − n n a a ) ∈ { 0 , 1 } a to an integer a 2 + ...a 2 a ( binary string + ... + n 0 n − 2 n − 1 1 1 − n 2 − n a 2 + a , where multiplication and addition are integer arithmetic. Let GF (2 ) be the 0 1 n n n { 0 , 1 } 2 as GF (2 elements and we regard ) . We identify an n -bit string field with n 2 − n n − 1 a + ...a ... a + ) ∈ { 0 , 1 } as a polynomial ( a a ∈ a x + a x + a x 0 − 1 − n 0 1 2 − 1 n 1 − n n 2 n x ] . To do operations on the elements of (2)[ (2 GF ) , we fix an irreducible polynomial GF are done ( x ) ∈ GF (2)[ x ] and addition, denoted as ⊕ and multiplication, denoted as · f n ( x ) . With a slight abuse of notation, we write { 0 f 1 } , to denote the set of n -bit modulo n GF (2 binary strings or the field ) . ( The set of all functions from to Y is denoted as Func X X , Y ) . Similarly, the set of all

5 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 5 X is represented by ( X ) . A function φ mapping an element from permutations over Perm n n 2 0 is called a block function . Similarly, if φ maps to ( { 0 , 1 } } ) , , an arbitrary domain to { 1 φ . We write a double block function as φ we call it a ,φ double-block function ) , where = ( 0 1 X and are block functions. We denote the set of all block functions with domain φ as φ 1 0 1 ) , we write and the set of all block permutations as Perm . For integers 1 ≤ b ≤ a Func ( X ) to denote a a ( a − 1) ... ( a − b + 1) , where ( a ) ( = 1 by convention. 0 b 2.2 Security Definitions with the key space K A X and the range keyed function PRF and PRP. , the domain F : K×X → Y and we denote F ( K,X ) Y F is a function ( X ) . Similarly, a keyed by K K and the domain X is a mapping with the key space : K×X →X such permutation E K ∈K , X 7→ E ( K,X ) that for each key X and we denote E ) ( X is a permutation over K E ( ) . for K,X be an oracle algorithm with oracle access to a function from Let that outputs A X to Y oracle can make at most A a single bit. Without loss of generality, we assume that q distinguisher . We queries with running time at most t . We call such an oracle algorithm a F as against a keyed function A define the prf-advantage of PRF F RF K | ( K ← $ K : A A ) := Pr[ = 1] Pr[ RF ← $ Func ( X − Y ) : A Adv = 1] | . , F A Similarly, we define the prp-advantage of the distinguisher against a keyed permutation E as PRP E Π K K Pr[ K ( $ | : A A ) := ← = 1] − Pr[Π ← $ Perm ( X ) : A . = 1] | Adv E xxx xxx Adv For a keyed function family , where xxx is either ( q,t ) denotes max ) Adv , A F ( F F A prf or prp and maximum is taken over all distinguishers running in time at most A and make at most t queries. If F is a keyed function (resp. permutation) family q xxx Adv ≤ is a ( q,t ) such that δ , then we say F is a ( δ : q,t ) -PRF (resp. PRP). If A F computationally unbounded distinguisher, then we disregard the time parameter from its advantage definition. Let and X be two K (Almost-XOR) Universal Advantage of Hash Function. h n } : K non-empty finite sets and 0 0 , 1 . A keyed function H is a -(almost-xor) > ×X →{ h ′ n and for any Y ∈{ 0 universal hash function, if for any distinct X,X } , , ∈X 1 ′ ← $ K Pr[ : H . ≤ ( X ) ⊕ ] Y ) = ( X K H K h K h h h ′ is said to be an -universal hash function, if for any distinct X,X , ∈X Moreover, H ′ K K Pr[ : H ← $ ( H ) = X ( )] ≤ . X K h h K h h H is said to be a Double-block A keyed hash function Double-Block Hash Function. n 2 H : K 0 ×X → ( { Hash ( , 1 } DbH ) ) function, if . We denote the pair of block outputs as h ∈X . ( X ) ,H ) ( ( X )) , where X H and H X ( X ) ‖ H ( ( X ) = H , 1 , 0 K K , 1 K , 0 K K h h h h h 2.3 Lazy Sampling of Random Permutation n } ← $ { Suppose, a distinguisher , 1 is interacting with a random permutation A . This Π 0 interaction is simulated by a simulator that maintains a partial function (or sometimes we call it a list) Ψ which is initially set to an empty function (i.e., a function with empty i -th query x Dom , the simulator checks whether x (Ψ) ∈ domain). On the (Ψ) , where Dom i i n , 1 } { on which Ψ is defined. If so, the corresponding response is the set of all elements of 0 n Ψ( , where y ) . Else, the response is sampled uniformly from { 0 , 1 } is set to \ Ran (Ψ) x i i n and { 0 , 1 } Ran which have at least one preimage under Ψ is the set of all elements of (Ψ) added to the set Dom (Ψ) . x i 1 n n = { 0 , 1 } When then we write Func to denote Func ( { 0 , 1 } ) X

6 6 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF 2.4 H-Coefficient Technique + Pat08c 14 ] which , In this section, we briefly discuss the H-Coefficient Technique [ CLL Pat08c has been introduced by Patarin [ ] and recently regained attention since Chen and CS14 Steinberger used it to analyze the iterated Even-Mansour cipher [ ]. This technique gives a kind of “systematic” way to upper bound the statistical distance between the answers of two interactive systems and is typically used to prove the information theoretic pseudo randomness of constructions. In this setting, we consider a computationally A unbounded and hence deterministic distinguisher that interacts with either the real oracle, i.e., the construction of our interest, or the ideal oracle which is usually considered to be a uniform random function or permutation. The collection of all the queries and transcript responses that A , A made and received to and from the oracle, is called the of . Sometimes, we allow the oracle to release more internal information to denoted as τ A completes all its queries and responses, but before it outputs its decision bit. A only after A includes the additional information about the oracle and In this case, the transcript of clearly the maximum distinguishing advantage of A in this setting can not be less than τ that of without additional information. Observe that the transcript is a random variable only comes from the randomness of the oracle and the randomness of the distribution of τ with which A interacts. τ X Let denote the probability distributions of the transcript X induced by and re id τ the real oracle and the ideal oracle respectively. The probability of realizing a transcript in the ideal oracle (i.e., X Pr = τ ] ) is called the ideal interpolation probability . Similarly, [ id one can define the real interpolation probability. A transcript τ is said to be attainable A if the ideal interpolation probability is non-zero (i.e., Pr [ X with respect to = τ ] > 0 ). id We denote the set of all attainable transcripts by Θ . Following these notations, we state + 14] as follows: the main theorem of H-Coefficient Technique [Pat08c, CLL ) . ( A be a fixed deterministic distinguisher H-Coefficient Technique Theorem 1 Let O or the ideal oracle that has access to either the real oracle O . Let Θ = Θ Θ t g b id re (disjoint union) be some partition of the set of all attainable transcripts of A . Suppose ∈ ≥ 0 such that for any τ there exists Θ , g ratio X = τ ] Pr[ re , − 1 ≥ ratio ] = X Pr[ τ id . Then, ≥ and there exists such that Pr[ X ∈ Θ ] ≤ 0 id b bad bad O O O id re id ) := | Pr[ A Adv ( A − Pr[ = 1] (1) = 1] |≤ A + . bad ratio O re O When is a uniform random function and O is some keyed construction defined over re id prf ≤ Adv (1) . ( A the same domain, then Eqn. says that + ) ratio bad O re 2.5 Some Results on Linear Algebra n L of dimension s × t defined over GF (2 j ) , L [ i ][ For a matrix ] denotes the element in 1 its -th column. For a column vector c of dimension s × j , L ‖ c denotes -th row and i s × ( t + 1) . For any row vector R := ( R the augmented matrix of dimension ,...,R of ) t 1 T 1 × t , transpose of row vector R , denoted as R dimension , denotes the column vector R 1 R 2 T := R . . . R t of dimension t × 1 .

7 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 7 linear equations with t unknowns ( Y One can represent any system of ,...,Y s ) defined 1 t n s , denoted as L , as a matrix L of dimension (2 × t , where the i -th equation over ) GF n a -th row vector i · Y , corresponds to the ⊕ ... ⊕ a ) · Y L = c (2 , where c := ∈ GF i i it 1 1 i i t as if it has at least one solution, otherwise we a of ( ,...,a L ) . We say L is consistent it 1 i 2 L to be consistent, one must have rank ( L ) = call it ( L ‖ c ) inconsistent , where . For rank T c has a unique solution if ,...,c and it has many solutions if ) c . L = ( rank ( L ) = t s 1 L rank . ) ( < t T Y = c represent a system of s linear equations with · unknowns ( Y Let ,...,Y L ) , t t 1 n L ) = r and the elements of L are from GF (2 where ) . Let Y := ( Y ( ,...,Y be ) rank t 1 n 0 , 1 } without replacement samples from a set and c is any arbitrary column vector Y ⊆{ n s with its elements from GF (2 1 ) . Thus, the probability of realizing a of dimension × 1 particular solution is at most as stated formally in the following lemma. t r ) |Y|− ( + r n Y := ( Y ,...,Y Lemma 1. Let ) be without replacement samples from a set Y ⊆{ 0 , 1 } t 1 n L be a matrix of dimension s × t defined over GF (2 and ) . Then, for any given column n vector s × 1 over GF (2 c ) , we have of dimension 1 T L , · Y ) = c ] ≤ Pr[( s × t ( r ) t + |Y|− r r L . is the rank of the matrix where Since, the rank of is r , the number of free variables in the system of equations Proof. L ( t − r ) . Now, each choice of free variables, which necessarily has to be distinct, uniquely is determine the remaining variables such that the overall system of equations is satisfied. Therefore, the number of solutions is at most |Y| ) ( and the total number of ways we r − t is distinct variables Y t ,...,Y . Dividing the former one by later gives can choose ( ( |Y| ) ) t t 1 the result. 2.6 Sum of Two Identical Permutations In this section, we briefly revisit the security result of the sum of two identical random permutations. The sum of two permutations is one of the PRP to PRF transformations, suggested by Bellare et al. [BKR98] as: ) = , ) E x ( ( SUM ⊕ E ) ( x x K E ,E K 1 2 K K 1 2 sum and E where are two independent PRPs. We call this construction as the E K K 1 2 2 n/ 3 construction Luc00 ] who proved 2 . This construction was later analyzed by Lucks [ Pat08b , Pat10 , Pat13 ]. The results are security. Further improvements have been shown in [ natively inherited by the construction that consists of the xor of three or more independent PRPs [CLP14, MP15]. K = K ), Security of the single-keyed sum construction (i.e., the sum construction with 1 2 Luc00 , BI99 ], has been shown as simulated through the domain separation, suggested in [ 3 / 2 q ( n ) · to be provably secure by Bellare and Impagliazzo [ BI99 ] up to O . However, 3 2 n/ 2 their security proof is too sketchy to verify and contains unverifiable gaps. In a series of Pat08b , Pat10 , Pat13 ], Patarin proved the optimal security of the construction papers [ Pat13 ] and the mirror theory technique [ Pat10 ] but the using the standard H technique [ √ n ] showed (1 . 5 q + 3 proof is still unverifiable. Recently, Dai et al. [ q ) / 2 DHT17 bound for the sum construction and its single-keyed variant using the chi-squared method. In the following, we state and prove that the single-keyed sum construction is a secure PRF that offers 2 n/ 3 -bit security. Formally, we have the following result: 2 rank of a matrix L is defined as the maximum number of linearly independent columns of L

8 8 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF ( T ,...,T For any block tuple ) of length q such that each T Lemma 2. is non-zero, let 1 q i ) q (2 n ,V . ) } : U Z ⊕ V = = T { ∀ i ∈ [ q ] , ( U ) ,V ( ) } ∈ ( { U 0 1 , i i i i i i i i i n 3 (2 ) q 6 q 2 2 − n Then, |Z|≥ 2 . ) , with the assumption q ≤ (1 − 2 n nq 2 2 + := 17 DDN B Datta et al. [ { B ] showed in Theorem 2, that for any set ,...,B }⊆ Proof. 1 s n 0 1 and a q -length block tuple ( T , ,...,T } ) such that each T is non-zero, the following { i 1 q holds: n (2 s − ) 2 q n 1 0 1 0 1 ) 0 (2 q μ − (1 ) , (2) H ) ,H ∈ ) : { 0 , 1 } = \B ) ⊕ , ( } H H |{ ,H |≥ T H ( ( 2 i i i i i i i i nq ︷︷ ︸ ︸ 2 H 2 2 3 +2 sq qs +4 q / 3 μ ≤ where . n 2 2 2 q − s − (2 ) H is the same as B as an empty set and hence s = 0 . Z Now, note that the set with n − 2 2 ≤ , we obtain the result. Therefore, from Eqn. (2) and with the assumption q . 1 Remark It is natural to wonder that why we prove a weaker bound of the construction in the face of its existing optimal security bound. We note that the optimal security bound of the construction has been proved for PRF advantage. However, we need a counting results on the number of permutations to apply the H-coefficient technique. Currently, we do not know how to use this optimum PRF security result directly in our proof setting. In this regard, one can possibly use the Patarin’s proof of sum construction using the mirror Pat10 ] technique. However, the reliability of Patarin’s proof [ Pat10 ] is debatable. theory [ 3 2 n/ 2 Thus, we independently prove the security of the sum construction up to bound, which is good enough for our purpose. Moreover, as we will see later in the paper that DbHtS we will use the above result in the security analysis of the two-keyed construction. The dominant term of its security bound appears due to the cover-free advantage (defined later in Sect. 3.3) of its underlying DbH function, overkilling the optimal bound of the single-keyed sum construction. 3 DbHtS : A BBB Secure VIL PRF Paradigm ) is a well known paradigm for constructing a Variable Input Hash-then-PRF or ( HtP Length ( VIL ) PRF by composing a universal hash function and a Fixed Input Length ( FIL ) HtP composition result says the following: PRF due to Shoup [Sho04]. Formally, is a H ( ` ) universal hash function that outputs m bits and F is an ( δ : q ) -PRF with If m 2 0 , 1 } domain , then the composition construction ( F ◦ H ) is a ( δ + ( ` ) q { / 2 : q,` ) -PRF. To obtain the BBB PRF-security of a keyed construction following the HtP paradigm, F H need to be the PRF advantage bound of and the universal advantage bound of beyond birthday. It is feasible to construct a double block hash function (which outputs c − 2 n ( ` ) = O m ` = 2 2 n bits) with ) (e.g., multi-linear hash [ HK97 ], PolyHash [ dB93 , ( BJKS93 , Tay93 ] etc). However, obtaining a beyond birthday bound secure PRF over 2 n bits input would not be easy and efficient. It is needless to say that a beyond birthday bound secure can be constructed from scratch or one can try some variants of the F -rounds Luby-Rackoff [ Pat98 ] or the Benes-Butterfly construction [ 5 ] that gives a Pat08a beyond birthday bound secure PRF over 2 n bits input. However, the former suggestion is non-trivial and the latter one would require at least 6 primitive calls for realizing 2 n bits to n bits PRF. Moreover, its security proof is based on pseudorandom function. A possible way out is to instantiate each pseudorandom function with the sum of two independent block ciphers. But this idea comes at the cost of using total 12 block cipher keys. To realize it with less block cipher keys is non-trivial. .

9 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 9 This motivates us to design a paradigm for constructing a beyond birthday secure VIL PRF, where the underlying hash function H is required to achieve some stronger security assumption than the universal property, whereas we require a simple and efficient keyed function that is not required to be a PRF. 3.1 Double-block Hash-then-Sum (DbHtS) Paradigm DbHtS ) paradigm In this section, we describe the Double-block Hash-then-Sum (in short, to build a BBB secure VIL PRF. In this paradigm, a Double-block Hash ( DbH ) function is used with a very simple and efficient single-keyed or two-keyed sum function: Sum y ( x,y ) = E - ( x ) ⊕ E ) ( Single-Keyed Sum Function: , K K K x Sum - , ) ( x,y ) = E y Two-Keyed Sum Function: ( ( ) ⊕ E K K K ,K 2 2 1 1 E , where E are independent. Given a K ,E and K are n -bit block ciphers and K K 2 K 1 1 2 function and the sum function over two blocks, we apply the composition of the DbH DbH function and the sum function to realize the DbHtS construction. Based on the types of sum function (i.e., single-keyed or two-keyed) used in the composition, we categorize DbHtS into following two categories: Three-Keyed DbHtS: C ) := [ H,E ]( M - Sum M . ( H )) M ( ,H ( ) 3 K ,K 1 K K , 0 , 2 1 h h - Two-Keyed DbHtS: C . [ H,E ]( M ) := Sum )) ( H M ( ,H ) ( M 0 , K , 1 2 K K h h M M H H K K h h E E E E K K K K 2 1 ⊕ ⊕ T T Figure 3.1: Two different types of Double block Hash then Sum constructions. Left : C . Right : [ H,E three-keyed construction M ) := E )) M ( H ( H ( E ( M )) ⊕ ]( 0 3 , K K K K 1 , 1 2 h h two-keyed construction C . [ H,E ]( M ) := E ∈K ( H K where )) M ( M )) ⊕ E ( ( H K K K 0 , 1 h K h 2 , h h C For simplicity of notations we sometimes simply refer them as and C respectively. 2 3 two-keyed (or three-keyed) DbHtS construction, as we count the hash key We use the name as one key and the sum function requiring one key (or two independent keys respectively), independent of the hash key. However, a concrete instantiation of a DbH function may require multiple keys. SUM-ECBC , PMAC_Plus , 3kf9 , Light- Most of the BBB secure deterministic MACs like MAC_Plus are specific instantiations of the three-keyed DbHtS paradigm. However, we would like to work with the two-keyed DbHtS construction as it involves more challenging analysis than its three-keyed version. We would like to note that the three-keyed DbHtS does not outperform its two-keyed version in terms of providing improved security bound as evident from the last column of Table 1 . Its only advantage lies in its simpler security proof, as the number of cases to analyze gets reduced.

10 10 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF 3 . , we can not apply the HtP composition As the sum function is not a PRF Remark 2 . This says that we need a different type result directly to analyze the security of DbHtS of composition result for the security analysis of construction in which we require DbHtS some higher security properties from its underlying DbH function instead of having only the universal property. 3.2 Proof Idea of Two-Keyed DbHtS Construction In this section, we provide a brief idea of proving the security of the two-keyed DbHtS construction. We believe that this will motivate the reader to understand the crux of the main proof given in Sect. 3.4 and also help to understand a few definitions introduced in Section 3.3. We use the H-Coefficient technique, which requires us to bound: (i) the probability of the bad transcripts in the ideal oracle and (ii) the ratio of the real to ideal interpolation probability of the good transcripts. The computation of the real interpolation probability is reduced to the probability of satisfying the following many bi-variate equations: q T )) = M , ( H Π( ⊕ Π( H )) M ( 0 1 1 K , 1 1 K , h h ( T , Π( H )) = M H Π( ( M ⊕ )) 2 2 , K 0 , 1 K 2 h h . . . )) , T Π( ( M )) = H ⊕ Π( H M ( , , K K q q 1 q 0 h h Now, to obtain a meaningful lower bound of the real interpolation probability, we need Π to be fresh for each equations and each T at least one of the inputs of to be non-zero. i or [ q ] , either H In this regard, we call a transcript to be good if for each ∈ ) M ( i 0 , K i h ) ( or both are fresh in the following tuple: H M i 1 , K h ( ) ̃ ( H H , := )) ( M M ) ,H ( ,H ) M ( M ( )) , ( H H ( ,..., )) ( M M ) ,H ( 1 , K 2 2 0 , K K , 0 1 1 q , K , 1 K 1 q 0 , K h h h h h h T is non-zero. In other words, we call a transcript to be bad if one of the and every i following three conditions occur: ∃ i ∈ [ q ] such that . We call it (i) . ( M ) = H the collision condition ( M ) H , , 1 i 0 i K K h h ′ ( = j,i 6 = k,b,b i ∈ { 0 , 1 } such that H (ii) ) = M ( ( M ,H ) = H ) M ∃ 6 1 ,b i K , K 0 , i K j h h h ′ ) ( M . We call it the covered condition . H k ,b K h ∃ i : T (iii) = 0 . i If none of the above conditions happen, then for each q ] , either H [ ∈ ( M ) and i i 0 , K h ̃ M ( ( M are colliding H both are fresh in ) H , or any one of the H H or ) ( M ) i , K K i 0 1 1 , i K , h h h ̃ in . If both the inputs are fresh, we can directly apply Lemma 2. Otherwise (w.l.o.g. H H H M ) is non-fresh), the permutation output of ( assume that is defined ( M ) 1 , 1 K , i i K h h (or may need to sampled, if not defined already), which in turn uniquely determines the permutation output of H ). However, T (as we have already fixed the response ( M ) i i , K 0 h this uniquely determined output may collide with some already sampled values in range. We call this condition which actually creates a permutation the range collision condition input-output compatibility issue . Therefore, bounding the probability of bad transcripts is nothing but to bound all of the above events. A detailed treatment of bounding the bad probability is given in Sect. 3.4. Finally, by computing the ratio of real to ideal interpolation probability concludes the proof of C H,E ] . [ 2 3 One can construct a PRF distinguisher with PRF advantage very close to 1 . A makes four queries A x ,y and check if the xor of their output is zero which holds with probability , ( x ( ,y ) , ( x ,y ) , ( x ,y ) ) 1 2 2 2 1 2 1 1 − n 1 for real oracle, and holds with probability 2 for ideal oracle.

11 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 11 . We would like to mention that we have identified the bad events with a clear 3 Remark intention in mind to apply the sum construction result when these bad events do not happen. As a result, the bad events essentially boil down to investigating the collision, the DbH covered and the range collision condition of the underlying function. Whether all of these bad events directly lead to an attack in the construction, is not known. 3.3 Security Notions for DbH Functions function which will be DbH In this section, we define the necessary security notions of a required in proving the main security result of this paper. ̃ ̃ Let be two tuples of length q . We say that the tuple ( ̃ g, ̃ h g is covered at an and ) h ̃ ( ] , if g ∈ and h i are colliding values in [ ̃ g, q h ) , but they do not collide at the same index i i ̃ 6 = h if for all i ∈ [ q ] . As a matter of fact, ( ̃ g, value i.e., h ) g is covered at an index ∈ [ q ] i i i j = i,k 6 = i such that either of the following conditions hold: ∃ and only if 6 ) g , h = g g , h = = h , h ( ii ) g h = h = ( g i h ) ( iii ) g iv = g ( , h g = = i j i k i i j k j k i i j k i i j and k , we can have j = k and therefore plugging-in j = k in As there is no restriction on i ) ( iv ) gives rises the following two possibilities: ( and g ) j 6 = i : g ( = h . , h h = g = ( vi ) ∃ j v = i : ∃ , h = g 6 j i j i j j i i j ii ( ( iii ) , ) = k case is excluded by the “no-collision at the same value Note that, for and at index i . Moreover, it is needless to mention that for q = 1 , the tuple ( g ,h condition” ) 1 1 is always cover-free. ̃ g and cross-collision ̃ , when any one of the conditions We say that there is a between h ̃ - ( v ) occur. The tuple ( ̃ g, ii h ) is called covered, if it is covered at some index i ∈ [ q ] . If ) ( ̃ ̃ g, the tuple h ) is not covered, we say that it is cover-free. So for a cover-free tuple ( ̃ g, ( h ) ̃ q ( such that none of ,h is fresh in ) collides at the same value, for every i ∈ [ g ] , either g i i i ̃ ̃ ̃ ̃ h ) or h ) is fresh in ( ̃ g, ( h ) ̃ ( ̃ g, g, h ) is said to be weak covered , if ( ̃ g, or both. The tuple h i ̃ ̃ ̃ g, cross-collision h ) . In other words, if ( ̃ g, ( h ) is weak is covered but there is no between i ) ( vi ) holds. Thus, a weak covered tuple is always a or covered, then only condition ( covered tuple but the other direction is not true. ̃ Example 1. = ( a,b,a,d,e,f ) and b,c,c,d,e,g h = ( Let us consider two tuples ) of ̃ g ̃ . Observe that ̃ g, 6 h ) is covered at index 1 , 2 , 3 , but not covered at index 4 and ( length 5 g = h as and g . Moreover, it is not a weak covered tuple. On the other hand, the = h 5 4 4 5 ̃ is a weak covered tuple. g ) and ̃ h = ( u,u,v,x,y,z ) of length 6 a,b,a,d,e,f tuple = ( 3.3.1 Security Definitions for DbH Function Having defined the cover-free tuple, we now introduce the necessary security definitions for a DbH function. We begin with defining the cover-free advantage of a DbH function H . q , a distinct tuple ( M 6 ,...,M , we ) and fixed i,j,k ∈ [ q ] such that i 6 = j,i For a = k q 1 define the following event: ) ( ∨ ′ ( H := H ( CF ) ) = H M ( M ) ,H ( M ) = M ,b 0 k j ,b K K , 1 ijk K i K , i h h h h ′ } 0 ∈{ b,b 1 , ( ) ∨ . H ) ( M M ) = H ( H ) = M ( M ( ) ,H 1 K 1 j 0 i , , K 0 , , K i j K h h h h We also define the event ( ) H := ( M ) = H ) ( ( M ) ,H ( M ) = H M WCF j ijk , K k , 1 K 0 i , 0 K K , 1 i h h h h ( ) ∨ . ) M ( ( M H ) = H ) = M ( ,H ( M H ) K 0 K , 1 , j i K i K , , 1 0 j h h h h

12 12 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF Let K be a function from a set of tuple of q distinct messages to the Definition 1. bad n 2 P . We say that a DbH function H : K power set of hash keys ×M→ ( { 0 , 1 } ( ) ) is a K h h M ( ) -cover-free DbH function, if for any q -tuple of distinct messages ( , , ,...,M ) K q 1 bad cf each of length at most ` blocks such that such that i 6 = j,i 6 = k, Pr[ CF holds, ∀ K . i,j,k \K ≤ ( M )] ,...,M ∈K q bad h cf h ijk 1 to be the of the DbH function H . cover-free advantage for three messages We call cf H as follows: function Similarly, we define the weak-cover-free advantage of the DbH Definition 2. q be a function from a set of tuple of Let distinct messages to the K bad n 2 ×M → ) . We say that a DbH function H : K K power set of hash keys ( { 0 , 1 } P ) ( h h ( K -tuple of distinct messages , q ) is a DbH function, if for any -weak-cover-free wcf bad M ) , each of length at most ` blocks such that, ( ,...,M 1 q ≤ such that 6 = j,i 6 = k, Pr[ WCF ∀ holds, K . ∈K \K i ( i,j,k )] ,...,M M q bad h wcf h ijk 1 function weak-cover-free advantage for three messages of the DbH We call to be the wcf . H Note. K is treated as a function that It is to be noted that in both the definitions bad maps a tuple of q distinct messages to a subset of hash keys. As we work on a fixed tuple q distinct messages, the set K is a fixed set and hence for the sake of ( M of ,...,M ) q 1 bad K to indicate the image set of the function notational simplicity, we abuse the notation bad K . bad ̃ g, i h ) and for a fixed index Note that, for a cover-free tuple ∈ [ q ] , either g ( is non-fresh ̃ i ̃ ̃ ̃ ( ̃ and h h ) or g ) is fresh and h h is non-fresh in ( ̃ g, . h ) or both are fresh in ( ̃ g, is fresh in g, i i i Considering the first two cases, we now define the block-wise universal advantage of DbH function as follows: For a q , a distinct tuple ( M , we define the ,...,M j ) and fixed i,j ∈ [ q ] such that i 6 = q 1 following event: ) ( ) ( ∨ := ( ( M H ) = H ) = M ( H ( M UNIV ) H ) M 1 j 0 , 0 , ij i K i K K , K 0 , j h h h h ( ) ) ( ∨ ∨ ( M M ) = H ( H ) = M ( M ( ) H . H ) i K j 0 i , K K , , 1 K i 1 1 , h h h h We also define the event ( ) ( ) ∨ ) = H M . ( M ) WUNIV := ( H M ( M ) = H ) ( H , K 0 , 1 K i i j ij K , , 1 0 K j h h h h n 2 DbH function H : K - ×M → ( { 0 , 1 } Definition 3. ) We say that a is ( K ) , univ bad h ) function, if for any ( M q ,...,M block-wise universal -tuple of distinct messages , DbH q 1 each of length at most ` blocks such that such that ∀ 6 = j, Pr[ UNIV holds, K i,j ∈K \K ] ≤ . i h h univ bad ij to be the block-wise universal advantage for two messages of DbH function We call univ H . DbH function H as Similarly, we define the weak-block-wise universal advantage of the follows; n 2 Definition 4. function H : K -weak- ×M→ ( { 0 , 1 } We say that a ) DbH is ( K ) , wuniv bad h ,...,M DbH q -tuple of distinct messages ( M block-wise universal function, if for any , ) q 1 each of length at most ` blocks such that, ∀ i,j,k such that . 6 = j,i 6 = k, Pr[ WUNIV holds, K ≤ ∈K ] \K i bad h h ij wuniv

13 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 13 weak-block-wise universal advantage for two messages of the DbH We call to be the wuniv . H function The prior two events perfectly capture all the possibilities of having non-freshness condition ̃ can collide at the same value. In the ) tuple except the condition that g ̃ and h g, h in ( i i g and h following, we define the event that captures the collision of at the same value. i i ∈ ( q ,...,M , a distinct tuple ) and a fixed i M [ q ] , we define the following event: For a q 1 ( ) := H M ) = H ( ( M ) . COLL 1 i 0 i K i K , , h h n 2 We say that a : K Definition 5. ×M → ( { 0 , 1 } function ) DbH is a ( K - , ) H coll bad h DbH function, if for any q tuple of distinct messages ( colliding , each of length ,...,M ) M q 1 ` at most blocks such that, ≤ ∈ q ] , Pr[ COLL i holds, K . ∈K \K ∀ ] [ h bad h i coll to be the of DbH function H . We call maximum collision probability coll (1) We would like to point out that only , Discussion. and ` are functions of coll cf univ as these values depend only on the length of a triplet of messages, pair of messages and a single message respectively. To emphasize this fact, we often write (3 ,` ) and ) (2 ,` univ cf to denote and should also respectively. In the same line of reasoning ) (1 ,` coll univ cf , but we prefer to denote it as denote . coll coll (2) The notion of weak-cover-free advantage and weak-block-wise universal advantage DbH function of the three-keyed DbHtS construction. are the required properties for the Because, in the three-keyed construction, we apply the two-keyed sum function DbHtS on the input of the underlying DbH function. As a result, we do not require to bother about considering any cross-collisions in the output of the hash function. Here we intend to use the notion weak in terms of the security definition. If a double-block hash function is cover-free or (block-wise universal) then it is also weak-cover-free or (weak-block-wise universal respectively), however the converse is not necessarily true. (3) The notion for cover-free and collision have also been used in the context of the + DNP16 ] security proof. However, the notion of cover-free and collision used in -MAC [ NI their paper is substantially different from ours: (i) In [ ], the cover-free notion was DNP16 used to refer to the collision event between the input of the final function call with the input of an intermediate function call and (ii) the collision event was used to denote the input collision in the final function call. 3.3.2 Security Definitions for Block-Separated DbH Function. function H = ( if the range of possible A DbH block-separated is said to be ) ,H H 0 K , 1 K K , h h h H are disjoint. It is easy to see that using functions, fix1 and and H fix0 values of , 1 , K K 0 h h ′ H DbH DbH function H function one can easily transform any to a block-separated K h K h as follows: ′ := ( fix0 ( H fix1 . H ( ) , )) H 0 , K K , 1 K h h h ̃ ̃ function H is covered at an index ) , ( H H Note that, for a block-separated DbH , K 0 K K 1 , , h h h i ∈ [ q ] implies that only condition (i) or (vi) holds i.e., one of the following conditions hold: - ∃ i 6 = j,i 6 = k such that H . ) M ( ( M H ) = H ) = M ( ,H ( M ) K j K , 1 , k i K i K , , 1 0 0 h h h h - ∃ i 6 = j such that H ) M ( H . M ) = ) = H M ( ,H ) ( M ( j , K K , 1 j K i 0 0 K , , 1 i h h h h

14 14 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF DbH function, the event Accordingly, for a block-separated will be CF ijk ( ) ) = H ( M ) ,H H ( M ) = H CF ( M ) M = ( K , i 0 ijk K K , 1 j i k , K 0 1 , h h h h ( ) ∨ ) = H (3) ( M ) ,H ( . H ( M ) = H M ( M ) , 1 0 K i i j K , , 1 0 K j K , h h h h Note that, the above event is exactly identical to and therefore, the cover-free WCF ijk notion of a block-separated DbH function is equivalent to its weak-cover-free notion. Therefore, the cover-free advantage of a block-separated function is equivalent to DbH H its weak-cover-free advantage. Similarly, for a block-separated DbH , the function K h block-wise universal advantage implies one of the following conditions hold: i 6 = j - H ∃ . ) M ( M ( ) = H such that K , 0 i K j , 0 h h ∃ i - = j such that H . ) M ( ( M H ) = 6 i K , 1 1 , j K h h function, the event UNIV Accordingly, for a block-separated will be DbH ij ( ) ) ( ∨ . = ) ( M M ) = H ( H ) = M ( M ( ) UNIV H (4) H , K 1 j 0 i , K K , , 1 K i j 0 ij h h h h UNIV is exactly identical to Similar as before, the above event WUNIV ij and therefore, ij the block-wise universal notion of a block-separated DbH function is equivalent to its weak-block-wise universal notion. Therefore, the block-wise universal advantage of a DbH function is equivalent to its weak-block-wise universal advantage. block-separated Moreover, it is easy to see that for a block-separated function, COLL is an impossible DbH i i ∈ [ q ] and hence a block separated DbH H is always ( K DbH event for any 0) -colliding , bad function. 3.4 Security of DbHtS DbHtS construction. In particular, In this section, we state and prove the PRF security of DbHtS construction C based on a [ H,E we prove only the PRF security of two-keyed ] 2 DbH function H and pseudo random permutation or block cipher E . n n K , K 1 and M be three non-empty finite sets. Let E : K×{ 0 , 1 } Theorem 2. →{ 0 , Let } h n 2 K H × M → ( { 0 , 1 } be a block cipher and ) : be a DbH function. Let K be a bad h distinct messages to the power set of hash keys P ( K function from a set of tuple of ) q h : ( M q ,...,M ∈ ) , one has Pr [ K such that for any tuple of $ K K distinct messages ← h 1 q ≤ ( K ,...,M . )] M bh bad 1 q i ) If H is ( K ) , , (3 ,` )) cover-free, ( K K , ( (2 ,` )) block-wise universal and ( bad univ cf coll bad bad colliding hash function, then 3 3 3 6 q 3 q q q prp prf ′ + · (2 (3 ,` )+ ,` , )+ · Adv q ( (2 q,t q,`,t )+ ) + ≤ · Adv + univ cf bh coll E ] H,E [ C n 2 n n 2 2 2 2 6 ′ , t + q ( t where + t be the time complexity of hash computation for a single message, ) t t = γ h h be the time complexity of making two primitive queries with xoring their reply and we t γ 2 n − have assumed that ≤ . q 2 ii ) If H is ( K ( , block-wise universal block- (3 ,` )) cover-free and ( K )) , ,` (2 univ cf bad bad separated DbH function, then 3 3 3 q 6 q 3 q q prp prf ′ + ≤ (2 q,t , ) + ) + + ( q,`,t ,` · (2 (3 ,` ) + ) Adv Adv · cf bh univ E C ] H,E [ 2 n n n 2 2 2 6 2 ′ t q = t + where ( t be the time complexity of hash computation for a single message, + t t ) , γ h h t be the time complexity of making two primitive queries with xoring their reply and we γ n − 2 2 have assumed that . ≤ q

15 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 15 K iii H is ( K ( , ) (3 ,` )) weak-cover-free and ( If weak-block-wise uni- , )) (2 ,` wuniv bad wcf bad versal hash function, then 3 3 3 q q 2 3 q prp prf ′ ( q,`,t (2 ) ≤ ) + + 2 Adv q,t , ,` (2 · ) + Adv ) + ,` (3 · bh wuniv wcf E C H,E ] [ 2 n n 3 2 6 2 ′ + t + q ( t where t t ) , t be the time complexity of hash computation for a single message, = h γ h be the time complexity of making two primitive queries with xoring their reply and we t γ n − 2 q have assumed that . 2 ≤ Using the standard argument of switching from computational setting Proof of part (i). ∗ ∗ to information theoretic setting, we analyze the security of the construction := C C H, [ Π] 2 2 n Π and a double block hash function H . This -bit random permutation based on an prp ′ conversion adds the term (2 q,t ) in the security bound. Therefore, we need to show Adv E that 3 3 3 q q 6 q 3 q prf + ) + + ) ≤ (5) ,` q,` ( (2 Adv + q . · · ) + ,` (3 · ∗ univ coll bh cf C 2 n n n 2 2 2 2 6 The remainder of the proof is organized as follows: We begin with describing the ideal oracle and the attack transcript of the adversary in Sect. 3.4.1. In Sect. 3.4.2, we define and bound the probability of bad transcripts in the ideal oracle. Analysis of the good ( i ) of Theorem 2 follows from Theorem 1 transcripts is shown in Sect. 3.4.3. Finally, part and Eqn. (5) above and Lemma 3 and Lemma 4 proven below. 3.4.1 Initial Setup We fix a computationally unbounded and hence deterministic non-repeating query making ∗ that interacts with either (1) a real oracle H D [ distinguisher C for a random Π] , K 2 h Π and a random hashing key K permutation or (2) an ideal oracle $ , making at most q h queries adaptively to the oracle. The ideal oracle consists of two phases: (i) Online Description of the Ideal Oracle. M , the oracle samples the response T Phase : In this phase, for each queried message i i n 0 , uniformly at random from } { and returns it to the distinguisher D . When all the 1 queries and responses are over, the oracle samples a dummy hash key K from the hash h key space K , uniformly and independently to all the previously sampled random variables. h If the sampled hash key happens to fall in the set of bad hash keys (note that the K h K ), then it aborts the game message tuple is fixed and thus we can talk about the set h (see line 2 of Fig. 3.2), otherwise the oracle computes the hash value for all the q queried messages. During this hash computation, if for any message M , one block of the hash i value collides with another block, then Coll is set to 1 and the game will be aborted (see line 5 of Fig. 3.2). i ∈ [ q ] has been covered or not. If covered, then Otherwise the oracle checks if any index is set to and the oracle aborts the game (see line 6 of Fig. 3.2); otherwise it 1 Cover continues. If the game does not abort, that means there is a non-empty set of free indices F for 2 q many hash blocks value. which both blocks of the hash value are fresh in the tuple of Then, the oracle samples the outputs for these fresh hash values in without replacement manner such that for any ∈F , the sampled output Z i and Z sums up to T , where ,i 0 ,i i 1 T 8 of Fig. 3.2). has already been sampled in the online phase of the game (see line i Now the remaining cases are those where exactly one block of the hash value collides. i ∈ [ ) ] \F , if the output of the colliding hash value, say H , has not been ( M For all q K i , 0 h , Z sampled yet, then the oracle samples its output in without replacement manner, say 0 ,i Z and sets the output of the remaining block, i.e., output of ( M ) as the sum of H 0 i ,i 1 K , h

16 16 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF Online Phase of O ideal n ← On i -th query M ∈ , return T [ q $ { 0 , 1 } i ; ] : ∀ i i ∃ i : T ; = 0 then ZeroT ← 1 , ⊥ 1 : if i O = ∅ Offline Phase of , initialize L ideal $ K ; K : 1 ← h h K 2 ∈K : , then Bad-Hash ← 1 , ⊥ ; if bad h ); M ( [ 3 ] : ( H : ∀ i ∈ ( M H ) , H ← )) M ( q i i K K i K , 0 , 1 h h h ̃ ̃ : := ( H )); M ( , . . . , H ( M ) ) , . . . , H M ( , H ( M := ( )) 4 H H 0 1 0 K 0 , 1 K K 1 1 q K q , 1 , , h h h h : if ∃ i ∈ [ q ] : H ) = , 1 ← ( M Coll 5 H then ) M ( ⊥ ; 1 K i 0 , i K , h h ̃ ̃ then : , ( H 6 ) is not a cover-free tuple if Cover ← 1 , ⊥ ; H 1 0 ̃ ̃ { i ∈ [ q ] : H H ; |F| = ( M f ) and H ; } ) H ( M 7 ) both are fresh in ( : F := , 0 i 1 , 1 K i 0 , K h h n (2 f ) 0 ← $ S := { ( Q ( ) ∈ ( { : , 1 } Z ) , Z 8 ) : Q ⊕ R = T ∀ i ∈F} ; , R ,i i i 1 i i 0 i i ∈F ,i i ∈F )) : ∈ [ q ] ∩F : Ψ( H 9 ( M i ← Z ∀ , Ψ( H ; ( M )) ← Z K K , 1 0 ,i i i , 0 1 ,i h h ̃ ̃ ∀ i ∈ [ q ] \F : let H ; } 1 ( M , ) be not fresh in ( 10 H 0 , : H ∈{ ) , b 1 0 i ,b K h n if : ; Z ( M ⊕ ) / ∈ Dom (Ψ) then Ψ( H T ← , Z ( M (Ψ) )) 11 Z H ← $ { 0 , 1 } ← \ Ran i i i 1 − K K ,b b,i ,b b,i b,i h h : else Z ; ← Ψ( H Z ⊕ T ( M ← )) and Z 12 i i − ,b b,i 1 K b,i b,i h ; ⊥ , 13 Z ∈ Ran (Ψ) if RC ← 1 : then b,i − 1 : Ψ( H ; M Z ← )) 14 ( i b − 1 , 1 − b,i K h ̃ ̃ ); K : , 15 Z Z return ( , 0 1 h Figure 3.2: $ : Boxed statements denote bad events. Whenever a bad event is Ideal oracle 1 , the ideal oracle immediately aborts (denoted as set to ) and returns the remaining ⊥ values of the transcript in any arbitrary manner. So, if the game aborts for some bad event, then we can surely assume that its previous bad events have not happened. Line 10 indicates that there exists some j for which H ) M ( ( M H ) = H ) = M ( ( M H ) or j K ,b ,b K i K i K j , 1 − b ,b h h h h ̃ Z M and line denotes ( 11 indicates that permutation output of ) is not defined yet. H 0 i ,b K h ̃ Z . ) ,...,Z ,Z the tuple ,Z Z ,...,Z ( denotes the tuple ) and ( Z 1 1 0 2 1 , 1 , ,q , 2 1 1 ,q , 0 0 and T to the (see line 11 of Fig. 3.2). Otherwise, the oracle sets the output of H ) M ( 0 , i K i h already defined element and adjusts the output of the other block accordingly (see line 12 of Fig. 3.2). Note that in the latter case, the oracle does not sample the output. M In the above said adjustment, if the output of happens to collide with any H ( ) i K , 1 h RC is set to 1 previously sampled output, then 13 of Fig. 3.2) and aborts the (see line game. Note that, this event cannot hold for the real oracle, as is fresh in the ) H M ( 1 , K i h tuple of 2 q many hash block values. Finally, it returns all these sampled values along with the sampled hash key to the distinguisher D . ( ) M Description of Attack Transcript. ( M ,T ) , ( τ ,T ) ,..., ( M Let ,T ) = be the 2 1 q 1 2 q list of queries and responses of which constitutes the query transcript of the attack. For D convenience, we slightly modify the experiment where we reveal some more information to the distinguisher D in addition to the queries and responses only after D made all its queries and responses but before it output its decision. Therefore, the transcript of D ∗ essentially consists of all the internal values which are obtained while computing C for all 2

17 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 17 queries. All in all, the transcript of the attack is q ( ) M τ ,T . ,Z ( = ) ,Z ,Z ,Z ,T ) , ( M M ,T ( ,Z ,..., ) ,Z ,K 2 , 2 , 0 2 2 q 1 q , 0 ,q 1 1 ,q 1 , h 0 1 1 1 interacting with the real oracle, we release the hash key and the values D In case of K h ∈ [ q ] ,Z ∀ , := Π( H )) M ( H ( i := Π( )) and Z M 1 i 0 K 0 , ,i , ,i i K 1 h h D where H . )) ( to M ) = ( H ( ,H ) M ( M 0 , i K K , 1 K i i h h h τ in the real oracle must satisfy all of the following: Note that a transcript and 1. ⊕ Z Z ] = T q for all i ∈ [ i 1 0 ,i ,i ̃ ̃ ̃ ̃ the , namely Π -tuples of input and output blocks of q ) 2 I ) and O := ( 2. := ( H H Z Z , , 0 1 0 1 4 I is uniquely determined by the message Note that, are permutation compatible. ( M . ,...,M ) tuples and the hash key K q 1 h X Recall that X are the probability distributions for the transcript τ induced by and re id the real and the ideal oracle respectively. τ is attainable if Pr [ X Θ = τ ] > 0 and let id denotes the set of all attainable transcripts. 3.4.2 Definition and Probability of Bad Transcripts An attainable transcript τ is said to be bad if either of the following bad flags Bad-Hash ZeroT , Cover , RC Coll , , as defined in Fig. 3.2. We define the event 1 is set to ZeroT ∨ Bad-Hash ∨ Coll ∨ Bad ∨ RC . := Cover Θ denote the set of all bad transcripts and Θ Let = Θ \ be the set of all good Θ b b g transcripts. Having identified the set of all bad transcripts, we bound the probability of realizing the bad transcript in the ideal oracle in the following lemma: Let X be defined as above then, and Θ Lemma 3. b id 3 3 q q 3 q ] ≤ ) + + q · ,` + (6) := Pr[ (2 · X ,` ) + . ∈ Θ · (3 cf univ bad coll bh b id n n 2 2 6 Proof. Bounding the probability of the bad transcripts in the ideal oracle is equivalent to bounding the probability of the event Bad in the ideal oracle. Using the union bound we have, Pr[ Bad Pr[ ZeroT ] + Pr[ Bad-Hash ] + Pr[ Coll ∧ Bad-Hash ] ] ≤ ] ∧ ] + Pr[ RC ∧ Bad-Hash Bad-Hash . (7) + Pr[ Cover In the following, we separately bound each of the above terms. ZeroT . The bad flag ZeroT is set to 1 , if out of q responses, there exists at Bounding 0 T T , i.e. = such that least one response i i q ∑ q q Pr[ T ] = Pr[ = 0 ] ≤ ZeroT ∨ (8) . Pr[ T ] = = 0 i i =1 i n 2 i =1 4 ̃ x and For two block tuples y having equal length over the same index set, we say ̃ x is permutation- ̃ . ̃ y , if there exists a permutation π such that ∀ i,π ( x y ) = compatible with i i

18 18 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF Last equality follows due to the uniform and independent sampling of the responses in the ideal oracle. Bounding Bad-Hash This probability is basically determined from the probability of . DbH sampling the hash key of the underlying function. Therefore, Bad-Hash . (9) Pr[ ] ≤ bh Bad-Hash From the definition of the ideal oracle game, Coll is set to 1 ∧ Coll Bounding . . ] such that H if there exists at least one i ∈ ( M ) = H [ ( M ) and K ∈K \K q i K i , h 1 h , bad K 0 h h Therefore, q ∑ - Hash ] ≤ ) = Pr[ Coll ] Pr[ H \K ∈K , K ) ( M ∧ Bad H M ( , i 1 K i 0 , h bad h K h h i =1 q ∑ (1) ] \K holds, K Pr[ ∈K (10) = , COLL ≤ q · coll bad h h i =1 i follows from Definition 5. where (1) Bad-Hash . From the definition of the ideal oracle game, Cover is set ∧ Bounding Cover ̃ ̃ belongs to H to , if the tuple H ( 1 is not cover-free where the sampled hash key K ) h 1 0 K \K . Moreover, the set event set to 1 implies Coll event has not occurred. Cover h bad Therefore, ( ) Pr[ ] = Pr[ Cover ( H - ] \K ( M ∈K )) K , ( H Bad ∧ is covered, Hash ( M )) i i 1 , i h i h 0 bad , K K h h 3 ∑ (1) q ,` (3 · (11) , ) ≤ holds, ∈K K \K Pr[ ] CF ≤ cf ijk h h bad 6 6 = 6 i = k j,i follows from Definition 1. where (1) ∧ RC Bounding The event holds when for some b ∈ { 0 , 1 Bad-Hash and i ∈ [ q ] , . } ) ( M ( )) ) is not fresh in M ( H ( H ,...,H ) ( M M ) ,...,H ( H ( ( M , )) 0 q , K , 1 K 1 1 0 , K , 1 K ,b q i K h h h h h and Z of Fig. 3.2). Observe that the event considers undesired 13 ∈ Ran (Ψ) (see line 12 - b,i − 1 ′ ,u with i < j i,j,k,b,b collision among range elements. This bad event will occur if for some , ′ ′ and b,b = ,u ∈{ 0 , 1 i , we have: (1) H ( M ) = H Z 6 ( M = ) and (2) Z k ⊕ T } j ,b K i u,k ,b i K b,i h h n Z $ { 0 , 1 } ← \ Ran (Ψ) . Now, we split this bad event into the following cases and where b,i compute the probabilities for these cases individually: Case A. j • = k . Since the first condition is an event of the sampling of hash key K 6 h and the second one is the event of lazy sampling (independent of the distribution of the hash key ), the probability of the bad event for this case for a specific choice K h ′ of ,u would be i,j,k,b,b ′ := Pr[ H ] Z ⊕ ( M T ) = H = Z Pr[ ,K ( M × ) P ] ∈K \K h bad j ,b h b,i K i i ,b K u,k h h UNIV holds, K ∈K \K ] × Pr[ Z ] = T ⊕ Z = Pr[ b,i i h ij bad h u,k (1) 1 , (2 ,` ) × ≤ univ n 2 q − 2 where (1) follows from Definition 3. By summing over all possible choices of ′ ,u i,j,k,b,b , the probability of bad event for this case would be bounded above by n n − 2 / q − 2) · q (2 ,` ) ( 2 2 , with the assumption that q ≤ 2 q − 1)( . univ n ′ j = k . Here we sample Z to ← $ { 0 , 1 } • \ Ran (Ψ) first and then set Z Case B. b ,j b,i Z . Now, we analyse this case in different sub cases: b,i

19 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 19 ′ ′ – Case B.1. . We first consider the case when u = b = . In this case, b u ′ ′ Z ) = H , But these two events implies H ( ( M Z ) and M = ⊕ T i b,i j b ,b ,j K i K ,b h h 0 T P = which is impossible and hence the probability, denoted by , becomes 1 . B i zero. ′ ′ – Case B.2. u 6 = b = . This case eventually boils down to the and b b i ) H M . Note Z ( M joint event ) = H = T ⊕ ( ( Z ) and ( ii ) j i ,b K i K ,b 1 − b,j b,i h h = T T holds, then condition that, if the event ii ) is implied by condition ( i j ) and the constraint T . Therefore, bounding the joint probability of = T ( i i j ) is equivalent to bounding the H M Z ) = H = T ⊕ ( M Z and ( K b,i ,b ,b i K j 1 − b,j i h h H ( . Now, to bound the T joint probability of M = ) = H T and ) ( M j ,b K i i ,b j K h h later one, we have ] \K := Pr[ T ∈K = T ,K ,H ) M ) = ( M ( P H h K ,b i B j K j . i h 2 bad ,b h h Pr[ H ] ] T ( M = ) = H T Pr[ · ( M = ) ,K T ∈K = \K T | K bad h j j ,b K h i i ,b j i h h Pr[ UNIV ] holds, K = ∈K T \K = | T T = T Pr[ ] · j ij bad h j h i i (1) 1 ≤ ,` ) × (12) , (2 univ n 2 (1) follows from Definition 3 and Eqn. (12) follows from the argument where T ,...,T , all the q messages would be fixed and hence, that after conditioning q 1 UNIV . ∈ K \K is at most the conditional probability of (2 ,` ) ,K h univ bad h ij 1 Moreover, the event = is bounded by T T T . On the other hand, if T = 6 n i j j i 2 ⊕ then Z 6 = Z T ⊕ T and hence the probability becomes zero. i j b,j b,i ′ ′ – Case B.3. u 6 b 6 = b b . This case eventually boils down to the joint and = and i H ( ( M ) = H event j ( M ) ) ( ii ) Z ⊕ T = Z . Note that, i 6 = b b,i ,b K i j K b,j i , 1 − h h T = 0 and hence the probability becomes zero. Now, if as that would leads to i T ii = T ) holds, then as before condition ( the event ) is implied by condition ( i j i T T = and the constraint . Using the previous argument we have j i (1) 1 × P := Pr[ T ) = T ,` ,H (2 ≤ ( M , ) = H ] ∈K\K ,K ) M ( b − 1 , h j bad K i ,b B univ K j i 3 . h h n 2 (1) follows from Definition 3. Moreover, if T ⊕ 6 = T = then Z 6 T where b,j j 1 j − i T ⊕ Z and hence the probability in that case becomes zero. i b,i ′ ′ with ,u ) ( i < j and b,b i,j,b,b By summing over all ∈{ 0 , 1 } , the probability ,u for case B, denoted by P , is bounded above by taking the maximum of B ) ,` (2 · 1) − q ( q univ P , which is upper bounded by and . P P , n 1 B . B . . 3 2 B 2 Therefore, we have ] Bad - Hash RC ≤ P + P Pr[ ∧ B A q q ,` (2 2 ( ) − 1)( q − 2) · · ( q (2 ,` ) q − 1) univ univ + ≤ n n 2 2 3 q 3 ≤ (13) . · ) (2 ,` univ n 2 Finally, the result follows from Eqn. (7) , Eqn. (8) , Eqn. (9) , Eqn. (10) , Eqn. (11) and Eqn. (13).

20 20 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF 3.4.3 Analysis of Good Transcripts In this section, we lower bound the ratio of the probability of realizing a good transcript τ in the real and the ideal oracle. For this, let us first understand what does a good transcript , both H are in the ideal oracle mean. Note that, for each i ∈F ( M ) ) and H M ( , , K i i 0 1 K h h ̃ ̃ 7 H H ), as shown in line fresh in the concatenated tuple ( of Fig. 3.2. Moreover, as the , 1 0 6∈F is not set to 1 and therefore, for every i is good, , exactly one of the transcript τ Cover ̃ ̃ ) ( M f ) or H + q ( ). Thus, we have exactly ( M H ) is fresh in ( many fresh H H , 0 K 1 , , K i i 0 1 h h blocks ( 2 f many fresh blocks for all those indices belong to F and additionally we have − 2 f ) / 2 many fresh blocks) and q − f many non-fresh blocks, where f = |F| . Now, we (2 q c ′ ′ } := [ q ] \F as i ∼ j if H define a relation . ∼ ( M 1 ) = H , 0 ∈{ on ( M F ) for b,b j K i ,b ,b K h h c c F ∼ as C F t···tC and hence partitions . Note Clearly, is an equivalence relation over r 1 contains at least two elements. Therefore, line 11 that each C is executed only for one i element of these := min C c be the minimum valued element of C . So, when C ’s. Let j j j j c i for some j ∈ [ r ] , we execute line 11 once for sampling the output of H = , ) ( M i K ,b j h . Due ( M ) , where which in turn determines the outputs for all ∈C H and b ∈{ 0 , 1 } p K j p ,b h to the definition of Z ,Z . T in line 8 , 9 , 11 and 12 , for all i ∈ = q ] we have Z Z ⊕ [ ,i 0 1 ,i 0 ,i i 1 ,i ZeroT does not hold, we also have Z As the event is 6 = Z RC is good, . Moreover, as τ ,i ,i 1 0 not set to 1 and thus no range collision occurs for two different inputs. Thus, we have the following result: For a good transcript τ , 2 q -tuples of input and output blocks of Π , namely Claim 1. ̃ ̃ ̃ ̃ are permutation compatible. I := ( H ) ) and O := ( , Z Z , H 0 1 0 1 We would like to mention here that the result of Claim 1 will be used to compute the ratio of real to ideal interpolation probability for a good transcript τ as follows: τ Lemma 4. be a good transcript. Then, Let 3 τ ] q Pr[ X 6 = re ≥ 1 − . 2 n ] 2 = Pr[ X τ id ̃ ̃ As , H is a good transcript, the pair of tuple Proof. ( H τ ) is cover-free. We have 0 1 considered the set F , the set of all free indices, as defined in line 7 of Fig. 3.2 and let = |F| . We have also defined a set S in line 8 of Fig. 3.2. Recall that, f is the list of Ψ responses of the lazy sampling made in the ideal game. Now, 1 1 X τ ] = Z ]] q [ · = ∈ i · Pr[Ψ( H ∀ Z )) = M ( M ( )) = Pr[ H Ψ( , 1 ,i K K , 1 i 0 i , ,i id 0 h h nq 2 | |K h 1 1 (1) ∈F i ∀ · ] Z )) = · Pr[Ψ( H M ( H Ψ( ( M , )) = Z = 1 , K ,i , 1 0 K i ,i 0 i h h nq |K | 2 ︸ ︸ ︷︷ h B Pr[Ψ( H M ] B \F | ( · ] )) = Z q [ , Ψ( H ∈ i ∀ Z ( M )) = ,i i 1 ,i , K K 1 0 i 0 , h h 1 1 1 1 (2) , = (14) · · · nq n − 2 f ) | |K (2 2 |S| r h r C . First, we use the fact that the hash where denotes the number of equivalence classes i ̃ key , the response tuple K T and the lazy sampling of Ψ are jointly independent as each h T and (ii) the distribution is distributed independent to (i) all the previously sampled T i and lazy sampling of Ψ , made in the offline phase of the game. Moreover, the K of h distribution of K is independent to the distribution of lazy sampling. For the last equality h , we note that Ψ is defined in two stages: (i) in the first stage, it samples elements from (2) − 1 i ∈F (see line 8 of Fig. 3.2) and thus Pr [ B ] = |S| S randomly for all the free indices and then (ii) in the next stage, it defines the rest of values by the lazy sampling method Ψ as described in line 11 - 14 . Note that, in the second stage of the sampling process, the oracle samples the permutation output for r many distinct values in such a manner that

21 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 21 these sampled output should not collide with the already sampled values in the first stage of the sampling process. Hence, we have 1 Z )) = Z , Ψ( H H ( M )) = Pr[Ψ( ∀ i ∈ [ q ] \F | B ] = ( M . 0 K ,i , 1 0 ,i i , i 1 K h h n − f ) 2 (2 r Now, we compute the real interpolation Computing Real Interpolation Probability. ̃ ̃ probability. From Claim 1, it is obvious that , H H is permutation compatible with ) ( 1 0 ̃ ̃ Z , Z ) . Note that, the number of permutation outputs that we need to sample is exactly ( 1 0 f + r . This is because, we have all total q + f many fresh hash blocks value and for q + each equivalent class, we need to additionally sample the output for a single hash block value. Hence, 1 1 τ ] = Pr[ = X · (15) real n |K (2 ) | + f + r h q Now we compute the ratio of Eqn. Computing the Ratio. as follows: to Eqn. (14) (15) n nq − ] Pr[ 2 X · (2 τ ·|S| 2 f ) = real r = n = τ ] Pr[ X ) (2 + + r id q f ( ) nq n n 3 (1) f 6 (2 · (2 2 ) − 2 f ) · f r 2 ≥ · 1 − nf n 2 n ) 2 2 · (2 q + r f + ( ( ) ) 3 3 f ( q ) − n (2) f 6 6 q 2 1 − · ≥ − 1 = n 2 n 2 n − + 2 2 r ) 2 (2 f q f − ︸ ︷︷ ︸ 1 ≥ follows after substituting the lower bound of (1) from Lemma 2 and (2) follows where |S| ≤ . f as q 3.5 Proof of Theorem 2 part (ii) Proof of the second part of Theorem 2, i.e., the proof of the PRF security of [ C ] H,E 2 construction when H is a block-separated DbH function, easily follows from that of the first part of Theorem 2. All the bad events from the first part of the theorem Coll cannot be set to as there cannot be will remain same, except that the bad flag 1 function and hence we have = 0 any collision event for a block-separated DbH . coll Moreover, the analysis for the ratio of the real to ideal interpolation probability for a good transcript τ remains identical to the proof of the first part of the theorem. For all ∈ F (set of free indices), we regard H M H . Since, V ( i ) = ) = U M and H ( i 1 K i i i 0 , , K h h f (2 ) n U . Now, ,U ,V ,...,U is a block-separated ,V DbH function, ) ,...,V ( ) ∈ ( { 0 , 1 } f 2 f 2 1 1 ( ,V , we sample ,U ) ,...,U ,...,V to sample the corresponding output tuple of U ,V 1 f f 2 1 2 ) f (2 n i ,Z ∀ , T ,...,Z = Z ,Z ⊕ Z such that ,Z ( ( Z ,...,Z ) , ) ∈ ∈F { 0 , 1 } 1 ,f , 1 1 , 0 ,i 1 ,f 2 ,i 0 2 i , 0 1 , 0 1 where f = |F| . This equivalence allows us to apply Lemma 2 for bounding the ideal interpolation probability (as done in the proof of the first part of the theorem). 3.6 Proof of Theorem 2 part (iii) There are subtle differences in the proof of the third part of the theorem from its first part which we list as follows: (a) Unlike C , where we used the same permutation in the sum function, in this case [ H,E ] 2 we use two “ independent ” random permutations instead of two identical permutation. Use of independent permutations makes the significant differences in defining the bad

22 22 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF T 0 events. Firstly, (i) we no longer need to have the zero output restriction, i.e., = i ∈ [ ] as the bad event. This is because, we do not care if H i for collides q ( M ) i , K 0 h for any , as the two permutations are independent. This ,...,q = 1 ( M with ) H i 1 i K , h condition also alleviates the necessity to consider the maximum collision probability of n 2 the function. Hence, in this security bound, we do not have the DbH q/ term and the maximum collision probability term. For analysing the ratio of the real to ideal interpolation probability, we use the result (b) ]) for lower bounding the number of solutions to the Luc00 of Lucks (see Theorem 5, [ sum of two independent permutations problem. Summarizing above, security result for three-keyed DbHtS follows. 3.7 Application of Theorem 2. DbHtS To prove the BBB security of a particular construction that follows paradigm, one needs to show the followings: The cover-free advantage of its underlying DbH (a) function for any triplet of distinct n c 2 / 2 ( O ) ` messages should be of the order of . The block-wise universal advantage of its underlying DbH function for any pair of (b) c n ` ) / 2 distinct messages should be O ( . (c) DbH function (wherever it is The maximum collision probability of its underlying c n O . / 2 ` ) applicable) must be of the order of ( Finally, the probability bound of the bad-hash-key must be of beyond birthday bound. (d) c is some small positive constant and ` is the maximum number of message blocks Here q queries. among all Discussion. The importance of introducing the set of bad hash keys in the security statement lies in providing the improved security bound for different instantiations of the two-keyed and the three-keyed DbHtS construction. A more detailed explanation follows in Sect. 6.6. Remark Dodis et al. [ DS11 ] have shown that if H is a cover-free DbH function and 4 . -bit keyed unforgeable functions, the sum function is instantiated with two independent n then C [ H,F ] is unforgeable. One can similarly show the PRF-security of the construction 3 n -bit keyed functions. For the when the sum function is instantiated with two independent C PRF security of [ H,F ] , if the output tuple of the underlying DbH function is cover-free, 3 then the output of C [ H,F ] is perfectly random. Hence, the security of the construction 3 DbH . boils down to the cover-free advantage of the underlying 4 Instantiation of DbHtS Using PolyHash In this section, we instantiate the DbH function using the double-block PolyHash function, that results in a PolyHash based DbHtS construction. PolyHash [ dB93 , BJKS93 , Tay93 ] is a very efficient algebraic hash function. To apply this on a message M , we first use apply ∗ 10 i.e., pad an injective padding such as followed by minimum number of zeros so that 1 the total number of bits in the padded message becomes mutiple of n . Let the padded ∗ M -bit blocks in it. Then, we = M message be ‖ M n ‖ ...M is the number of , where l l 1 2 define the PolyHash as follows: l 2 K ( M ) = M M K ⊕ ⊕ PH ... ⊕ . K M 1 − l h K 1 l h h h

23 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 23 DbH function: Now, we define the following PolyHash- ) ( ? ? ) := ( fix0 ( PH ( M PH-DbH , fix1 ( PH ( , M M )) )) ,K K K K h h h h ? and PH-DbH K are two independent hash keys. Note that, where is a block-separated K h h function. By composing PH-DbH with the single-keyed sum function, we obtain DbH construction, which we denote as C PH-DbH [ the two-keyed PolyHash based DbHtS ] . ,E 2 with the double-keyed sum function, where Similarly, by composing PH3-DbH ( ) ? ? ( ) := ( ( PH , PH3-DbH M )) , ( PH ( M M )) K ,K K K h h h h construction, which we denote as we obtain the three-keyed PolyHash based DbHtS [ PH3-DbH ,E ] C ). 3 For PolyHash based DbH function, we consider that the set of the bad Bad Hash Key. hash keys is empty, i.e., . = Φ for both PH-DbH and PH3-DbH K bad 2 2 n n , / 2 4 ` ) -cover-free and (Φ , 2 `/ 2 PH-DbH ) -block- (Φ is a The following result shows that 2 n 2 (Φ ,` wise universal block-separated / 2 DbH function. Moreover, ) -weak- PH3-DbH is a n function. ,`/ ) -weak-block-wise universal DbH 2 (Φ cover-free and 2 2 n n (Φ , 4 ` PH / 2 - Theorem 3. ) -cover-free and (Φ , 2 `/ 2 is a ) -block-wise universal DbH n 2 2 -weak-cover-free and - is a (Φ ,` PH3 / 2 function. Moreover, DbH ) DbH block-separated n (Φ ,`/ 2 ) -weak-block-wise universal DbH function. We defer the proof of Theorem 3 to Sect. 4.3. Assuming that the theorem holds, we now prove the PRF security of C in Sect. 4.1 and Sect. 4.2 [ PH-DbH ,E ] and C ] [ PH3-DbH ,E 3 2 respectively. 4.1 Implication for PolyHash Based Two-Keyed DbHtS is a block-separated function. As the set of bad hash keys of PH-DbH DbH Recall that, ] PH-DbH C = 0 [ PH-DbH ,E . Security result for is as follows: is empty, we have 2 bh n n K and Let be three non-empty finite sets. Let E : K×{ 0 , 1 } K →{ 0 , 1 } , Theorem 4. M h n 2 DbH : ( K ) ×K DbH be a block cipher and ×M → ( { 0 , 1 } PH ) - be a block separated h h function. Assume that there is no set of bad hash keys. Then, any distinguisher with t , making q tuple of distinct messages each of at most ` blocks long, running time at most from an [ PH - DbH ,E ] can distinguish n -bit uniform random function by C 2 3 3 2 3 ` q q 6 q 6 ` 2 q prp prf ′ + + , + ) ≤ Adv ( Adv (2 q,t q,`,t ) + E - ] [ PH ,E DbH C n 2 n 2 n n 2 2 2 · 2 2 3 2 ′ t = t + q ( t + t ) , t where be the time complexity of PH - DbH computation for a single h h γ message and t be the time complexity of making two primitive queries with xoring their γ reply. of Theorem 2. = 0 , Theorem 3 and part Proof of the theorem directly follows from ii ) ( bh 4.2 Implication for PolyHash Based Three-Keyed DbHtS Recall that, PH3-DbH is not a block-separated DbH function and for PH3-DbH , we have [ = 0 (as its set of bad hash keys is empty). The security result for C is ] PH3-DbH ,E bh 3 as follows:

24 24 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF n n Let and M be three non-empty finite sets. Let E : K×{ 0 , 1 } Theorem 5. →{ 0 , 1 } K K , h n 2 K PH3 ×K - ) ×M→ ( { 0 , 1 } DbH ) : ( be a DbH function. Assume be a block cipher and h h that there is no set of bad hash keys. Then, any distinguisher with running time at most t , making q tuple of distinct messages each of at most ` blocks long, can distinguish [ PH3 C DbH ,E ] from an n -bit uniform random function by - 3 3 3 3 2 ` 2 q 3 ` q q prp prf ′ ( + ( q,t Adv ) + ≤ ) q,`,t 2 + Adv E C ] ,E DbH - PH3 [ n n 2 2 n 2 3 2 6 2 · 2 ′ where = t + q ( t computation for a single + t DbH ) , t - be the time complexity of PH3 t h h γ t message and be the time complexity of making two primitive queries with xoring their γ reply. , Theorem 3 and part ( iii ) of Theorem 2. Proof of the theorem directly follows from = 0 bh 4.3 Proof of Theorem 3 In this section, we bound the cover-free and the block-wise universal advantage of . PH-DbH We also bound the weak-cover-free and the weak-block-wise universal advantage of PH3- DbH . Recall that, we have considered that there is an empty set of bad hash keys for both PH3-DbH PH-DbH and . Therefore, for analyzing the cover-free and the block-wise universal PH-DbH advantage of and for analyzing the weak-cover-free and the weak-block-wise , we sample the hash key from the set of all hash keys PH3-DbH universal advantage of and as a result we have - Hash Pr[ Bad = 0 . ] := bh PH-DbH . It is a well known result Bounding Block-wise Universal advantage of dB93 that the (almost-xor) universal advantage of the PolyHash [ BJKS93 , Tay93 ] is about , n 2 ` is the maximum number of message blocks. One can trivially extend this , where `/ result to show that the universal advantage of the one-bit chopped version of the PolyHash, n PH ( i.e., fixb ( M )) , is 2 `/ . } , where b ∈{ 0 , 1 2 K h ′ For a fixed pair of messages M and M , where the maximum number of message ′ M and M ` is blocks of , and for any b ∈{ 0 , 1 } , we denote the event fixb ( PH )) = M ( K h ′ ′ b ( M PH )) by P , we have } 1 , ( M,M fixb ) . Therefore, for a fixed ( ∈{ 0 , b K K h h ∑ ` 2 ′ ′ )] = Pr[ ( P PH Pr[ M,M PH , M ) = (16) ( ] ≤ b ⊕ ( M ) K K b , K h h h n 2 b 1 ∈ 0 , where the last inequality follows from the almost-xor universal advantage of the PolyHash. ? [ UNIV holds, For brevity, let us denote ( K . Therefore, we ,K Pr P ) ∈K by ×K ] univ h h h ij h have ) ( (1) ′ ? ? ′ ? ] ×K ∈K ) ( P = ) , ( K max ,K M,M ,K ) ∈K K ×K ( ] , Pr[ P , Pr[ ) P M,M ( h 1 K h h h univ h K 0 , h , h h h h ( ) (3) ` 2 (2) ′ ′ ? ≤ ( M,M M,M )] , Pr[ P Pr[ P , )] = ( max 1 K 0 , K , h n h 2 (2) is equivalent to (1) and (3) follows from Eqn. (16). Therefore, we have where 2 ` (2 ,` ) = (17) . univ n 2 Bounding Cover-free advantage of PH-DbH . To bound the cover-free advantage for any three distinct messages, we first fix three distinct messages and for M ,M and M j i k

25 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 25 ? Pr[ ( K CF ,K brevity we denote holds, ) ∈K . Therefore, we have ×K P ] by ijk h h h cf h (1) ? ? P ] ×K ∈K ( M ) ,M Pr[ ) , P ,K P K ( , = M ) ,M ( k 1 , cf h K j i i 0 h , h K h h h (2) ? ) Pr[ ( M ,M P , P = )] ( M ,M K 0 j , 1 K , i i k h h (3) ? M )] ,M Pr[ = ( M P ,M P )] · Pr[ ( j i K , 1 0 , i K k h h ( ) 2 (4) 2 2 ` ` 4 ≤ , = 2 n n 2 2 where (1) follows from the definition of PH-DbH , (2) is an equivalent form of (1) , (3) follows ? from the independence of and K K . Therefore, and finally (4) follows from Eqn. (16) h h we have 2 4 ` (3 ) = (18) ,` . cf n 2 2 Therefore, the first part of Theorem 3 follows from Eqn. (17) and Eqn. (18). Bounding Weak-Cover-free and Weak-Block-Wise Universal advantage of n . We know that PolyHash is an `/ PH3-DbH -AXU hash function. Therefore, by doing a 2 similar analysis of the weak-cover-free and weak-block-wise universal advantage of PH3-DbH PH-DbH , we have as similarly done for 2 ` ` , (19) . (3 ,` ) = ) = ,` (2 wuniv wcf 2 n n 2 2 Therefore, the second part of Theorem 3 follows from Eqn. (19). Remark 5 . We would like to point out that the security proof for the MAC part of GCM- SIV2 (Lemma 2 of [ ]) follows a similar analysis as used in the proof of Theorem 3. IM16 The MAC part of GCM-SIV2 uses two independent keyed hash functions to generate the two hash e values and independent random permutations in the sum function. Therefore, it provides the desired security even with much weaker assumption on the underlying hash function. To be more precise, the almost universal property of the hash function is sufficient and there is no need to have the cover-free or the blockwise universal restriction of hash function. 5 Parallel Block Cipher Evaluation In this section, we instantiate the function using block ciphers that operate in a DbH DbHtS construction. We analyze the parallel mode, results in a parallel block cipher based and the LightMAC_Plus construction, which underlying hash function of the PMAC_Plus PMAC_Plus-Hash and LightMAC_Plus-Hash respectively. We make a little we refer to as PMAC_Plus and twist in their design to construct the two-keyed variants of , LightMAC_Plus which we refer to as and 2K-LightMAC_Plus respectively and prove their 2K-PMAC_Plus DbHtS PRF security using our generalized security result for the two-keyed construction. The double block hash function for 2K-PMAC_Plus and 2K-LightMAC_Plus , which we refer to as 2K-PMAC_Plus-Hash and 2K-LightMAC_Plus-Hash respectively, are structurally almost similar to the LightMAC_Plus-Hash , except the following: and the PMAC_Plus-Hash fix0 and fix1 functions (to incorporate the block-separated feature). (i) We use the ′ 5 fix1 by 2 before applying the (ii) We multiply function on it Λ (see Fig. 5.1). and their The algorithms of the function for the PMAC_Plus and the LightMAC_Plus DbH respective two-keyed variants are depicted in Figure 5.1. 5 If we do not multiply by 2 , then there exists a trivial birthday bound attack.

26 26 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF ) K,M ( LightMAC_Plus-Hash PMAC_Plus-Hash ( ) K,M ∗ ′ ′ ′ ′ ′ ∗ M ; ; 1 M ‖ : ‖ . . . ‖ M 1 : M 10 ← ← M ‖ 10 M ; M l 1 ′ ′ ′ : 2 : ← ; M ‖ . . . ‖ ∆ M M 2 ); 1 ( E E ← ( ); ∆ 0 1 K K 0 l 1 to for j j for : 3 to = 1 l ; ; l : 3 = 1 ′ j 2 j ′ : ; 4 X M ‖ = 〉 j 〈 j j ⊕ X 2 = ⊕ ∆ M ; ∆ 2 4 : j 1 0 s j X = 5 ( Y E ); : j K j ); E = ( Y : 5 X j K j ′ ′ Y Y Σ : 6 ⊕ = ⊕ . . . ⊕ Y ; 2 1 l ⊕ 6 : Σ = Y ⊕ Y ; Y ⊕ . . . 1 2 l 2 ′ l 1 l − − ′ l − 1 l − 2 Y · ; Λ : 2 Y ⊕ . . . ⊕ · ⊕ Y = 2 7 2 1 l ⊕ Y ⊕ . . . 7 Y · ; ⊕ : Y · = 2 Λ 2 1 2 l ′ ′ ′ ′ ); , (Σ return Λ ); , (Σ return Λ ) 2K-LightMAC_Plus-Hash K,M ( ( K,M ) 2K-PMAC_Plus-Hash ′ ′ LightMAC_Plus-Hash ( K, M ); ← Λ) 1 : (Σ , ) ← : ( K, M ); (Σ PMAC_Plus-Hash , Λ 1 ′ ′ ′ ′ 2 ); (2Λ : Σ = fix0 (Σ fix1 ); Λ = ); fix0 2 : ); Λ = fix1 (2Λ Σ = (Σ return (Σ , Λ); Λ); , (Σ return Figure 5.1: Left: PMAC_Plus-Hash and 2K-PMAC_Plus-Hash ; Right: LightMAC_Plus- ′ ′ ′ Hash -bit counter. M and 2K-LightMAC_Plus-Hash denotes parsing with s M ‖ M ... ‖ 1 l ′ n bit blocks for PMAC_Plus-Hash ; of message − s bit blocks for LightMAC_Plus- into ( n M 〈 j 〉 denotes the Hash s -bit binary representation of integer ). . j s 5.1 Bounding Cover-free and Universal Advantages , In this section, we bound the cover-free and universal advantages for 2K-PMAC_Plus-Hash , PMAC_Plus-Hash and LightMAC_Plus-Hash . To do so, we first 2K-LightMAC_Plus-Hash need to identify the set of bad hash keys for PMAC_Plus-Hash , 2K-PMAC_Plus-Hash , and LightMAC_Plus-Hash . Note that, for all these hash functions, 2K-LightMAC_Plus-Hash Π (we consider the underlying set of bad hash keys is nothing but the set of permutations only the information theoretic setting as switching to the computational setting from the information theoretic one is done by a standard hybrid argument). Now, to identify the set of bad hash keys, we develop a few notations, which will also be required for the analysis of the cover-free and the block-wise universal advantage of these double block hash functions when the hash key is sampled from outside of the set of bad hash keys. For a q ( M Notations. ,...,M tuple of distinct messages ) , w.l.o.g we assume that the q 1 q messages is a multiple n for PMAC_Plus and multiple of message size(# of bits) for all n −d log is the maximum message length (# of blocks). ` e ) for LightMAC_Plus ( ` , where 2 [ i,j [ q ] and define the set NEQ ] : := { α We consider two distinct indices ∈ min { l } ,l ∈ j i i,j i j NEQ 6 = M M . In other words, the set } ∪ { α : min { l }} ,l ,l } + 1 ≤ α ≤ max { l i j j i i,j α α j i -th message are not equal. -th and contains all the positions, where the message blocks of min min NEQ NEQ denote the minimum and second minimum element of the set and 2 i,j i,j . NEQ i,j 2K-PMAC_Plus-Hash PMAC_Plus-Hash . Recall that a Bad Hash Keys for and or PMAC_Plus-Hash is a random permutation. We say hash key for 2K-PMAC_Plus-Hash 2K-PMAC_Plus-Hash is bad , if any of the following events holds: that a hash key for i i X ∈ [ q ] ,α ∈ [ l (a) ] such that ∃ ZeroOneX: . = 0 or X i 1 = i α α i ZeroY: ∃ i ∈ [ q ] ,α ∈ [ l . ] such that Y (b) 0 = i α (c) 3CollX: ∃ i 6 = j ∈ [ q ] ,i where ,i NEQ ,i min ∈ { i,j } ,α ∈ [ l ∈ ,γ ] ,β ∈ [ l ] i i 3 2 1 i,j 2 1 i i i 2 1 3 γ . X α 6 = = X β 6 = = X , such that α γ β

27 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 27 and The set of bad hash keys for 2K-PMAC_Plus-Hash PMAC_Plus-Hash is same and we pp ⊆ Perm K denote it as . Therefore, to bound the probability that a hash key, sampled bad pp K uniformly at random from the hash key space, falls in the set , is same as bounding bad ∨ ZeroY ∨ 3CollX . Therefore, we bound the probability of the event Bad-Hash := ZeroOneX as follows: Bad-Hash the probability of - Hash ] ≤ Pr[ := Pr[ ] + Pr[ ZeroY ] + Pr[ 3CollX ] Bad ZeroOneX bh q` 2 ( q` q` q` − 1) ≤ + + n n n n q` − 2 2 (2 1 − 1) 2 − 2 2 q` 5 q ` + . (20) ≤ n 2 n 2 2 Bad Hash Keys for LightMAC_Plus-Hash . For 2K- 2K-LightMAC_Plus-Hash and and LightMAC_Plus-Hash , we consider an empty set of bad hash key LightMAC_Plus-Hash and as a result we have = 0 . bh In the following, we bound the cover-free and the block-wise universal advantage of 2K-LightMAC_Plus-Hash 2K-PMAC_Plus-Hash and . pp pp 2 n - Hash is a ( K + 22) Theorem 6. , (18 ` 2K - 2 PMAC _ ) -cover-free, ( K Plus + , (2 ` / bad bad n 2 n ) -block-wise universal DbH function and 2K - 5) _ Plus - Hash is a (Φ , 16 / 2 / 2 ) - LightMAC n ) / 2 (Φ 4 -block-wise universal DbH function. In both the cases, we have assumed cover-free, , 1 − n 2 / 3 . ` < that Similarly, we bound the cover-free and the block-wise universal advantage of PMAC_Plus- and LightMAC_Plus-Hash as follows: Hash pp pp n 2 - Hash , Theorem 7. PMAC _ Plus , (6( ` 2 + 1)) K ) -weak-cover-free, ( K ( / is a (2 ` + bad bad n 2 n is a DbH function and LightMAC _ Plus - Hash / (Φ , 4 / 2 3) ) ) - 2 -weak-block-wise universal n , 2 / 2 -weak-block-wise universal ) weak-cover-free and DbH function. Here also we have (Φ − 1 n ` < / 3 . 2 assumed that Proofs of Theorem 6 and Theorem 7 are deferred to Sect. 5.4. Assuming that these 2K-PMAC_Plus 2K-LightMAC_Plus and theorems hold, we now prove the PRF security of PMAC_Plus LightMAC_Plus in Sect. 5.3. in Sect. 5.2 and that of and 5.2 PRF Security of 2K-PMAC_Plus and 2K-LightMAC_Plus and 2K-LightMAC_Plus are two parallel mode of block cipher based 2K-PMAC_Plus DbHtS . Algorithmic description of these two constructions instantiations of the two-keyed are depicted in Fig. 5.2. ( K 2K-LightMAC_Plus ,K K ,M ( 2K-PMAC_Plus ) ,M ,K ) 2 1 2 1 K ); , M ); , M K ( 2K-LightMAC_Plus-Hash ← Λ) , (Σ : 1 1 : (Σ , Λ) ← 2K-PMAC_Plus-Hash ( 1 1 2 ⊕ E ⊕ (Σ) (Σ) E E ← T : 2 (Λ); E : T ← (Λ); K K K K 2 2 2 2 ; return return T ; T Figure 5.2: Algorithm for 2K-PMAC_Plus 2K-LightMAC_Plus . The following two results show the PRF security bound of 2K- 2K-PMAC_Plus and LightMACPlus . ( PRF-Security of 2K-PMAC_Plus ). Let K and M be two non-empty Theorem 8 n n : K×{ 0 , 1 } be a block cipher. Then, any distinguisher with →{ 0 , 1 } E finite sets. Let

28 28 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF t , making tuple of distinct messages each of at most ` blocks long, running time at most q from a - Plus [ E ] _ n -bit uniform random function by, can distinguish PMAC 2K 2 3 2 3 q ` 5 q 9 q q ` 25 q` prp prf ′ `q + 2 ,t + ) + ( q,`,t ) ≤ 2 + Adv + , + ( Adv E - E 2K PMAC ] Plus [ _ 2 2 n n n n n 2 2 2 2 2 2 ′ is about t where E for `q + 2 t + 2 times plus a time complexity necessary to compute q n − 1 ` < / 3 . and 2 (20) , Theorem 6 and part ( ii ) of Theorem 2. Proof. Proof of the theorem follows from Eqn. ( PRF-Security of 2K-LightMAC_Plus ). Let Theorem 9 and M be two non-empty K n n K×{ 0 , 1 } finite sets. Let →{ 0 , 1 } : be a block cipher. Then, any distinguisher with E t tuple of distinct messages each of at most ` blocks long, q running time at most , making - LightMAC _ Plus [ E ] from a n -bit uniform random function by, can distinguish 2K 3 q 21 q prp prf ′ `q,t ) + ( q,`,t ) ≤ 2 Adv ( , Adv + E _ LightMAC E ] 2K Plus [ - n 2 n 2 2 ′ times and is about t plus a time complexity necessary to compute E for `q + 2 q t where − 1 n 2 / 3 ` < . As there is no set of bad hash keys, = 0 and the rest of the proof follows from Proof. bh ( ii ) Theorem 6 and part of Theorem 2. 5.3 PRF Security of PMAC_Plus and LightMAC_Plus PMAC_Plus and LightMAC_Plus are two instantiations of the three-keyed DbHtS . Although, these constructions are existing ones, as proposed by Yasuda [ Yas11 ] and Naito [ Nai17 ] respectively, for the sake of completeness of this paper, we state and prove the security of these two constructions in our setting. We recall these two constructions in Fig. 5.3. K ) ( ,K LightMAC_Plus ,M ,K K ,M ( ,K PMAC_Plus ,K ) 1 2 3 3 2 1 ′ ′ ′ ′ ); , M K ( LightMAC_Plus-Hash ← ) (Σ Λ , : (Σ , 1 Λ 1 ) ← PMAC_Plus-Hash ( K : , M ); 1 1 ′ ′ ′ ′ (Λ ); (Λ ); (Σ E ⊕ ) ⊕ (Σ ) E ← : : T ← E E 2 T 2 K K K K 3 3 2 2 return ; return T ; T Algorithm for Figure 5.3: LightMAC_Plus . PMAC_Plus and and LightMAC_Plus . The following two results show the PRF security bound of PMAC_Plus ( PRF-Security of PMAC_Plus ). Let K and M be two non-empty finite Theorem 10 n n : K×{ 0 , 1 } sets. Let →{ 0 , 1 } E be a block cipher. Then, any distinguisher with running time at most q tuple of distinct messages each of at most ` blocks long, can , making t PMAC _ Plus [ E ] from a n -bit uniform random function by, distinguish 3 2 3 2 ` q 7 12 q q` 5 ` q prf prp ′ Adv + 2 ,t Adv ) + 3 ≤ ) q,`,t ( `q ( + + + , E E [ ] PMAC Plus _ 2 n n 2 n n 2 2 2 2 2 ′ for is about t plus a time complexity necessary to compute E where `q + 2 q + 2 times t n − 1 and ` < 2 / 3 . Proof. Proof of the theorem follows from Eqn. (20) , Theorem 7 and part ( iii ) of Theorem 2.

29 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 29 PRF-Security of LightMAC_Plus ). Let K and M be two non-empty Theorem 11 ( n n 1 } : →{ 0 , , } 1 be a block cipher. Then, any distinguisher with 0 K×{ E finite sets. Let q tuple of distinct messages each of at most ` blocks long, running time at most t , making _ Plus E ] from a n -bit uniform random function by, can distinguish [ LightMAC 3 q 9 prf prp ′ ( q,`,t ) ≤ Adv Adv , ) + ( `q,t 3 E E [ Plus LightMAC ] _ n 2 2 ′ is about t plus a time complexity necessary to compute E for `q + 2 t times and q where n 1 − / 3 . ` < 2 ( iii ) of Theorem 2 and the Proof of the theorem follows from Theorem 7, part Proof. (as there is no set of bad hash keys). = 0 fact that bh Note. , as proven by Yasuda [ Yas11 ], is The original security bound of the PMAC_Plus 3 3 2 n roughly / (we only mention the dominating term of the security bound). But, ` q 2 PMAC_Plus according to Theorem 10, the dominating term of the security bound of the n 2 3 `/ , a substantial improvement of the security bound over its existing one. A 2 is q + similar improvement in the security bound is also done in 1k-PMAC_Plus 17 ] over [ DDN . However, we are not gaining any security improvement for . PMAC_Plus LightMAC_Plus 5.4 Proof of Theorem 6 and Theorem 7 In this section, we mainly prove Theorem 6. In particular, we bound the cover-free advan- tage and the block-wise universal advantage of 2K-LightMAC_Plus- and 2K-PMAC_Plus-Hash . Using parts of these analysis, we prove Theorem 7. Hash 5.4.1 Cover-free and Block-wise universal Advantage of 2K-PMAC_Plus-Hash We bound the cover-free and the block-wise universal advantage of 2K-PMAC_Plus-Hash . We fix three distinct messages M Bounding Cover-free-advantage. ,M M and j i k i i 6 2 1 CollX are distinct and = X i,j,k := } X , where i and define the event ,i ∈ { 2 1 ijk α β ∈{ l , β are distinct. , min NEQ ∈ α } , min [ NEQ l ] 2 i i ,i i i ,i 1 2 2 1 2 1 For brevity, let us introduce the following notations: ′ ′ • E . := (Σ = b, Λ b ⊕ Λ ) = ⊕ Σ b,b k i j i pp Perm . • K := \K g bad 3CollX ZeroOneX ∧ ZeroY . ∧ := • Good Π ∈ K by P and . Now we denote the probability of the joint event that holds CF cf g ijk Acording to the definition of cover-free advantage (see Definition 1), we have ∑ ′ := ] ∈K Π , E Pr[ P cf g b,b ′ } , 0 ∈{ b,b 1 ∑ ∑ ′ Π , ) ,δ δ = ) = ( ∆ E , (∆ , Pr[ ] ∈K b,b 0 g 1 1 0 ︷︷ ︸ ︸ ′ ∈{ δ , 0 ( } ,δ b,b Good ): 1 0 1 ′ b,b ∑ ∑ ∑ ′ = + (21) b,b 1 , 0 ′ ,δ δ Good ): ): ,δ δ ( ( Good 0 , 1 , b,b } ∈{ 1 0 0 1 ′ ︸ ︸ ︷︷ ︸ ︷︷ ︸ 1 , 0 ) b,b ( ) 6 =( ν μ 6 Although the event CollX involves only two indices, we define it over three indices as the set of bad ijk hash keys are themselves defined over three indices.

30 30 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF μ : We bound μ Bounding as follows: ∑ = · )] ,δ δ ) = ( Pr[ E ∆ , Pr[(∆ , Π ∈K μ | (∆ )] , ∆ ,δ ) = ( δ 0 0 1 1 0 g 0 0 , 1 1 1 ︸ ︷︷ ︸ ,δ ( δ Good ): 0 1 ψ i ) to a fixed ( δ By conditioning ) , we fix all the X (∆ , values. This gives a collision ∆ ,δ 1 0 0 1 α j i i relation values: ( i,α ) ∼ ( j,β ) iff X among the X = X ∼ is a good . Since, ( δ ) ,δ 1 0 α α β i i 7 i Y 0 , 1 , , and hence X pair / (the corresponding permutation output of X ∈{ ) values } α α α n , 1 } \{ are wor sampled from δ { ,δ 0 } . Now the event ( Σ ) gives a ⊕ Σ 0 = 1 , Λ = ⊕ Λ k j i i 0 1 variables system of two linear equations in Y { j j i i Y := L ⊕ , ...Y 1 = ⊕ Y Y ⊕ ⊕ ... 1 1 1 l l i j E = j j i l i l j i . = 0 ... ⊕ 2 Y ⊕ Y Y ⊕ Y := 2 L ⊕ ... 2 2 2 1 1 l l i j over L By applying the collision relation and L ∼ , we obtain a reduced system of 1 2 ∼ ∼ equations, denoted as is 2 and hence, by applying . It is easy to see that the rank of E E 1 . Therefore, Lemma 1, we have ≤ ψ n (2 +1) 3 − ` 2 ∑ 1 4 1 − n (2 3 + 1) / ≤ ` where , . μ ≤ · Pr[(∆ , ∆ ≤ ) = ( δ )] ,δ 1 1 0 0 2 n n + 1) 3 2 − ` (2 2 ): ,δ δ ( Good 0 1 (22) Bounding : Here we have ν ∑ ∑ ′ ′ ν + = b,b b,b Good ): Good ( ,δ δ ( ): ,δ δ 0 0 1 1 CollX ∧ ijk ∧ CollX ijk ∑ ′ )] ,δ δ ) = ( ∆ , Pr[(∆ · )] ,δ Pr[ E δ = , Π ∈K ) = ( | (∆ ∆ , 0 1 0 g 1 b,b 1 0 0 1 ( Good δ ): ,δ 1 0 ∧ CollX ijk ∑ ′ )] ,δ + ) = ( ∆ , Pr[(∆ · Pr[ E )] δ , Π ∈K ,δ | (∆ δ , ∆ ) = ( (23) 1 0 g 1 b,b 0 1 0 0 1 Good ): ( ,δ δ 0 1 ∧ CollX ijk Now, we follow the similar approach as in the previous case. Here, we argue that (i) if ∼ E is at least 1 and (ii) CollX occurs, then the rank of the reduced system of equations ijk ∼ does not occur) the rank of the reduced system of equations E else (i.e. is CollX (see 2 ijk + ′ = 0 ,b b = 0 , we need the event ZeroY as otherwise Claim 5, [DDN 17]). Note that, for ∼ CollX E the rank of the reduced system of equations occurs) would have been 1 (when ijk M (say there are two messages M ‖ and , then Y = 0 makes the first equation trivial). M 2 2 1 1 Hence, we have { 1 occurs CollX if n ijk ` − 3 (2 1) − 1 ′ , E )] = ) = ( δ ∆ , Π ∈K (∆ | ,δ Pr[ g 0 0 1 1 b,b 1 else n (2 − 1) − ` 3 2 Both these bounds follow from Lemma 1. Therefore, from Eqn.(23) ∑ ∑ ∆ δ , Pr[(∆ )] ) = ( )] ,δ δ ,δ Pr[(∆ ) = ( , ∆ 1 1 0 1 1 0 0 0 + ≤ ν n n 1) 1) − 3 ` − − ` 3 − (2 (2 2 1 ,δ δ CollX ( ): Good ∧ 1 0 ijk ( Good ,δ ): δ ∧ CollX 1 0 ijk 1 , ∆ Putting the inequalities (i) Pr δ ∧ ,δ Good )] = [(∆ ) : ,δ | δ ( , (ii) ) = ( n n 0 1 1 0 1 0 1) (2 2 − n n n 1) CollX − |≤ 2 , we have (2 δ |≤ ,δ CollX ) : Good ∧ 2 · 3 ` and (iii) | ( ijk 0 ijk 1 n n n 3 ` + 1) 2 6( 1 1 1) − 2 (2 · ` · ν (24) ≤ · , + ≤ n n n n n 2 n n − − 1) 3 (2 (2 − − 3 ` − 1) 2 1) − 2 (2 2 1) (2 ` 2 7 ( δ ZeroOneX ,δ or occur. is said to be a good pair if none of the three events 3CollX , ZeroY ) 1 0

31 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 31 n − 1 ≤ (2 − 1) / 3 . where ` ` 18 +22 1 − n P Combining Eqn.(21), Eqn.(22) and Eqn.(24), we obtain ≤ (2 − ` where , ≤ n 2 cf 2 , and hence we can set 1) 3 / ` + 22 18 n − 1 3 , assuming / ≤ (2 (25) ` . − 1) ,` (3 ) = cf n 2 2 and M We fix two distinct messages Bounding Block-wise-universal advantage. i i i 2 1 X X and define the event are distinct and = CollX M := } , where i i,j ,i ∈ { 2 ij j 1 α β l α are distinct. With a similar argument as , min NEQ ] ∈{ [ l , min , β NEQ } ∈ 2 i i i ,i i ,i 2 1 1 1 2 2 used in the case of bounding the cover-free advantage, one can see that the number of n 2 ∆ ) for which CollX . holds is at most to , (∆ · 2 ` ij 1 0 For brevity, let us introduce the notation: 1 E • := Σ ⊕ Σ b. = j i b 2 = ⊕ Λ := Λ • b. E i k b holds Now we denote the probability of the joint event that Π ∈K UNIV by P and . univ g ij According to the definition of block-wise universal advantage (see Definition 3), we have ∑ ) ( 1 2 , ∈K max ∈K Pr[ E Π ] , Π E ] , Pr[ P := g g univ b b 0 , } ∈{ b 1 Using similar approach as used in case of the cover-free case, here we have, ∑ 1 1 1 ] ∈K Π , E ] + Pr[ , ∈K Π E ] = Pr[ ∈K Π , Pr[ E g g g 0 1 b 0 , 1 } b ∈{ ∑ ) = ( )] ∆ ,δ , Pr[(∆ δ 0 0 1 1 ≤ n 2 (2 − ` − 1) 1 ): Good ( ,δ δ 1 0 ∑ + )] δ ,δ Pr[(∆ ) = ( , ∆ 1 0 1 0 δ ): Good ∧ CollX ( ,δ ij 0 1 ∑ )] ,δ δ ) = ( ∆ , Pr[(∆ 1 0 1 0 + n 2 1) − − (2 ` 1 CollX ,δ ( ): Good ∧ δ ij 0 1 1 , Pr ∆ [(∆ ) = ( δ | ≤ ,δ Good )] = Putting the inequalities (i) ) : ,δ δ ( | , (ii) n n 0 1 0 1 1 0 2 1) − (2 n n n − 1) , (iii) | ( δ (2 ,δ | ≤ ) : Good ∧ CollX CollX | ≤ 2 2 · 2 ` and (iv) | ( δ ∧ ,δ Good ) : 1 1 ij 0 ij 0 n n 1) , we have (2 2 − n n n ∑ 1 1) · (2 2 ` 2 2 − 1 , ≤ Π ∈K ] + Pr[ E + g b n n n n n n n − (2 2 − 1)(2 ` − 2 ` − 1) − 1) − ` 2 − (2 2 1) (2 2 − 1)(2 } 1 0 ∈{ b , 2 + 5 ` , ≤ n 2 n − 2 or (ii) assuming ` . Here use the fact that (i) if b = 1 ≤ b = 0 2 CollX doesn’t and ij 1 ∆ ) given a fixed value of (∆ E occurs, then the rank of the reduced system of equations , 0 1 b is at least 1 . With a similar argument, one can show that ∑ + 5 ` 2 2 E Pr[ ] ∈K , ≤ Π , g b n 2 0 1 } b , ∈{ and hence we can set ` + 5 2 2 n − . assuming ` ≤ 2 (26) , (2 ,` ) = univ n 2 The first part of Theorem 6 follows from Eqn. (25) and Eqn. (26).

32 32 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF 5.4.2 Cover-free and Block-wise universal Advantage of 2K-LightMAC_Plus-Hash In this section, we bound the cover-free and the block-wise universal advantage of 2K- 2K-LightMAC_Plus-Hash LightMAC_Plus-Hash , we have considered an . Recall that, for empty set of bad hash keys. Since there is an empty set of bad hash keys, we Bounding Cover-free-advantage. sample the hash key, i.e., the random permutation Π , from the set of all permutations for and M bounding the cover-free advantage. First, we fix three distinct messages . ,M M j i k ′ , 1 } , we write the two equations b,b Similar to the previous analysis, for two fixed ∈ { 0 ′ Σ = b and Λ -variables as follows: ⊕ Λ Y = b Σ in terms of the ⊕ k i j i { j j i i ) = b Y ⊕ ... ⊕ ) ⊕ ( Y ⊕ Y ⊕ ... Y ( 1 1 l l i j E = l i k i l ′ k i k Y (2 ... ) ⊕ (2 Y 2 Y ⊕ ⊕ ⊕ ⊕ . 2 Y ... b ) = 1 1 l l i k i 1 Y and Given the two equations are consistent, one can always find two random variables α i 2 Y , where i is ,i E ∈{ i,j,k } and distinct α ∈ NEQ such that the rank of ,β ∈ NEQ 1 2 ij ik β Π to denote Pr [ CF 2 holds, . Again we use the notation ∈ Perm ] . Therefore, we have P cf ijk ∑ ′ ⊕ Perm ∈ Π , = b Pr[Σ ] Σ = b, Λ ⊕ Λ P = k i j i cf ′ } , 0 ∈{ b,b 1 ∑ (1) 1 16 , (27) ≤ ≤ n 2 n ` 2 + 2) (2 3 − 2 ′ 1 } b,b ∈{ 0 , n − 1 (1) 2 follows by applying Lemma 1 and we assume that ` ≤ / 3 . Hence, we can set where 16 ,` ) = (3 (28) . cf n 2 2 Bounding Block-wise-universal-advantage. To bound the block-wise-universal advantage, we first fix two distinct messages M . By definition, we need to bound and M j i ) ( ∑ ∑ (29) , = max Perm ∈ Pr[Σ Π ⊕ Σ b, = b, Π ∈ Perm ] , P = Λ ⊕ Pr[Λ ] i j j i univ , b 1 0 } 1 ∈{ , 0 ∈{ b } P ∈ [ UNIV holds, Π Pr Perm ] . Now, we bound these is a shorthand notation for where univ ij terms case by case as follows: Perm Bounding Pr Σ = 1 , Π ∈ [Σ ] : Σ ⊕ Σ = 1 implies the following non-trivial ⊕ i j i j equation: j j i i ⊕ . 1 ) ⊕ ( Y ⊕ ) = ...Y ... ⊕ Y Y ( 1 l 1 l i j 2 1 ≤ , when From Lemma 1, the above equation holds with probability at most n n 2 2 − 2 ` +1 n − 2 ` ≤ 2 . ∈ Bounding = 0 , Π Σ Perm ] : This is proven in the following sub-cases: Pr[Σ ⊕ i j NEQ We first consider the case = l , otherwise the . Observe that, | 1 | ≥ l • i j i,j | NEQ | probability would have been zero. Therefore, let us assume = s > 1 . Now, i,j Σ = Σ implies the following equation: j i j i j i ⊕ ⊕ Y , 0 ) ⊕ ( ... Y ( ) = ⊕ ... ⊕ Y Y α α α α s 1 1 s | α ,...,α , we obtain at least one random ∈ NEQ where . Since, 1 NEQ > | 1 s i,j i,j ? Y α 1 , where variable ∈ NEQ for which the rank of the above equation is i,j α and hence from Lemma 1, the above equations holds with probability at most 2 1 2 − n . 2 ≤ ≤ , when ` n n 2 +1 ` 2 − 2

33 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 33 Now, we consider the case when l = l • . W.l.o.g we assume that l 6 > l . Then j i i j ′ ∈ NEQ + 1 . Let NEQ ,...,l l := NEQ and let us also consider \{ l } + 1 ,...,l i j j i i,j i,j i,j ′ that | = s . Note that, s can also be zero. Therefore, | NEQ = Σ Σ implies j i i,j i i i i j j Y ( 0 ) ⊕ ( Y , ) = ⊕ ... Y Y ⊕ ... ) ⊕ ( Y ⊕ Y ⊕ ... ⊕ ⊕ α α α α l +1 l s s j i 1 1 ′ . The above equation is non-trivial and hence its rank is ∈ NEQ where ,...,α α 1 s i,j . Therefore, from Lemma 1, the above equation holds with probability at most 1 1 2 2 n − ≤ , when ` ≤ 2 . n n 2 − 2 2 ` +1 Λ Pr ⊕ Λ Bounding = 1 , Π ∈ Perm ] : Λ [Λ ⊕ gives rise to the following non-trivial 1 = j i i j equation: j j i l i l j i 2 1 ⊕ ... ⊕ , Y ) = Y (2 ⊕ ) Y ⊕ Y 2 ... (2 l 1 1 l i j 1 2 n − 2 which holds with probability at most ` ≤ 2 ≤ . , when n n − 2 2 ` +1 2 ⊕ Pr [Λ Λ Bounding : Similar to the earlier analysis, we bound the = 0 , Π ∈ Perm ] j i probability of the event in different sub-cases as follows: Similar to the previous argument, if l and = l = 1 • | NEQ | , then the probability i j i,j . Then, | = Λ | = would have been zero. Hence, we assume that 1 NEQ Λ s > i j i,j implies the following equation: j l i − α 1 − 1 − α i − l j i s 1 i ( 2 ⊕ Y Y ⊕ ) ... ( Y ⊕ , ⊕ Y 2 0 ) = α α α α s 1 1 s where α ,...,α ∈ NEQ . Since, the above equation is non-trivial, from Lemma 1, s 1 i,j 2 1 2 − n . ≤ the probability that the above equation holds is at most , when ` ≤ 2 n n 2 2 +1 ` − 2 For the case of l NEQ 6 = l . (w.l.o.g we assume l • > l ∈ ), then l ,...,l + 1 j i j i i j i,j ′ ′ := NEQ NEQ \{ l . + 1 ,...,l s } and let us also consider | NEQ Moreover, = | j i i,j i,j i,j Therefore, the event Λ = Λ implies i j ( ( ) ) l l i i − − − α − l i i 1 1 − l α i j s 1 i i ⊕ Y 2 Y ⊕ ... 2 ... ⊕ 2 Y Y 2 ⊕ ⊕ +1 l l α α i j 1 s ( ) j − 1 1 j − l − α α − l 1 s j j 2 2 ... ⊕ ⊕ Y ⊕ Y = 0 , α α s 1 ′ ,...,α α ∈ NEQ where , from Lemma 1, . Since, the rank of the above equation is 1 1 s i,j 1 2 . the probability that the above equation holds is at most ≤ n n 2 +1 2 2 ` − Therefore, we have ∑ ∑ 4 4 b, = Λ ⊕ Pr[Λ ≤ ] Perm . ∈ (30) Π , b, ] ≤ Pr[Σ ⊕ Perm ∈ Π Σ = j i j i n n 2 2 1 } b ∈{ 0 , } 1 0 ∈{ b , 4 P ≤ Therefore, from Eqn. (29) and Eqn. (30) we have , and hence we can set n univ 2 4 (31) . ,` ) = (2 univ n 2 The second part of Theorem 6 follows from Eqn. (28) and Eqn. (31).

34 34 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF 5.4.3 Weak-cover-free and Weak-block-wise-universal Advantage of PMAC_Plus- Hash PMAC_Plus-Hash , we have For + 1) ` 6( pp , Λ = Pr[Σ = Λ P , Π = Σ Perm \K ∈ , ] ≤ i wcf k j i bad 2 n 2 ( ) + 3 2 ` pp pp Π ∈ Perm \K = Σ P ] , Pr[Λ = max = Λ Pr[Σ , Π ∈ Perm \K , ≤ ] i j j i wuniv bad bad n 2 The bound for P PMAC_Plus-Hash with follows directly from the cover-free analysis of wcf ′ b = = 0 and the bound for P b follows directly from the universal analysis with b = 0 . wuniv Hence, we have 6( ` + 1) + 3 ` 2 ,` (32) ) = , . (2 ,` ) = (3 wcf wuniv 2 n n 2 2 The first part of Theorem 7 follows from Eqn. (32). 5.4.4 Weak-cover-free and Weak-block-wise-universal Advantage of LightMAC_Plus- Hash , we have For LightMAC_Plus-Hash 4 P ∈ = Σ ≤ , Λ ] = Λ Perm , Π = Pr[Σ , k i i j wcf n 2 2 ( ) 2 , Π ∈ Perm ] , P Pr[Λ = Λ , Π ∈ Perm ] Pr[Σ ≤ = Σ = max wuniv j j i i n 2 P 2K-LightMAC_Plus- The bounds are directly derived from the bound for P used in and wuniv wcf ′ in the first case and b with the restriction that = 0 = b = 0 in the second. Hash b Hence, we have 2 4 . (33) , (2 ,` ) = ,` ) = (3 wuniv wcf n n 2 2 2 The second part of Theorem 7 follows from Eqn. (33). 6 Sequential Block Cipher Evaluation function using block ciphers that operate in In this section, we instantiate the DbH construction. We DbHtS sequential mode, results in a sequential block cipher based SUM-ECBC and the 3kf9 construction, which analyze the underlying hash function of the ECBC-Hash and f9-Hash respectively and we also make a little twist in their we refer to as SUM-ECBC design to construct the two-keyed variant of the 3kf9 . As a result, and the SUM-ECBC , which we refer to as 3kf9 we propose a two-keyed variant of the and the and 2K-ECBC_Plus respectively and prove their PRF security using our generalized 2Kf9 security result for the two-keyed DbHtS construction. We refer to the DbH function for 2K-ECBC_Plus and 2Kf9 as 2K-ECBC-Hash and f9-Hash (for , we use the same DbH function as used for 3kf9 ) respectively. 2K-ECBC-Hash is 2Kf9 structurally very similar to the ECBC-Hash , except the following that 2K-ECBC-Hash uses fix0 fix1 functions to incorporate the block-separated feature, which are absent in the and ECBC-Hash . is depicted in Figure 6.1. DbH function for 2K-ECBC_Plus and 2Kf9 The algorithms of the

35 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 35 f9-Hash ( K,M ) ) K,K ECBC-Hash ,M ( ? ′ ′ ′ ′ ′ ∗ ′ ′ ′ ∗ : M M ; M M ‖ ← ; 1 M 10 ‖ . . . M ‖ . . . ‖ 1 ‖ M ; M 10 ‖ M ← ; M : 1 l l 1 ′ ′ 0 ); 2 : , 0 ( ← ) ( Y, Y ( : 2 Y, Y ); ) ← ( 0 , 0 = 1 to l ; 3 3 : for : for j = 1 to l j ; ′ ′ ′ ′ ′ : E ← Y ; Y ⊕ X Y M = X : 4 4 ); X = M X = M ⊕ ( ; ; Y ⊕ K j j j ′ ′ ′ ′ ( ( E ( ← ) Y Y, Y ( : 5 : 5 ⊕ Y )); ← X Y ; , E ) X K K ? ′ ′ ′ ′ ′ ′ ); (Σ Y, Y ) = ( : Λ , Λ (Σ 6 6 ) ← ( Y, Y : ); ′ ′ ′ ′ Λ (Σ return return (Σ Λ , , ); ); 2K-ECBC-Hash ) ,M K,K ( ? ′ ′ ); Λ , M , (Σ : 1 K, K ( ECBC-Hash ← ) ? ′ ′ (Σ Σ ← fix0 ); 2 ); Λ ← fix1 (Θ : Λ); , return (Σ ′ ′ ′ Left: ; Right: f9-Hash . M ‖ ECBC-Hash ‖ ... Figure 6.1: M and 2K-ECBC-Hash M 1 l ′ into l many n bit blocks. denotes the parsing of the message M 6.1 Bounding Cover-free and Universal Advantages In this section, we bound the cover-free and universal advantages for , 2K-ECBC-Hash 2K-LightMAC_Plus-Hash , PMAC_Plus-Hash and LightMAC_Plus-Hash . To do so, we first 2K-ECBC-Hash and f9-Hash . Note that, for need to identify the set of bad hash keys for DbH both of the functions, the underlying set of bad hash keys is nothing but the set of Π or the set of pair of independent permutations (Π permutations , Π 2K-ECBC- ) (for 2 1 ). We consider only the information theoretic setting as switching to the computational Hash setting from the information theoretic one is done by a standard hybrid argument. To structure identify the set of bad hash keys, we revisit to an important notion called JN16 [ , GPR14 graph DNP16 , BPR05 ] and some of its important results which will help , us in bounding the cover-free and the block-wise universal advantage of 2K-ECBC-Hash and f9-Hash , when the hash key is sampled outside from the set of bad hash keys. Revisiting the Structure Graph. Here we briefly revisit the structure graphs, intro- duced by Bellare et al. [ BPR05 ] and recall some of their results which would be required in and be a message and without loss . Let M the security analysis of 2K-ECBC-Hash f9-Hash (in number of bits) is a multiple of n . Thus, of generality, we assume that the size of M M as a sequence of l many n -bit blocks as M = M [1] ‖ M [2] ‖ ... ‖ M [ l ] . Now, we partition M CBC-MAC ], based on an n -bit uniform random permutation Π , on BKR00 we apply [ CBC-MAC ( M ) be as follows: and let the intermediate chaining values of n M = 0 and Y = Π( Y Y ⊕ , [ i ]) for i = 1 ,...,l, 1 0 − i i . where i ] is the i -th block of message M [ M ′ M,M and a uniformly chosen random Informally, for any two fixed distinct messages Π ′ n G , ( M,M permutation ) with the set of nodes { 0 Π 1 } , we construct the structure graph ′ as follows: We follow the computations for M followed by those of M by CBC-MAC creating nodes which are labeled by the intermediate chaining variables Y . In this process, i if we arrive at a vertex already labeled, while not following an existing edge, we call 8 this event a collision. The sequence of alternating vertices and edges corresponding to the computations for a message M is called a message walk of M . Like for two distinct 8 We use the term collision and accident interchangeably.

36 36 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF messages, we can similarly construct a structure graph corresponding to a q tuple of 3 q distinct messages, where . It is needless to say that the structure graph constructed ≥ q message walks for each message q ,i for a tuple of [ M ] . q distinct messages is a union of ∈ i Let M ,...,M := ( ) denotes a tuple of q distinct messages and let G ( M ) denotes M q 1 the set of all structure graphs corresponding to the tuple of messages M (by varying Perm ). For a fixed structure graph V ∈ G ( M ) , let Coll ( V ) denote the set of all Π over . Now, we state the following two folklore results. collisions in V GPR14 ]) . For a fixed structure graph V ∈G ( M ) , Pr [ G ← $ G ( M Proposition 1 ) : (Lemma 2, [ V − n | Coll ( ) | ≤ ] 2 V . G = 2 $ ` a Pr [ G | ←−G ( M ) : Proposition 2 Coll ( G ) |≥ a ] ≤ ( (Corollary 1, [ JN16 ]) is ) . , where ` n 2 . the maximum number of message blocks in a single message among all messages in M -distinct messages := Now, we define the following events: for a fixed tuple of M q blocks long, we sample a permutation ,...,M ( ) , such that each message is at most ` M q 1 Π ) G Π ( M uniformly at random from . Now we and construct the structure graph Perm define three events as follows: Π • Coll ∃ i ∈ [ q ] such that the number of accidents in the i -th message walk in G M ( : ) 1 is at least 1 . Coll • such that the number of accidents between the i,j }⊆ [ q ] : i -th and the j -th ∃{ 2 Π M ( message walk in ) is at least 2 . G ] Coll : ∃{ i,j,k }⊆ [ q • susch that the number of accidents between the i -th, the j -th 3 Π k -th message walk in G and the ( M ) is at least 2 . It is easy to see that Coll ⇒ . We need the event Coll Coll in the analysis of 2K-ECBC-Hash 2 3 2 for the analysis of and f9-Hash . Coll 3 Using Proposition 2, we can easily bound the probabilities of each of these events as follows: 4 3 2 4 2 ` q ` q` q ≤ Coll ≤ Pr[ , Pr[ (34) . Coll ] , Pr[ Coll ] ] ≤ 3 2 1 2 2 n n n 2 2 2 . Recall that a hash key for 2K-ECBC-Hash is a pair 2K-ECBC-Hash Bad Hash Keys for , Π ) . Therefore, evaluation of 2K-ECBC-Hash on of independent random permutations (Π 1 2 q distinct messages M := ( M ) ,...,M gives two structure graphs; one a fixed tuple of q 1 Π 1 , denoted as G , and the other is := that is induced from the permutation Π G ( M ) 1 1 Π 2 , denoted as := G Π induced from the permutation ( M ) . Now, we say a hash key G 2 2 , ) (Π Π is bad , if either of the following holds: 1 2 or holds in either of G (a) Coll G . 2 1 1 Coll (b) holds in either of G . or G 2 2 1 ecbc ⊆ We denote the set of all bad hash keys as × Perm . Therefore, from Eqn. (34) K Perm bad Bad-Hash as follows: we bound the probability of 2 4 2 ( ) q ` q` (35) := Pr[ Bad-Hash ] . ≤ 2 + bh n 2 n 2 2 is a uniform random f9-Hash Recall that a hash key for . f9-Hash Bad Hash Keys for Π . Therefore, evaluation of f9-Hash on a fixed tuple of q distinct messages permutation M := ( M , ,...,M Π ) gives a structure graph, that is induced from the permutation q 1 Π G := G if either of the following holds: denoted as M ) . Now, we say a hash key Π is bad (

37 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 37 . (a) Coll holds in G 1 . (b) G Coll holds in 3 f9 We denote the set of all bad hash keys as (34) , we Perm ⊆ K . Therefore, from Eqn. bad bound the probability of ∨ Coll Bad-Hash as follows: := Coll 3 1 2 3 4 q` q ` ] + ≤ Bad-Hash := Pr[ (36) . bh n n 2 2 2 2K-ECBC- In the following, we bound the cover-free and block-wise universal advantage of . Hash f9-Hash and 2 ecbc n ecbc n 2 2 Theorem 12. 2K , 12 ` - / 2 ECBC - ) -cover-free and ( K Hash is a , 2 ` ( / 2 K )) -block- bad bad n − 1 - wise universal function, assuming ` + 1) / 2 . On the other hand, f9 DbH Hash is a ≤ (2 2 2 n f9 f9 2 n f9 n -cover-free, ( ) , ( K 84 -colliding , 3 ` ` / 2 K ) -block-wise universal and ( K / ) , 2 / 2 2 bad bad bad − 1 n 3 + 2) / ` . ≤ (2 function, assuming DbH Similarly, we bound the weak-cover-free and the weak-block-wise universal advantage of and collision of f9-hash as follows: ECBC-Hash and f9-Hash ecbc 2 n ecbc n Hash - ECBC Theorem 13. / 2 K is a ) -weak-cover-free and ( K ( , , 2 / 2 4 ) -weak- bad bad n − 1 ≤ (2 block-wise universal DbH function, assuming + 1) / 2 . On the other hand, f9 - Hash ` 2 n n f9 f9 2 2 ( / 2 is a DbH ) -weak-cover-free and ( K K -weak-block-wise universal ) 3 ` 18 / 2 ` , , bad bad n − 1 (2 function, assuming ` ≤ + 2) / 3 . Proofs of Theorem 12 and Theorem 13 are deferred to Sect. 6.4. Assuming that these theorems hold, we now prove the PRF security of and 2Kf9 in Sect. 6.2 2K-ECBC_Plus ECBC_Plus 3Kf9 and that of and in Sect. 6.3 respectively. 6.2 PRF Security of 2K-ECBC_Plus and 2Kf9 are two sequential mode of block cipher based instantiations 2K-ECBC_Plus and 2Kf9 DbHtS . Algorithmic description of these two constructions are depicted in of two-keyed Fig. 6.2. The following two results show the PRF security bound of 2K-ECBC_Plus and . 2Kf9 2Kf9 ,M ,K K ) ( ) ,K 2K-ECBC_Plus ( ,K K ,M 1 2 2 3 1 ′ ′ , M ); : 1 ); , M : K ( (Σ f9-Hash ← , ) Λ) Λ ← 2K-ECBC-Hash , K 1 , K (Σ ( 1 2 1 ′ ′ (Λ ); (Λ); E ⊕ (Σ) E ⊕ ) (Σ : T E 2 : T ← E ← 2 K K K K 2 3 2 3 ; T return T ; return Figure 6.2: Algorithm for 2K-ECBC_Plus 2Kf9 . Theorem 14 ( PRF-Security of 2K-ECBC_Plus ). Let K and M be two non-empty n n finite sets. Let 0 , 1 } E →{ 0 , 1 } K×{ be a block cipher. Then, any distinguisher with : t ` q tuple of distinct messages each of at most running time at most blocks long, , making n 2K ECBC _ Plus can distinguish E ] from an - -bit uniform random function by, [ 4 2 2 3 3 2 2 q ` q 8 q q 6 ` q` 2 prp prf ′ ) + ( q,`,t ) ( ≤ `q,t Adv Adv 3 + + + , + E [ Plus _ 2K ECBC - ] E n n n n 2 2 n 2 2 2 2 2 2 ′ t t is about where plus a time complexity necessary to compute E for `q + 2 q times and n − 1 ` ≤ (2 + 1) / 2 .

38 38 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF ii ) of Theorem 2, Theorem 12 and Proof of this theorem directly follows from part ( Eqn. (35). ( Let K and M be two non-empty finite sets. Let Theorem 15 PRF-Security of 2Kf9 ). n n , 0 →{ 0 , 1 } } be a block cipher. Then, any distinguisher with running time at 1 E : K×{ tuple of distinct messages each of at most ` blocks long, can distinguish q , making t most ] from an n -bit uniform random function by, 2Kf9 [ E 3 2 4 3 3 2 q q 23 q q ` 3 6 ` q` prf prp ′ + + + + , ) + ≤ Adv Adv 2 ( q,`,t `q,t ) ( E 2Kf9 [ E ] n 2 n 2 n 2 n n 2 2 2 2 2 ′ plus a time complexity necessary to compute t t E for is about + 2 q times where `q 1 − n (2 ≤ 3 . ` + 2) / ) i of Theorem 2, Theorem 12 and Proof of this theorem directly follows from part ( Eqn. (36). 6.3 PRF Security of SUM-ECBC and 3kf9 are two instantiations of the three-keyed DbHtS . Although, these con- SUM-ECBC and 3kf9 ZWSW12 ] ] and Zhang et al. [ Yas10 structions are the existing ones, as proposed by Yasuda [ respectively, for the sake of completeness of this paper, we state and prove the security of these two constructions in our setting. We recall these two constructions in Fig. 6.3. The and 3kf9 . following two results show the PRF security bound of SUM-ECBC ,M K ( 3kf9 ,K ,K ) ,K ) SUM-ECBC K ( ,K ,K ,M 2 1 3 1 4 3 2 ′ ′ ′ ′ : ); K ( f9-Hash ← ) (Σ Λ , , M (Σ : 1 , Λ 1 ) ← ECBC-Hash ( K ); , K , M 1 1 2 ′ ′ ′ ′ (Λ ); (Λ ); ⊕ ) E (Σ ⊕ ) E (Σ 2 : 2 : T ← E T E ← K K K K 4 3 2 3 return ; return T ; T Algorithm for Figure 6.3: . SUM-ECBC and 3kf9 Theorem 16 SUM-ECBC K and M be two non-empty finite Let ). ( PRF-Security of n n , sets. Let } E →{ 0 , 1 } : be a block cipher. Then, any distinguisher with running K×{ 0 1 , making q tuple of distinct messages each of at most ` blocks long, can time at most t - E ] from an n -bit uniform random function by, [ SUM ECBC distinguish 2 3 4 2 q` 2 q 9 ` q 2 prf prp ′ + , Adv + 4 ≤ ( q,`,t ( `q,t Adv ) + ) E ] E ECBC SUM [ - n n 2 n 2 2 2 2 ′ t is about where plus a time complexity necessary to compute E t `q + 2 q times and for n − 1 + 1) ` ≤ (2 / 2 . Proof of this theorem directly follows from part ( of Theorem 2, Theorem 13 and iii ) Eqn. (35). and 3kf9 ). Theorem 17 K PRF-Security of M be two non-empty finite sets. Let ( Let n n 0 , 1 } be a block cipher. Then, any distinguisher with running time at →{ 0 , 1 } E : K×{ t tuple of distinct messages each of at most ` blocks long, can distinguish q most , making E ] from an n -bit uniform random function by, 3kf9 [ 2 3 4 3 3 2 12 q ` ` 2 q q q` prp prf ′ , + + + ) + `q,t ( Adv 3 ≤ ( q,`,t ) Adv E [ ] E 3kf9 2 n n 2 n n 2 2 2 2 2 ′ t is about where t plus a time complexity necessary to compute E for `q + 2 q times and n − 1 ` ≤ (2 + 2) / 3 .

39 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 39 ( ) iii Proof of this theorem directly follows from part of Theorem 2, Theorem 13 and Eqn. (36). . , as proven by Yasuda [ Yas10 ], The original security bound of the SUM-ECBC Remark 6 n 2 3 4 q (we only mention the dominating term of the security bound). But, ` is roughly / 2 SUM-ECBC according to Theorem 16, the dominating term of the security bound of the n 3 2 2 n / 2 2 q` + , a substantially improved security bound than the existing one. On is q / n 2 3 4 ` 3kf9 q , our proven security bound, i.e., roughly , is infact worse the other hand, for / 2 2 3 n 3 ` / ) [ 2 ]. However, we have identified that the existing than the existing one( q ZWSW12 is flawed one and the root cause of the fallacy is discussed in details in the 3kf9 bound of following subsection. 6.4 Proof of Theorem 12 and 13 In this section, we prove Theorem 12. In particular, we bound the cover-free and the block- f9-Hash along with the maximum collision wise universal advantage of and 2K-ECBC-Hash . Before doing that, we state a technical result in the following, probability of f9-Hash which will be useful for us to bound the cover-free advantage and the block-wise-universal and f9-Hash along with the maximum collision probability of advantage of 2K-ECBC-Hash when the hash key is sampled outside from the set of bad hash keys. f9-Hash 6.4.1 A Technical Result n be a ,...,Y Let be t many variables which take values from some set Y ⊆{ 0 , 1 } Y and L t 1 n L set of system of linear equations ,...,L represents a } over { 0 , 1 } { . For any i ∈ [ s ] , L i s 1 n } linear (or affine) equation of the form Y a ⊕ ... ⊕ a 1 Y , ⊕ c 0 = 0 , where c ∈{ ,a i,j i t i,t 1 1 i, i . Let the rank of the system of equations i,j is r ; maximum number of linearly for all L independent equations present in L . L is consistent (i.e., at least one solution Now, we know that if the system of equations r − |Y| . Moreover, exists), then the probabilty that the system of equations holds is at most n , the due to ,...,Y if be t many wor variables which take values from Y ⊆ { 0 , 1 } Y 1 t 1 ) ( |Y|− t + r Lemma1, the above probability becomes at most / . r Now, we want to estimate the probability of a given system of linear equations L along with a given collision relation ∼ . In other words, we want to estimate the number of solutions ( Y . Unlike ,...,Y ∼ ) that satisfy L and inducing the given collision relation t 1 L does not help us to give a good estimation on the number before, in this case the rank of of such solutions. As an example, we consider the following: 6 { 1 ,..., is an equivalence relation over } which partitions the Suppose ∼ Example 1. 1 , 4 } , { 2 } , { 3 , 5 index set as 6 }} , i.e., 1 ∼ 4 , 3 ∼ 5 ∼ 6 . Now, we want to compute the {{ , ( Y ,...,Y ) which satisfy the following system of linear equations E number of solutions 1 6 for some fixed constant and the above defined equivalence relation ∼ . c 0 , = c L ⊕ := Y Y ⊕ Y ⊕ ⊕ Y 4 2 5 1 3 E = = Y , := Y 0 ⊕ L c ⊕ 2 1 2 Y E [ ] := ∼ = ∼ ∼ Note that E [ ∼ ] actually represents a system of equations of the form Y , ⊕ Y 0 = 0 , Y = ⊕ Y 5 3 1 4 ,Y ⊕ Y = 0 and some non-equations saying that Y are distinct. Even though Y Y and 2 3 1 6 5 L and L E are linearly independent, we see that given these equalities of L [ ∼ ] , L and 1 2 2 1 ( Y are not linearly independent. Therefore, to obtain a solution, we choose ,Y ) in such ,Y 1 2 3 a way so that Y ) ,Y ,Y and Y ,Y are distinct to each other. Once we choose a triplet ( Y 1 3 2 3 1 2 Y ,Y such that and Y are distinct, the rest of the Y ’s are defined by the equalities of 1 i 2 3 (by eliminating the [ ∼ ] . So, we write equations L Y and L and in terms of Y ,Y E 1 2 2 1 3

40 40 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF variables). After applying these substitutions, both Y and L L represents the other 2 1 same equation: Y ⊕ c = 0 ⊕ Y . 2 1 reduced equation . Therefore, we see that the reduced We call the above equation a and L form of are not linearly independent even though those were before reduction. L 2 1 [ t ] and thus partitions ∼ t ] into the following Let be an equivalence relation over the set [ = ,...,C . To . From each class C C , we choose an element x disjoint classes: C min i i v 1 i L ∈ ] , we associate a variable Y x . Now, given any linear equation t over Y each variables, [ x x x present in L by Y we can replace every variable and then simplify the where Y ∈ C i x x i ∼ reduced equation L . Observe , denoted as equation. The modified equation is called a [ that the system of equations and non-equations ] ∪{ L } is equivalent to the system of E ∼ ∼ [ ∼ ] ∪{ L equations and non-equations } . Applying the above said reduction for more than E ∼ ∼ { L L : L ∈L} . one linear equations yields us a reduced system of linear equations = In other words, we apply the reduction to every equation individually and the above observation can be easily extended to multiple linear equations. More precisely, for a ∼ ( E [ system of linear equations ] ∪L ) is equivalent to L E [ ∼ ] ∪L , ) . One can also easily ( ∼ ∼ := ( Y Y ,...,Y observe that the tuple ) satisfies E [ ∼ ] ∪L is equivalent to the tuple Y t 1 ∼ ∼ satisfies is the reduced tuple of Y after applying the relation Y on Y , where L ∼ i variables. Therefore, we have ) L ( Y be an be a system of linear equations in variables Let and ∼ Lemma 5. x ] x ∈ [ t ∼ [ ] with v many classes. If rank( L t ) = r , then equivalence relation over ∼ ∼ ∼ : Y Y satisfies L |{ }|≤ ( |Y| ) . − r v Proof of the lemma directly follows from the proof of Lemma 1 where the number of variables is now t . v instead of q Structure Graph and Collision Relation. tuple of distinct messages For a fixed M between the ,...M M ) , a structure graph G ( M ) gives a collision relation ∼ := ( Y 1 q variables, where CBC-MAC computation. Y variables are the intermediate chaining values of In specific, whenever there is an accident in a single message walk or between more than Y one message walks, the corresponding variables are said to be related. This relation , which one can easily see to be an equivalence relation. is called the collision relation ( M ) denotes the set of all possible structure graphs (by varying the underlying Let G permutation ). Π Now, let us consider a system of linear equations over ( Y L ,...,Y variables and with ) t 1 distinct messages M , we fix a structure graph G q M ) , which is respect to a tuple of ( Y yields a collision relation variables. The structure graph G ( realized through these ) M i L between the Y variables. Applying the collision relation ∼ ∼ to all the equations of i ∼ 9 gives a reduced system of linear equations, denoted as L . Moreover, each accident in the structure graph G ( M ) yields a linear equation of the form Y , and all ⊕ Y c = b a G ( ) , are linearly independent. Let a such linear equations induced by the accidents in M ( G ) and r be the rank of the system of equations be the total number of accidents in M ∼ ∪{ L Y ⊕ Y is the set of all such linearly independent = c } , where { Y } ⊕ Y c = b a b a equations which are induced from the accidents in G ( M ) . We call this rank as the joint rank . Now, following Lemma 5, we have the following result. ( G M ) Let us consider a structure graph ( M ) with respect to a fixed tuple Lemma 6. ∈G q distinct messages M , realized through ( Y ,...,Y be a system of ) variables. Let L of t 1 and linear equations in variables := ( Y with ,...,Y ] ) Y ∼ be a collision relation over [1 ,t t 1 9 We use the term collision and accident interchangebaly.

41 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 41 ∼ ( M ) . If the joint rank of L v ∪{ Y G ⊕ Y many classes, induced by = c } is r , then a b 1 Pr[ = G ( M )] ≤ Y L ,G satisfies . + ) ( v |Y|− r r ∼ and all the L To prove this result, the total number of solutions that satisfy Proof. many equations induced by the accidents in a M ) , are at most ( linearly independent G (follows from Lemma 5). Moreover, the total number of ways we can choose the |Y| ( ) v − r |Y| ) variables are (keeping the distinctness of the variables). Dividing the former one by ( v the latter yields the result. 6.4.2 Cover-free and Block-wise universal Advantage of 2K-ECBC-Hash 2K-ECBC-Hash when We bound the cover-free and the block-wise universal advantage of the hash key, i.e., the pair of independent random permutation , Π (Π ) , is sampled outside 1 2 ecbc from K . bad 2K-ECBC- To bound the cover-free advantage of Bounding Cover-free-advantage. , M Hash M , we first fix three distinct messages . For brevity, we write M and k i j ecbc × [ (Π Pr , Π . Now, we consider the two ) ∈ ( Perm P Perm ) \ K CF as ] holds, cf 2 1 ijk bad G ( M ) : ( i ) G ( subsets of M ) , which is the set of all structure graphs of G ( M ) such that 0 there is no accident in between the -th message walks and ( ii ) G j ( M ) , which -th and the i 1 ( M ) such that there is exactly one accident in between is the set of all structure graphs of G -th and the j -th message walks. Now, by definition we have, i the ( ∑ ′ )] M ( ∈G ,G ) M = Pr[Σ ( ⊕ Σ ∈G = b, Λ ,G ⊕ Λ P = b k cf j 0 i i 1 0 2 ′ 0 ∈{ b,b 1 , } ′ = b, Λ ⊕ Λ = + Pr[Σ ⊕ ,G ∈G ( M ) ,G Σ ∈G ( M )] b i 1 k 1 0 j i 2 ′ ⊕ = b, Λ ⊕ Λ = b + Pr[Σ ,G Σ ∈G ( M ) ,G ∈G ( M )] 1 2 1 0 i k i j ) ′ ⊕ Σ ⊕ = b, Λ )] + Pr[Σ Λ M = b , ,G ( ∈G ∈G ( M ) ,G 2 1 i j i 1 1 k and are two independent structure graphs (when viewed as random variables G where G 2 1 M defined over the sample space ). In other words, we may view that G G is induced ( ) 1 by a random permutation whereas G Π is induced by an another random permutation 1 2 ⊕ Π Π . Moreover, the event Σ , which is independent of is independent over Σ b = j 2 i 1 ′ ⊕ Λ Λ = b and the second event as the first event is induced by the randomness of Π 1 k i are two independent random Π Π Π and is induced by the randomness of , where 2 1 2 permutations. Therefore, we write ( ∑ ′ )] M ( ∈G ,G Σ b = Pr[Σ = ⊕ P Λ = b,G ⊕ ∈G Pr[Λ ( M )] · 0 1 j k i i 2 0 cf ′ 0 1 ∈{ , b,b } ′ )] ⊕ Σ M = b,G ( ∈G ∈G ( M )] · Pr[Λ ,G ⊕ Λ + Pr[Σ = b k 0 1 1 j i i 2 ′ ⊕ Σ )] = b,G M ∈G ( ( M + Pr[Σ · Pr[Λ ∈G ⊕ Λ ,G = b )] k 2 i 0 1 1 j i ) ′ ⊕ Σ . = b,G + Pr[Σ ∈G )] ( M )] · Pr[Λ M ⊕ Λ ( = b (37) ,G ∈G j 2 i 1 1 k i 1 Analysis of Cases: Now, we analyze different cases. Basically, we will bound the following four probabilities: (A) Pr[Σ , ⊕ Σ )] = 0 ,G M ∈G ( ( M )] , (B) Pr[Σ ∈G ⊕ Σ ,G = 1 j i 0 0 1 j i 1 (C) Pr[Σ )] ⊕ Σ M = 0 ,G ( ∈G ∈G . M )] , (D) Pr[Σ ,G ⊕ Σ 1 = ( j i 1 1 1 1 j i

42 42 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF Σ Bounding Case (A): ⊕ Σ It is easy to see that the event = 0 ,G is an ∈ G ) ( M 0 i 1 j impossible event. Because we are considering those structure graphs in which there is no j i accident in between the -th message walks. But at the same time we are -th and the considering the event , which itself is an accident between the Σ -th and the j -th i = Σ i j message walks. Hence, the probability in this case is zero. variables. In ⊕ Bounding Case (B): = 1 is a non-trivial linear equation over Y Σ Σ i j specific, the equation is: j i ⊕ Y , 1 = Y l l i j n (2 which holds with probability − 2 ` + 1) , when there is no accident in between the 1 / j i -th message walks. Moreover, the number of such structure graphs is only -th and the one, which is uniquely determined by the message tuple. Hence, the probability in this − n n n 1 (2 ` ≤ 2 / 2 − when ` ≤ (2 + 1) / 1 + 1) / 2 . case is at most 2 To compute this probability, we write Bounding Case (C): ∑ ⊕ Σ ] = 0 ,G V ∈G = ( M )] = Pr[Σ ,G 0 = Σ ⊕ Pr[Σ i j i 1 1 1 j ) ( ∈G V M 1 ⊕ Σ The joint rank of the system of equations = 0 along with the equation induced Σ j i 1 . Therefore, from Lemma 6, we have from the accident, is at least 1 Σ Pr[Σ = 0 ,G = ⊕ V ] ≤ . 1 j i n ` 2 − 2 + 1 Moreover, in this case the number of structure graphs with exactly one accident is 1 . 1 2 , with the assumption Therefore, the probability in this case is at at most ≤ n n +1 2 2 − 2 ` n − 1 that ` ≤ + 1) / 2 . (2 To compute this probability, we write Bounding Case (D): ∑ Σ = 1 Pr[Σ ∈G ( M )] = ⊕ ,G V ] = ,G 1 = Σ ⊕ Pr[Σ i j i 1 1 1 j ) ( ∈G M V 1 Σ Σ ⊕ The joint rank of the system of equations along with the equation induced = 1 j i 2 as the linear equation induced from the accident is linearly from the accident, is exactly Σ . Therefore, from Lemma 6, we have Σ independent over the equation = 1 ⊕ j i 1 Pr[Σ = 1 ,G ⊕ = V ] ≤ . Σ j 1 i n − 2 ` + 2) (2 2 ( ) 2 ` 2 2 ` ≤ . Moreover, in this case the number of structure graphs with exactly one accident is 2 2 2 2 2 ` 8 ` ` 2 ≤ Therefore, the probability in this case is at most with the ≤ n n n 2 2 2 +1) − − (2 2 +2) (2 2 ` ` 2 n − 1 + 1) ≤ (2 / 2 . assumption ` Σ Σ and All the above result equally holds when respectively. are replaced by Λ Λ and i j k i Now, we split up Eqn. (37) and write as follows: ∑ ′ ∈G )] ( ∈G = ,G Pr[Σ P Σ = b,G M ( M )] · Pr[Λ ⊕ Λ = b ⊕ i 1 i 2 0 k 0 j cf ′ } 0 ∈{ b,b 1 , ∑ ′ )] M ( ∈G ,G = Pr[Σ b ⊕ Σ + = b,G Λ ∈G ⊕ ( M )] · Pr[Λ i 0 k j i 1 1 2 ′ 1 } 0 ∈{ b,b , ∑ ′ ∈G M )] ,G Pr[Σ ⊕ Σ = b,G + ( ( M )] · Pr[Λ ⊕ Λ = b ∈G 0 i 1 j k 1 i 2 ′ } , 0 ∈{ b,b 1 ∑ ′ )] M ( ∈G ,G . b Pr[Σ = ⊕ Σ Λ = b,G (38) ∈G ⊕ ( M )] · Pr[Λ + 2 j k i i 1 1 1 ′ , 0 1 ∈{ b,b }

43 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 43 ′ b and plugging-in the above derived bound and b By varying over all possible choices of in Eqn. (38), we have the following result: 2 4 2 64 ` ` 64 12 ` 16 + , + (39) ≤ ≤ P cf n 4 n 3 2 2 n n 2 2 2 2 n − 2 ` ≤ . Hence we can set 2 assuming 2 12 ` (3 ) = ,` . (40) cf n 2 2 Bounding Block-wise-universal advantage. To bound the block-wise universal , we first fix two distinct messages M and M . For brevity, 2K-ECBC-Hash advantage of i j ecbc [ UNIV . Now, as before we holds, (Π P , Π as ) ∈ ( Perm × we write ) \K Pr ] Perm 1 univ ij 2 bad G G ) : ( i ) G ( ( M ) and ( ii ) M consider the two subsets of ( M ) . Now, by definition we can 1 0 write, ( ) ∑ ∑ ( P = max ( ∈G ⊕ Pr[Σ b,G , Σ = = b,G Λ ∈G ⊕ ( M )] , )] Pr[Λ M univ i i 01 1 j j 2 01 ∈{ b , 0 1 1 , 0 ∈{ b } } (41) where G . Now, by varying all possible choices of ( M ) denotes the set G ) ( M ) ∪G M ( 1 01 0 ′ b and plugging-in the above bound of Case (A)-Case (D) into Eqn. (41) , we have and b 2 4 16 ` P + ≤ and hence we have 2 n n univ 2 2 2 2 4 ` ` 2 8 + ≤ (2 ,` ) = (42) , univ n 2 n n 2 2 2 − 2 n ≤ assuming . ` 2 The first part of Theorem 12 follows from Eqn. (40) and Eqn. (42). 6.4.3 Collision, Cover-free and Block-wise universal Advantage of f9-Hash In this section, we bound the maximum collision probability, the cover-free advantage f9-Hash . Recall that, f9-Hash is not a block- and the block-wise universal advantage of DbH function and thus we require to bound its maximum collision probability separated (or equivalently the collision advantage) along with its cover-free and block-wise universal advantage. To bound this event, we first fix a message M Bounding Collision advantage. and i f9 ̃ G COLL be the set holds, Π ∈ Perm \K ) for brevity, we write ] as P M . Let Pr [ ( 0 i coll bad M ) of all structure graphs of i -th message ( G such that the number of accidents in the ̃ walk is zero, i.e., in a stucture graph of ( M ) , there contains no accident within the i -th G 0 message walk. This says that, we need to bound the probability of the event when number of accidents in the message walk of is zero. Now, by definition we have, M i ∑ ′ ′ ′ ′ ̃ ,G ,G ∈ ] G P ( M )] = = = Λ (43) = Λ Pr[Σ V = Pr[Σ 0 coll i i i i ̃ M ) ( G V ∈ 0 As there is no accident in the V , it does not induce any linear equation. i -th message walk of ′ ′ Σ Therefore, the only linear equation we have due to = Λ , which is non-trivial and hence i i ′ ′ = Λ implies the rank of the system of linear equations is one. In other words, the event Σ i i the following non-trivial equation: i i , ...Y Y ⊕ = 0 − 1 l 1 i

44 44 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF 1 2 1 − n . which holds with probability at most ≤ , with the assumption that ` ≤ 2 n n − 2 2 ` 1 i . Moreover, the number of structure graphs with no accident in the -th message walk is 2 and hence we have, ≤ Therefore, from Eqn. (43), we have P n coll 2 2 = . (44) coll n 2 and ,M Bounding Cover-free-advantage. Fix three distinct messages M M . As i j k f9 ] before, for brevity, we write Π ∈ Perm \K Pr [ holds, as P CF . Now, we consider the cf ijk bad ( M ) : ( two subsets of ) G G ( M ) , which is the set of all structure graphs of G ( M ) such that i 2 -th, the j -th and the k -th message walks and ( ii ) G the there is no accident in the ( M ) , i 3 G M ) such that the there is exactly one accident which is the set of all structure graphs of ( -th, the j -th and the k -th message walks. Let us denote G in the ( i ) ∪G ) ( M ) by G M ( M 23 3 2 G ) ( M ) denotes the set G is the set of all ( M and recall that ∪G ) ( M ) where G M ( 0 01 0 1 M ) such that there is no accident in the structure graphs of -th and the j -th message ( G i G ( M ) is the set of all structure graphs of walks and ( M ) such that there is exactly one G 1 i j -th message walks.Now, by definition we have, accident in the -th and the ′ ′ ′ ′ ′ ′ ′ ′ Λ P ( = Λ )] ∈G ,G ∈G ,G ( M )] + Pr[Σ = Σ M = Λ = Pr[Σ = Λ , Λ , cf 23 23 i k k i j i j i ′ ′ ′ ′ ′ ′ ′ ′ = Λ Λ ( M )] + Pr[Σ = Σ = Σ , , Λ ,G + Pr[Σ = Σ ∈G ,G ∈G )] ( M 23 23 k j k j i i i i ′ ′ ′ ′ + Pr[Σ , Λ = Σ (45) = Λ ∈G )] ,G M ( 01 j i i j f9-Hash is not block separated and hence to Note that, unlike all the earlier constructions, analyze its cover-free advantage, we need to consider all the possible ways that the cover free event can occur, as described in Sect. 3.3. Now, to bound P , we state the following cf claim, the proof of which is given in Appendix A. M and M Let be any three distinct messages such that the maximum ,M Claim 2. i j k number of message blocks among all these three messages is . Then, we have, ` 2 2 20 18 ` ` ′ ′ ′ ′ ′ ′ ′ ′ ≤ ( M )] ) Pr[Σ , Λ ; ( = Λ ; ( b ) Pr[Σ = Σ )] = Λ a M , Λ ,G ( = Λ ∈G ∈G ,G ≤ 23 23 j i i k i j i k n 2 n 2 2 2 2 2 ` 20 ` 18 ′ ′ ′ ′ ′ ′ ′ ′ )] ,G ( ( M )] ≤ . = Σ c ) Pr[Σ ≤ ∈G ; ( d ) Pr[Σ Λ M = Λ , ( , Λ ∈G ,G = Σ = Σ 23 23 i j i k k i j i 2 n 2 n 2 2 2 ` 8 ′ ′ ′ ′ M Λ , = Σ ,G ∈ G , where we assume ( = Λ )] ≤ [Σ Pr Moreover, we also have 2 n 01 j i j i 2 n − 1 ` + 2) / 3 . ≤ (2 2 84 ` Following Eqn. (45) and Claim 2 we have, P and hence ≤ 2 n cf 2 2 84 ` ,` ) = (3 (46) . cf n 2 2 Fix two distinct messages M Bounding Block-wise-universal advantage. and M . j i According to the definition of block-wise universal advantage for a pair of distinct messages we have the following: ( ′ ′ ′ ′ = Σ )] ,G ∈G M ( = max )] , Pr[Λ , Pr[Σ = Λ P ,G ∈G ( M 01 01 univ j i i j ) ′ ′ ( = Λ ,G ∈G (47) , M )] Pr[Σ 01 i j f9 P ) is the shorthand notation for Pr [ UNIV M holds, Π ∈ Perm \K where ( ] and G univ 01 ij bad denotes G , we state the following claim, proof of ( M ) ∪G P ( M ) . Now, to bound 1 univ 0 which is given in Appendix B.

45 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 45 Let Claim 3. ,M M be any two distinct messages such that the maximum number of j i message blocks among these two messages is . Then, we have, ` 2 2 ` ` 3 ′ ′ ′ ′ ) Pr[Σ )] ≤ )] = Λ ( ,G ; ( b ∈G a = Σ ( ,G ∈G ) Pr[Σ ( M M ≤ ; 01 01 i j i j n n 2 2 2 ` 3 ′ ′ = Λ ,G ∈G , ( M )] ≤ ( c ) Pr[Λ 01 j i n 2 − n 1 ` ≤ (2 / 2 . where we assume + 1) 2 3 ` P From Eqn. (47) and Claim 3, we have ≤ and hence we have n univ 2 2 3 ` . (48) (2 ) = ,` univ n 2 Remark Unlike 2K-PMAC_Plus-Hash , 2K-LightMAC_Plus-Hash and 2K-ECBC-Hash , for . 7 , we have avoided the use of and f9-Hash fix1 functions to make its DbH the analysis of fix0 Σ function block-separated. Hence, we dealt with all the cross collision events (among Λ ) while analysing its cover-free and block-wise universal advantage along with the and maximum collision probability. This is an example to show that we could have proved the beyond birthday bound security of all the ealier two-keyed variants without using fix0 and functions, but then the analysis would have been more involved and tedious. fix1 6.4.4 Weak-cover-free and Weak-block-wise-universal Advantage of ECBC-Hash ′ To bound the weak cover-free advantage of Σ ECBC-Hash , we only need the case = i 4 ′ ′ ′ Σ , = Λ Λ . Similarly, to bound the block-wise , probability of which is bounded by 2 n i j k 2 ′ ′ ′ ′ = Σ Λ or , probability of each of Σ universal advantage, we only need the case that = Λ i j i j 2 them is bounded by . n 2 Hence, we have 2 4 ) = (49) , . (2 ,` (3 ) = ,` univ cf n n 2 2 2 6.4.5 Weak cover-free and Weak-block-wise-universal Advantage of f9-Hash 3 4 2 q ` q` Since the = DbH function for 3kf9 and 2Kf9 . Similar is same, we have + n n 2 bh 2 2 , bounding the cover-free advantage requires us to analyze only the case to ECBC-Hash 2 ` 18 ′ ′ ′ ′ ( Λ , of Claim 2). Similarly, , probability of which is bounded by ) = Σ a = Λ (see Σ n 2 i i j k 2 ′ ′ = Σ to bound the block-wise universal advantage, we only need the case that or Σ i j 2 3 ` ′ ′ , the maximum probability of these two is atmost = Λ of Claim 3). ) Λ c (see ( b ) and ( n i j 2 Hence, we have 2 2 18 ` ` 3 ,` . ) = , ,` (2 (3 ) = cf univ n n 2 2 2 6.5 Incorrectness of the Existing Security Bound of 3kf9 3 3 2 n n q 2 ` We have found that the existing bound of / 2 3kf9 (i.e., + q`/ O ( ) ) proven in [ ] is incorrect. The main flaw of the security proof lies in bounding the cover- ZWSW12 free advantage (Case D, [ ZWSW12 ]) of the underlying DbH function (See Lemma 1 ZWSW12 ]) while making a flawed assumption about the probability of Σ of [ = Σ is at j i n 1 / 2 most . But, this assumption is not true. Σ is essentially the collision event of = Σ j i the CBC-MAC and the authors have assumed that the probability of this collision is at n 1 / 2 , missing many accidents from considerations. The correct bound of the collision most

46 46 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF n CBC-MAC ( ` ) / 2 probability of the as shown in [ BPR05 ], where d ( ` ) is the maximum is d for any ≤ ` . number of divisors of l l 2 n 4 3 q proven in this paper (i.e., ( / 2 O 3kf9 ) ) is Observe that, the security bound of ` 10 ). We believe that it and ` q q beyond birthday in terms of only (not in terms of both 3kf9 and would be very difficult, if not impossible, to show the beyond birthday security of 2 4 3 n q ` ` and / 2 q its reduced keyed variant, in terms of both . In our analysis, the term arises as we allow at most one accident for any choice of three messages. Hence, it makes the security bound to be beyond birthday in terms of ` . Generically, , but not in terms of q if one goes up to allowing a many accidents in any triplet of messages, then one needs + 1 in any to bound the probability for the number of accidents greater than equal to a 3 2( a +1) +1) a ( n ` / q ( O triplet of messages, which gives the bound ) ; not beyond birthday 2 q ` . Henceforth, to avoid the bound which is beyond birthday secure in terms of both and q , one needs to allow n many accidents for three distinct messages and only in terms of then analyze the probability of its cover-free advantage. This seems really difficult as the number of possibilities of having many accidents in three messages is huge (e.g., one n 3 may try to enumerate the number of cases for allowing only accidents in three distinct messages). 6.6 Importance of the Set of Bad Hash Keys We have seen that for some constructions, we have analyzed their cover-free and the block-wise universal advantage when the hash key was sampled from outside of the set of all bad hash keys. The importance of drawing the hash key from a good key space while analyzing the cover-free and block-wise universal advantage lies in obtaining an improved security bound for those constructions. For example, in the analysis of the cover-free 2K-PMAC_Plus-Hash , if we had sampled the hash key from the set of all advantage of the 2 3 2 n ( / 2 hash keys, we would have obtained a bound ` q . This is because, to bound its O ) 3CollX cover-free advantage for a triplet of distinct messages, we would have to consider the 2 2 n 2 event among the chosen three messages, which would happen with probability ` . / 3 2 2 n 3 q , makes the resultant bound of the order of / 2 q This would get multiplied with , a ` ` blow up of an extra factor in the security bound. 2K-ECBC_Plus . If we had sample A much serious degradation of bound takes place for the hash key from the entire hash key space, then we would have obtained the bound 2 n 3 4 ` O / 2 ( q ) . This is because, to bound its cover-free advantage for a triplet of distinct messages, we would have to consider the Coll event among the chosen three messages, 2 3 2 n 4 / . This would get multiplied with q 2 , makes which would happen with probability ` 3 4 2 n / 2 ` the resultant bound of the order of , a blow up of an extra q factor in the security q bound. 7 Conclusion and Future Work With a rapid growth of computing power, birthday attacks gradually become a practical threat to cryptographic algorithms. Therefore, designing modes that guarantees security beyond the birthday bound is active and promising. In this paper, we give a generic treatment of constructing the two-keyed and the three-keyed beyond birthday bound secure PRFs with an actual concrete instantiations, backed up with a proper security proof. This work immediately opens up two different directions of possible future works: A trivial question that comes to the mind is, whether it is possible to Open Problem I: DbHtS , where the hash key would extend this work to analyze the security of the single-keyed 10 − 10 As an example, if the security advantage happens to be 2 , then with block length n = 128 and 50 24 q = 2 , it limits the maximum value of the message length to 2 blocks.

47 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 47 It is well known that any generic be same as the block cipher key used in the sum function? composition result demands independent keys for each module, and whether the security holds even with the same key is non-trivial and requires a different approach. In the same DbHtS would require a different line of reasoning, the security analysis of the single-keyed approach and the proof may become quite complex and involved. Technically speaking, the analysis of the single-keyed DbHtS would require one to bound the collision between hash values and the intermediate block inputs (during the internal hash computation) along with the usual hash collisions. This enforces many more bad events. Analyzing these bad events and obtaining a generic result is non-trivial and is left as an open problem. In + 17 ] have shown the BBB DDN this regard, we would like to mention that Datta et al. [ security of single-keyed PMAC_Plus . We believe that using a similar approach, one can also LightMAC_Plus prove BBB security of the single-keyed version of . However, we think that proving the beyond birthday bound security of single-keyed version of is challenging 3kf9 and one needs to employ extreme care in analyzing the security of this construction. Open Problem II: LNS18 ], SUM-ECBC , In a very recent work of Leurent et al. [ , 3kf9 PMAC_Plus LightMAC_Plus and their reduced keyed-variant have been attacked , 3 n/ 4 with the query complexity 2 . We believe that all these constructions can also be 4 n/ 3 2 proven secured upto , and hence establishing the tightness of the bound. But to prove that, one needs to analyze (i) the rank of three linear equations (instead of two), which we believe is cumbersome and non-trivial to do and (ii) uplift the security of the sum of 3 n/ 4 2 permutation result to . We would like to thank Damian Vizár for his invaluable comments Acknowledgements. and suggestions in preparing the final draft. We would also like to thank all the anonymous reviewers of FSE 2019 for helping us improve the work. Nilanjan Datta performed part of his work during his PhD at Indian Statistical Institute, Kolkata. Avijit Dutta and Mridul Nandi are supported by R.C.Bose Centre for Cryptology and Security. References Jee Hea An and Mihir Bellare. Constructing vil-macsfrom fil-macs: Message [AB99] authentication under weakened assumptions. In Advances in Cryptology - CRYPTO ’99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 1999, Proceedings , pages 252–269, 1999. [BCK96] Mihir Bellare, Ran Canetti, and Hugo Krawczyk. Keying hash functions for message authentication. In Advances in Cryptology - CRYPTO ’96, 16th Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 1996, Proceedings , pages 1–15, 1996. [BI99] Mihir Bellare and Russell Impagliazzo. A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion. IACR Cryptology ePrint Archive , 1999:24, 1999. [BJKS93] Jürgen Bierbrauer, Thomas Johansson, Gregory Kabatianskii, and Ben J. M. Smeets. On families of hash functions via geometric codes and concatenation. In Advances in Cryptology - CRYPTO ’93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings , pages 331–342, 1993. + [BKL 07] Andrey Bogdanov, Lars R. Knudsen, Gregor Leander, Christof Paar, Axel Poschmann, Matthew J. B. Robshaw, Yannick Seurin, and C. Vikkelsoe. PRESENT: an ultra-lightweight block cipher. In Cryptographic Hardware

48 48 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF and Embedded Systems - CHES 2007, 9th International Workshop, Vienna, Austria, September 10-13, 2007, Proceedings , pages 450–466, 2007. [BKR98] Mihir Bellare, Ted Krovetz, and Phillip Rogaway. Luby-rackoff backwards: Increasing security by making block ciphers non-invertible. In Advances in Cryptology - EUROCRYPT ’98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31 - June 4, 1998, Proceeding , pages 266–280, 1998. [BKR00] Mihir Bellare, Joe Kilian, and Phillip Rogaway. The security of the cipher block , 61(3):362–399, J. Comput. Syst. Sci. chaining message authentication code. 2000. + [BPP 17] Subhadeep Banik, Sumit Kumar Pandey, Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. GIFT: A small present - towards reaching the limit of lightweight encryption. In Cryptographic Hardware and Embed- ded Systems - CHES 2017 - 19th International Conference, Taipei, Taiwan, September 25-28, 2017, Proceedings , pages 321–345, 2017. [BPR05] Mihir Bellare, Krzysztof Pietrzak, and Phillip Rogaway. Improved security analyses for CBC macs. In CRYPTO 2005 , pages 527–545, 2005. [BR02] John Black and Phillip Rogaway. A block-cipher mode of operation for parallelizable message authentication. In EUROCRYPT 2002 , pages 384–397, 2002. + [CLL 14] Shan Chen, Rodolphe Lampe, Jooyoung Lee, Yannick Seurin, and John P. Steinberger. Minimizing the two-round even-mansour cipher. In Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I , pages 39–56, 2014. [CLP14] Benoit Cogliati, Rodolphe Lampe, and Jacques Patarin. The indistinguisha- bility of the XOR of k permutations. In Fast Software Encryption - 21st International Workshop, FSE 2014, London, UK, March 3-5, 2014. Revised Selected Papers , pages 285–302, 2014. [CS14] Shan Chen and John P. Steinberger. Tight security bounds for key-alternating ciphers. In Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings , pages 327–350, 2014. [dB93] Bert den Boer. A simple and key-economical unconditional authentication Journal of Computer Security , 2:65–72, 1993. scheme. + [DDN 17] Nilanjan Datta, Avijit Dutta, Mridul Nandi, Goutam Paul, and Liting Zhang. Single key variant of pmac_plus. IACR Trans. Symmetric Cryp- tol. , 2017(4):268–305, 2017. [DHT17] Wei Dai, Viet Tung Hoang, and Stefano Tessaro. Information-theoretic in- distinguishability via the chi-squared method. In Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part III , pages 497–523, 2017.

49 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 49 Avijit Dutta, Mridul Nandi, and Goutam Paul. One-key compression function [DNP16] based MAC with security beyond birthday bound. In Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Melbourne, VIC, , pages 343–358, 2016. Australia, July 4-6, 2016, Proceedings, Part I [DS11] Yevgeniy Dodis and John P. Steinberger. Domain extension for macs beyond , volume 6632 of LNCS , pages the birthday barrier. In EUROCRYPT 2011 323–342. Springer, 2011. Jian Guo, Thomas Peyrin, Axel Poschmann, and Matthew J. B. Robshaw. [GPPR12] The LED block cipher. IACR Cryptology ePrint Archive , 2012:600, 2012. Peter Gazi, Krzysztof Pietrzak, and Michal Rybár. The exact prf-security [GPR14] Advances in Cryptology - CRYPTO 2014 - 34th of NMAC and HMAC. In Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I , pages 113–130, 2014. [HK97] Shai Halevi and Hugo Krawczyk. MMH: software message authentication in the gbit/second rates. In Fast Software Encryption, 4th International Workshop, FSE ’97, Haifa, Israel, January 20-22, 1997, Proceedings , pages 172–189, 1997. Tetsu Iwata and Kaoru Kurosawa. OMAC: one-key CBC MAC. In Fast [IK03] Software Encryption, 2003 , pages 129–153, 2003. Tetsu Iwata and Kazuhiko Minematsu. Stronger security variants of GCM-SIV. [IM16] IACR Trans. Symmetric Cryptol. , 2016(1):134–157, 2016. Ashwin Jha and Mridul Nandi. Revisiting structure graphs: Applications to [JN16] CBC-MAC and EMAC. , 10(3-4):157–180, 2016. J. Mathematical Cryptology Gaetan Leurent, Mridul Nandi, and Ferdinand Sibleyras. Generic attacks [LNS18] against beyond-birthday-bound macs. volume 2018, page 541, 2018. [LPTY16] Atul Luykx, Bart Preneel, Elmar Tischhauser, and Kan Yasuda. A MAC mode for lightweight block ciphers. IACR Cryptology ePrint Archive , 2016:190, 2016. [Luc00] EUROCRYPT 2000 , pages Stefan Lucks. The sum of prps is a secure PRF. In 470–484, 2000. [MP15] Bart Mennink and Bart Preneel. On the XOR of multiple random permutations. In Applied Cryptography and Network Security - 13th International Conference, ACNS 2015, New York, NY, USA, June 2-5, 2015, Revised Selected Papers , pages 619–634, 2015. Yusuke Naito. Blockcipher-based macs: Beyond the birthday bound without [Nai17] message length. Cryptology ePrint Archive, Report 2017/852, 2017. [NM08] Mridul Nandi and Avradip Mandal. Improved security analysis of PMAC. J. Mathematical Cryptology , 2(2):149–162, 2008. [Pat98] Jacques Patarin. About feistel schemes with six (or more) rounds. In Fast Software Encryption , pages 103–121, 1998. n Jacques Patarin. A proof of security in o (2 [Pat08a] ) for the benes scheme. In AFRICACRYPT , pages 209–220, 2008.

50 50 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF [Pat08b] Jacques Patarin. A proof of security in o(2n) for the xor of two random permutations. In Information Theoretic Security, Third International Confer- , pages ence, ICITS 2008, Calgary, Canada, August 10-13, 2008, Proceedings 232–248, 2008. Selected Areas in [Pat08c] Jacques Patarin. The “Coefficients H” Technique. In , pages 328–345, 2008. Cryptography, SAC [Pat10] Jacques Patarin. Introduction to mirror theory: Analysis of systems of linear IACR Cryptology ePrint equalities and linear non equalities for cryptography. Archive , 2010:287, 2010. n Jacques Patarin. Security in o(2 ) for the xor of two random permutations [Pat13] , \\ - proof with the standard H technique -. IACR Cryptology ePrint Archive 2013:368, 2013. Victor Shoup. Sequences of games: a tool for taming complexity in security [Sho04] , 2004:332, 2004. proofs. IACR Cryptology ePrint Archive Richard Taylor. An integrity check value algorithm for stream ciphers. In [Tay93] Advances in Cryptology - CRYPTO ’93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings , pages 40–48, 1993. [Yas08] Kan Yasuda. A one-pass mode of operation for deterministic message authentication- security beyond the birthday barrier. In Fast Software En- cryption, 15th International Workshop, FSE 2008, Lausanne, Switzerland, February 10-13, 2008, Revised Selected Papers , pages 316–333, 2008. Kan Yasuda. The sum of CBC macs is a secure PRF. In CT-RSA 2010 , pages [Yas10] 366–381, 2010. [Yas11] Kan Yasuda. A new variant of PMAC: beyond the birthday bound. In , pages 596–609, 2011. CRYPTO 2011 [ZWSW12] Liting Zhang, Wenling Wu, Han Sui, and Peng Wang. 3kf9: Enhancing , pages 296–312, 3gpp-mac beyond the birthday bound. In ASIACRYPT 2012 2012. Appendix A Proof of Claim 2 In this section, we prove claim 2, where we analyse the probability of the events according to the structure graph notion. First we recall the statement of the claim: Claim 2. M and ,M be any three distinct messages such that the maximum Let M j k i ` . Then, we have, number of message blocks among all these three messages is 2 2 ` 20 18 ` ′ ′ ′ ′ ′ ′ ′ ′ = Σ ,G ∈G ≤ ( M )] ≤ ( a , )] M ( ; ( b ) Pr[Σ Λ ∈G = Λ ) Pr[Σ ,G , Λ = Λ ; = Λ 23 23 i j i j i k i k 2 n 2 n 2 2 2 2 ` 20 18 ` ′ ′ ′ ′ ′ ′ ′ ′ = Σ )] M Λ , ( = Λ . ∈G ,G ≤ ) Pr[Σ d ; ( , ( c )] M ) Pr[Σ ( = Σ ∈G Λ ,G ≤ = Σ 23 23 k i j i i j i k n 2 2 n 2 2 2 ` 8 ′ ′ ′ ′ [Σ , Λ = Σ , where we assume = Λ Moreover, we also have Pr ,G ∈ G ≤ ( M )] n 2 01 j i i j 2 n − 1 ` . (2 + 2) / 3 ≤

51 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 51 We bound the events as stated in claim 2 based on the randomness of the underlying permutation . We would like to first set up the following notational convention, which Π will be used in our subsequent analysis: i M is denoted by Notational Convention: Number of message blocks of -th message i α -th message block of i -th message is denoted by M l [ α ] . Moreover, the block and the i i i ` Y α i . -th block of denotes the maximum -th message is denoted by cipher output of α q queries. number of message blocks among all ′ ′ ′ ′ )] M ( ∈G , G = Λ , Λ = Σ A.1 Bound of Pr[Σ 23 k i j i blocks. ,M We have fixed three distinct messages and M M each of the length at most ` k j i M ,M ,M ( G Let ) denotes the set of all structure graphs corresponding to the fixed triple i j k of messages ,M M and M . Now, we write k j i ′ ′ ′ ′ ′ ′ ′ ′ | = Λ Pr[Σ ,G ∈G = 0] ( M )] = Pr[Σ , Λ = Σ ) G , Λ = Σ ( = Λ Coll ∧| 23 k i j j i i k i ′ ′ ′ ′ , Λ ∧| (50) = Λ + Pr[Σ . = Σ Coll ( G ) | = 1] k i j i ′ ′ ′ ′ = Σ = Λ Σ Now, we analyse the probability of , when number of accident in the Λ , j i i k and 1 as follows: 0 structure graph is 0 , Number of Accident =0. When the number of accidents in the structure graph is ′ ′ = Σ as the event itself implies either (a) at least one then the probability of is 0 Σ i j collision between a pair of messages or (b) a collision in either of the message walk of M i ′ ′ . But since the number of accident is zero, Σ M is an impossible event and hence = Σ or j j i ′ ′ ′ ′ is also 0 . Therefore, Λ the probability of the joint event and = Λ = Σ Σ i j i k ′ ′ ′ ′ Pr[Σ . , Λ = Λ = 0] = 0 (51) = Σ | ∧| Coll ( G ) k i j i Number of Accident = 1. be the length of the common suffix of M M and α Let and i j M β and M be the length of the common prefix of . Then we have, k i j ′ ′ i (52) ⇒ Y Σ . ] α − l = Σ ⊕ Y [ M ⊕ ] α − l = M [ j i j i − i α − 1 l j l − α − 1 i j ′ ′ Moreover, Λ = Λ implies the following equation: i k i k k i Y ... ⊕ Y ⊕ Y ⊕ Y ⊕ ... ⊕ . = 0 (53) +1 l β +1 β l i k (52) and Eqn. (53) along with the equation induced from the Note that, the rank of Eqn. 2 . Therefore, from Lemma 6 we have accident is atleast 2 2 ` 18 ` 9 ′ ′ ′ ′ ≤ = Λ Coll ( G ) | = 1] ∧| Λ , (54) , Pr[Σ = Σ ≤ i k i j 2 n n − 3 ` + 2) 2 2(2 2 n − 1 where we assume ` ≤ + 2) / 3 and the number of structure graphs with exactly (2 ( ) 3 ` 2 ` one accident among a triplet of messages is at most / 2 . Plug-in the bound of ≤ 9 2 Eqn. (51) and Eqn. (54) into Eqn. (50), we have 2 2 ` 18 18 ` ′ ′ ′ ′ = Λ Pr[Σ )] ,G ∈G ≤ ( M , ≤ 0 + Λ , = Σ 23 k i j i 2 n n 2 2 2 n − 1 (2 . ` ≤ + 2) / 3 with the assumption

52 52 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF ′ ′ ′ ′ Pr[Σ , Λ A.2 Bound of )] = Λ = Λ M , G ∈G ( 23 k i j i ′ ′ ′ ′ , Λ Pr We bound the event in a similar way as we did in bounding = Σ [Σ ∈ ,G = Λ i j i k M G . Let G )] M ( ,M denotes the set of all structure graphs corresponding to the ,M ) ( k 23 i j ,M M . Now, we write M fixed triple of messages and j i k ′ ′ ′ ′ ′ ′ ′ ′ ) Λ Pr[Σ ,G ∈G = 0] ( M )] = Pr[Σ , | = Λ = Λ G , Λ = Λ ( = Λ Coll ∧| 23 k i j j i i k i ′ ′ ′ ′ , Λ ∧| (55) = Λ + Pr[Σ . = Λ Coll ( G ) | = 1] k i j i ′ ′ ′ ′ = Λ = Λ , Λ , when number of accident in the Now, we analyse the probability of Σ i j i k 0 1 as follows: and structure graph is ′ ′ ′ ′ Number of Accident = 0. = Λ and Λ , then Σ = Λ 0 When number of accident is i j i k implies the following two system of equations: { j j i ... Y ⊕ ⊕ = 0 Y ⊕ Y 1 l l i j i k k i ... = 0 Y ⊕ ⊕ , ⊕ Y Y Y ⊕ ⊕ ... +1 α α +1 l l i k be the length of the common prefix of M = and M , then . Now, if l where 6 α α + 1 i k i i i 2 . If the rank of the above system of equations is for two random variables Y Y and α +1 l i + 1 = α l , then also the rank of the above system of equations is 2 for two random variables i j k Y and Y and hence from Lemma 6, the 2 . Thefore, in each of the cases, the rank is l l k j 1 probability that the above system of equations hold is . Moreover, the number n 3 ` (2 − +2) 2 of structure graphs with no accident is exactly 1 . Therefore, 4 1 ′ ′ ′ ′ (56) , , = Λ = Λ Λ ∧| Coll ( G ) | = 0] ≤ Pr[Σ ≤ j i k i n 2 n 2 (2 + 2) ` − 3 2 − n 1 ≤ + 2) (2 3 . ` with the assumption / Number of Accident = 1. Let be the length of the common prefix of α and M . M k i Then we have, j j i ′ ′ Σ ⊕ Y Y = Λ ⇒ ⊕ . = 0 ⊕ ... (57) Y l j i 1 l i j ′ ′ Λ = Λ Moreover, implies the following equation: i k i k i k ... ⊕ Y Y Y ⊕ ⊕ Y ⊕ ... ⊕ (58) = 0 . l +1 l α +1 α i k M and M then Eqn. (57) Note that, if the accident occurs in between the message walk of i j M is non-trivial. Similarly, if the accident occurs in between the message walk of and M i k (58) and M is non-trivial. Otherwise accident occurs in the message walk of then Eqn. j and in that case Eqn. (57) is non-trivial. Therefore, in either of the three cases the M k rank of system of equations Eqn. (57) and Eqn. (58) along with the equation induced from the accident is at least 2 . Hence, from Lemma 6, the probability that the above system 1 of equations hold is at most . Moreover, the number of structure graphs with n ` +2) (2 − 3 2 ( ) ` 3 2 exactly one accident in a triplet of messages is at most ` ≤ / 9 . Therefore, 2 2 2 2 ` 18 ` 9 ′ ′ ′ ′ ≤ = Λ Coll ( G ) | = 1] ∧| Λ , (59) , Pr[Σ = Λ ≤ i i j k 2 n n + 2) ` 3 2 2(2 − 2 1 − n (56) (2 + 2) / 3 . Plug-in the bound of Eqn. with the assumption and Eqn. (59) into ≤ ` Eqn. (55), we have 2 2 2 4 ` 20 + 2) ` 2(9 ` 18 ′ ′ ′ ′ ,G ( )] ≤ , , Λ + ≤ ∈G M ≤ = Λ = Λ Pr[Σ 23 i i j k n 2 2 n 2 n n 2 2 2 2 2 n − 1 . with the assumption ` ≤ + 2) / 3 (2

53 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 53 ′ ′ ′ ′ Λ A.3 Bound of Pr[Σ = Σ = Σ )] , ∈G M ( , G 23 k i i j M ,M ,M As before, we consider G ( ) denotes the set of all structure graphs corresponding k i j ,M to the fixed triple of messages and M M . Now, we write j k i ′ ′ ′ ′ ′ ′ ′ ′ = Σ = Σ ) ,G ∈G ( ( M )] = Pr[Σ = 0] , = Σ Λ Coll , Λ Pr[Σ ∧| = Σ | G 23 j i k k i j i i ′ ′ ′ ′ = Σ Λ ∧| Coll ( , ) | = 1] . (60) G + Pr[Σ = Σ i j i k ′ ′ ′ ′ , when number of accident in the Λ Now, we analyse the probability of = Σ Σ = Σ , i j i k and as follows: 1 structure graph is 0 Number of Accident = 0. When number of accident is 0 , then we have seen in Sect. A.1 ′ ′ = Σ 0 is that probability of unless M are = M Σ but this is not possible as M M and i j i j i j 0 , then the probability of the joint distinct. Therefore, when the number of accident is ′ ′ ′ ′ . Therefore, = Σ 0 is also and Λ = Σ event Σ i j i k ′ ′ ′ ′ G Λ Pr[Σ = Σ = Σ (61) ∧| Coll ( . ) | = 0] = 0 , j k i i Number of Accident = 1. be the length of the common suffix of M Let and M α . j i Then we have, j ′ ′ i Y = Σ l ⊕ Y ⇒ (62) . ] Σ − [ = M M [ l ⊕ − α ] α i i j j j − α − 1 i l 1 − l α − i j ′ ′ = Σ Moreover, implies the following equation: Λ i k i i k Y ... ⊕ ⊕ Y ⊕ Y = 0 . (63) 1 l l i k and Eqn. (63) along with the equation induced from the (62) Note that, the rank of Eqn. . Therefore, from Lemma 6 we have, accident is atleast 2 2 2 9 ` ` 18 ′ ′ ′ ′ , (64) ∧| Coll ( G ) | = 1] ≤ , Λ Pr[Σ = Σ = Σ ≤ i k i j 2 n n 2 ` − 2(2 + 2) 3 2 n − 1 where we assume ` ≤ + 2) / 3 and the number of structure graphs with exactly one (2 2 9 / 2 . Plug-in the bound of Eqn. (61) and accident in a triplet of messages is at most ` Eqn. (64) into Eqn. (60), we have 2 2 ` 18 18 ` ′ ′ ′ ′ , , Λ ∈G ≤ ( M )] ≤ 0 + = Σ Pr[Σ = Σ ,G 23 i j k i 2 2 n n 2 2 1 − n (2 ≤ + 2) / 3 . ` with the assumption ′ ′ ′ ′ , G Λ Pr[Σ = Λ A.4 Bound of = Σ )] M , ∈G ( 23 k i i j G ( M As before, we consider ,M denotes the set of all structure graphs corresponding ,M ) k i j M . Now, we write ,M to the fixed triple of messages and M k j i ′ ′ ′ ′ ′ ′ ′ ′ ( ) = Σ = 0] G ,G ∈G ( = Λ M )] = Pr[Σ Pr[Σ Coll = Λ | ∧| , Λ , Λ = Σ 23 j i i k i j i k ′ ′ ′ ′ + Pr[Σ . , Λ G = 1] = Σ (65) | ∧| Coll ( = Λ ) k j i i ′ ′ ′ ′ = Λ Now, we analyse the probability of Σ , Λ , when number of accident in the = Σ i j i k structure graph is 0 and 1 as follows:

54 54 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF ′ ′ ′ ′ = Λ Σ When number of accident is and Λ Number of Accident = 0. 0 = Σ , then j i i k implies the following two system of equations: { j j i ⊕ ⊕ ... ⊕ Y Y Y = 0 1 l l i j k i i Y ⊕ . ⊕ ... ⊕ Y Y = 0 l l l i i k i for random variables 2 and Note that, the rank of the above system of equations is Y l i k . Thefore, due to Lemma 6, the probability that the above system of equations hold is Y l k 1 . Moreover, the number of structure graphs with no accident is exactly 1 . As a n − +2) (2 3 ` 2 result, we have, 4 1 ′ ′ ′ ′ (66) , , Pr[Σ ∧| Coll ( Λ ) | = 0] ≤ G = Λ ≤ = Σ i i j k n 2 n 2 ` + 2) (2 − 3 2 n − 1 3 ` + 2) / ≤ . (2 with the assumption The argument for bounding the event when number of accident is one is similar to that of ′ ′ ′ ′ = Λ [Σ . If the accident occurs in , Λ in Sect. A.2 while bounding = 1] = Λ Pr | ∧| Coll ( G ) i i j k j j i = 0 or in between of M the message walk of and M M then Y M Y ⊕ ⊕ Y and ... ⊕ i k j j 1 l l i j and M is a non-trivial equation. Similarly, if the accident is between message walk of i i k i ... is a non-trivial one. Therefore, in each cases the above ⊕ Y then = 0 ⊕ Y ⊕ Y M k l l l i i k system of equations along with the equation induced from the accident has rank at least 2 and hence, from Lemma 6, the probability of the event when number of accident is one 1 is bounded by . Moreover, the number of structure graphs with exactly one n 3 +2) − (2 ` 2 2 ` / 2 . Therefore, accident among a triplet of messages is at most 9 2 2 18 ` ` 9 ′ ′ ′ ′ (67) , = 1] Coll ( G ) | ≤ ≤ , = Σ = Λ Λ Pr[Σ ∧| i k i j n 2 n + 2) 3 − 2(2 2 ` 2 1 − n (67) / 3 . Plug-in the bound of Eqn. (66) and Eqn. ≤ into ` with the assumption + 2) (2 Eqn. (65), we have 2 2 2 ` ` 2(9 4 20 + 2) 18 ` ′ ′ ′ ′ M )] Λ Pr[Σ = Λ ≤ = Σ + ≤ , ,G ∈G , ( ≤ 23 i i j k 2 2 2 n n 2 n n 2 2 2 2 n − 1 . with the assumption ` + 2) / 3 ≤ (2 ′ ′ ′ ′ A.5 Bound of , Λ = Σ )] = Λ Pr[Σ M , G ∈G ( 01 j j i i and ,M We have fixed two distinct messages M M blocks. each of the length at most ` k i j G ( M denotes the set of all structure graphs corresponding to the fixed pair of ,M Let ) j i and M . Now, we write M messages i j ′ ′ ′ ′ ′ ′ ′ ′ Pr[Σ ,G = 0] | ( M )] = Pr[Σ , = Σ Λ , Λ = Σ = Λ = Λ ∧| Coll ( G ) ∈G 01 j j j i i i j i ′ ′ ′ ′ (68) , Λ = Σ . = Λ + Pr[Σ = 1] ∧ Coll ( G ) | j i j i As argued before that when the number of accidents in the structure graph is zero, then ′ ′ ′ ′ ′ ′ Σ Σ = Λ = Σ = Σ is zero. , Λ is an impossible event and therefore, the probability of i j j j i i Number of Accident = 1. α and β be the length of the common suffix and prefix Let of M respectively. Then we have, and M j i j ′ ′ i = Σ ⇒ Σ ⊕ Y Y − l [ M ⊕ (69) . ] ] α − α l [ = M j i j i − 1 − α i j l l − 1 − α i j

55 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 55 ′ ′ Λ Moreover, implies the following equation: = Λ j i j j i i ⊕ Y Y (70) . ⊕ Y Y = 0 ⊕ ⊕ ... ⊕ ... β +1 l +1 β l i j and Eqn. (70) along with the equation induced from the Note that, the rank of Eqn. (69) . Therefore, from Lemma 6 we have accident is atleast 2 2 2 ` 8 ` 2 ′ ′ ′ ′ , (71) ∧| Pr[Σ ) | = 1] ≤ Coll = Λ ( = Σ , Λ ≤ G j i i j n n 2 − ` (2 + 2) 3 2 2 − 1 n ` ≤ + 2) / 3 and the number of structure graphs with exactly one (2 where we assume 2 accident among a pair of messages is at most . Plug-in the bound of Eqn. (71) into ` 2 Eqn. (68), we have 2 2 ` 8 8 ` ′ ′ ′ ′ , ≤ ,G ∈G Λ ( M )] ≤ 0 + Pr[Σ = Λ , = Σ 01 i j i j n 2 2 n 2 2 n − 1 / with the assumption ` + 2) ≤ 3 . (2 B Proof of Claim 3 In this section, we prove claim 3. Again, we first recall the statement of the claim: Claim 3. M be any two distinct messages such that the maximum number of ,M Let j i message blocks among these two messages is ` . Then, we have, 2 2 ` ` 3 ′ ′ ′ ′ ( M )] ≤ ; = Λ ) Pr[Σ ( a ; ( b ) Pr[Σ ∈G ≤ = Σ ,G )] ,G ∈G M ( 01 01 i i j j n n 2 2 2 ` 3 ′ ′ , ,G ∈G ( ( M )] c = Λ ) Pr[Λ ≤ 01 i j n 2 − n 1 (2 ` + 1) / ≤ . where we assume 2 Like proof of claim 2, we analyse the probability of the events according to the structure graph notion. Hence, we bound the events as stated in claim 3 based on the randomness Π . Using the same notational convention as developed in of the underlying permutation Sect. A, we bound the following: ′ ′ M B.1 Bound of )] , G ∈G = Λ ( Pr[Σ 01 j i We fix two distinct messages M M . We denote the set of all structure graphs and i j M ) and M . Now, we write . by G ( M corresponding to ,M j j i i ′ ′ ′ ′ ′ ′ | ( M )] = Pr[Σ = Λ = Λ Pr[Σ = 1] Coll ( G ) | = 0] + Pr[Σ ,G = Λ ∈G ∧| Coll ( G ) ∧| 01 j i i j j i ′ ′ ≤ = Λ Pr[Σ = 1] ∧| Coll ( G ) | = 0] + Pr[ | Coll ( G ) | j i 2 ` ′ ′ (72) , ∧| Coll ( = Λ ) | = 0] + ≤ Pr[Σ G j i n 2 where the last inequality follows from Proposition 2. Now, we analyse the probability of ′ ′ Σ as follows: , when number of accident in the structure graph is = Λ 0 j i Number of Accident = 0. We analyse this case into different subcases as follows: M - (i) Without loss of generality we assume is a prefix of M . In this case, the event i j ′ ′ Σ = Λ implies the following non-trivial equation: j i i i i , = 0 ⊕ Y ...Y Y ⊕ l l 1 i j

56 56 Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF 1 2 , follows from Lemma 1, with the which holds with probability at most ≤ n n +1 − 2 2 ` 2 n 1 − + 1) / 2 (2 ≤ ` assumption . - (ii) When none of the messages is a prefix of another. Without loss of generality, we ≥ l assume and p be the length of the common prefix of l M and M . Now, the event i j i j ′ ′ implies the following non-trivial equation: = Λ Σ j i j j i i i = 0 , ⊕ Y Y ⊕ Y ⊕ ...Y Y ⊕ l p 1 +1 p l i j 2 1 ≤ , follows from Lemma 1, with the which holds with probability at most n n − 2 2 ` +1 2 n − 1 2 ≤ + 1) / ` . assumption (2 Plug-in the bound into Eqn. (72) we obtain 2 2 2 1 ` ` 3 + 2 ` ′ ′ ( ∈G Pr[Σ M ≤ ,G ≤ ≤ )] , = Λ + 01 i j n n n n ` + 1 2 − 2 2 2 2 n − 1 ` where we assume + 1) / 2 . ≤ (2 ′ ′ B.2 Bound of Pr[Σ = Σ , G ∈G )] ( M 01 i j M M and Let us fix two distinct messages denotes the set of all structure . Let G ( M ) ,M j j i i M M and graphs corresponding to . Now, we write j i ′ ′ ′ ′ ′ ′ ∈G ) ( M )] = Pr[Σ = 1] G = Σ = Σ ( ∧| Coll Pr[Σ G ) | = 0] + Pr[Σ | Coll = Σ ,G ∧| ( 01 j i j i j i ′ ′ Coll = 1] = Σ ≤ | ∧| Pr[Σ ( G ) | = 0] + Pr[ | Coll ( G ) j i 2 ` ′ ′ ∧| Coll ( G ) = Σ = 0] + Pr[Σ ≤ (73) , | j i n 2 where the last inequality follows from Proposition 2. Now, we analyse the probability of ′ ′ = Σ 0 as follows: , when number of accident in the structure graph is Σ i j Number of Accident = 0. As argued in Sect. A.1, when the number of accident is ′ ′ 0 , then the probability of Σ = Σ is 0 as the event itself implies either (a) at least one j i collision between a pair of messages or (b) a collision in either of the message walk of M i ′ ′ . But since we condition on the number of accident is zero, Σ or M = Σ is an impossible j j i event. Therefore, 2 2 ` ` ′ ′ . ( M )] = Σ ≤ Pr[Σ ,G ∈G ≤ 0 + 01 i j n n 2 2 ′ ′ ( B.3 Bound of = Λ , G ∈G )] Pr[Λ M 01 j i ′ ′ ,M We follow the similar analysis as we did for bounding = Σ Pr ,G ∈G [Σ ( M )] . G ( M ) j i 01 j i M and denotes the set of all structure graphs corresponding to the fixed pair of messages i M . Now, we write j ′ ′ ′ ′ ′ ′ = 0] + Pr[Λ ∈G ( M )] = Pr[Λ ,G Pr[Λ = Λ = 1] | ∧| Coll ( G ) | ) = Λ G = Λ ( Coll ∧| 01 j i i j j i ′ ′ = Λ = 1] ≤ Pr[Λ | ∧| Coll ( G ) | = 0] + Pr[ | Coll ( G ) j i 2 ` ′ ′ ) = Λ ∧| Coll ( G ≤ | = 0] + Pr[Λ , (74) i j n 2 where the last inequality follows from Proposition 2. Now, we analyse the probability of ′ ′ = Λ Λ , when number of accident in the structure graph is 0 as follows: j i Number of Accident = 0. We analyse this case into different subcases as follows:

57 Nilanjan Datta , Avijit Dutta , Mridul Nandi , Goutam Paul 57 M . Then the event is a prefix of - (i) Without loss of generality we assume that M i j ′ ′ implies the following non-trivial equation: = Λ Λ j i i i , ⊕ ... ⊕ Y Y = 0 +1 l l i j 1 probability of which is bounded by , follows from Lemma 1, with the assumption n ` +1 2 − 2 n − 1 (2 ` + 1) / 2 . ≤ - (ii) when none of the message is a prefix of another. Let us assume l ≥ l . Let us assume, j i ′ ′ implies the and M . Now, the event is the length of the common prefix of Λ M p = Λ j i j i following non-trivial equation j j i i ⊕ ... ⊕ Y Y ... Y ⊕ Y , ⊕ = 0 +1 l p +1 p l i j 1 , follows from Lemma 1, with the assumption probability of which is bounded by n ` 2 − 2 n − 1 ` ≤ + 1) / 2 . Note that, if l (2 = l otherwise the probaility would then p < l 1 − j i j become zero. Plug-in the bound into Eqn. (74) we obtain 2 2 2 1 ` ` 3 + 2 ` ′ ′ )] ,G ∈G = Λ ( M Pr[Λ ≤ + ≤ , ≤ 01 i j n n n n 2 ` 2 − + 1 2 2 2 − n 1 (2 where we assume ` ≤ + 1) / 2 .

Physician Directory By A to Z Abbate , Antonio , MD Abdallah , Adel , MD Pediatrics Cardiology Neonatology General Internal Medicine Ambulatory Care Center VCU Medical Center Critical Care Hospital 12...

More info »Physician Directory By A to Z Abbate , Antonio , MD Abdallah , Adel , MD Pediatrics Cardiology Neonatology General Internal Medicine Ambulatory Care Center VCU Medical Center Critical Care Hospital 12...

More info »Virginia Victim Assistance Directory Department of Cri minal Justice Services th 1100 Bank Street , 1 Floor 2 Richmond, Virginia 23219 (804) 371 - 6507 Fax: (804) 786 - 3414 www.dcjs.virginia.gov

More info »S. Pub. 115-7 2017-2018 Official Congressional Directory 115th Congress Convened January 3, 2017 JOINT COMMITTEE ON PRINTING UNITED STATES CONGRESS UNITED STATES GOVERNMENT PUBLISHING OFFICE WASHINGTO...

More info »NATIONAL BUDGET DEFENSE ESTIMATES FOR FY 201 9 OFFICE OF THE UNDER SECRE TA RY OF DEFENSE (COMPTROLLER) APRIL 201 8

More info »SCRIE TENANTS LIST ~ By Docket Number ~ Borough of Bronx SCRIE in the last year; it includes tenants that have a lease expiration date equal or who have received • This report displays information on ...

More info »DOE/EIA ‐ 0035( 2019/4 ) April 2019 Monthly Energy Review www.eia.gov/mer

More info »* = mailing address different than service Treatment Service Provider Directory by City location City Zip Code Phone Number Treatment Provider Service Address Abingdon Appalachian Clinical Services 24...

More info »ALICE: A STUDY OF 2018 FINANCIAL HARDSHIP REPORT IN LOUISIANA ® L imited, is an acronym for A sset ALICE I ncome C onstrained, E mployed. The United Way ALICE Project is a collaboration of United Ways...

More info »* = mailing address different than service Treatment Service Provider Directory by City location City Zip Code Phone Number Treatment Provider Service Address Abingdon Appalachian Clinical Services 24...

More info »The Economic Benefits of More Fully Utilizing Advanced 2 201 M ay Practice Registered Nurses in the Provision of Health An Analysis of Local and Statewide Effects on Care in Texas: Business Activity T...

More info »D / E I A - 0 3 8 4 ( 2 0 1 1 ) E | S e p t e m b e r 2 0 1 2 O 1 1 0 2 w e i v e R y g r A n n u a l E n e . r a / v o g e a i e . w w w

More info »The Health Consequences of Smoking—50 Years of Progress A Report of the Surgeon General U.S. Department of Health and Human Services

More info »Local Departments of Social Services Albemarle County Department of Social Accomack Department of Social Services Mary E. Parker, Director Services Kathy Ralston, Director 22554 Center Parkway Accawma...

More info »1 2019 Majoring in Money Sallie Mae | Ipsos 2019 Majoring in Money How college students and other young adults manage their finances Let’ s Make College Happen Conducted by Ipsos Public Affairs

More info »201 8 Fourth National Report on Human Exposure to Environmental Chemicals U pdated Tables, March 2018 , Volume One

More info »State of California Civil Service Pay Scale - Alpha by Class Title Class Schem Full Class Title Code Pay CBID NT Prob. Mo. WWG MCR Period AR Crit Footnotes Compensation SISA ACCOUNT CLERK II 1733 CU70...

More info »Userid: CPM Pt. size: 10 Leadpct: 100% Schema: Draft Ok to Print i1040x Fileid: ... ions/I1040/2018/A/XML/Cycle08/source (Init. & Date) _______ AH XSL/XML Page 1 of 117 14:16 - 24-Jan-2019 The type an...

More info »APD Issued 2017-1.5 Manual Policy 7/20/2017 Austin Police Department Policy Manual CHIEF'S MESSAGE I am proud to present the newest edition of the Austin Police Department Policy Manual. The Policy Ma...

More info »