Jiangtao Li
email: lijiangtao@stu.ecnu.edu.cn

Junqing Gong
email: junqing.gong@ens-lyon.fr

Improved Anonymous Broadcast Encryptions Tight Security and Shorter Ciphertext

Keywords: broadcast encryption, full anonymity, chosen-ciphertext security, tight reduction, short ciphertext

We investigate anonymous broadcast encryptions (ANOBE) in which a ciphertext hides not only the message but also the target recipients associated with it. Following Libert et al.'s generic construction [PKC, 2012], we propose two concrete ANOBE schemes with tight reduction and better space efficiency. -The IND-CCA security and anonymity of our two ANOBE schemes can be tightly reduced to standard k-Linear assumption (and the existence of other primitives). For a broadcast system with n users, Libert et al.'s security analysis suffers from O(n 3 ) loss while our security loss is constant. -Our first ANOBE supports fast decryption and has a shorter ciphertext than the fast-decryption version of Libert et al.'s concrete ANOBE. Our second ANOBE is adapted from the first one. We sacrifice the fast decryption feature and achieve shorter ciphertexts than Libert et al.'s concrete ANOBE with the help of bilinear groups. Technically, we start from an instantiation of Libert et al.'s generic ANOBE [PKC, 2012], but we work out all our proofs from scratch instead of relying on their generic security result. This intuitively allows our optimizations in the concrete setting.

Table of Contents 1 Introduction

Broadcast Encryption. Broadcast encryption [Ber91,FN94] (BE) is a public-key cryptosystem designed for securely sending information to multiple users via a public channel. In a BE system, we may index each user by integers 1, . . . , n and name set U := {1, . . . , n} the universe. It would be convenient to describe BE in the framework of Functional Encryption [BSW11]. An authority publishes a set of public parameters generated by the Setup algorithm. Each user's secret key is then created by the KeyGen algorithm from the master secret key which is the output of Setup. By invoking the encryption algorithm Enc, a sender can create a ciphertext for users specified by a target set S ⊆ U. Any user with an index i ∈ S is able to decrypt the ciphertext using the Dec algorithm.

The basic security requirement is collusion-resistance which ensures that a ciphertext leaks no information about the message even when multiple users outside the target set S decide to cooperate. More formally, it is required that {ct ← R Enc(mpk, S, m 0 )} ≈ c {ct ← R Enc(mpk, S, m 1 )} where mpk is the public parameters, (S ⊆ U, m 0 , m 1 ) are chosen by the adversary; and we allow the adversary to adaptively learn secret keys for all i / ∈ S. With more powerful functional encryptions such as attribute-based encryptions [SW05], [GPSW06,OT10,LOS + 10,CGW15], we can securely broadcast information in a structural way which is more efficient and much easier to manage. However the classical BE still serves as the most general tool for broadcasting information in the systems where users are not wellorganized, e.g., a country-wide pay-TV system.

Anonymity. Since been introduced, a series of BE schemes have been published [FN94], [NNL01,YFDL04,BGW05,DPP07,GW09,Wee16], but they only ensure the confidentiality of the message while the target set S is entirely exposed to the public. In fact, the description of S will be directly transmitted through the insecure channel for decryption. However in many applications, the confidentiality of the target set is also crucial. For instance, in the pay-TV setting, everyone has access to the full list of subscribers, which is not acceptable. Therefore, it is desirable and non-trivial to build a BE system taking both the message and the target set into account in terms of confidentiality. In this paper, we call the latter feature anonymity and name such a BE as anonymous broadcast encryption [LPQ12] (ANOBE). More formally, it is required that {ct ← R Enc(mpk, S 0 , m 0 )} ≈ c {ct ← R Enc(mpk, S 1 , m 1 )} where (m 0 , m 1 , S 0 , S 1 ) are chosen by the adversary and secret keys for all i / ∈ (S 0 \ S 1 ) ∪ (S 1 \ S 0 ) can be revealed. The subtlety is that any secret key for i ∈ S 0 ∩ S 1 will give an adversary the power to correctly decrypt both ciphertexts above. In this case, m 0 = m 1 is disallowed in order to avoid the trivial attack.

State of the Art. Although anonymity is crucial for BE, it has not received much attentions to construct ANOBE with the proper security guarantee.

In 2006, Barth et al.

[BBW06] first identified the anonymity (i.e., recipient privacy in their work) in the context of encrypted file system. They introduced the notion of ANOBE in the name of private broadcast encryption. In their work, two constructions were described. The first one is a generic construction from an IND-CCA secure PKE with key-privacy and a strongly unforgeable signature scheme. They claimed that it achieves IND-CCA security and anonymity but in the selective (or static) model which means that the adversary must commit the challenge target sets (S 0 , S 1 ) in advance. Basically, a BE ciphertext there is a set of PKE ciphertexts intended for every recipient in S bound together via a signature. One drawback of this construction is that the decryption time is proportional to |S| since each receiver has to try to decrypt each PKE ciphertext one by one. In their second construction, they introduced a method helping a receiver to find the right PKE ciphertext and reduced the decryption cost to constant. However, it unfortunately relies on the random oracle model.

At PKC 2012, Libert el al.

[LPQ12] formally revisited Barth et al.'s results. They described the adaptive security for ANOBE where the adversary can choose the challenge target sets (S 0 , S 1 ) at any time (i.e., the security notation we have reviewed), and showed that it can be achieved from IND-CCA secure PKE (plus strongly secure signatures). Note that this result is quite strong in that the underlying PKE is not necessarily key-private. Moreover, the receiver can decrypt in a constant time. However, the size of ciphertext depends on n, the size of universe. They then demonstrated that Barth et al.'s first BE is actually IND-CCA secure and anonymous in an adaptive sense and provided an alternative construction from IBE [Sha84,CHK04]. This ANOBE has shorter ciphertext (of size O(|S|)) but requires the underlying PKE to be weakly robust [ABN10,Moh10] and key-private, and the decryption cost increases to O(|S|). They also formalized the method helping to reduce the decryption cost in Barth et al.'s second construction [BBW06] as anonymous hint system, which can be viewed as a variant of extractable hash proof systems [Wee10]. The classical randomness-reuse technique [Kur02,BBS03] was then formally studied to reduce the ciphertext size. Finally, a concrete ANOBE based on the Kurosawa-Desmedt PKE [KD04] was proposed. Having their generic ANOBE, they showed that the Kurosawa-Desmedt PKE can be adapted to be keyprivate and robust, and also support randomness-reuse technique.

Also at PKC 2012, Fazio and Perera [FP12] proposed an ANOBE scheme with sublinearsize ciphertexts but with a much weaker outsider-anonymity where users identified by S 0 ∩ S 1 are not considered to be malicious. More formally, the adversary is forbidden to get any secret key for i ∈ S 0 ∩ S 1 . However Barth et al.'s early work [BBW06] has actually recognized such an inside attacker as a hazard and illustrated how serious the issue is under a chosenciphertext attack. In the end, we want to note that Libert et al.'s results [LPQ12] are still the best in the sense that they achieve (1) IND-CCA security, (2) fully anonymity and (3) randomoracle-freeness. To our best knowledge, there is no follow-up result with all these features simultaneously even when taking the identity-based variant into account (see recent work [HWL + 16] for more details).

Contributions

In this paper, we propose two concrete ANOBE schemes. Both of them are obtained by optimizing an instantiation of Libert et al.'s generic construction [LPQ12] with Cramer-Shoup PKE [CS98,CS02]. We prove, from scratch, that they are secure in the sense of [LPQ12] from the standard k-Linear (k-Lin) assumption and the existence of several other cryptographic primitives (such as strongly unforgeable signature and collision-resistant hash function) .

Although our proposals do not deviate from Libert et al.'s generic framework [LPQ12], our new start point and customized security proof allow us to gain shorter ciphertexts and tighter reduction than the concrete instantiation in [LPQ12]. (Recall that it is based on Kurosawa-Desmedt PKE [KD04] and the security result follows the generic construction directly.) A comparison between them is shown in Table 1 where we consider instantiations of our two ANOBE under DDH=1-Lin (or SXDH=1-Lin) assumption 3 . We note that these two instantiations are the most efficient ones. , but it permits us to use some customized method to optimize the system.

Tighter Reduction. In [LPQ12]

, their security reduction suffers from O(n 3 ) loss where n is the size of the universe. This makes it infeasible for large-scale systems such as aforementioned pay-TV application. In particular, we need to use a larger group to compensate the loss, which of course increases the bandwidth and computation costs. In our work, we prove the security of two ANOBE from basic assumption and only suffer constant security loss, which is of both theoretical and practical interest. We argue that the result is non-trivial: A potential solution is to employ an IND-CCA secure PKE with tight reduction for multiple users (like [GHKW16,Hof17]) in Libert et al.'s generic construction [LPQ12]. However, the simulator still needs to guess which public keys will be associated with target set which is chosen adversarially and causes significant security loss.

Technical Overview

Our starting point is an instantiation of Libert et al.'s generic construction with Cramer-Shoup PKE [CS98,CS02]. In this overview, we first give this instantiation and describe how to derive our two ANOBE schemes from it.

Starting point. Assume a prime-order group (p, G, g). We let [a] := g a ∈ G for all a ∈ Z p and extend it to matrix over Z p . Assume S := {i 1 , . . . , i }. We can instantiate Libert et al.'s construction using Cramer-Shoup PKE under k-Lin assumption as below: The above BE is IND-CCA secure and anonymous according to Libert et al.'s generic result. However, we can do better by showing a tighter reduction for this concrete ANOBE. The security loss of Libert et al.'s reduction (which is O(n 3 )) is mainly caused by blackbox-reduction to the underlying PKE where the simulation need to guess some information about challenge target set. We prove our security result from scratch. In particular, we employ the proof technique for IND-CCA PKE in the multi-user setting [GHKW16,Hof17] but adapt it to our broadcast encryption case. We found that we can now avoid guessing adversary's behavior and also corresponding reduction loss.

mpk : { [A] , [A k i ], [A x i ], [A y i ] } i∈[n] , (Gen ots , Sig, Ver), h sk i : k i , x i , y i ct S : { [r A ] , [r A k i j ] • m, [r A (x i j + α • y i j )] } j∈[ ] , pk ots , σ where A ← R Z (k+1)×k p , k i , x i , y i ← R Z k+1 p for i ∈ [n] and r ← R Z k p .
Our first ANOBE: Shorter Ciphertext for Fast Decryption. The above instantiation has not been equipped with anonymous hint system [LPQ12], so the decryption cost should be O( ). (Recall that, intuitively, an anonymous hint system can help the decryptor to find the right ciphertext component intended for him and avoid O( ) factor.) However we observe that {[r A (x i j + α • y i j )]} j∈[ ] can serve as the hints for fast decryption. This benefits from the fact that tag α is shared by all users in S. In the decryption procedure, a user with secret Observe that we have group elements (i.e., {[r A (x i j + α • y i j )]} j∈[ ] ) for consistency check (which is necessary for IND-CCA security) in our first ANOBE. If we assume that each recipient can correctly guess which part is intended for him/her, we can see that only one of these elements will be used in the decryption procedure. Therefore a promising idea is to ask all recipients to share the consistency check process. A direct way to do so is to

key k i , x i , y i can recover v = [r A (x i + α • y i )] and try to find the index j * such that v = [r A (x i j * + α • y i j * )],
replace {[r A (x i j + α • y i j )]} j∈[ ] with [r A (x + α • y)]
and publish [A x] and [A y] in mpk. Unfortunately, there is a fatal issue. To do the consistency check, we should give each user x and y directly and they will be leaked to an adversary through any corrupted user. This totally breaks the IND-CCA security. We circumvent the difficulty by making the consistency check public using the technique by Kiltz and Wee [KW15]. In particular, we adapt our first ANOBE to G 1 of a pairing group

(p, G 1 , G 2 , G T , e) and replace [r A (x + α • y)] 1 with [r A (X + α • Y)] 1
where X, Y ← R Z (k+1)×(k+1) p . In the public parameter mpk, we publish

([A X] 1 , [A Y] 1 ) and ([B] 2 , [XB] 2 , [YB] 2 )
where B ← R Z (k+1)×k p and the right-hand side part allow anyone to publicly check the ciphertext consistency.

We have successfully compressed the ciphertext but lose the correctness of decryption since we do not have hint system now. It is easy to fix using key-binding symmetric encryption scheme (E, D). That is we pick session key K from the key space of (E, D) and

replace [r A k i j ] 1 • m with [r A k i j ] 1 • K, E K (m).
We note that we are not pursuing fast decryption now. We can further get rid of σ by defining α as in Cramer-Shoup PKE [CS98,CS02]. We sketch our second ANOBE as follows:

mpk : (E, D), h; { [A ] 1 , [A k i ] 1 , [A X] 1 , [A Y] 1 } i∈[n] ; [B] 2 , [XB] 2 , [YB] 2 sk i : k i ct S : { [r A ] 1 , [r A k i j ] 1 • K, E K (m) , [r A (X + α • Y)] 1 } j∈[ ]
where all terms in gray box are shared by all users/receivers. As our first ANOBE, the reduction loss is constant.

Compared with Libert et al.'s concrete ANOBE [LPQ12], our second ANOBE is based on weaker assumptions -we don't require the existence of strongly one-time signature and (E, D) is not necessarily authenticated encryption. Furthermore, in the ciphertext, we share as many components as possible among receivers in the target set, the remaining group elements seem to be inevitable by the lower bound [KS12].

Organization. Our paper is organized as follows. We review some basic notions in Section 2. Our two ANOBE constructions along with security analysis will be presented in Section 3 and Section 4, respectively. We finally conclude the paper in Section 5.

Preliminaries

Notations. For n ∈ N, we define [n] := {1, 2, . . . , n}. We use a ← R A to denote the process of uniformly sampling an element from set A and assigning it to variable a. For two sets S 0 , S 1 , define S 0 S 1 := (S 0 \ S 1 ) ∪ (S 1 \ S 0 ). "p.p.t." stands for probabilistic polynomial time.

Anonymous Broadcast Encryption

Algorithms. Let U := [n] be the universe. A broadcast encryption (BE) scheme consists of four algorithms (Setup, KeyGen, Enc, Dec):

-Setup(1 λ , n) → (mpk, msk): on input 1 λ and n, the setup algorithm outputs a master public key mpk and a master secret key msk. -KeyGen(mpk, msk, i) → sk i : on input mpk, msk and an index i ∈ U, the key generation algorithm outputs a secret key sk i . -Enc(mpk, m, S) → ct S : on input mpk, a message m and a subset S ⊆ U, the encryption algorithm outputs a ciphertext ct S . -Dec(mpk, ct S , sk i ) → m/⊥: on input mpk, ct S and sk i , the decryption algorithm outputs m or a failure symbol ⊥.

Correctness. For all λ, all (mpk, msk) ← R Setup(1 λ , n), all m, all S ⊆ U, and all i ∈ S, it is required that Dec(mpk, Enc(mpk, m, S), KeyGen(mpk, msk, i)) = m.

Chosen-ciphertext security and anonymity. For any adversary A , define

Adv BE A (1 λ ) := Pr          b = b (mpk, msk) ← R Setup(1 λ , n), b ← R {0, 1} (m 0 , m 1 , S 0 , S 1 ) ← R A KeyO(•),DecO(•,•) (1 λ , mpk) ct * ← R Enc(mpk, m b , S b ) b ← R A KeyO(•),DecO(•,•) (1 λ , mpk, ct * )          - 1 2
where oracles work as follows:

-KeyO: on input i, key extraction oracle KeyO outputs sk i ← R KeyGen(msk, mpk, i) and sets Q sk := Q sk ∪ {i} which is initialized to be ∅ at the beginning. -DecO: on input (ct, i), decryption oracle DecO outputs Dec(mpk, ct, sk i ) when ct * (a.k.a.

challenge ciphertext) has not been defined or ct = ct * .

A broadcast encryption scheme achieves chosen-ciphertext security and anonymity (ANO-IND-CCA) if, for all p.p.t. adversary A, Adv BE A (λ) is negligible in λ under the restrictions that (1)

|m 0 | = |m 1 | and |S 0 | = |S 1 |; (2) Q sk ∩ (S 0 S 1 ) = ∅; (3) if Q sk ∩ (S 0 ∩ S 1 ) = ∅, then m 0 = m 1 .

Prime-Order (Bilinear) Groups

Prime-order group. A group generator GGen is a p.p.t. algorithm which takes 1 λ as input and outputs a description G := (p, G, g). Here G is a finite cyclic group of prime order p and g is a random generator of G. Throughout the paper, we will use implicit representation [EHK + 13]. We let [a] := g a ∈ G for all a ∈ Z p . For a matrix A = (a ij ) ∈ Z m×n p , we let

[A] = (g a ij ) ∈ G m×n .
Prime-order bilinear group. A group generator PGGen is a p.p.t. algorithm which takes 1 λ as input and outputs a description PG := (p, G 1 , G 2 , G T , e, g 1 , g 2 ) of (asymmetric) bilinear group. Here G 1 , G 2 , G T are finite cyclic groups of prime order p and e is an admissible bilinear map. g 1 ∈ G 1 and g 2 ∈ G 2 are random generators of G 1 and G 2 , and g T := e(g 1 , g 2 ) will be a generator of group G T . The implicit representation is also be applied to prime-order bilinear groups: We let [a] s := g a s ∈ G s for all a ∈ Z p and s ∈ {1, 2, T }. The notation can be easily extended to matrices analogously and we let e([A] 1 , [B] 2 ) := [AB] T for matrices A and B when the multiplication is well-defined.

Cryptographic assumption. For any k ∈ N, we call D k a matrix distribution if it outputs full-rank matrices in Z (k+1)×k p in polynomial time. We may assume that for all A ← R D k , the first k rows of A form an invertible matrix.

We will use the D k -Matrix Diffie-Hellman (D k -MDDH) assumption in G described as follows. The D k -MDDH assumption in G 1 and G 2 are analogous.

Assumption 1 (D k -MDDH)

We say that the D k -Matrix Diffie-Hellman assumption holds relative to GGen, if for any p.p.t. adversary A, the following advantage function is negligible in λ. Assumption 2 (D k -KerMDH) Let s ∈ {1, 2}. We say that the D k -Kernel Matrix Diffie-Hellman Assumption holds relative to PGGen, if for any p.p.t. adversary A, the following advantage function is negligible in λ.

Adv mddh A,G (λ) := | Pr[A(G, [A], [As]) = 1] -Pr[A(G, [A], [u]) = 1]| where G ← R GGen(1 λ ), A ← R D k , s ← R Z k p ,
Adv kmdh A,G s (λ) := Pr[A a ⊥ = 0 ∧ a ⊥ = 0 | [a ⊥ ] 3-s ← R A(PG, [A] s )]
where PG ← R PGGen(1 λ ), A ← R D k .

Cryptographic Primitives

Our constructions will use the following cryptographic primitives:

Key-binding secure symmetric encryption. A symmetric encryption scheme with a key space K consists of two algorithms (E, D):

-E K (m) → c : the encryption algorithm generates a encryption c of the message m under the secret key K. -D K (c) → m/⊥ : the decryption algorithm decrypts the ciphertext c using K, and returns m or a failure symbol ⊥.

The correctness can be stated as follows: for all K ← R K and all message m, we have D K (E K (m)) = m with overwhelming probability. We then review the semantic security of symmetric encryptions. For any adversary A, define

Adv se A (λ) := Pr       b = b (m 0 , m 1 ) ← R A(1 λ , K) K ← R K, b ← R {0, 1}, c * ← R E K (m b ) b ← R A(1 λ , K, c * )       - 1 2 .
A symmetric encryption is semantically secure, if for all p.p.t. adversary A, the advantage function Adv se A (λ) is negligible in λ. Furthermore, we require the symmetric encryption to be key-binding [Fis99]. Namely, for any message m and any secret key K ∈ K, there exists no key K ∈ K such that K = K and D K (E K (m)) =⊥. See [Fis99] for more details.

Collision-resilient hash function.

A family of hash functions H is said to be collisionresistant if, for all p.p.t. algorithm A, the following advantage function is negligible in λ.

Adv hash A (λ) := Pr[h(x) = h(y) ∧ x = y | h ← R H, (x, y) ← R A(1 λ , h)].
Strongly secure one-time signature. A signature scheme consists of the following three algorithms.

-Gen ots (1 λ ) → (sk ots , pk ots ) : on input the security parameter λ, the key generation algorithm outputs a signing key sk ots and the verification key pk ots . -Sign(sk ots , m) → σ : on input sk ots and a message m, the signing algorithm outputs a signature σ.

-Ver(pk ots , m, σ) → 0/1 : on input pk ots , m, and σ, the verification algorithm outputs 0 (reject) or 1 (accept).

We require the signature scheme strongly unforgeable against all adversaries with at most one message-signature pair. Formally, for any adversary A, we define

Adv ots A (λ) := Pr   Ver(pk ots , m * , σ * ) = 1 ∧ (m, σ) = (m * , σ * ) (sk ots , pk ots ) ← R Gen ots (1 λ ) (m * , σ * ) ← R A SigO(•) (1 λ , pk ots )   - 1 2 ,
where the oracle SigO takes m as input and returns σ ← R Sign(sk ots , m), and can only be called once. We say that a signature scheme is strongly unforgeable under one-time chosen message attack if the advantage function Adv ots A (λ) is negligible in λ for all p.p.t. adversary A.

Core Lemma

We review the core lemma in [KW15].

Lemma 1 (Core lemma, [KW15]

). Let k ∈ N. For any A, B ∈ Z (k+1)×k p and any (possibly unbounded) adversary A, we have

Pr   u / ∈ span(A) ∧ α = α * X, Y ← R Z (k+1)×(k+1) p ∧ π = u (X + α • Y) (u, α, π) ← R A O(•) (A X, A Y, XB, YB)   1 p
where O(α * ) → X + α * • Y may only be called one time.

3 Tightly Secure ANOBE with Fast Decryption

Construction

Our first broadcast encryption scheme is described as follows.

-

Setup(1 λ , n): Run G := (p, G, g) ← R GGen(1 λ ). Sample A ← R D k and k i , x i , y i ← R Z k+1 p for i ∈ [n].
Select a strongly unforgeable one-time signature scheme (Gen ots , Sig, Ver) and a hash function h : {0, 1} * → Z p from H. The master public key is

mpk := (G, h, (Gen ots , Sig, Ver), [A], {[A k i ], [A x i ], [A y i ]} n i=1 )
and the master secret key is msk := ({k i , x i , y i } n i=1 ). -KeyGen(msk, mpk, i): Output the secret key sk i = (k i , x i , y i ).

-Enc(mpk, m, S):

Let := |S| and S = {i 1 , . . . , i } ⊆ U = [n]. Sample r ← R Z k p and compute [u ] := [r A ].
Generate (sk ots , pk ots ) ← R Gen ots (1 λ ), compute α := h(pk ots ) and

c 1 := [r A k i 1 ] • m, v 1 := [r A (x i 1 + α • y i 1 )], . . . . . . c := [r A k i ] • m, v := [r A (x i + α • y i )].
Choose a random permutation τ over [ ] and compute

σ := Sig(sk ots , ([u ], c τ(1) , v τ(1) , . . . , c τ( ) , v τ( ) )).
The ciphertext is

ct := ([u ], c τ(1) , v τ(1) , . . . , c τ( ) , v τ( ) , pk ots , σ).
-Dec(mpk, ct, sk i ): Parse the ciphertext ct as ([u ], c1 , v1 , . . . , c , v , pk ots , σ) and the secret key sk i as

(k i , x i , y i ). Return ⊥ if Ver(pk ots , ([u ], c1 , v1 , . . . , c , v ), σ) = 0, otherwise, compute v := [u (x i + α • y i )],
where α = h(pk ots ). If there exists j ∈ [ ] such that v = vj , return m := cj /[u k i ]; otherwise, return ⊥.

Correctness.

For any ciphertext ct = ([u ], c1 , v1 , . . . , c , v , pk ots , σ) for set S ⊆ U generated by Enc, we always have Ver(pk ots , ([u ], c1 , v1 , . . . , c , v ), σ) = 1 by the correctness of signature scheme (Gen ots , Sig, Ver). Given secret key sk i = (k i , x i , y i ) for i ∈ S, there must exist an index j

∈ [ ] such that v = [u (x i + α • y i )] = vj ,
and then it is not hard to see that the message can be recovered from cj .

Security Result and Proof Overview

We prove the following theorem.

Theorem 1 Our broadcast encryption scheme in Section 3.1 is adaptively ANO-IND-CCA secure assuming that: (1) H is collision-resistant; (2) the D k -MDDH assumption holds in G; (3) signature scheme (Gen ots , Sig, Ver) is strongly unforgeable under one-time chosen message attack. Concretely, for any adversary A, there exist algorithms B 1 , B 2 , B 3 such that

Adv BE A (λ) Adv mddh G,B 1 (λ) + Adv ots B 2 (λ) + Adv hash B 3 (λ) + O(1/p)
and Time(B 1 ), Time(B 2 ), Time(B 3 ) ≈ Time(A).

We prove the theorem via the following game sequence.

Game 0 . This game is identical to the real game described in Section 2.1. In particular, our simulation is as follows: Setup. Run Setup(1 λ , n) and send A the master public key

mpk := (G, h, (Gen ots , Sig, Ver), [A], {[A k i ], [A x i ], [A y i ]} n i=1 )
and keep the master secret key msk := ({k i , x i , y i } n i=1 ). Set Q sk := ∅. Challenge ciphertext. Receiving (m 0 , m 1 , S 0 , S 1 ) from A where we let S 0 = {i 1,0 , . . . , i ,0 }

and Simulating KeyO. On input i ∈ U, output sk i = (k i , x i , y i ) and update Lemma 2 (Game 1 ≈ c Game 0 ). There exists an adversary B 1 such that

S 1 = {i 1,1 , . . . , i ,1 }, pick b ← R {0, 1}, u * ← R span(A), (sk * ots , pk * ots ) ← R Gen ots (1 λ ),
Q sk := Q sk ∪ {i}. Simulating DecO. On input (ct, i), parse ct = (ct 1 = ([u ], c 1 , v 1 , . . . , c , v ), pk ots , σ),
| Pr[Win 1 ] -Pr[Win 0 ]| Adv mddh G,B 1 (λ).
Game 2 . This game is identical to Game 1 except that DecO, on input (ct, i), rejects the query if (a) or (b) or (c) pk ots = pk * ots . This game is identical to Game 1 until A submits a query with pk ots = pk * ots which survives under condition (a) and (b). However σ in such a query will violate the strong unforgeability of (Gen ots , Sig, Ver), and this game is indistinguishable from Game 1 . Formally, we have the following lemma. Game 3 . This game is identical to Game 2 except the following substitution:

(c) pk ots = pk * ots -→ (c ) α = α *
This game is identical to Game 2 until A submits a query with pk ots = pk * ots but α = α * . This immediately violates the collision-resistance of H, and this game is indistinguishable from Game 2 . Formally, we have the following lemma.

Lemma 4 (Game 3 ≈ c Game 2 ). There exists an algorithm B 3 such that

| Pr[Win 3 ] -Pr[Win 2 ]| Adv hash B 3 (λ).
Game 4 . This game is identical to Game 3 except that except that DecO, on input (ct, i), rejects the query if (a) or (b) or (c ) or

(d) u / ∈ span(A)
We have the following lemma stating that this game is statistically indistinguishable with Game Let q D be the number of decryption queries. The lemma can be proved in q D steps. In the j-th step, assuming that the first j -1 decryption queries have been processed with condition (d), we demonstrate that the j-th query will finally be rejected if it survives under condition (a), (b), (c ) with u / ∈ span(A). In other words, we can introduce condition (d) here without changing adversary's view. The proof (for the j-th step) relies on the observation that we leak no more information than {A x η , A y η } η∈[n] when answering the first j -1 queries to DecO. With the help of condition (c ), which ensures that α = α * , we can claim that u (x i + α • y i ) is independently and uniformly distributed and thus hard to guess.

Finally, we have the following lemma which proves Theorem 1 when combining with all previous lemmas and claims. This follows from the fact that (u * k i , u * (x i + α • y i )) are uniformly distributed over G 2 , especially unrelated to b, for all i ∈ S b (resp. i ∈ S b /S 1-b ) when Q sk ∩ (S 0 ∩ S 1 ) = ∅ (resp. Q sk ∩ (S 0 ∩ S 1 ) = ∅), conditioned on mpk, KeyO and DecO. The analysis is similar to that for Lemma 5.

Let (ct = ([u ], c 1 , v 1 , . . . , c , v , pk ots , σ), i) be the j-th query. The event BadSpan j can be restated as follows: the j-th query survives under condition (a), (b), (c ) with u / ∈ span(A) but there exists

i ∈ [ ] such that v i = [u (x i + α • y i )].
To bound Pr[BadSpan j ], we introduce another event BadSpan j which is defined exactly as BadSpan j except that we replace [u (x i + α • y i )] with a random group element [v] ← R G. Firstly, since v is independent of A's behaviour, we have that Pr[BadSpan j ] = /p.

Secondly, we claim that Pr[BadSpan

j ] = Pr[BadSpan j ].
This follows from the fact that, for all

Q sk ∈ [n], all S b ∈ [n] and all i ∈ [n] \ Q sk , we have mpk, DecO : KeyO : ct * : → DecO :          A, {A x η , A y η } η∈[n] {x η , y η } η∈Q sk {u * (x η + α * • y η )} η∈S b u (x i + α • y i )          ≡          A, {A x η , A y η } η∈[n] {x η , y η } η∈Q sk {u * (x η + α * • y η )} η∈S b v          when x η , y η ← R Z k+1 p for all η ∈ [n] and v ← R Z p for all u, u * /
∈ span(A). We note that (1) the first j -1 decryption queries leak no more information than mpk since all queries with u / ∈ span(A) will be rejected (see the first line); (2) we naturally assume that i / ∈ Q sk , otherwise the adversary can simulate DecO (on this query) by itself; (3) two distributions are perfectly identical, so our non-adaptive statement implies the adaptive one. This readily proves the lemma. Select a key-binding secure symmetric encryption scheme (E, D) with the key space K := G 1 and a collision-resilient hash function h ← R H mapping from {0, 1} * to Z p . The master public key is mpk :=   PG, (E, D), h;

Proof of

[A ] 1 , {[A k i ] 1 } n i=1 , [A X] 1 , [A Y] 1 [B]

Conclusion

In this paper, we described two concrete ANOBE schemes. The first one is an instantiation of Libert et al.'s generic ANOBE. However, by working out the proof directly, we achieved a constantly tight reduction to standard assumptions. Furthermore, we pointed out that this scheme supports fast decryption for free and thus enjoys shorter ciphertexts. By the second scheme, we showed how to shorten the ciphertext again while preserving the tightness at the cost of slower decryption.

  The public parameter mpk is basically n public keys of Cramer-Shoup PKE 6 sharing [A] which is a common technique in the multi-user setting. The ciphertext for S contains ciphertexts of Cramer-Shoup PKE with randomness [r A ] reused as [LPQ12]. Following Libert et al.'s suggestion, they are then bound together via a strongly unforgeable signature σ under fresh verification key pk ots instead of encrypting m||pk ots .

  and u ← R Z k+1 p . The famous k-Linear (k-Lin) assumption is an instantiation of the D k -MDDH assumption. The classical decisional Diffie-Hellman (DDH) assumption (a.k.a symmetric external Diffie-Hellman (SXDH) assumption in asymmetric bilinear groups) is just the k-Lin assumption with k = 1. See [EHK + 13] for more details. For bilinear groups, we also use the D k -Matrix Kernel Diffie-Hellman (D k -KerMDH) Assumption [MRV16], which is implied by the D k -MDDH assumption.

  choose a random permutation τ over [ ], let α * = h(pk * ots ) and computect * 1 := ([u * ], c * 1 , v * 1 , . . . , c * , v * ) where c * j = [u * k i τ(j),b ] • m b and v * j = [u * (x i τ(j),b + α * • y i τ(j),b )] for j ∈ [ ].Output the challenge ciphertext ct * := (ct * 1 , pk * ots , σ * := Sig(sk * ots , ct * 1 )).

  reject the query if (a) ct = ct * or (b) Ver(pk ots , ct 1 , σ) = 0. Then compute α = h(pk ots ) and v = [u (x i + α • y i )]. If there exists j ∈ [ ] such that v = v j , return m := c j /[u k i ]; otherwise, return ⊥. Finalize. Received b from A, return 1 if b = b ; otherwise return 0.Let Win i denote the event that A in Game i guesses b correctly. Since Game 0 perfectly simulates the real game, we haveAdv BE A (1 λ ) = | Pr[Win 0 ] -1/2|. Game 1 .This game is identical to Game 0 except that we sample u * ← R Z k+1 p when generating the challenge ciphertext ct * . It is easy to see that this game is indistinguishable from Game 0 under the D k -MDDH assumption. Formally, we have the following lemma.

Lemma 3 (

 3 Game 2 ≈ c Game 1 ). There exists an adversary B 2 such that | Pr[Win 2 ] -Pr[Win 1 ]| Adv ots B 2 (λ).

3 . 5 (

 35 Lemma Game4 ≈ s Game 3 ). |Win 4 -Win 3 | O(1/p).

Lemma 6 .

 6 Pr[Win 4 ] = 1/2.

Lemma 6 :

 6 We will prove that Pr[Win 4 ] = 1/2 in two cases. Combining them together immediately proves the lemma. Case 1: Q sk ∩ (S 0 ∩ S 1 ) = ∅. We claim that (c * j , v * j ) are uniformly distributed over G 2 for all j ∈ [ ]. This means that ct * is actually independent of b and the adversary's advantage is 0 in this case. This follows from the fact that, for allQ sk ⊆ [n] and all S b ⊆ [n] satisfying Q sk ∩ S b = ∅, we have mpk, DecO : {A k η , A x η , A y η } η∈[n] {k η , x η , y η } η∈Q sk {u * k η , u * (x η + α * • y η )} η∈S b {A k η , A x η , A y η } η∈[n] {k η , x η , y η } η∈Q sk { c * η , ṽ * η } η∈S b when k η , x η , y η ← R Z k+1 p for all η ∈ [n] and c * η , ṽ * η ← R Z p for all η ∈ S b if u * / ∈ span(A). Case 2: Q sk ∩ (S 0 ∩ S 1 ) = ∅. We claim that all (c * j , v * j ) such that i τ(j),b ∈ S b \ S 1-b are uniformly distributed over G 2 .This follows from a statistical statement identical to that in Case 1 except that (c * j , v * j ) with i τ(j),b ∈ S b ∩ S 1-b remain unchanged. The claim is sufficient to argue that ct * reveals nothing about b since it must hold that m 0 = m 1 in this case.

-

  Setup (1 λ , n): Run PG := (p, G 1 , G 2 , G T , e, g 1 , g 2 ) ← R PGGen(1 λ ). Sample A, B ← R D k , X, Y ← R Z (k+1)×(k+1) p , k i ← R Z k+1 p for i ∈ [n].

  2 , [XB] 2 , [YB] 2   and the master secret key is msk := {k i } n i=1 . -KeyGen (msk, mpk, i): Output the secret key ski := k i . -Enc (mpk, m, S): Let := |S| and S = {i 1 , . . . , i } ⊆ U. Sample r ← R Z k p and compute [u ] 1 := [r A ] 1 .Select session key K ← R G 1 and computec 0 := E K (m), c 1 := [r A k i 1 ] 1 • K, . . . , c := [r A k i ] 1 • KChoose a random permutation τ over [ ] and compute[π] 1 := [r A (X + α • Y)] 1 where α := h([u ] 1 , c 0 , c τ(1) , . . . , c τ( ) ). The ciphertext is ct := ( [u ] 1 , c 0 , c τ(1) , . . . , c τ( ) , , [π] 1 ).-Dec(mpk, ct, sk i ): Parse ct as ([u ] 1 , c 0 , c1 , . . . , c , [π] 1 ) and sk i as k i . Computeα = h([u ] 1 , c 0 , c1 , . . . , c )and checke([π] 1 , [B] 2 ) ? = e([u ] 1 , [(X + α • Y)B] 2 ).(1)If Equation (1) does not hold, return ⊥; otherwise, do the following two steps from j := 1.1. Compute K := cj /[u k i ] 1 and m := D K (c 0 ). If m =⊥, return m and halt; otherwise, go to the second step. 2. If j = , return ⊥ and halt; otherwise, do the first step with j := j + 1.

Table 1 .

 1 Comparison of our two proposals and the concrete ANOBE from [LPQ12] in terms of ciphertext size and reduction tightness. Table (a) is for the schemes supporting fast decryption while we tolerate linear decryption cost in Table (b). In our comparison, the system has n users and is the size of target set S. We let G be a finite group where DDH holds while G 1 denotes the first source group of a bilinear group where SXDH holds. The column "Reduction" shows the security loss.

	(a) Comparing our first ANOBE with	(b) Comparing our second ANOBE with
	[LPQ12] plus anonymous hint system.	[LPQ12] without anonymous hint system.
	Scheme	|ct|	Reduction	Scheme	|ct|	Reduction
	[LPQ12] (4 + 5)|G| + 2|Z p | O(n 3 )	[LPQ12] (2 + 5)|G| + 2|Z p | O(n 3 )
	Sec. 3 (2 + 5)|G| + 2|Z p |	O(1)	Sec. 4	( + 6)|G 1 |	O(1)
	Shorter Ciphertext. Our first ANOBE scheme supports fast decryption. Compared with
	the concrete ANOBE in [LPQ12] equipped with their DDH-based anonymous hint system 4 ,
	our ANOBE can save rougly 50% bandwidth. Our second ANOBE is derived from the first
	one. We sacrifice fast decryption and peruse shorter ciphertext. Compared with concrete
	ANOBE in [LPQ12], our second ANOBE works with bilinear groups and roughly saves 50%
	bandwidth 5 . We highlight that this construction almost touches the lower bound of cipher-
	text size in an anonymous broadcast encryption [KS12]. It is quite surprising that we start
	from a less efficient basic PKE

scheme but finally achieves better space efficiency. We note that the Cramer-Shoup PKE [CS98,CS02] is indeed less efficient than Kurosawa-Desmedt PKE [KD04]

  which indicates the right ciphertext. This already saves the bandwidth since we need the DDH-based anonymous hint system in [LPQ12] to upgrade Libert et al.'s concrete ANOBE in order to achieve fast decryption. Even with randomness reuse technique, this will introduce 2 • |S| additional group elements to the ciphertext. The perspective here is that {[r A (x i j + α • y i j )] } j∈[ ] act as crucial components for achieving IND-CCA security and hints for fast decryption at the same time while they are realized separately in Libert et al.'s concrete ANOBE.Can we reduce the ciphertext size if we can tolerate slower decryption?

	Our Second ANOBE: Compressing Ciphertext Again. We now ask:

We assume that (1) the verification key and signature for strongly unforgeable one-time signatures consist of 3 group elements and 2 integers, respectively [Gro06] (see Section

4, [CCS09]);(2) the authenticated encryption with key-binding property has a ciphertext of roughly 2 group elements (see Section 6, [LPQ12]).4 The resulting ANOBE will also support fast decryption, here we share the randomness between ANOBE and anonymous hint system.5 Here we implement the concrete ANOBE from [LPQ12] using elliptic curve.

Here we use a direct generalization of Cramer-Shoup PKE under the k-Lin assumption. The original Cramer-Shoup PKE corresponds to the case k = 1.

Acknowledgment. We greatly thank Benoît Libert for his encouragement and support. We also thank all anonymous reviewers for their constructive comments.

and Software Engineering. Supported by the National Key R&D program of China (No. 2017YFB0802000) and NSF of China (Nos. 61572198, 61632012, 61672239). Part of this work was done while the author was visiting ENS de Lyon. Supported by the French ANR ALAMBIC project (ANR-16-CE39-0006).

Perspective. Lemma 5 and Lemma 6 are at the core of our proof. Although our proofs still rely on the proof technique of underlying Cramer-Shoup PKE, we get rid of large reduction loss by carrying out the argument in the broadcast setting directly. In particular, we employ the technique beneath the core lemma from Kiltz and Wee [KW15] (see Lemma 1), which allows us to take all users into account in a non-adaptive way first and then upgrade to the adaptive setting for free. This avoids guessing adversary's behaviour in the simulation which caused large security loss in Libert et al.'s work [LPQ12]. Furthermore, we note that our proof indeed involves robustness [ABN10, Moh10,LPQ12] but in an implicit manner since we are not working with generic PKE anymore.

Omitted Proofs

Proof of Lemma 3: In Game 2 , let Forge denote the event that A submits a query with ct := (ct 1 , pk ots = pk * ots , σ) to DecO which can not be rejected by condition (a) and (b). Observe that Game 2 is identical to Game 1 if Forge does not happen, we have

We bound Pr[Forge] via the following reduction. On input pk * ots , algorithm B 2 prepares mpk and simulates KeyO, DecO honestly as in Game 2 . When generating the challenge ciphertext, it generates ct * 1 as in Game 2 and output ct * := (ct * 1 , pk * ots , σ * ), where σ * is obtained from the SigO with input ct * 1 . Once Forge happens when answering query with (ct 1 , pk ots = pk * ots , σ), B 2 outputs (ct 1 , σ). The condition (b) ensure that σ is valid signature and condition (a) ensure that (ct 1 , σ) = (ct * 1 , σ * ). This readily proves the lemma.

Proof of Lemma 4:

In Game 3 , let Coll be the event that A submits a query with ct := (ct 1 , pk ots , σ) to DecO such that pk ots = pk * ots but α = α * . Observe that Game 3 is identical to Game 2 if Coll does not happen. That is we have

We bound Pr[Coll] via the following reduction. On input h, B 3 simulates Game 3 honestly except that we publish h in mpk and pk * ots is created before B 3 answers any queries. This will not change the view of A since pk * ots is independent of (m 0 , m 1 , S 0 , S 1 ). Once Coll happens when answering query with (ct 1 , pk ots , σ), B 3 outputs (pk ots , pk * ots ) as a collision. This readily proves the lemma.

Proof of Lemma 5:

We prove the lemma via the following hybrid argument:

where Game 3.j , for all j ∈ [0, q D ], is the same as Game 3 except that for the first j queries sent to DecO, we introduce condition (d).

Let BadSpan j be the event that the j-th query is rejected in Game 3.j but is replied with m = ⊥ in Game 3.j-1 . We prove the theorem by showing that

Correctness. For any ciphertext ct := ([u ] 1 , c 0 , c1 , . . . , c , [π] 1 ) for set S ⊆ U produced by Enc, we have

where α = h([u ] 1 , c 0 , c1 , . . . , c ). That is the ciphertext always satisfies Equation (1). Given a secret key sk i = k i for i ∈ S, we know that there exists

The correctness of our ANOBE then follows from the following two observations:

1. For each j < i , we know that c j = [r A k j ] 1 • K for some j ∈ S \ {i}, and thus we have

with overwhelming probability. From the key-binding feature of (E, D), the decryption algorithm Dec will return nothing before the i -th iteration. 2. It is easy to see that

By the correctness of (E, D), the decryption algorithm Dec will return m in the i -th iteration.

Security Result and Proof Overview

We prove the following theorem.

and Time(B 1 ), Time(B 2 ), Time(B 3 ), Time(B 4 ) ≈ Time(A).

We prove the theorem via the following game sequence.

Game 0 . This game is identical to the real game described in Section 2.1. In particular, our simulation is as follows:

Setup. Run Setup(1 λ , n) and send A the master public key

and keep the master secret key msk := {k i } n i=1 as well as X, Y. We also set Q sk := ∅.

Challenge ciphertext.

Receiving (m 0 , m 1 , S 0 , S 1 ) from A where we let S 0 = {i 1,0 , . . . , i ,0 } and

and choose a random permutation τ, and compute

) and reject the query (by returning ⊥) if

Then recover m using k i as Dec and return m. Finalize. Received b from A, return 1 if b = b ; otherwise return 0. We let Win i denote the event that A guesses b correctly in Game i . Since Game 0 perfectly simulates the real game, we have

This game is identical to Game 0 except that we sample u * ← R Z k+1 p when generating the challenge ciphertext ct * . This game is indistinguishable from Game 0 under the D k -MDDH assumption. Formally, we have the following lemma and the proof is analgous to that for Lemma 2.

Lemma 7 (Game 1 ≈ c Game 0 ). There exists an adversary B 1 such that

Game 2 . This game is identical to Game 1 except that DecO, on input (ct, i), returns ⊥ if (a) or (b) or (c) ct 1 = ct * 1 but α = α * . By the collision-resilience of H, this game is indistinguishable from Game 1 . Formally, we have the following lemma and the proof is similar to that for Lemma 4.

Lemma 8 (Game 2 ≈ c Game 1 ). There exists an algorithm B 2 such that

Game 3 . This game is identical to Game 2 except the following substitution:

This game is the same as Game 2 until A sends DecO a query which is rejected by condition (b ) but survives under condition (b). One can see that such a query immediately gives a solution to the D k -KerMDH problem w.r.t [B] 2 . Formally, we have the following lemma.

Lemma 9 (Game 3 ≈ c Game 2 ).

There exists an algorithm B 3 such that

Game 4 . This game is identical to Game 3 except the following substitution

Here " " denotes the OR operation which neglects the second operand if the first one is satisfied. We have the following lemma stating that this game is statistically close to Game 3 .

Lemma 10 (Game

Let q D be the number of decryption queries. The lemma will be proved in q D steps. In the j-th step, assuming that the first j -1 decryption queries have been processed with condition (b ), we demonstrate that the j-th query with u / ∈ span(A) can be rejected by condition (a), (b ), (c) with high probability. This simply follows from Lemma 1 (the core lemma).

To complete the proof of Theorem 2, we show the following lemma.

Lemma 11 (Bounding Pr[Win 4 ]

). There exists an algorithm B 4 such that

To prove the lemma, we consider two cases: (1) when Q sk ∩ (S 0 ∩ S 1 ) = ∅, we can prove that [u * k i ] 1 for i ∈ S b are independently and uniformly distributed over G 1 , which hide both S b and K * . The proof is similar to the proof of Lemma 6. Then the semantic security of (E, D) allows us to hide m b ; (2) when Q sk ∩ (S 0 ∩ S 1 ) = ∅, we can only prove that [u * k i ] 1 for i ∈ S b \ S 1-b are randomly distributed, but it is sufficient for proving the lemma since m 0 = m 1 .

Two Simple Missing Proofs

Proof of Lemma 9: In Game 3 , define BadKer the event that A sends DecO a query which is rejected by condition (b ), but survives under condition (b). It is easy to see that if BadKer does not occur, Game 3 is identical to Game 2 . Namely we have

We bound Pr[BadKer] via the following reduction. On input

and simulates Game 3 honestly using [B] 2 . Once BadKer happens when answering query with ct = (ct 1 = ([u ] 1 , c 0 , c 1 , . . . , c ), [π] 1 ), B 3 computes and outputs

We note that (1) the query has been rejected by condition (b ), we have t = 0; (2) the condition (b) ensures that t ∈ Ker(B). This readily proves the lemma.

Proof of Lemma 10:

We prove the lemma via the following hybrid argument:

where Game 3.j , for all j ∈ [0, q D ], is the same as Game 3 except that for the first j queries sent to DecO, the condition (b ) is replaced by condition (b ). Let BadSpan j be the event that the j-th query is rejected in Game 3.j but survives in Game 3.j-1 . We have that

The event BadSpan j can be restated as follows: the j-th query survives under condition (a), (b ), (c) with u / ∈ span(A). We first claim that α = α * . Then Lemma 1, the core lemma, immediately implies that Pr[BadSpan j ] < 1/p. The observation is we leak no more information than A X, A Y when answering the first j -1 queries to DecO due to the newly introduced condition u / ∈ span(A). Let the j-th query be associated with (ct 1 , π). We justify the claim (α = α * ) as follows. Thanks to condition (c), we only need to show that ct 1 = ct * 1 . We suppose ct 1 = ct * 1 . Observe that, (1) when π = π * , the query will be rejected by condition (b ); (2) when π = π * , the query will be rejected by condition (a). This readily proves the claim and thus complete the proof of the lemma.

Proof for Lemma 11

We will prove Lemma 11 by considering two cases. Let Win 1 4 and Win 2 4 denote that event Win 4 occurs in Case 1 and Case 2, respectively. This notation also applies to all later events. Case 1: Q sk ∩ (S 0 ∩ S 1 ) = ∅. We define the following two auxiliary games.

Game 5 . This game is identical to Game 4 except that we pick

This game is statistically indistinguishable with Game 4 , which follows that fact that all [u * k i ] 1 in ct * 1 is independently and uniformly distributed conditioned on mpk, KeyO and DecO. Formally, we show the following lemma. The proof is quite similar to the proof for Lemma 6 (Case 1).

Lemma 12 (Game

]. Game 6 . This game is identical to Game 5 except that we compute

This game is indistinguishable with Game 5 due to the semantic security of (E, D). Formally, we have the following lemma.

Lemma 13 (Game 6 ≈ c Game 5 ). There exists an algorithm B 4 such that

and Time(B 4 ) ≈ Time(A).

Observe that the challenge ciphertext ct * in Game 6 is independent of b and we have that Pr[Win 1 6 ] = 1/2. This immediately gives the following bound.

We now provide the full proof of Lemma 13 which completes our proof.

Proof of Lemma 13:

We construct B 4 as follows. On input (E, D), B 4 prepares mpk honestly as in Game 5 using the input. Both KeyO and DecO can be simulated honestly.

For the challenge ciphertext, B 4 samples [u * ] 1 and c * 1 , . . . , c * as in Game 5 . Then it picks b ← R {0, 1} and submits (m b , 0) to the environment, the ciphertext returned is set to be c * 0 . Finally, the last component [π * ] 1 is computed as in Game 5 .

Observe that, when c * 0 ← R E K * (m b ) for some random K * , our simulation is identical to Game 5 ; otherwise, when c * 0 ← R E K * (0), our simulation is identical to Game 6 . This readily proves the lemma.

Case 2: Q sk ∩ (S 0 ∩ S 1 ) = ∅. We define the following auxiliary game. This completes the proof of Lemma 11.


Emilie Charlier
email: echarlier@ulg.ac.be

Tero Harju
email: harju@utu.fi

Svetlana Puzynina
email: s.puzynina@gmail.com

Luca Q Zamboni
email: zamboni@math.univ-lyon1.fr

Émilie Charlier

Abelian bordered factors and periodicity

come   L'archive ouverte pluridisciplinaire

Introduction

A finite word u is bordered, if there exists a non-empty word z which is a proper prefix and a suffix of u. The following theorem states a well-known connection between periodicity and unbordered factors: Theorem 1. [START_REF] Ehrenfeucht | Periodicity and unbordered segments of words[END_REF][START_REF] Saari | Lyndon words and Fibonacci numbers[END_REF] An infinite word w is purely periodic if and only if there exists a constant C such that every factor v of w with |v| ≥ C is bordered.

In this paper we are interested in extending this result to the abelian and weak abelian settings.

Two finite words u and v are abelian equivalent if and only if for each letter a, the number of occurrences of a in u (denoted |u| a ) is equal to |v| a . In other words, u and v are permutations of one another. An infinite word w is called abelian ultimately periodic if w = uv 1 v 2 v 3 • • • , where the v i are pairwise abelian equivalent.

An infinite word w is called weakly abelian ultimately periodic if w = uv 1 v 2 v 3 • • • , where v i are finite words with the same frequencies of letters for i ≥ 1. In other words, a word is weakly abelian ultimately periodic if it can be factored into some prefix u followed by infinitely many words of possibly different lengths with the same letter frequencies. For more on weak abelian periodicity see [START_REF] Avgustinovich | Weak abelian periodicity of infinite words[END_REF].

We say that a finite word u is abelian bordered if u contains a non-empty proper prefix which is abelian equivalent to a suffix of u. Abelian bordered words were recently considered in [START_REF] Christodoulakis | Abelian borders in binary words[END_REF][START_REF] Rampersad | On the number of abelian bordered words[END_REF]. A finite word u is weakly abelian bordered if it has a non-empty proper prefix and a suffix with the same letter frequencies.

In Sections 3 and 4, we consider weak abelian borders in the binary and non-binary cases, respectively. We prove that the condition on finitely many weak abelian unbordered factors implies weak abelian periodicity plus some additional restrictions (Theorems 2 and 3). In Section 5, we consider infinite words having only finitely many abelian unbordered factors. We do not know if such words are necessarily abelian periodic. However, we are able to show that such words have bounded abelian complexity. In Section 6, we provide an answer to a question from [START_REF] Avgustinovich | On abelian versions of critical factorization theorem[END_REF] concerning abelian critical factorization theorem. In the last section we summarize the results and propose some open problems.

Preliminaries

In this section we give some basics on words following terminology from [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF] and introduce our notions.

Given a finite non-empty set Σ (called the alphabet), we denote by Σ * and Σ ω , respectively, the set of finite words and the set of (right) infinite words over the alphabet Σ. Given a finite word u = u 1 u 2 • • • u n with n ≥ 1 and u i ∈ Σ, we denote the length n of u by |u|. The empty word will be denoted by ε and we set |ε| = 0. Given the words w, x, y, z such that w = xyz, x is called a prefix, y is a factor and z a suffix of w. The word x is a proper prefix if 0 < |x| < |w|. We let w[i, j] = w i w i+1 • • • w j denote the factor starting at position i and ending at position j of w = w 1 w 2 w 3 • • • , where the w k ∈ Σ. An infinite word w is ultimately periodic (or briefly periodic) if for some finite words u and v it holds w = uv ω = uvv • • • ; w is purely periodic if u = ε. An infinite word is aperiodic if it is not ultimately periodic. Given a finite word u = u 1 u 2 • • • u n with n ≥ 1 and u i ∈ Σ, for each a ∈ Σ, we let |u| a denote the number of occurrences of the letter a in u. Two words u and v in Σ * are abelian equivalent, denoted u ∼ ab v, if and only if |u| a = |v| a for all a ∈ Σ. It is easy to see that abelian equivalence is an equivalence relation on Σ * . An infinite word w is called abelian ultimately periodic (or briefly abelian periodic

) if w = uv 1 v 2 v 3 • • • , where v i ∼ ab v j for all integers i, j ≥ 1.
For a finite non-empty word w ∈ Σ * , we define the frequency ρ a (w) of a letter a ∈ Σ in w as ρ a (w) = |w|a |w| . For an infinite word w ∈ Σ ω and a letter a ∈ Σ, if the limit

lim n→∞ ρ a (w[1..n])
exists, then we define the frequency ρ a (w) of a in w to be the latter limit. The infinite word w has uniform letter frequencies if, for every letter a of w, the ratio |w[k..k+n]|a n+1 has a limit ρ a (w) when n → ∞, uniformly in k. In general the existence of uniform frequencies is stronger than (prefix) frequencies, but in our consideration in fact all the words have uniform frequencies. Now we provide some background on weak abelian periodicity from [START_REF] Avgustinovich | Weak abelian periodicity of infinite words[END_REF]. Definition 1. An infinite word w over an alphabet Σ is called weakly abelian ultimately periodic (or briefly weakly abelian periodic

) if w = uv 1 v 2 v 3 • • • , where ρ a (v i ) = ρ a (v j ) for all a ∈ Σ and all integers i, j ≥ 1.
An infinite word w is called bounded weakly abelian periodic, if it is weakly abelian periodic with bounded lengths of blocks, i.e., there exists C such that for every i we have

|v i | ≤ C.
Example 1. The word (01)(0 2 1 2 )(0 3 1 3 )(0 4 1 4 ) • • • is weakly abelian periodic but not bounded weakly abelian periodic.

We make use of the following geometric interpretation of weak abelian periodicity. We translate an infinite word w = w 1 w 2 • • • ∈ Σ ω to a graph visiting points of the lattice Z |Σ| by interpreting letters of w as drawing instructions. In the binary case we associate 0 with a move by the vector v 0 = (1, -1), and 1 with a move by v 1 = (1, 1). We start at the origin (x 0 , y 0 ) = (0, 0). At step n, we are at a point (x n-1 , y n-1 ) and we move by a vector corresponding to the letter w n , so that we come to a point (x n , y n ) = (x n-1 , y n-1 ) + v wn , and the two points (x n-1 , y n-1 ) and (x n , y n ) are connected with a line segment. We let G w denote the corresponding graph, and G w (n) = (x n , y n ). Lemma 1. A weakly abelian periodic word w has a graph with infinitely many integer points on some line with a rational slope.

We remark that instead of the vectors (1, -1) and (1, 1), one could use any other pair of noncollinear vectors v 0 and v 1 . For a k-letter alphabet one can consider a similar graph in Z k with linearly independent integer vectors v 1 , . . . , v k . For example, one can take as v i a unit vector with 1 at position i and all other coordinates equal to 0.

In the binary case and for vectors v 0 = (1, -1) and v 1 = (1, 1), it will be convenient for us to use a function g w : n → y n , so that G w (n) = (n, g w (n)). It can also be regarded as a piecewise linear function with line segments connecting integer points (see an example on Figure 1).

Weak abelian borders: binary alphabet

We proceed with the following theorem relating weak abelian borders and weak abelian periodicity, giving one way analog of the characterization of periodicity in terms of unbordered factors (Theorem 1): Theorem 2. Let w be an infinite binary word. If there exists a constant C such that every factor v of w with |v| ≥ C is weakly abelian bordered, then w is bounded weakly abelian periodic. Moreover, its graph lies between two rational lines and has points on each of these two lines with bounded gaps.

Remark that following the terminology from [START_REF] Avgustinovich | Weak abelian periodicity of infinite words[END_REF], a bounded weakly abelian periodic word is necessarily of bounded width. Namely, a word w is of bounded width if there exist two lines with the same slope, so that the graph of w lies between these two lines. Formally, there exist numbers α, β, β ′ so that αx + β ≤ g w (x) ≤ αx + β ′ . We note that in the case of weak abelian periodicity α must be rational.

We will also need the notion of balance. A word w ∈ Σ ω is called K-balanced, if for each letter a and two factors u, v of w such that |u| = |v| the inequality ||u| a -|v| a | ≤ K holds. We simply say that w is balanced if it is K-balanced for some K. We remark that balance implies the existence of letter frequencies: Proposition 1. [3, Proposition 2.4] An infinite word w ∈ Σ ω is balanced if and only if it has uniform letter frequencies and there exists a constant B such that for any factor u of w and for all letters a ∈ Σ, we have |u| a -ρ a (w)|u| ≤ B.

In fact, the latter proposition implies that balance is equivalent to the bounded width property. Indeed, the bounded width property implies balance. The converse is obtained by applying the above proposition to the prefixes of the word. Corollary 1. An infinite word is balanced if and only if it is of bounded width.

The proof of Theorem 2 heavily relies on the graph representation of the word. It consists of several lemmas restricting the form of the word. We first prove that if a factor w[i + 1..j] of w is such that the graph of the word between i and j lies above or below the line segment connecting the points (i, g w (i)) and (j, g w (j)), then w[i + 1..j] is weakly abelian unbordered: Lemma 2. Let w be an infinite binary word, and i, j be integers, i < j. If g w (k) > gw(j)-gw(i) j-i k+ gw(i)j-gw(j)i j-i for each i < k < j, then the factor w[i + 1..j] is weakly abelian unbordered.

We also note that a symmetric assertion holds for the case when the graph lies below this line: simply invert the inequality in the statement of the lemma. Proof. For any proper prefix p and any proper suffix

s of w[i + 1..j] we have ρ 1 (p) -ρ 0 (p) > gw(j)-gw(i) j-i
and ρ 1 (s) -ρ 0 (s) < gw(j)-gw(i) j-i

. Hence there is no weak abelian border.

However, the reciprocal of the previous lemma does not hold. A counterexample is given by the weakly abelian unbordered word 1110000011000: see Figure 3.

Figure 3: The reciprocal of Lemma 2 is not true: weakly abelian unbordered factor 1110000011000.

Lemma 3. Let w be an infinite binary word with finitely many weakly abelian unbordered factors. Then w is balanced.

We remind that by balance we mean K-balance for some K.

Proof. Suppose the converse. Unbalance implies that for every K there exist i, j, l with i < l < j, such that

g w (l) - g w (j) -g w (i) j -i l - g w (i)j -g w (j)i j -i ≥ K. (1)
In other words, the point (l, g w (l)) lies at distance at least K from the line connecting the points i and j (distance measured vertically). Indeed, unbalance implies that there exist two factors u and v of the same length in which the number of occurrences of the letter 0 (and hence also the letter 1) differs by more than K. Consider the factor w[i + 1..j] starting with u and ending with v. It is not hard to see that it satisfies the inequality (1) for either l = i + |u| or l = j -|v|.

Take the shortest such factor (i.e., choose i, j satisfying the condition (1) with the smallest j -i). Then the graph G w does not intersect the line segment connecting the points (i, g w (i)) and (j, g w (j)), for otherwise there exists a shorter factor satisfying [START_REF] Avgustinovich | On abelian versions of critical factorization theorem[END_REF]. Hence due to Lemma 2, it remains to notice that the lengths of such factors grow as K grows (in fact, j -i > K).

Since balance implies the existence of letter frequencies, Lemma 3 implies that a word satisfying the conditions of Theorem 2 has letter frequencies. We will now prove that the frequencies are rational.

Lemma 4. Let w be an infinite binary word with finitely many weakly abelian unbordered factors.

Then the letter frequencies are rational.

Proof. Balance implies bounded width, i.e., there exist α, β ′ , β ′′ such that the graph of w lies between two lines: αx

+ β ′ ≤ g w (x) ≤ αx + β ′′ .
Here α is related to the letter frequencies as follows: ρ 0 = 1-α 2 and ρ 1 = 1+α 2 . So, we need to prove that α is rational. Assume the converse. Take the lowest (in the sense of the smallest β) line y = αx + β such that there are points of the graph arbitrarily close to it. We build the line (and prove its existence) as follows.

Take ε > 0, divide the stripe αx + β ′ ≤ y ≤ αx + β ′′ into stripes of width at most ε (width can be measured vertically, although this is not important). At least one of the stripes contains infinitely many points (i, g w (i)) of the graph G w . Choose the lowest such stripe αx

+ β ′ 1 ≤ y ≤ αx + β ′′ 1 . Divide it into stripes of width ε 1 < ε, continue the process with ε n → 0. The value of β in the desired line is obtained as a limit β = lim n→∞ β ′ n = lim n→∞ β ′′ n .
To prove that α is rational, we consider three cases:

Case 1: There are no points of the graph G w below the line y = αx + β. In this case take ε > 0 and consider the stripe αx + β ≤ y ≤ αx + β + ε. There are infinitely many points in this stripe by the definition of the line y = αx + β. Consider any two consecutive points (n 1 , g w (n 1 )) and (n 2 , g w (n 2 )) from the stripe (consecutive in the sense that for any n, n 1 < n < n 2 , we have g w (n) > αx + β + ε). By Lemma 2, the factor w[n 1 + 1..n 2 ] is weakly abelian unbordered, since the points of the graph G w between n 1 and n 2 lie above the line y = αx + β + ε, which in turn lies above the line segment connecting the points (n 1 , g w (n 1 )) and (n 2 , g w (n 2 )). Now we will prove that the minimal possible length (n 2 -n 1 ) grows as ε → 0. Indeed, take the shortest factor w[n 1 + 1..n 2 ] with n 1 , n 2 consecutive points in the stripe such that the slope of the line segment connecting the points (n 1 , g w (n 1 )) and (n 2 , g w (n 2 )) is the closest to α, i.e., α -| gw(n 2 )-gw(n 1 )

n 2 -n 1
| is minimal among the factors of the length (n 2 -n 1 ) with both ends in the stripe. If there are several such factors, choose one of them, say the leftmost. Since α is irrational, it is not equal to the slope of the line connecting points (n 1 , g w (n 1 )) and (n 2 , g w (n 2 )). So, take

ε ′ < |g w (n 2 ) -g w (n 1 )| -α(n 2 -n 1 )
, then no two points of the graph corresponding to positions in the word at distance (n 2 -n 1 ) can simultaneously be in the stripe αx + β ≤ y ≤ αx + β + ε ′ . So, the minimal distance between points in the new (thinner) stripe of width ε ′ increased, which corresponds to weak abelian unbordered factors of length more than n 2 -n 1 . Continuing this line of reasoning and taking smaller and smaller ε, we get arbitrary long weakly abelian unbordered factors.

Case 2: There are finitely many points of the graph G w below the line y = αx + β (but the number of such points is nonzero). In this case take the last point (n 0 , g w (n 0 )) below the line: g w (n 0 ) ≤ αn 0 + β, and g w (n) > αn + β for each n > n 0 . Consider a prefix of length N > n 0 of w, and the part of the graph between n 0 and N . Choose a point n ′ , n 0 < n ′ ≤ N , such that the point (n ′ , g w (n ′ )) is the closest to the line among the points (n, g w (n)), n 0 < n ≤ N :

|g w (n ′ ) -αn ′ -β| = min n 0 <n≤N |g w (n) -αn -β|.
Then due to Lemma 2, the factor w[n 0 + 1..n ′ ] is weak abelian unbordered. Indeed, the points of the graph G w between n 0 and n ′ lie above the line y = αx + g w (n ′ ) -αn ′ (the line parallel to y = αx + β and passing through the point (n ′ , g w (n ′ ))), which in turn lies above the line segment connecting the points (n 0 , g w (n 0 )) and (n ′ , g w (n ′ )):

g w (n) ≥ αn + g w (n ′ ) -αn ′ > g w (n ′ ) -g w (n 0 ) n ′ -n 0 n + g w (n 0 )n ′ -g w (n ′ )n 0 n ′ -n 0
for n 0 < n < n ′ . Since there are points of the graph arbitrary close to the line y = αx + β, then, increasing N , we will find larger and larger values n ′ and hence find arbitrary long weakly abelian unbordered factors.

Case 3: There are infinitely many points of the graph G w below the line y = αx + β. Since we chose the lowest line with the property that there are infinitely many points arbitrary close to the line, it follows that for any ε > 0 there are only finitely many points below the line y = αx + β -ε (if any). Take ε such that there are points below the line y = αx + β -ε. By the condition of Case 3 there are infinitely many points in the stripe αx + β -ε ≤ y ≤ αx + β. For each two consecutive points in the stripe the corresponding factor is weakly abelian unbordered due to Lemma 2. As ε → 0, the lengths of such factors grow for irrational α (the proof of this is similar to the proof of the similar fact from Case 1).

Therefore, we came to a contradiction in each case. So the frequency must be rational.

Proof of Theorem 2. Lemmas 3 and 4 imply that the graph of the word lies between two lines of rational slope α: αn + β ′ ≤ g w (n) ≤ αn + β ′′ for each n. We can choose such lines with the minimal β ′′ and maximal β ′ . To prove the theorem it remains to show that the graph of the word has points on each of these two lines with bounded gaps. We provide a proof for the line y = αx + β ′ , for the other line the proof is symmetric.

First we prove that there are points of the graph on the line. Clearly, for rational α there is a fixed minimal distance from the integer points of the lattice Z 2 to the line (note that for irrational slope this does not hold). If there are no points of the graph on the line, since the slope is rational, instead of y = αx + β ′ we could choose a different line y = αx + β ′′′ with the same slope passing through the point of the graph closest to the line, and with β ′′′ > β ′ , which contradicts the choice of β ′ as the maximal possible.

Secondly, there are infinitely many points on the line. Otherwise consider a line y = αx + β ′′′ with β ′′′ > β ′ , with infinitely many points of the graph on the line and with the smallest such β ′′′ . Note that here we need again α to be rational. Then there exists n 0 such that for all n > n 0 we have g w (n) ≥ αn + β ′′′ , i.e., starting from n 0 the graph lies above the line. Taking the smallest possible n 0 satisfying the condition, we get that the point (n 0 , g w (n 0 )) lies below the line. Hence for each n ′ > n 0 corresponding to a point on the line, i.e., with g w (n ′ ) = αn ′ + β ′′′ , we have that the factor w[n 0 + 1..n ′ ] is weakly abelian unbordered by Lemma 2. Indeed, all the points between n 0 and n ′′ lie above the line y = αx + β ′′′ and hence above the line segment connecting the points (n 0 , g w (n 0 )) and (n ′ , g w (n ′ )) of the graph corresponding to the beginning and the end of the factor.

Finally, we need to prove that the points on the line y = αx + β ′ appear in bounded gaps. This follows from the fact that for two consecutive points n 1 , n 2 on the line y = αx + β ′ the factor w[n 1 + 1..n 2 ] is weakly abelian unbordered by Lemma 2.

Remark 1. Except for the case ρ 0 = ρ 1 = 1/2 (equal frequencies), we do not know whether the converse of Theorem 2 is true (see Question 2). In the case of equal frequencies the converse holds, and it could be easily seen from the graph of the word. In fact, we will prove that all sufficiently long factors have weak abelian borders with frequencies 1/2. Frequencies equal to 1/2 correspond to α = 0, so the graph lies between two horizontal lines y = β ′ and y = β ′′ , and intersects each of them with bounded gaps. Denote the maximal gap by C. Consider a factor w[i + 1..j] of length > C: j -i > C. Then there exist n ′ , n ′′ , i < n ′ , n ′′ < j, such that g w (n ′ ) = β ′ , g w (n ′′ ) = β ′′ . Without loss of generality n ′ < n ′′ . For each integer β, β ′ ≤ β ≤ β ′′ , there exists n, n ′ ≤ n ≤ n ′′ , such that g w (n) = β. In other words, in the interval [n ′ , n ′′ ] the graph passes through any integer horizontal line between β ′ and β ′′ . In particular, there exist i ′ , i ′′ , i < n ′ ≤ i ′ , i ′′ ≤ n ′′ < j, such that g w (i) = g w (i ′ ), g w (j) = g w (j ′ ). So, the prefix w[i + 1..i ′ ] and the suffix w[j + 1..j ′ ] give a weak abelian border with the frequencies 1/2. But we do not see how to generalize this observation to the case of nonequal frequencies, since in general the graph can "jump" through several rational non-horizontal lines and it does not have to pass through all rational lines between points on lower and upper lines.

Weak abelian borders: nonbinary alphabet

Now we continue with non-binary alphabets and prove the analogue of Theorem 2. Basically, a non-binary word with finitely many weakly abelian unbordered factors must also be balanced, weakly abelian periodic and have rational letter frequencies. To state the analogue of the additional condition in Theorem 2 (graph lying between two parallel rational lines and bounded weak abelian periodicity along those lines) we need some notation.

First, in the non-binary case, instead of bounded width we define cylinder set. Let l denote a line in R k , l :

x i = x 0 i + a i t, i = 1, . . . , k, and let M be a constant. A k-dimensional cylinder C(l, M ) is defined as C(l, M ) = {x ∈ R k |d(l, x) ≤ M }
= (x ′ 1 , . . . , x ′ n ) ∈ G w such that b 1 x ′ 1 + • • • + b k x ′ k = d.
We remark that a tangential hyperplane to the graph G w does not have to be a "proper" tangential hyperplane to the cylinder C(l, M ), but it is a hyperplane parallel to it. In the remaining part of the text, by "tangential" we always mean tangential to the graph. Next, we define a tangential line l ′ to G w , l ′ : x i = x ′0 i + a i t, i = 1, . . . , k, as a line which belongs to some tangential hyperplane

H to G w , H : b 1 x 1 + • • • + b k x k = d, such that for each point x ∈ G w ∩ H one has also x ∈ l ′ .
In other words, a tangential line l ′ is defined as a line parallel to the cylinder lying in some tangential hyperplane, such that the only points of the graph belonging to the hyperplane also belong to the line. We remark that this line can be inside the cylinder. Now we are ready to state the non-binary analogue of Theorem 2: Theorem 3. Let w be an infinite word over a k-letter alphabet. If there exists a constant C such that every factor v of w with |v| ≥ C is weakly abelian bordered, then w is bounded weakly abelian periodic. Moreover, its graph G w belongs to a k-dimensional cylinder with axis with rational coefficients, and each tangential line to G w has points of G w on it with bounded gaps.

We emphasize that in fact Theorem 2 is a particular case of Theorem 3. We state and prove it separately for several reasons. First, for clarity reasons: the statement of Theorem 2 is easier and more intuitive. Second, key lemmas in non-binary case are simple consequences of those in the binary case. On the other hand, the proof of the body of the theorem is more involved, so there is not much repetition in the proofs.

First we prove that Lemmas 3 and 4 also hold for the non-binary case: Lemma 5. If an infinite word has finitely many weakly abelian unbordered factors, then it is balanced.

Proof. Assume that w is an infinite word with finitely many weakly abelian unbordered factors. For a ∈ alph(w), consider a morphism h a : a → a, b → c for all b = a where c is a letter not belonging to alph(w). We call such a morphism a projection. Clearly, if two words u and v have the same letter frequencies, then so do h a (u) and h a (v), for each a ∈ alph(w). Hence if u is weakly abelian bordered, then so is h a (u). Then h a (w) has finitely many weakly abelian unbordered factors. Now, since a projection of w is a binary word (over the alphabet {a, c}), we can apply Lemma 3, hence h a (w) is also balanced: There exists a constant K a , such that for each two factors u, v of h a (w) such that |u| = |v| the inequality ||u| a -|v| a | ≤ K a holds. Taking K = max a∈Σ K a , we get that w itself is K-balanced by definition. Lemma 6. If an infinite word has finitely many weakly abelian unbordered factors, then its letter frequencies are rational.

Proof. Clearly, the frequency of any letter a exists in an infinite word x if and only if the frequency of the letter a exists in its projection h a (x), and these frequencies are equal. Since the projection is a binary word, Lemma 4 implies that w has letter frequencies and they are rational.

We let ( b, x) denote the scalar product of vectors b and x :

( b, x) = b 1 x 1 + • • • + b k x k .
We make use of the following analogue of Lemma 2.

Lemma 7. Let w be an infinite word, and i, j be integers, i < j. If there exists a hyperplane

H : b 1 x 1 + • • • + b k x k = d such that G w (i), G w (j) ∈ H
and ( b, G w (l)) > d for each i < l < j (or ( b, G w (l)) < d for each i < l < j), then the factor w[i + 1..j] is weakly abelian unbordered.

Proof. Two factors w[i 1 + 1..j 1 ] and w[i 2 + 1..j 2 ] share the same letter frequencies if the vectors G w (j 1 ) -G w (i 1 ) and G w (j 2 ) -G w (i 2 ) connecting their ends are collinear. Moreover, they differ by a positive multiple. For any proper prefix w[i + 1..p] and any proper suffix w[s + 1..j] of w[i + 1..j] we have (G w (p) -G w (i), b) > 0 and (G w (j) -G w (s), b) < 0, which implies that w[i + 1..p] and w[s + 1..j] do not have the same letter frequencies.

Proof of Theorem 3. Like in the binary case, balance implies that G w belongs to some kdimensional cylinder C(l, M ). The coefficients a i of the axis l of the cylinder are related to the letter frequencies and can be defined via {v 1 , . . . , v k }. Since frequencies are rational and all v i have integer entries, the coefficients a i are also rational. In fact, the graph of the word lies on finitely many lines with rational coefficients parallel to the cylinder axis. Clearly, in dimension two this is equivalent to bounded width.

First notice that such tangential lines always exist. We can choose a cylinder with the minimal M . Similarly to the binary case and using the fact that the slope vector ā of the cylinder is rational it is not hard to show that there exists a point x′ ∈ G w with d(l, x′ ) = M. Consider the line l ′ parallel to l and passing through one of such points, l ′ : x = x′ + āt. Taking the tangential plane H to the cylinder passing through x′ , we see that l ′ is a tangential line to the graph G w . We remark that this tangential plane H is both a tangential plane to the graph G w and a "proper" tangential plane to the cylinder C(l, M ). Although there can be other tangential lines to the graph G w lying inside the cylinder, so that the corresponding tangential planes to G w are not tangential to the cylinder.

To prove the theorem it remains to show that for a tangential line l ′′ : x = x′′ + āt the points of the graph lie on this line with bounded gaps.

Like in the binary case, we first show that there are infinitely many points of the graph on the line l ′′ . Suppose that there are only finitely many of those. Take the corresponding tangential hyperplane

H ′′ : b 1 x 1 + • • • + b k x k = d ′′ and consider the hyperplane H ′ : b 1 x 1 + • • • + b k x k = d ′
parallel to H ′′ such that it has infinitely many points of G w on it (since G w lies on finitely many lines parallel to l ′′ due to rational coefficients, it also lies on finitely many hyperplanes parallel to H ′′ ). So, there are finitely many points of G w such that b

1 x 1 + • • • + b k x k < d ′ ,

and infinitely many with b

1 x 1 + • • • + b k x k = d ′ .
Now take the point x(n 0 ) = G w (n 0 ) on the line with the largest n 0 such that b 1 x

(n 0 ) 1 + • • • + b k x (n 0 ) k < d ′ . Then for each n with b 1 x (n) 1 + • • • + b k x (n) k = d ′ for x(n) = G w (n) the factor w[n 0 + 1.
.n] is weakly abelian unbordered. Indeed, arguing as in Lemma 7, for any proper prefix w[i + 1..p] and any proper suffix w[s + 1..j] of w[i + 1..j] we have (G w (p) -G w (i), b) > 0 and (G w (j) -G w (s), b) < 0, which implies that w[i + 1..p] cannot be weakly abelian equivalent to w[s + 1..j]. So, we proved that there are infinitely many points of the graph on a tangential line.

Finally, we need to prove that the points on the tangential line l ′′ appear in bounded gaps. It follows from the fact that for two consecutive points n 1 , n 2 on l ′′ the factor w[n 1 + 1..n 2 ] is weakly abelian unbordered by Lemma 7.

Abelian borders

In this section we consider the connections between abelian periodicity and the condition of having finitely many abelian unbordered factors. First we show that finitely many abelian unbordered factors is not a sufficient condition for periodicity: Proposition 2. There exists an infinite aperiodic word w and constants C, D such that every factor v of w with |v| ≥ C has an abelian border of length at most D.

Proof. Any aperiodic word w ∈ {010100110011, 0101001100110011} ω satisfies the condition with C = 15 and D = 14. The proof is a fairly straightforward and not too technical case study: If u is a sufficiently long abelian unbordered factor, then it must begin or end with either 0100 or with 1101 because the other factors of length 4 have equal frequencies. So there are only these two cases to consider: the factor starts with 0100 (the case of ending with 1101 is symmetric) or with 1101 (the case of ending with 0100 is symmetric).

Consider first the case of a factor beginning with 0100. If it ends with 0, we have an abelian border of length 1; if it ends with 01, we have an abelian border of length 2. So we need to analyze the remaining case of the form 0100 • • • 0011.

Considering extension of the prefix 0100 to the right, one has after 01 abelian period 4 with equal frequencies. Considering extension of the suffix 0011 to the left, one has abelian period 4 with equal frequencies. So, extending to the left the suffix, one will get an abelian border as soon as there is a block 0101. Thus, there exists an abelian border of length 4k + 2, where k is at most 3. Now consider the case of a factor beginning with 1101. It continues uniquely to the right with 01001100, so that 110101001100 is the prefix of the factor. If it ends with 1, we have an abelian border of length 1, so we need to consider the cases of ending with 00 and 10.

If it ends with 00, then it has either a suffix 0100, or 1100. The suffix 0100 extends uniquely to the left to 11010100, giving an abelian border of length 8. The suffix 1100 extends to either 11001100 giving an abelian border of length 8, or to 110101001100, giving an abelian border of length 12.

If it ends with 10, then it has a suffix 010 (otherwise there is an abelian border of length 3), which extends uniquely to 1010. This suffix in turn extends to 01010 (otherwise there is an abelian border of length 5), which extends to 1101010, giving an abelian border of length 7. This concludes the proof.

We observe that all infinite word w ∈ {010100110011, 0101001100110011} ω occurrring in the proof of Proposition 2 are abelian periodic with period 2. In general, we do not know whether an infinite word containing only finitely many abelian unbordered factors is necessarily abelian periodic. However, we begin by showing that abelian periodicity alone does not in general imply only finitely many abelian unbordered factors. In other words, at least one direction of Theorem 1 fails in the abelian setting. Proposition 3. Let x be a uniformly recurrent aperiodic word containing infinitely many distinct palindromes. Then x admits an infinite number of abelian unbordered factors.

Proof. Let N be any positive integer. We claim that x admits a factor of the form aU b where a and b are distinct letters and U a palindrome with |U | ≥ N . In fact, since x contains infinitely many palindromes, there exists a palindromic factor u of x with |u| ∈ {N, N + 1}. By uniform recurrence there exists a constant M such that every factor of x of length M contains an occurrence of u. Since x is aperiodic, there exists a word v with |v| = 3M and distinct letters c and d such that both cv and dv are factors of x. In the usual terminology, v is a left special factor of x. Let η denote the center of the first occurrence of u in the prefix of v of length M . So η is either an integer or a half integer depending on the parity of |u|. Let U be the longest palindromic factor of v centered at η. It follows that 2M ≥ |U | ≥ |u| ≥ N . If U is a not a prefix of v, then there exist distinct letters a and b such that the word aU b is a factor of v centered at η. On the other hand, if U is a prefix of v, then let b be a letter such that U b is a prefix of v. Since both cv and dv are factors of x we can find a letter a different from b such that aU b is a factor of x. Having established our claim, the result of the proposition now follows immediately since any word of the form aU b with a = b and U a palindrome is clearly abelian unbordered.

As an immediate corollary we have:

Corollary 2. There exist abelian periodic words having infinitely many abelian unbordered factors.

Proof. Let x ∈ {0, 1} ω be any binary uniformly recurrent aperiodic word containing infinitely many palindromes. For instance x can be taken to be the Thue-Morse infinite word or any Sturmian word. Let τ denote the morphism 0 → 0110, 1 → 1001. Then τ (x) is abelian periodic (with abelian period 2). Moreover, it is readily verified that τ (x) is uniformly recurrent, aperiodic, and contains infinitely many distinct palindromes. By Proposition 3, it follows that τ (x) admits infinitely many abelian unbordered factors.

As mentioned earlier, we do not know whether the other direction of Theorem 1 holds in the abelian context, that is whether a word having only finitely many abelian unbordered factors is necessarily abelian periodic. However we are able to establish the abelian analogue of the following weaker version of Theorem 1: Theorem 4. Let x be an infinite word having only finitely many unbordered factors. Then there exists a constant N such that x contains at most N factors of each given length n ≥ 1. In other words, x has bounded factor complexity.

The reason this is a weaker version of Theorem 1 is because bounded complexity is equivalent to ultimate periodicity. For this reason the converse of Theorem 4 does not hold in general. For instance x = 01111 • • • has bounded complexity, yet contains infinitely many unbordered prefixes.

We now give several new proofs of Theorem 1 which may be of independent interest. One direction is of course trivial: namely, if x is purely periodic then all sufficiently long factors of x are bordered. For the other direction, as in the original proof by Ehrenfeucht and Silberger, we break the proof into two parts; in a first part we show that if x is any infinite word with the property that all sufficiently long factors are bordered, then x is ultimately periodic. We give three proofs of this first part which to our knowledge are all new. However, each of the following proofs relies on one or more key features which do not extend to the abelian context. See the remark following the proofs. In a second part we show that x must be purely periodic. Also our proof of the second part is new and greatly simplifies the original proof by Ehrenfeucht and Silberger.

Proof of Theorem 1. Let U (x) denote the set of unbordered factors of x. Clearly if x is purely periodic then U (x) is finite. Conversely, assume U (x) is finite. We first show that x is ultimately periodic.

A first quantitative proof of this was given by K. Saari in which he shows that for any aperiodic word x and any positive integer n, the number L x (n) of Lyndon words of length ≤ n occurring in x is greater or equal to L f (n) where f is the Fibonacci word. See Theorem 3 and Remark 3 in [START_REF] Saari | Lyndon words and Fibonacci numbers[END_REF].

A second proof, also using Lyndon words proceeds as follows: If x is aperiodic, then by Proposition 4.8 in [START_REF] Charlier | Infinite self-shuffling words[END_REF], x contains an infinite Lyndon word x ′ in its shift orbit closure, i.e., there exists an ordering of the alphabet of x relative to which x ′ is lexicographically smaller than all its proper suffixes. Since x ′ begins in infinitely many unbordered prefixes, it follows that x contains infinitely many unbordered factors.

A third proof uses the so-called Duval conjecture, first proved by the second author together with D. Nowotka in [START_REF] Harju | Periodicity and unbordered words: a proof of the extended Duval conjecture[END_REF], which states that if v is a word of length 2n such that the prefix u of v of length n is unbordered and every factor of v of length greater than n is bordered, then v = uu. Assume U (x) is finite and let u ∈ U (x) be of maximal length. Then by the Duval conjecture, every occurrence of u in x is an occurrence of u 2 . Hence x is ultimately periodic with period u.

A fourth proof, perhaps the simplest in that it is completely self contained, proceeds as follows: Assume U (x) is finite. By replacing x if necessary by some suffix of x, we can assume that each u ∈ U (x) is recurrent in x, i.e., occurs in x an infinite number of times. Let u ∈ U (x) be of maximal length. Let v be any first return to u in x, i.e., vu is a factor of x which begins and ends in u and |vu| u = 2. Then since u is unbordered, |v| ≥ |u| i.e., u is a prefix of v. If |v| > |u|, then v is bordered (by maximality of |u|). Let v ′ denote the shortest border of v. Then v ′ ∈ U (x) from which it follows that |v ′ | ≤ |u| and hence v ′ is a proper prefix of u (since u is not a suffix of v). But then the factor v ′ u of x is an unbordered factor of x of length greater than |u|, a contradiction. Hence, if v is a first return to u, then |v| = |u|, i.e., v = u. It follows that x is ultimately periodic with period u.

We next show that if x = x 1 x 2 x 3 • • • is ultimately periodic and all sufficiently long factors of x are bordered, then x is purely periodic. Let x ′ denote the left infinite word • • • x 3 x 2 x 1 obtained by reflecting x. By assumption there exists a primitive word u such that ω u is a prefix of x ′ (where ω u denotes the left infinite word • • • uuu). Clearly if u = a for some letter a, then x ′ = ω a. Thus we can assume that u contains at least two distinct letters. Let < be a linear order of alph(x) and let < ′ denote the opposite order, i.e., a < ′ b if and only if b < a. Let M (m, respectively) denote the Lyndon conjugate of u relative to < (< ′ , respectively). Without loss of generality we can write x ′ = ω M z = ω myz for some suffix z of x ′ and some suffix y of M . We will show that z is a prefix of M ω and hence that x ′ is purely periodic. Let M z denote the prefix of M ω of length |z| and m yz the prefix of m ω of length |yz|. Since M is unbordered and all sufficiently long factors of x ′ are bordered, it follows that z is a product of prefixes of M and hence that z ≤ M z . Similarly, yz ≤ ′ m yz or equivalently yz ≥ m yz . Since m ω = yM ω , we deduce that z ≥ M z and hence z = M z as required.

Remark 2. We note that none of the above proofs readily extend to the abelian context. In fact, we know of no suitable analogue of Lyndon words in the abelian setting. Also, the Duval conjecture fails miserably in the abelian setting. More precisely, there exists an infinite word x with the following properties: i) x begins in an unbordered factor u, ii) all factors of x of length greater than |u| are abelian bordered, iii) the prefix of x of length 2|u| is not an abelian square. To see this, let y be any infinite word in {010100110011, 0101001100110011} ω beginning in (0101001100110011) 2 . Let x denote the second shift of y, i.e., x = (01) -1 y. Then x begins in the unbordered factor u = 01001100110011 of length 14. As in the proof of Proposition 2, every factor of x of length greater than 14 is abelian bordered. Yet it is easily checked that the prefix of length 28 of x is not an abelian square, i.e., not of the form uu ′ with u ′ abelian equivalent to u. Finally, the fourth proof uses the following fact which is no longer true in the abelian setting, namely that if v is a proper prefix of an unbordered word u, then vu is unbordered. For instance, we can take the prefix v = 01 of the abelian unbordered word u = 010011. Yet vu = 01010011 is abelian bordered.

We end by establishing the following abelian analogue of Theorem 4: Theorem 5. Let x be an infinite word having only finitely many abelian unbordered factors. Then there exists a constant N such that x contains at most N abelian equivalence classes of factors of each given length n ≥ 1. In other words, x has bounded abelian factor complexity.

Proof. Since the condition that x has only finitely many abelian unbordered factors implies that x has only finitely many weakly abelian unbordered factors, it follows that all conclusions we derived earlier in the weak abelian setting still hold. In particular x is balanced. Thus x has bounded abelian complexity (see Lemma 3 in [START_REF] Richomme | Abelian complexity of minimal subshifts[END_REF]).

6 A non-abelian periodic word with bounded abelian square at each position

In [START_REF] Avgustinovich | On abelian versions of critical factorization theorem[END_REF], the following open question was proposed: Let w be an infinite word and C be an integer such that each position in w is a centre of an abelian square of length at most C. Is w abelian periodic? We answer this question negatively by providing an example (actually, a family of examples).

Consider a family of infinite words of the following form:

(000101010111000111000(111000) * 111010101) ω

A straightforward case study shows that words of this form have an abelian square of length at most 12 at each position. It is not hard to see that this family contains abelian aperiodic words.

Conclusions and open questions

We conclude with the summary of our results and propose two open problems.

Question 1. Let w be an infinite word and C a constant such that every factor v of w with |v| ≥ C is abelian bordered. Does it follow that w is abelian periodic?

Recall that we showed that there exist examples of words satisfying these conditions which are not periodic (Proposition 2), but all examples we have are abelian periodic.

The next question asks whether the converse of Theorem 3 (and in particular Theorem 2) is true:

Question 2. Let w be an infinite bounded weakly abelian periodic word over a k-letter alphabet such that its graph G w belongs to a k-dimensional cylinder with axis with rational coefficients, and each tangential line to G w has points of G w on it with bounded gaps. Does it follow that w has only finitely many weakly abelian unbordered factors?

We remark that in the case of binary alphabets and letter frequencies equal to 1/2 the answer to this question is positive (see Remark after Theorem 2).

Our main results and open questions are summarized in Figure 1.

Figure 1 :

 1 Figure 1: The graph of the Thue-Morse word with v 0 = (1, -1), v 1 = (1, 1).

Figure 2 :

 2 Figure 2: Illustration of Lemma 2: weakly abelian unbordered factor 11010.

  where d(l, x) denotes the distance between the point x and the line l. The line l is the axis of the cylinder. Now we will give an analogue of the two parallel lines such that the graph lies between those two lines and has points on each of those lines with bounded gaps. If the graph G w of an infinite word w over a k-letter alphabet belongs to some cylinder C(l, M ), we define a tangential hyperplane to the graph of G w as a hyperplane H : b1 x 1 + • • • + b k x k = dparallel to the line l such that for each point x = (x 1 , . . . , x k ) ∈ G w one has b 1 x 1 + • • • + b k x k ≥ d, and in addition there is a point x′

2 Figure 4 :

 24 Figure 4: Results and open questions. WAP means "weakly abelian periodic". Condition 1: The graph G w of the word belongs to a k-dimensional cylinder with axis with rational coefficients, and each tangential line to G w has points of G w on it with bounded gaps.

supported in part by the Academy of Finland under FiDiPro grant