Damien Vergnaud

Ecient and Secure Generalized Pattern Matching via Fast Fourier Transform

Keywords: Two-party secure computation, Pattern matching, Homomorphic encryption, Fast Fourier Transform

We present simple protocols for secure two-party computation of generalized pattern matching in the presence of malicious parties.

The problem is to determine all positions in a text T where a pattern P occurs (or matches with few mismatches) allowing possibly both T and P to contain single character wildcards. We propose constant-round protocols that exhibit linear communication and quasilinear computational costs with simulation-based security. Our constructions rely on a well-known technique for pattern matching proposed by Fischer and Paterson in 1974 and based on the Fast Fourier Transform. The security of the new schemes is reduced to the semantic security of the ElGamal encryption scheme.

Introduction

We present secure protocols for two-party computation of (exact or approximate) pattern matching which are more ecient and conceptually simpler than previous approaches. Our proposals are constant-round and requires linear communication and quasilinear computational costs.

Prior work. The pattern matching problem [START_REF] Crochemore | Jewels of Stringology[END_REF] is to nd all the occurrences of a given pattern P of length m in a text T of length n, both being sequences of characters drawn from a nite character set Σ. It is an important problem for many kinds of processes of strings, for instance in molecular biology, information retrieval, pattern recognition, compiling, data compression, program analysis and security. These applications often require more sophisticated forms of searching: approximate pattern matching [START_REF] Schoenmeyr | FFT-based algorithms for the string matching with mismatches problem[END_REF], where the problem is to nd the locations where the Hamming distance of T substrings and P is less than some threshold k ≤ m; pattern matching with wildcards (or don't cares) [START_REF] Fischer | Paterson String Matching and Other Products , Complexity of Computation[END_REF], where the problem is to nd all occurrences of a pattern P ∈ (Σ ∪ { }) m in a text T ∈ (Σ ∪ { }) n where the wildcard character / ∈ Σ matches any character in Σ.

An intensive research eort since the 1970s has led to the design of several ecient algorithms for generalized pattern matching (see [START_REF] Crochemore | Jewels of Stringology[END_REF]). In 1974, Fischer and Paterson [START_REF] Fischer | Paterson String Matching and Other Products , Complexity of Computation[END_REF] solved the pattern matching with wildcards problem in O(n log m log(#Σ)) time using convolution and Fast Fourier Transform (FFT).

After several improvements, Cliord and Cliord [START_REF] Clifford | Simple Deterministic Wildcard Matching[END_REF] proposed a simple deterministic algorithm that also involves convolutions and runs in time O(n log m). A more complex algorithm in optimal O(n) time was proposed in [START_REF] Rahman | Iliopoulos Pattern Matching Algorithms with Don't Cares[END_REF]. The FFT was also used to propose fast algorithms for the approximate pattern matching problem (e.g. [START_REF] Schoenmeyr | FFT-based algorithms for the string matching with mismatches problem[END_REF]).

In the setting of secure two-party computation, introduced in 1982 by Yao [START_REF] Yao | Protocols for Secure Computations[END_REF], two parties wish to jointly compute some function of their private inputs while preserving a number of security properties. Troncoso-Pastoriza, Katzenbeisser and Celik [START_REF] Troncoso-Pastoriza | Privacy preserving error resilient dna searching through oblivious automata[END_REF] were the rst to consider (basic) pattern matching in the context of secure computation (in the semi-honest setting). Their protocol implements the well-known Knuth-Morris-Pratt algorithm [START_REF] Knuth | Pratt Fast Pattern Matching in Strings[END_REF] and is linear in the input length. Hazay and Lindell [START_REF] Hazay | Lindell Ecient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries[END_REF] proposed later a protocol based on oblivious pseudorandom function evaluation which achieves one-sided simulatability security. The rst construction for the (basic) pattern matching problem with full simulation-based security in the malicious setting was developed by Gennaro, Hazay and Sorensen in [START_REF] Gennaro | Text Search Protocols with Simulation Based Security[END_REF]. Their protocol relies on the Knuth-Morris-Pratt algorithm but requires linear round complexity and quadratic communication and computational cost. The rst work which addresses the approximate pattern matching problem is [START_REF] Jarrous | Pinkas Secure Hamming Distance Based Computation and Its Applications[END_REF].

Very recently, Hazay and Toft [START_REF] Hazay | Toft Computationally Secure Pattern Matching in the Presence of Malicious Adversaries[END_REF] proposed constant-rounds and ecient protocols for the (basic) pattern matching, the approximate pattern matching and the pattern matching with wildcards problems. Their schemes achieve security against malicious adversaries with (optimal) linear computational cost and bandwidth for the rst problem but quadratic communication and computational complexity for the two extended problems.

Contributions of the paper. The main contribution of the paper is to provide protocols for approximate pattern matching (permitting a constant number of mismatches) and pattern matching with wildcards with constant-rounds, linear communication and O(n log m) computational costs.

# of Rounds Communication Exponentiations

Basic Pattern Matching with alphabet Σ

Hazay & Toft [START_REF] Hazay | Toft Computationally Secure Pattern Matching in the Presence of Malicious Adversaries[END_REF][START_REF] Canetti | Security and composition of multiparty cryptographic protocols[END_REF]

O(1) O(n log |Σ|) O(n log |Σ|) 3 O(1) O(n) O(nm)
Approximate Binary Pattern Matching with k Mismatches

Hazay & Toft [START_REF] Hazay | Toft Computationally Secure Pattern Matching in the Presence of Malicious Adversaries[END_REF][START_REF] Cheon | Seo Multi-Party Privacy-Preserving Set Intersection with Quasi-Linear Complexity[END_REF] O(1) O(nm) O(nm)

5.1 O(1) O(nk) O(n(log m + k))
Binary Pattern Matching with Wildcards

Hazay & Toft [START_REF] Hazay | Toft Computationally Secure Pattern Matching in the Presence of Malicious Adversaries[END_REF][START_REF] Chaum | Wallet Databases with Observers[END_REF] O(1) O(nm) O(nm) The problem we address can be described as follows: let us assume that Alice holds a text T ∈ (Σ ∪ { }) n , while Bob has a pattern P ∈ (Σ ∪ { }) m . The goal is for Bob to learn where P occurs (or matches with few mismatches) in T while Alice does not gain any information about P from the protocol execution and Bob does not learn anything but the matched text locations. Our approach relies on the classical homomorphic encryption paradigm (e.g. [16, 7.2.2.]): Bob will encrypt P bit by bit for an additively homomorphic encryption scheme and Alice will then apply the deterministic algorithm from [START_REF] Clifford | Simple Deterministic Wildcard Matching[END_REF][START_REF] Schoenmeyr | FFT-based algorithms for the string matching with mismatches problem[END_REF] under encryption (using the homomorphic properties of the cryptosystem) and sends back the encrypted result to Bob.

5.2 O(1) O(n) O(n log m)
First, we present a protocol for the (basic) pattern matching problem [START_REF] Canetti | Security and composition of multiparty cryptographic protocols[END_REF] that is secure against malicious adversaries, but for the so-called one-sided simulatability weaker security notion. The construction relies on a straightforward observation that permits to perform secure pattern matching independently of the size of the alphabet Σ. Our main goal by presenting this scheme is to illustrate the ideas we will use in the following sections.

The Fast Fourier Transform (FFT) [START_REF] Cooley | An algorithm for the machine calculation of complex fourier series[END_REF] is an algorithm to compute the discrete Fourier transform and its inverse. It leads notably to quasilinear polynomial multiplication algorithms. In order to apply Fischer and Paterson technique to secure two-party generalized pattern matching, one needs to construct a protocol for two-party FFT with quasilinear computational complexity. The idea of using FFT in secure two-party computation is probably not new 1 but we have not been able to locate a reference in the literature. We provide a description [START_REF] Chaum | Wallet Databases with Observers[END_REF] in the hope that it may be of independent interest. We denote the security parameter by κ and input lengths are always assumed to be bounded by some polynomial in κ. A probabilistic algorithm is said to run in polynomial-time (PPT) if it runs in time that is polynomial in κ. Let A be a PPT algorithm and let x be an input for A. The probability space that assigns to a string σ the probability that A, on input x, outputs σ is denoted by A(x).

Given a probability space S, a PPT algorithm that samples a random element according to S is denoted by x R ← -S. For a nite set X, x R ← -X denotes a PPT algorithm that samples a random element uniformly at random from X.

ElGamal Encryption

For a security parameter κ, the ElGamal encryption scheme [START_REF]A Public Key Cryptosystem and a Signature Scheme based on Discrete Logarithms[END_REF] operates on a cyclic group G of κ-bits prime order q and identity element 1 G . Let g denote a generator of G. The ElGamal public and secret keys are (G, q, g, y) and (G, q, g, x) (respectively) where x is picked uniformly at random in Z q and y = g x . A message m ∈ G is encrypted by picking r uniformly at random in Z q and the ciphertext is (g r , y r • m). We will use the notation: The ElGamal scheme is homomorphic relative to multiplication. In this paper, we consider a modied version of ElGamal where the encryption is performed in the exponents: one chooses r uniformly at random in Z q and computes (g r , y r • g m ). Decryption of a ciphertext c = (α, β) is performed by computing g m = β/α x . The fact that m cannot be eciently recovered is not problematic for the way ElGamal is incorporated in our protocols. This variant of ElGamal is additively homomorphic and can be used to perform oblivious linear computations in the exponent: it naturally allows for multiplication with a plaintext constant using repeated doubling and adding.

(g r , y r • m) R ← -Enc y (m) or (g r , y r • m) ← Enc y (m; r) A ciphertext (α, β) is decrypted as m = β/α x ← Dec x (α, β).

Zero-Knowledge

Security in the presence of malicious behavior is usually achieved by forcing the parties to demonstrate that they are well-behaved. In our protocols, we need zero-knowledge proofs of knowledge that some algebraic statement R holds in a group G = g of prime order q with 2 κ-1 < q < 2 κ . We will use Σ-protocols made secure against malicious veriers (using standard techniques) since they are ecient and achieves constant communication complexity (see [START_REF] Hazay | Toft Computationally Secure Pattern Matching in the Presence of Malicious Adversaries[END_REF]):

π DL : due to Schnorr [START_REF] Bieliková | Schnorr Ecient Signature Generation by Smart Cards[END_REF], this Σ-protocol allows a prover to demonstrate knowledge of the solution to a discrete logarithm problem:

R DL = {[h, x] | h = g x }.
π eqDL : due to Chaum and Pedersen [START_REF] Chaum | Wallet Databases with Observers[END_REF], this Σ-protocol demonstrates equality of two discrete logarithm problems (as well as its knowledge):

R eqDL = {[(g 1 , g 2 , h 1 , h 2 ), x] | h 1 = g x 1 ∧ h 2 = g x 2 }.
We will use Σ-protocols for ElGamal ciphertexts for the public key (G, q, g, y):

π Mult : due to Abe, Cramer and Fehr [START_REF] Abe | Non-interactive distributed-verier proofs and proving relations among commitments[END_REF], this Σ-protocol demonstrates that a ciphertext is an encryption of the product of the plaintexts of two given ciphertexts:

R Mult = {[(c 1 , c 2 , c 3 ), (m, r, s)] |c 1 = Enc y (g m ; r) ∧ c 3 = c 2 m • Enc y (1 G ; s) } .
π Perm : due to Groth [START_REF] Groth | A Veriable Secret Shue of Homomorphic Encryptions[END_REF], this Σ-protocol demonstrates that a set of ciphertexts is a permutation and rerandomization of another set of ciphertexts:

R Perm = [(c i , c i ) i∈[[k]] , (σ, (r i ) i∈[[k]] )] σ ∈ S k c i = c σ(i) •Enc y (1 G ; r i ), ∀i ∈ [[k]]
.

π nze : this Σ-protocol demonstrates that a ciphertext is a rerandomization of another ciphertext at some non-zero power:

R nze = [(c 1 , c 2 ), (R, r)] c 1 = c R 2 • Enc y (1 G ; r) ∧ R = 0 .
π isBit : this Σ-protocol demonstrates that a ciphertext encrypts 0 or 1:

R isBit = {[c, (b, r)] | c = Enc y (g b ; r) ∧ b ∈ {0, 1}}.
π isTrit : this Σ-protocol demonstrates that a ciphertext encrypts 0, 1 or 2:

R isTrit = {[c, (b, r)] | c = Enc y (g b ; r) ∧ b ∈ {0, 1, 2}}.
The protocol π nze can be otained from π Mult as described in [START_REF] Hazay | Toft Computationally Secure Pattern Matching in the Presence of Malicious Adversaries[END_REF] and the protocols π isBit and π isTrit can be obtained from π EqDL using the technique of Cramer, Gennaro and Schoenmakers [START_REF] Cramer | A Secure and Optimally Ecient Multi-Authority Election Scheme[END_REF].

We also need a protocol π KeyGen for generation of an ElGamal public key such that two parties hold shares of the secret key and a protocol π Dec for shared decryption of a ciphertext encrypted using a key generated by π KeyGen .

We consider a protocol where only one party obtains the decrypted result (see [17, 2.3]). We denote the associated ideal functionalities F KeyGen and F Dec .

Secure Two-Party Computation

We only provide a brief review of two-party computation denitions and we refer the reader to the recent book [16, Chapter 2] for more details. Let f be a twoargument function and let Alice and Bob be two possibly malicious parties, the rst having an input x and the second having an input y. Securely computing f means that Alice and Bob keep turns exchanging message strings so that:

-Bob learns z = f (x, y) but nothing about x (not already implied by y and z); -Alice learns nothing about y (and nothing about z not already implied by x).

In particular, Alice and Bob wish to ensure that nothing is revealed from the protocol execution to an outsider or the other party (privacy ) and that the output is computed according to the specied function (correctness ). In this paper, we do not require the correctness to hold with probability 1 but instead allow negligible probability of error in the value output by the protocol.

The simulation-based security denitions formalize the intuition that whatever can be computed by a party can be computed based on its input and output only. This is done by comparing a party's view in a real protocol execution to an ideal execution, where a trusted party computes the function and sends the output to the parties. In this paper, we consider two avors of simulation-based security in the presence of malicious adversaries: Full simulation security [START_REF] Canetti | Security and composition of multiparty cryptographic protocols[END_REF]: it requires that for every PPT adversary A in the real world, there exists a corresponding PPT simulator S in the ideal world such that the view are computationally indistinguishable.

One-sided simulation security: where full simulation is provided for only one of the corruption cases and only privacy is achieved for the other case (guaranteeing that the adversary does not learn anything but the output of the computation).

Warm Up: (Basic) Pattern Matching Protocol

In this section, we address the question of how to securely compute the functionality F PM dened by

((P, n), (T , m)) → ({j ∈ [[n -m + 1]], T j = P}, ⊥) if P ∈ Σ m ∧ T ∈ Σ n (⊥, ⊥)
otherwise where T j denotes the substring of length m that begins at the j-th position in T . Note that Alice learns nothing about P and the only thing Bob learns about T is the locations where P appears. We assume that #Σ = poly(κ) and Σ ⊆ Z q .

Motivated by the task of constructing a simple protocol for F PM , we use the straightforward observation that P = (p 1 , . . . , p m ) occurs at the j-th position in T = (t 1 , . . . , t n ) if and only if p i -t i+j-1 = 0 for all i ∈ [[m]] and that consequently for random (s 1,j , . . . , s m,j ) ∈ Z m q , the equality

m i=1 s i,j (p i -t i+j-1 ) = 0 (1)
holds with probability 1 if P = T j and with probability 1/q otherwise (where the probability is taken over the random s i,j for i ∈ [[m]]).

This observation results in a simple protocol for F PM that can be summarized as follows:

1. Bob picks at random x ∈ Z q and sets y = g x . He sends y to Alice and proves his knowledge of x by running π DL using x.

2. Bob encrypts P character by character with his own public key y:

c i = (α i , β i ) R ← -Enc y (g pi ) for i ∈ [[m]]
d j = g rj m i=1 α si,j i , y rj m i=1 β i g -tj+i-1 si,j = Enc y (1 G , r j ) • m i=1 c i • (1 G , g -tj+i-1 )
si,j for r j , s 1,j , . . . , s m,j picked uniformly at random in Z q . Alice sends d j for j ∈ [[n -m + 1]] to Bob. 4. Bob decrypts d j for j ∈ [[n-m+1]] thanks to his knowledge of x and outputs the set of indices of ciphertexts that encrypt 1 G .

Alice Bob

x R ← -Zq; y ← g x y, πDL[y, x] ⇐==========⇒ ci R ← -Ency(g p i ) for 1 ≤ i ≤ m (ci) ← ------------ i∈[[m]] rj, s1,j, . . . , sm,j R ← -Zq dj ← Ency(1 G , rj) • m i=1 ci • (1 G , g -t j+i-1 ) s i,j (for j ∈ [[n -m + 1]]) (dj) ------------→ j∈[[n-m+1]] aj ← Decx(dj) (for 1 ≤ j ≤ n -m + 1) S ← {j ∈ [[n -m + 1]], aj = 1 G } Output ⊥ Output S
Fig. 1: Secure Basic Pattern Matching

The protocol ow is described in Fig. 1 (where simple arrows indicate data transmission and double arrows stand for interactive protocols). The protocol is less ecient than the scheme from [START_REF] Hazay | Toft Computationally Secure Pattern Matching in the Presence of Malicious Adversaries[END_REF] since it exhibits linear communication 2 but quadratic computation costs. However it is simpler and illustrates the ideas we will use in the next sections. It achieves one-sided simulation security against malicious adversaries.

Theorem 1. If π DL is a zero-knowledge proof of knowledge of a discrete logarithm secure against malicious veriers and if the ElGamal encryption scheme is semantically secure, then the protocol described in Fig. 1 securely computes F PM with one-sided simulation security against malicious adversaries.

Proof (Sketch). As in [17, Theorem 1], we separately prove the security in the case that Alice is corrupted and the case that Bob is corrupted.

Alice is corrupted: Since Alice does not receive any output from the execution, and we are only proving one-sided simulation security here, all we need to show is that privacy is preserved. This follows readily from the semantic security of the ElGamal encryption scheme.

Bob is corrupted: Let A denote an adversary controlling Bob. We need to prove that A does not learn anything but the matching text locations. We construct a simulator S as follows:

1. S is given a pattern of length m, an integer n and A's auxiliary input and invokes A on these values. 2. S obtains A's secret key x from the proof of knowledge extractor for π DL .

d j R ← -Enc y (g bj ) θj for j ∈ [[n -m + 1]] where b j ∈ {0, 1} with b j = 0 ⇐⇒ j ∈ I and θ j R ← -Z q . (b) If there is an i ∈ [[m]] such z i = g σi for all σ i ∈ Σ, then S aborts
by sending ⊥ to the trusted party for F P M and produces a vector of ciphertexts:

d j R ← -(Enc y (g)) θj for j ∈ [[n -m + 1]]
where θ j R ← -Z q . 4. If at any point A sends an invalid message S aborts, sending ⊥ to the trusted party for F P M . Otherwise, it outputs whatever A does.

Since |Σ| = poly(κ), the simulator S runs in polynomial time (the running time of the third step being upper-bounded by O(m |Σ|) group operations using generic technique for discrete logarithm computation in short intervals). Our basic observation on [START_REF] Abe | Non-interactive distributed-verier proofs and proving relations among commitments[END_REF] shows readily that the adversary's view is statistically close to its view in the real execution of the protocol.

Remark 1. Observe that the protocol from Fig. 1 does not achieve correctness when Alice is corrupted. However, it is possible to achieve full simulation security against malicious adversaries by enforcing Alice to use only text symbols t i in Σ for i ∈ [[n]] (using for instance generalization of π isBit and π isTrit ) and proving consistency of the ciphertexts (δ j , γ j ) 1≤j≤n-m+1 .

4 Secure Fast Fourier Transform and Polynomial Multiplication

FFT and Polynomial Multiplication: a Brief Recall

Let q be a prime number, D a divisor of q -1 and ω a primitive D-th root of 1 in Z * q (for simplicity, one can assume that D is a power of two). Suppose we are given two polynomials in A, B ∈ Z q [X] of degree less than d = D/2. The FFT is a well-known method to compute the coecients of C(X) = A(X)B(X) in O(D log D) multiplications in Z q :

1. Evaluate A and B at the D points: 1, ω, ω 2 , . . . , ω D-1 using the Discrete Fourier Transform (DFT):

Evaluation of P ∈ Z q [X] at 1, ω, ω 2 , . . . , ω D-1 Write P (X) = P 0 (X 2 ) + XP 1 (X 2 ) Evaluate (recursively) P 0 and P 1 at 1, ω 2 , ω 4 , . . . , ω D-1 Write P (ω i ) = P 0 (ω 2i ) +

ω i P 1 (ω 2i ) for i ∈ [[D]]
2. Compute the values of C(X) at these D points 1, ω, ω 2 , . . . , ω D-1 .

3. Interpolate the polynomial C using the inverse DFT:

Interpolation of P ∈ Z q [X] given values at 1, ω, ω 2 , . . . , ω D-1 Write P (X) = P (1) + P (ω)X + • • • + P (ω D-1 )X D-1 Evaluate (as in 1.) P at 1, ω -1 , ω -2 , . . . , ω 1-D Output P (X) = 1 D P (1) + P (ω -1 )X + • • • + P (ω 1-D )X D-1

Secure Fast Polynomial Multiplication

We now outline a protocol to eciently and securely compute the encryption of the product of two polynomials (for a given public key y). Let us assume that Alice holds a polynomial A(X)

= d-1 i=0 a i X i ∈ Z q [X] and that Bob holds a polynomial B(X) = d-1 i=0 b i X i ∈ Z q [X
] both of degree less than d.

Alice encrypts the polynomial A coecient by coecient (in the exponents):

α 0 = Enc y (g a0 ), α 1 = Enc y (g a1 ), . . . , α d-1 = Enc y (g a d-1 ) and sends the ciphertexts (α 0 , α 1 , . . . , α d-1 ) to Bob. 2. Bob encrypts the polynomial B coecient by coecient (in the exponents):

β 0 = Enc y (g b0 ), β 1 = Enc y (g b1 ), . . . , β d-1 = Enc y (g b d-1 )
and sends the ciphertexts (β 0 , β 1 , . . . , β d-1 ) to Alice.

3. Alice and Bob (simultaneously and independently) compute the encrypted value of g A(ω i ) and g B(ω i ) for i ∈ [[D]] using the DFT (Step 1 in the FFT method). Since the encryption scheme is additively homomorphic, it can be used to perform deterministic oblivious linear computations in the exponent. At this step of the protocol, Alice and Bob then share (identical) encryption of g A(ω i ) and g B(ω i ) for i ∈ [[D]] and Alice 3 knows the randomness corresponding to the encryption of g A(ω i ) . 4. Alice computes the encryption of g A(ω i )B(ω i ) for i ∈ [[D]] knowing A(ω i ) and the shared encryption of g B(ω i ) (Step 2 in the FFT method). Alice sends the resulting ciphertexts to Bob and, thanks to her knowledge of the randomness in the shared encryption of g A(ω i ) she can prove its validity by running the protocol π Mult .

5. Alice and Bob (simultaneously and independently) compute the encrypted coecients of AB (in the exponents) using the inverse DFT (Step 3 in the FFT method).

The computational complexity of the protocol is O(D log D) exponentiations in G and its communication complexity is O(D) (and therefore optimal). In order to use this fast two-party polynomial multiplication protocol in our generalized pattern matching schemes, we will need the encrypted computation to be done under a public-key whose corresponding secret-key is shared between Alice and Bob. The fact that intermediate values are encrypted under a key which neither Alice or Bob know permits the zero-knowledge simulation.

We do not propose any specic application in the realm of polynomial arithmetic for this protocol but we will rather provide applications to the generalized pattern matching problem in the following section. Remark 2. It is possible to enforce the polynomials coecients to belong to a specic subset of Z q (e.g. we will use the set {0, 1} or {0, 1, 2} in the following and use the protocols π isBit and π isTrit to ensure these properties).

Fast Secure Generalized Pattern Matching

The main idea of the algorithm from [START_REF] Clifford | Simple Deterministic Wildcard Matching[END_REF] is to calculate the sum of squared differences between the pattern and the text for every possible alignment. Suppose 3 Of course, Bob knows the randomness corresponding to the encryption of g B(ω i ) and in the rest of the protocol, one can exchange the role of Alice and Bob. without loss of generality that Σ ⊂ N. If there are no wildcards then for each

location i ∈ [[n -m + 1]], we can calculate m j=1 (p j -t i+j-1 ) 2 = m j=1 p j 2 -2p j • t i+j-1 + t i+j-1 2 (2)
in O(n log n) time using FFT. Wherever there is an exact match this sum will be exactly 0. When wildcards are allowed in the pattern and the text we replace the wildcard symbols by 0's (and other symbols by non-negative integers) and then consider the sum m j=1

p j t i+j-1 (p j -t i+j-1 ) 2 = m j=1 p j 3 t i+j-1 -2p j 2 • t i+j-1 2 + p j t i+j-1 3 (3)
which equals 0 if and only if there is an exact match with wildcards. The sum (3) can be computed with three convolutions and therefore in O(n log n) time using FFT.

In order to reduce the time complexity from O(n log n) to O(n log m), we will use a standard trick which consists in partitioning T into n/m overlapping substrings of length 2m with the rst substring starting at the beginning of the text and each subsequent substring having an overlap of length m with the previous one. The matching algorithm is then performed separately on each sub- In the following, we will use this trick and for simplicity we will assume (without loss of generality) that n = 2m and that 4m is a power of 2 dividing q -1.

The protocol for (fast) secure polynomial multiplication can be used to securely compute sums of the form (2) or (3) in time O(m log m). The gure Fig. 2 presents the common opening for our generalized pattern matching protocols.

At the end of this subprotocol, Alice and Bob hold shares (x a , x b ) of the secret key corresponding to the public key y. encryption a i of the bit

t i for i ∈ [[2m]]. encryption b i of the bit p m-i+1 for i ∈ [[m]]. encryption f i+m of the sum m j=1 p j • t i+j-1 for i ∈ [[m]].
Note that we modify the ordering of the pattern bits, in order to compute [START_REF] Abrahamson | Generalized String Matching[END_REF] or (3) as an actual convolution and that we enforce ciphertexts a i and b i to encrypt bits using the protocol π isBit (as mentioned above).

Pattern Matching with Mismatches

Our rst algorithm is in fact independent of the bound k and report the Hamming distance at every position irrespective of its value.

Alice

Bob ----------------------

y ∈ G πKeyGen[κ, κ] ⇐====================⇒ y ∈ G xa ∈ Zq [with y = g xa+x b ] x b ∈ Zq σi R ← -Zq ρi R ← -Zq ai ← Ency(g t i ; σi) bi ← Ency(g p m-i+1 ; ρi) (for i ∈ [[2m]]) (for i ∈ [[m]]) (ai) ----------------------→ i∈[[2m]] (bi) ← ---------------------- i∈[[m]] πisBit [(ai, ti, σi)] ⇐====================⇒ i∈[[2m]] πisBit [(bi), pm-i+1, ρi)] ⇐====================⇒ i∈[[m]] ct ← m i=1 ai w ti ct ← m i=1 ai w ti dt ← m i=1 bi w ti dt ← m i=1 bi w ti τt ← d i=1 σiω ti ζt R ← -Zq et ← bt T (ω t ) g ζ t (for t ∈ [[4m]]) (for t ∈ [[4m]]) (et)
→ t∈[[4m]] π Mult [(ct, dt, et), (T (ω t ), τt, ζt)] ⇐====================⇒ t∈[[4m]] fi ← 2m t=1 (et) w -ti 1/4m fi ← 2m t=1 (et) w -ti 1/4m (for i ∈ [[4m]]) (for i ∈ [[4m]])
((P, n), (T , m)) → d H (T i , P) i∈[[n-m+1]] , ⊥
Again Alice learns nothing about P and the only thing that Bob learns about T is the number of matches of P and T i for i ∈ [[n -m + 1]]. We denote HD(P, T )

the Hamming distance vector of P and T output by this functionality.

Over a binary alphabet, the sum (2) becomes:

d H (T i , P) = m j=1 p j 2 -2p j • t i+j + t i+j 2 = m j=1 (p j -2p j • t i+j + t i+j ) (4)
and therefore, with the previous notation, the product

m j=1 a i+j • b j • f i+m -2 encrypts the value d H (T i , P) for i ∈ [[n -m + 1]].
It is therefore easy to extend the opening of Fig. 2 in order to securely compute the functionality F HD . The detailed protocol ow is given in Fig. 3.

(follows the protocol described in Fig. 2)

Alice Bob θi ← m j=1 ai+j • bj • fi+m -2 θi ← m j=1 ai+j • bj • fi+m -2 ψi R ← -Zq θi ← θi • Ency(1 G ; ψi) (for i ∈ [[n -m + 1]]) (for i ∈ [[n -m + 1]]) (θi) ----------------→ i∈[[n-m+1]] πeqDL[(θi/θi, g, y), ψi] ⇐ =============== ⇒ i∈[[n-m+1]] πDec[(θi, xa)] ⇐ =============== ⇒ i∈[[n-m+1]] ( θi) 1≤i≤n-m+1 hi ← log g (Decx b ( θi)) (for i ∈ [[n -m + 1]]) Output ⊥
Output (h1, . . . , hn-m+1) Fig. 3: Secure Computation of the Hamming distance vector HD(P, T )

The protocol is constant-round with linear communication complexity and O(n √ m) time complexity. We can prove that it achieves full simulation security against malicious adversaries.

Theorem 2. If π eqDL , π Mult , π isBit are zero-knowledge proofs of knowledge secure against malicious veriers for the languages R eqDL , R Mult and R isBit , if π KeyGen and π Dec are protocols secure against malicious veriers for the functionality F KeyGen and F Dec and if the ElGamal encryption scheme is semantically secure, then the protocol described in Fig. 3 securely computes F HD in the presence of malicious adversaries.

Proof (Sketch). We consider only the security in the case that Bob is corrupted (the proof in the case that Alice is corrupted follows the same lines).

Bob is corrupted: Let A denote an adversary controlling Bob. We need to prove that A does not learn anything but the matching text locations. We construct a simulator S as follows:

1. S is given a pattern of length m, an integer n and A's auxiliary input and invokes A on these values. 2. S emulates the trusted party for π KeyGen as follows by choosing two random elements x A and x B in Z q and hands A, its share x B and the public key y = g x A +x B . 3. S receives from the adversary A a vector of m ciphertexts (α i , β i

) for i ∈ [[m]]. If the functionality F R isBit

ZK

aborts, then S aborts, sending ⊥ to the trusted party for F HW . 4. Otherwise S denes the pattern P using the witnesses for π isBit and sends P to the ideal functionality F HW . 5. The simulator S sets T = 1 n ∈ Σ n . 6. S completes the execution as the honest Alice would on input T but simulates the proof in order to be consistent with the vector output by the ideal functionality F HW . If at any point A sends an invalid message S aborts, sending ⊥ to the trusted party for F P M . Otherwise, it outputs whatever A does.

Following the proof of [START_REF] Hazay | Toft Computationally Secure Pattern Matching in the Presence of Malicious Adversaries[END_REF]Theorem 1], it is easy to prove that if there exists a distinguisher D for these executions, then there exist a PPT adversary breaking the semantic security of ElGamal encryption.

Secure Pattern Matching with k Mismatches. We now propose an ecient protocol for the following problem: given an integer k, a binary text T of length n and a binary pattern P of length m, compute the functionality, denoted by F PM-k :

((P, n), (T , m)) → ({i ∈ [[n -m + 1]], d H (T i , P) ≤ k}, ⊥)
Again Alice learns nothing about P and the only thing that Bob learns about T is the locations where P appears with less than k mismatches.

Let us recall that the protocol of Fig. 3

produces ciphertexts θ i that encrypt the value d H (T i , P) for i ∈ [[n -m + 1]]. Therefore [θ i • (1 G , g -)] u • Enc y (1 G , v) (5) for random u R ← -Z * q and v R ← -Z q is a uniformly distributed encryption of 1 G if d H (T i , P) = and of a random element from G otherwise.
(follows the protocol described in Fig. 2) such that the vector of (permuted) at location i contains one (and only one)

Alice Bob S ← ∅ θi ← m j=1 ai+j • bj • fi+m -2 θi ← m j=1 ai+j • bj • fi+m -2 (for i ∈ [[n -m + 1]]) (for i ∈ [[n -m + 1]]) u1,i, . . . , u k,i R ← -Z * q v1,i, . . . , v k,i R ← -Zq (for i ∈ [[n -m + 1]]) ζi, ← [θi • (1 G , g -)] u ,i • Ency(1 G , v ,i ) (for (i, ) ∈ [[n -m + 1]] × [[k]]) (ζi, ) ---------------→ (i, )∈[[n-m+1]]×[[k]] πnze ζi, , θi •(1 G , g -) (u ,i , v ,i ) ⇐ ============= ⇒ (i, )∈[[n-m+1]]×[[k]] r1,i, . . . , r k,i R ← -Zq πi R ← -S k (for i ∈ [[n -m + 1]]) γi, = ζ i,π i ( ) • Ency(1 G , r ,i ) (for (i, ) ∈ [[n -m + 1]] × [[k]]) (γi, ) ---------------→ (i, )∈[[n-m+1]]×[[k]] πPerm (ζi, , γi, ) (πi, r1,i, . . . , r k,i ) ⇐ ============= ⇒ i∈[[n-m+1]] πDec[γi, , xa, x b ] ⇐ ============= ⇒ i∈[[n-m+1]] h ,i ← Decx a+xb (γi, ) (for (i, ) ∈ [[n -m + 1]] × [[k]]) Add i to S if 1 G ∈ {h1,i, . . . , h k,i } (i ∈ [[n -m + 1]]) Output ⊥ Output S
encryption of 1 G . The detailed protocol ow is given in Fig. 4.

We have the following theorem whose proof will be given in the full version of the paper:

Theorem 3. If π eqDL , π Mult , π Perm , π nze and π isBit are zero-knowledge proofs of knowledge secure against malicious veriers for the languages R eqDL , R Mult , R Perm , R nze and R isBit , if π KeyGen and π Dec are protocols secure against malicious veriers for the functionality F KeyGen and F Dec and if the ElGamal encryption scheme is semantically secure, then the protocol described in Fig. 4 securely computes F PM-k in the presence of malicious adversaries.

Pattern Matching with Wildcards

Finally, we consider the secure computation of the functionality F PM that on input ((P, n), (T , m)) computes

   ({j ∈ [[n -m + 1]] | ∀i ∈ [[m]], p i = ∨ t i+j-1 = ∨ p i = t i+j-1 }, ⊥) if P ∈ { , 0, 1} m ∧ T ∈ { , 0, 1} n (⊥, ⊥)
otherwise Again, Alice learns nothing about P and the only thing Bob learns about T is the locations where P appears (with wildcards).

The protocol is similar to the previous ones and relies on the fact that the sum (3) can be computed with three convolutions and therefore in O(n log n) time using FFT. Due to space constraints, details will be given in the full version of the paper.

We consider a shifted binary alphabet Σ = {1, 2} and identify the wildcard with the number 0. Obviously, one needs to replace in the protocol from Fig. 2 the protocol π isBit by π isTrit . In order to compute (3) via FFT, it is also necessary for Alice to provide encryption of t i We can readily prove the security of this protocol (details will be given in the full version of the paper):

Theorem 4. If π eqDL , π Mult , π Perm , π nze and π isTrit are zero-knowledge proofs of knowledge secure against malicious veriers for the languages R eqDL , R Mult , R Perm , R nze and R isTrit , if π KeyGen and π Dec are protocols secure against malicious veriers for the functionality F KeyGen and F Dec and if the ElGamal encryption scheme is semantically secure, then the protocol outlined above securely computes F PM in the presence of malicious adversaries.

Conclusion

We presented protocols for secure two-party computation of generalized pattern matching. Our schemes can easily be combined in order to solve, for instance, the approximate pattern matching with wildcards problem. They can be extended in various directions: they can handle larger alphabets, longer pattern, and variants where the length of the pattern or the text remains hidden (as the schemes from [START_REF] Hazay | Toft Computationally Secure Pattern Matching in the Presence of Malicious Adversaries[END_REF]). Our technique can also provide round-optimal protocols (with similar eciency) with universally composable security in the common reference string model (using the Groth-Sahai proof system [START_REF] Groth | Sahai Ecient Non-interactive Proof Systems for Bilinear Groups[END_REF]). Details will be given in the full version of the paper.

  The semantic security of the ElGamal encryption scheme follows from the hardness of Decision Die-Hellman (DDH) problem in G[START_REF] Tsiounis | On the Security of ElGamal Based Encryption , PKC'98: 1st International Workshop on Theory and Practice in Public Key Cryptography[END_REF].

  and sends c i to Alice for i ∈ [[m]].

3 .

 3 Using the homomorphic property of ElGamal encryption, Alice computes, for j ∈ [[n -m + 1]], a (uniformly distributed) encryption of the left-hand side of (1) as

3 .

 3 S receives from the adversary A a vector of m ciphertexts c i for i ∈ [[m]]. Using x, it decrypts each ciphertext and try to compute the discrete log of the corresponding plaintext z i . (a) If z i = g σi where σ i ∈ Σ for all i ∈ [[m]], S denes the pattern P as P = (σ 1 , . . . , σ m ) and sends it to the trusted party for F P M and obtains a subset I ⊆ [[n -m + 1]]. The simulator S produces a vector of ciphertexts:

  string. Each iteration takes O(m log m) time giving an overall time complexity of O((n/m)m log m) = O(n log m).

Fig. 2 :

 2 Fig. 2: Basic Protocol for Secure Generalized Pattern Matching

Fig. 4 :

 4 Fig. 4: End of the Protocol for Secure Pattern Matching with Mismatches

2 and t i 3

 3 for i ∈ [[n]] and for Bob to provide encryption of p j 2 and p j 3 for j ∈ [[m]]. They have to prove the consistency of these ciphertexts with a i for i ∈ [[n]] and b j for j ∈ [[m]] using π eqDL . The algorithm then follows the protocol from Fig. 3 in order to get the Hamming distance (with wildcards) between P and T i for i ∈ [[n -m + 1]]. We nally use the technique from Fig. 1 to only reveal to Bob whether this distance is equal to 0 or not.

Table 1 .

 1 Eciency Comparison of Secure Generalized Pattern Matching Protocols

  N, the set of n-bit strings is denoted by {0, 1} n , the set of integers {1, . . . , n} is denoted[[n]] and the symmetric group on[[n]] is denoted by S n . The Hamming distance d H (x, y) between two words x, y ∈ {0, 1} n is dened as the number of coordinates in which they dier.

	Using this tool we provide adaptation of the generalized pattern matching
	algorithms from [6, 22, 2] and obtains schemes with overall eciency summarized
	in the table Tab. 1 ( 5.1 and 5.2). As a by-product, we propose a protocol that
	reports the Hamming distance at every position (irrespective of its value) in O(n √ m) time.
	2 Preliminaries
	2.1 Notation

For n ∈

An anonymous referee kindly informed us of the recent report[START_REF] Cheon | Seo Multi-Party Privacy-Preserving Set Intersection with Quasi-Linear Complexity[END_REF] in which Cheon, Jarecki and Seo use FFT to speed-up secure set intersection protocols.

The round complexity and the communication complexity of our scheme are however smaller by a constant factor and independent of the size of the underlying alphabet.

Acknowledgements. The author would like to thank Benoît Libert and anonymous referees for their comments and Carmit Hazay for helpful discussions on security models. The author was supported in part by the European Commission through the ICT Program under contract ICT-2007-216676 ECRYPT II.


Florian Boudin

Ygor Gallina

Akiko Aa Aizawa
email: aizawa@nii.ac.jp

Keyphrase Generation for Scientific Document Retrieval

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

With the exponential growth of the scientific literature [START_REF] Bornmann | Growth rates of modern science: A bibliometric analysis based on the number of publications and cited references[END_REF], retrieving relevant scientific papers becomes increasingly difficult. Keywords, also referred to as keyphrases, provide an effective way to supplement paper indexing and improve retrieval effectiveness in scientific digital libraries [START_REF] Barker | Comparative efficiency of searching titles, abstracts, and index terms in a free-text data base[END_REF][START_REF] Zhai | Fast statistical parsing of noun phrases for document indexing[END_REF][START_REF] Gutwin | Improving browsing in digital libraries with keyphrase indexes[END_REF][START_REF] Lu | Understanding the retrieval effectiveness of collaborative tags and author keywords in different retrieval environments: An experimental study on medical collections[END_REF]. However, only few documents have assigned keyphrases, and those who do were, for the most part, selflabeled by their authors, thus exhibiting annotation inconsistencies [START_REF] Strader | Author-assigned keywords versus library of congress subject headings[END_REF][START_REF] Suzuki | Analyzing the characteristics of academic paper categories by using an index of representativeness[END_REF]. This has motivated an active line of research on automatic keyphrase extraction (see [START_REF] Kazi | Automatic keyphrase extraction: A survey of the state of the art[END_REF] for an overview) and, more recently, keyphrase generation [START_REF] Meng | Deep keyphrase generation[END_REF], where the task is to find a set of words and phrases that represents the main content of a document.

Although models for predicting keyphrases have been extensively evaluated on their ability to reproduce author's keywords, it still remains unclear whether they can be usefully applied in information retrieval. One reason for this lack of evidence may have been their relatively low performance discouraging attempts at using them for indexing [START_REF] Liu | Automatic keyphrase extraction via topic decomposition[END_REF][START_REF] Kazi | Automatic keyphrase extraction: A survey of the state of the art[END_REF]). Yet, recently proposed models not only achieve much better performance, but also display a property that may have a significant impact on retrieval effectiveness: the capacity to generate keyphrases that do not appear in the source text. These absent keyphrases do not just highlight the topics that are most relevant, but provide some form of semantic expansion by adding new content (e.g. synonyms, semantically related terms) to the index [START_REF] Greulich | Scientific texts and the indexer[END_REF]. The goal of this paper is two-fold: to gather empirical evidence as to whether current keyphrase generation models are good enough to improve scientific document retrieval, and to gain further insights into the performance of these models from an extrinsic perspective. Our contributions are listed as follows:

• We report significant improvements for strong retrieval models on a standard benchmark collection, showing that keyphrases produced by state-of-the-art models are consistently helpful for document retrieval, even, to our surprise, when author keywords are provided.

• We introduce a new extrinsic evaluation framework for keyphrase generation that allows for a deeper understanding of the limitations of current models. Using it, we discuss the difficulties associated with domain generalization and absent keyphrase prediction.

Methodology

This section presents our methodology for assessing the usefulness ( §2.3) of keyphrase generation ( §2.2) in scientific document retrieval ( §2.1).

Scientific Document Retrieval

Here, we focus on the task of searching through a collection of scientific papers for relevant docu-ments. All of our experiments are conducted on the NTCIR-2 test collection [START_REF] Kando | Overview of the second ntcir workshop[END_REF] which is, to our knowledge, the only available benchmark dataset for that task. It contains 322,058 documents 1 (title and abstract pairs) and 49 search topics (queries) with relevance judgments. Most of the documents (98.6%) include author keywords (4.8 per doc. on avg.), which we later use to investigate the performance of keyphrase generation models. Documents cover a broad range of domains from pure science to social sciences and humanities, although half of the documents are about engineering and computer science. Queries are also categorized into one or more research fields (e.g. science, chemistry, engineering), the original intent being to help retrieval models in narrowing down the search space. We follow common practice and use short 2 queries with binary relevance judgments (i.e. without "partially relevant" documents).

We consider two standard ad-hoc retrieval models to rank documents against queries: BM25 and query likelihood (QL), both implemented in the Anserini IR toolkit [START_REF] Yang | Anserini: Enabling the use of lucene for information retrieval research[END_REF]. These models use unsupervised techniques based on corpus statistics for term weighting, and will therefore be straightforwardly affected when keyphrases are added to a document. We further apply a pseudorelevance feedback method, known as RM3 [START_REF] Abdul-Jaleel | Umass at trec 2004: Novelty and hard[END_REF], on top of the models to achieve strong, near state-of-the-art retrieval results [START_REF] Lin | The neural hype and comparisons against weak baselines[END_REF][START_REF] Yang | Critically examining the "neural hype": Weak baselines and the additivity of effectiveness gains from neural ranking models[END_REF]. For all models, we use Anserini's default parameters.

To verify the effectiveness of the adopted retrieval models, we compared their performance with that of the best participating systems in NTCIR-2. Retrieval performance is measured using mean average precision (MAP) and precision at 10 retrieved documents (P@10). MAP measures the overall ranking quality and P@10 reflects the number of relevant documents on the first page of search results. Documents are indexed with author keywords, same as for participating systems. Results are presented in Table 1. We see that the considered retrieval models achieve strong performance, even outperforming the best participating system by a substantial margin. Note that the two best-performing systems use pseudo-relevance feedback, and that the second-ranked system is based on BM25.

1 Scientific abstracts and summaries of research results. 2 <description> field of topic description.

Model

MAP P@10 BM25+RM3 35.17 38.57 QL+RM3 33.00 34.90 1 st [START_REF] Fujita | Notes on the limits of clir effectiveness: Ntcir-2 evaluation experiments at justsystem[END_REF] 31.93 37.35 BM25 31.38 36.33 2 nd [START_REF] Murata | Crl at ntcir2[END_REF] 31.31 36.12 QL 30.63 34.08 3 rd [START_REF] Chen | Berkeley at ntcir-2: Chinese, japanese, and english ir experiments[END_REF] 26.24 33.88

Table 1: Retrieval effectiveness of the considered models and the best participating systems on NTCIR-2.

Keyphrase Generation

Keyphrase generation is the task of producing a set of words and phrases that best summarise a document [START_REF] Evans | Noun phrase analysis in large unrestricted text for information retrieval[END_REF]. In contrast with most previous work that formulates this task as an extraction problem (a.k.a. keyphrase extraction), which can be seen as ranking phrases extracted from a document, recent neural models for keyphrase generation are based on sequence-to-sequence learning [START_REF] Sutskever | Sequence to sequence learning with neural networks[END_REF][START_REF] Bahdanau | Neural machine translation by jointly learning to align and translate[END_REF], thus potentially allowing them to generate any phrase, also beyond those that appear verbatim in the text. In this study, we consider the following two neural keyphrase generation models:

seq2seq+copy [START_REF] Meng | Deep keyphrase generation[END_REF] is a sequenceto-sequence model with attention, augmented with a copying mechanism [START_REF] Gu | Incorporating copying mechanism in sequence-to-sequence learning[END_REF] to predict phrases that rarely occur. The model is trained with document-keyphrase pairs and uses beam search decoding for inference.

seq2seq+corr [START_REF] Chen | Keyphrase generation with correlation constraints[END_REF] extends the aforementioned model with correlation constraints. It employs a coverage mechanism [START_REF] Tu | Modeling coverage for neural machine translation[END_REF] that diversifies attention distributions to increase topic coverage, and a review mechanism to avoid generating duplicates.

We implemented the models in PyTorch [START_REF] Paszke | Automatic differentiation in pytorch[END_REF] using AllenNLP [START_REF] Gardner | AllenNLP: A deep semantic natural language processing platform[END_REF]. Models are trained on the KP20k dataset [START_REF] Meng | Deep keyphrase generation[END_REF], which contains 567,830 scientific abstracts with gold-standard, author-assigned keywords (5.3 per doc. on avg.). We use the parameters suggested by the authors for each model.

To validate the effectiveness of our implementations, we conducted an intrinsic evaluation by counting the number of exact matches between predicted and gold keyphrases. We adopt the standard metric and compute the f-measure at top 5, as it corresponds to the average number of keyphrases in KP20k and NTCIR-2, that is, 5.3 and 4.8, respectively. We also examine cross-domain generalization using the KPTimes news dataset [START_REF] Gallina | Kptimes: A large-scale dataset for news keyphrase generation[END_REF], and include a state-of-the-art unsupervised keyphrase extraction model [START_REF] Boudin | Unsupervised keyphrase extraction with multipartite graphs[END_REF], henceforth mp-rank) for comparison purposes. This latter baseline also provides an additional relevance signal based on graph-based ranking whose usefulness in retrieval will be tested in subsequent experiments. Results are reported in Table 2. Overall, our results are consistent with those reported in [START_REF] Meng | Deep keyphrase generation[END_REF][START_REF] Chen | Keyphrase generation with correlation constraints[END_REF], demonstrating the superiority of well-trained neural models over unsupervised ones, and stressing their lack of robustness across domains. Rather surprisingly, seq2seq+corr is outperformed by seq2seq+copy which indicates that relevant, yet possibly redundant, keyphrases are filtered out by the added mechanisms for promoting diversity in the output.

Model

Extrinsic Evaluation Framework

Our goal is to find out whether the keyphrase generation models described above are reliable enough to be beneficial for document retrieval. To do so, we contrast the performance of the retrieval models with and without automatically predicted keyphrases. Two initial indexing configurations are also examined: title and abstract only (T +A), and title, abstract and author keywords (T +A+K).

The idea here is to investigate whether generated keyphrases simply act as a proxy for author keywords, or instead supplement them. Unless mentioned otherwise, the top-5 predicted keyphrases are used to expand documents, which is in accordance with the average number of author keywords in NTCIR-2. We evaluate retrieval performance in terms of MAP and omit P@10 for brevity. We use the Student's paired t-test to assess statistical significance of our retrieval results at p < 0.05 [START_REF] Mark | A comparison of statistical significance tests for information retrieval evaluation[END_REF].

Results

Results for retrieval models using keyphrase generation are reported in Table 3. We note that indexing keyphrases generated by seq2seq+copy, which performs best in our intrinsic evaluation, significantly improves retrieval effectiveness for all models. More interestingly, gains in effectiveness are also significant when both keyphrases and author keywords are indexed, indicating they complement each other well. This important finding suggests that predicted keyphrases are consistently helpful for document retrieval, and should be used even when author keywords are provided. Another important observation is that while both keyphrase generation models perform reasonably well in our intrinsic evaluation on NTCIR-2 (cf. Table 2, column 3), their impact on retrieval effectiveness are quite different, as only s2s+copy reaches consistent significance. This finding advocates for the importance of using document retrieval as an extrinsic evaluation task for keyphrase generation. Overall, BM25+RM3 achieves the best retrieval effectiveness, confirming previous findings on adhoc retrieval in limited data scenarios [START_REF] Lin | The neural hype and comparisons against weak baselines[END_REF]. For clarity and conciseness, we focus on this model in the rest of this paper. Encouraging diversity in keyphrases seems not to be appropriate for retrieval, as seq2seq+corr consistently gives lower results than seq2seq+copy. It is also interesting to see that the effectiveness gains of query expansion (RM3) and document expansion are additive, suggesting that they provide different but complementary relevance signals. Moreover, our results show that query expansion is more effective, which is in line with past work [START_REF] Billerbeck | Document expansion versus query expansion for ad-hoc retrieval[END_REF].

Index

One hyper-parameter that we have deliberately left untouched so far is the number N of predicted keyphrases that directly controls the precisionrecall trade-off of keyphrase generation models. To understand how this parameter affects retrieval effectiveness, we repeated our experiments by varying N within the range [0, 9], and plotted the results in Figure 1. Without author keywords, we observe that all models achieve gains, but only seq2seq+copy does yield significant improvements. With author keywords, seq2seq+copy is again the only model that achieves significance, while the others show mixed results, sometimes even degrading scores. One likely explanation for this is that these models produce keyphrases that cause documents to drift away from their original meaning. We note that results are close to optimal for N = 5, supporting our initial setting for this parameter. From our experiments, it appears that unsupervised keyphrase extraction is not effective enough to significantly improve retrieval effectiveness. The fact that keyphrase generation does so, suggests that the ability to predict absent keyphrases may be what enables better performance. Yet counterintuitively, we found that most of the gains in retrieval effectiveness are due to the high extractive accuracy of keyphrase generation models. Results in Table 4 show that expanding documents with only absent keyphrases is at best useless and at worst harmful, while using only present keyphrases brings significant improvements. We draw two conclusions from this. First, absent keyphrases may not be useful in practice unless they are tied to some form of domain terminology to prevent semantic drift. Second, as generation does not yield improvements, keyphrase extraction models may be worth further investigation. In particular, supervised models could theoretically provide similar results while being easier to train.

Model

T Neural models for keyphrase generation exhibit a limited generalization ability, which means that their performance degrades on documents that differ from the ones encountered during training (cf. Table 2, columns 3 and 4). To quantify how much this affects retrieval effectiveness, we divided the queries into two disjoint sets: in-domain for those that belong to research fields present in KP20k, and out-domain for the others. Results are presented in Table 5. The first thing we notice is the overall lower performance of out-domain queries, which may be explained by the unbalanced distribution of domains in the NTCIR-2 collection. Most importantly, out-domain queries on full indexing (i.e. T +A+K) is the only configuration in which no significant gains in retrieval effectiveness are achieved. This last experiment shows that expanding documents using existing keyphrase generation models may be ineffective in the absence of in-domain training data, and stresses the need of domain adaptation for keyphrase generation.

Model

Conclusion

We presented the first study of the usefulness of keyphrase generation for scientific document retrieval. Our results show that keyphrases can significantly improve retrieval effectiveness, and also highlight the importance of evaluating keyphrase generation models from an extrinsic perspective.

Other retrieval tasks may also benefit from using keyphrase information and we expect our results to serve as a basis for further improvements.

Figure 1 :

 1 Figure 1: MAP scores for BM25+RM3 w.r.t. the number N of predicted keyphrases. denotes significance.

Table 3 :

 3 MAP scores for retrieval models using various indexing configurations. † and ‡ indicate significance over T +A and T +A+K, respectively.

		BM25 +RM3	QL	+RM3
	T +A	29.16	31.93	28.98	31.47
	+ s2s+copy 30.54 † 34.30 † 30.58 † 33.26 †
	+ s2s+corr	30.30 † 33.24	29.76	31.38
	+ mp-rank	29.24	32.27	29.57	32.29
	T +A+K	31.38	35.17	30.63	33.00
	+ s2s+copy 31.55	36.53 ‡ 31.70 ‡ 35.15 ‡
	+ s2s+corr	31.37	35.84	31.14	33.65
	+ mp-rank	31.38	35.18	31.23	33.47

Table 4 :

 4 +A (cf. 31.93) T +A+K (cf. 35.17) MAP scores for BM25+RM3 using the top-5 present or absent keyphrases. † indicates significance over indexing without predicted keyphrases.

		pres.	abs.	pres.	abs.
	s2s+copy 34.17 † 32.14	36.30 † 34.97
	s2s+corr	32.97	31.96	36.09	34.77

Table 5 :

 5 MAP scores for BM25+RM3 on in-domain (I) and out-domain (O) queries. † indicates significance over w/o keyphrases whose scores are in parentheses.

		T +A		T +A+K
		I (32.70) O (30.99) I (36.18) O (33.93)
	s2s+copy 35.40 †	32.96 †	38.13 †	34.55
	s2s+corr	33.49	32.92	37.13	34.25
	mp-rank	32.73	31.71	36.74	33.26

Acknowledgements

We thank the anonymous reviewers for their valuable comments. This work was supported by the IKEBANA project (grant of Atlanstic 2020) and the French National Research Agency (ANR) through the DELICES project (ANR-19-CE38-0005-01).

A Supplementary material A.1 Related Work

Keyphrase extraction and generation

Identifying keyphrases for a given document is a long standing task in NLP. Earlier work typically involves two steps: 1) extracting keyphrase candidates; and 2) ranking those candidates by importance. Models mainly differ in how they do the latter, commonly used techniques being supervised learning [START_REF] Witten | Kea: Practical automatic keyphrase extraction[END_REF][START_REF] Peter | Coherent keyphrase extraction via web mining[END_REF][START_REF] Nguyen | Keyphrase extraction in scientific publications[END_REF][START_REF] Jiang | A ranking approach to keyphrase extraction[END_REF] and graph-based methods [START_REF] Mihalcea | Textrank: Bringing order into texts[END_REF][START_REF] Wan | Collabrank: Towards a collaborative approach to single-document keyphrase extraction[END_REF][START_REF] Bougouin | Topicrank: Graph-based topic ranking for keyphrase extraction[END_REF][START_REF] Florescu | Positionrank: An unsupervised approach to keyphrase extraction from scholarly documents[END_REF]. These models are, however, inherently limited in the sense that they can only output keyphrases that appear in the text. To allow the prediction of keyphrases describing implicit topics or using different wordings, previous work relied on external resources like controlled vocabularies [START_REF] Witten | Thesaurus based automatic keyphrase indexing[END_REF][START_REF] Bougouin | Keyphrase annotation with graph co-ranking[END_REF], while recent attempts leveraged neural generative models [START_REF] Meng | Deep keyphrase generation[END_REF][START_REF] Chen | Keyphrase generation with correlation constraints[END_REF][START_REF] Zhao | Incorporating linguistic constraints into keyphrase generation[END_REF].

Biomedical indexing

Also related to our work is the research done on biomedical semantic indexing using MeSH 3 , a hierarchically-organized controlled vocabulary. Automated methods for assigning MeSH terms make use of all sorts of techniques, such as pattern matching [START_REF] Alan R Aronson | The nlm indexing initiative's medical text indexer[END_REF] or learning to rank [START_REF] Liu | Meshlabeler: improving the accuracy of large-scale mesh indexing by integrating diverse evidence[END_REF][START_REF] Peng | Deepmesh: deep semantic representation for improving large-scale mesh indexing[END_REF].

Document expansion

Our work is similar in nature to previous research on document expansion [START_REF] Tao | Language model information retrieval with document expansion[END_REF][START_REF] Efron | Improving retrieval of short texts through document expansion[END_REF], and is closely related to recent work on document expansion using automatically generated queries [START_REF] Nogueira | Document expansion by query prediction[END_REF].

A.2 Parameters

Table 6 displays the model parameters we use for seq2seq+copy and seq2seq+corr.

Table 7 presents the research fields used for dividing queries into two sets.

A.3 Example

An example of document along with automatically generated keyphrases is shown in title Grammatical Inference for Concept Acquisition from Documents.

abstract The purpose of this study is to acquire knowledge from large scale natural language documents. There are two types of knowledge in the documents. One is explicitly represented knowledge which is acquired using natural language processing. The other is implicit constrain. In this paper, how to acquire implicit constraint using grammatical inference from the documents is described. We propose a grammatical inference system which uses inference rules based on logic, and show that the system can learn easy pattern of character lists. We also discuss its application to knowledge acquisition from real documents.

gold grammatical inference // knowledge acquisition // logic ::::::::::: progamming // concept learning s2s+copy grammatical inference // knowledge // grammatical // knowledge representation // natural language processing s2s+corr grammatical inference // knowledge acquisition // concept acquisition // inference rules // natural language processing mp-rank grammatical inference // documents // knowledge // large scale // concept acquisition Table 8: Example document (id: gakkai-e-0001014453 from ntc2-e1g) with author keywords (gold) and automatically generated keyphrases. We note a typo in the gold annotation (progamming).