Adeline Langlois
email: adeline.langlois@ens-lyon.fr

San Ling
email: lingsan@ntu.edu.sg

Khoa Nguyen

Huaxiong Wang
email: hxwang@ntu.edu.sg

Lattice-based Group Signature Scheme with Verifier-local Revocation

Keywords: group signature, verifier-local revocation, lattice-based cryptography

Support of membership revocation is a desirable functionality for any group signature scheme. Among the known revocation approaches, verifier-local revocation (VLR) seems to be the most flexible one, because it only requires the verifiers to possess some up-to-date revocation information, but not the signers. All of the contemporary VLR group signatures operate in the bilinear map setting, and all of them will be insecure once quantum computers become a reality. In this work, we introduce the first lattice-based VLR group signature, and thus, the first such scheme that is believed to be quantum-resistant. In comparison with existing lattice-based group signatures, our scheme has several noticeable advantages: support of membership revocation, logarithmic-size signatures, and weaker security assumption. In the random oracle model, our scheme is proved to be secure based on the hardness of the SIVP O(n 1.5 ) problem in general lattices -an assumption that is as weak as those of state-of-the-art lattice-based standard signatures. Moreover, our construction works without relying on encryption schemes, which is an intriguing feature for group signatures.

Introduction

Group Signatures. Group signatures have been an important research topic in public-key cryptography since their introduction by Chaum and van Heyst [START_REF] Chaum | Group Signatures[END_REF]. In these schemes, all the potential signers form a group, where each signer can anonymously issue a signature on behalf of the whole group (anonymity). On the other hand, in cases of disputes, there is a tracing mechanism which can link a given signature to the identity of the misbehaving member (traceability). These two attractive features allow group signatures to find applications in various real-life scenarios, such as anonymous online communications, digital right management, e-commerce systems, and much more. Over the last two decades, many group signature schemes with different security models, different levels of efficiency and functionality have been proposed ( [START_REF] Chen | New Group Signature Schemes (Extended Abstract)[END_REF][START_REF] Ateniese | A Practical and Provably Secure Coalition-Resistant Group Signature Scheme[END_REF][START_REF] Bellare | Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions[END_REF][START_REF] Boneh | Short Group Signatures[END_REF][START_REF] Boneh | Group Signatures with Verifier-local Revocation[END_REF][START_REF] Bellare | Foundations of Group Signatures: The Case of Dynamic Groups[END_REF][START_REF] Groth | Fully Anonymous Group Signatures Without Random Oracles[END_REF][START_REF] Libert | Group Signatures with Almost-for-Free Revocation[END_REF], ...).

One desirable functionality of group signatures is the support for membership revocation. For example, misbehaving members who issue signatures for documents, which they are not allowed to sign, should be revoked from the group. In these cases, if a group signature scheme does not support revocation, then the whole system has to be re-initialized, which is obviously an unsuitable solution in practice. Currently there are two main revocation approaches for group signatures. The first approach requires all the unrevoked members to update their signing keys after each revocation ([4,12,8,11],...). At the same time, all the signature verifiers need to download the up-to-date group public key. As a consequence, it is sometimes inconvenient to practically implement such schemes. The second approach, that is group signatures with verifier-local revocation (VLR), only requires the verifiers to possess some up-to-date revocation information, but not the signers. Since in most of real-life scenarios, the number of signature verifiers is much smaller than the number of signers, this revocation approach is more flexible and more practical. Moreover, it is akin to that of the traditional Public Key Infrastructures, where the verifiers use the latest Certificate Revocation List to check the public key of the signer. The notion of VLR group signatures was introduced by Brickell [START_REF] Brickell | An Efficient Protocol for Anonymously Providing Assurance of the Container of the Private Key[END_REF], then formalized by Boneh and Shacham [START_REF] Boneh | Group Signatures with Verifier-local Revocation[END_REF], further investigated and extended by Nakanishi and Funabiki [START_REF] Nakanishi | Verifier-Local Revocation Group Signature Schemes with Backward Unlinkability from Bilinear Maps[END_REF][START_REF] Nakanishi | A Short Verifier-Local Revocation Group Signature Scheme with Backward Unlinkability[END_REF], Libert and Vergnaud [START_REF] Libert | Group Signatures with Verifier-Local Revocation and Backward Unlinkability in the Standard Model[END_REF], and Bichsel et al. [START_REF] Bichsel | Get Shorty via Group Signatures without Encryption[END_REF]. It is worth mentioning that all the existing VLR group signatures scheme operate in the bilinear map setting. Furthermore, all these schemes will be insecure once quantum computers become a reality [START_REF] Shor | Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[END_REF]. Thus, constructing a VLR group signature schemes which is secure against quantum computers, or even outside of the bilinear map setting, is a challenging open question.

Lattice-based Group Signatures. Lattice-based cryptography is currently considered as the most promising candidate for post-quantum cryptography. As opposed to classical cryptography (i.e., based on the hardness of factoring or discrete log problems), lattice-based cryptography is widely believed to be resistant against quantum computers, moreover, it enjoys provable security under worst-case hardness assumptions ( [START_REF] Ajtai | Generating Hard Instances of Lattice Problems (Extended Abstract)[END_REF][START_REF] Regev | On Lattices, Learning with Errors, Random Linear Codes, and Cryptography[END_REF][START_REF] Gentry | Trapdoors for Hard Lattices and New Cryptographic Constructions[END_REF][START_REF] Micciancio | Lattice-based Cryptography[END_REF]). Designing secure and efficient lattice-based cryptographic constructions (and group signatures, in particular) becomes an intriguing challenge for the research community looking forward to the future. To the best of our knowledge, three lattice-based group signature schemes have been proposed, but none of them supports membership revocation. The first one was introduced by Gordon et al. [START_REF] Gordon | A Group Signature Scheme from Lattice Assumptions[END_REF] in 2010. While their scheme is of great theoretical interest, its signatures have size O(N ), where N is the number of group users. In terms of efficiency, this is a noticeable disadvantage if the group is large, e.g., group of all employees of a big company. Camenisch et al. [START_REF] Camenisch | Fully Anonymous Attribute Tokens from Lattices[END_REF] later proposed lattice-based anonymous attribute tokens system, a primitive that can be considered as a generalization of group signature. However, in their construction, the signatures size is still linear in N . Recently, Laguillaumie et al. [START_REF] Laguillaumie | Lattice-Based Group Signatures with Logarithmic Signature Size[END_REF] designed a scheme featuring signature size O(log N ), which is the first lattice-based group signature that overcomes the linear-size barrier. We remark that all the above mentioned schemes follow the traditional sign-and-encrypt-and-prove paradigm: to enable the tracing mechanism, these schemes require the signer to encrypt some private information via certain type of encryption based on the Learning With Errors (LWE) problem, and then generate a sophisticated proof to prove particularly that the ciphertext is well-formed. Relying on encryption to construct group signatures may imply two troublesome issues: firstly, it makes the construction less efficient; secondly, since the whole system is secure only if the underlying encryption scheme is secure, it usually leads to a relatively strong security assumption. In particular, the recent scheme by Laguillaumie et al. [START_REF] Laguillaumie | Lattice-Based Group Signatures with Logarithmic Signature Size[END_REF] is only provably secure if there is no quantum algorithm to approximate the Shortest Independent Vectors Problem (SIVP γ ) on lattices of dimension n to within certain γ = O(n 8.5 ). This yields several interesting open questions in this direction: Is it possible to construct a scheme that supports membership revocation? Can lattice-based group signature schemes be free of LWE-based encryptions? How to design a more efficient scheme based on weaker security assumption?

Our Contributions. In the present work, we reply to all the above open questions positively. In particular, we introduce the first group signature with verifier-local revocation from lattice assumptions, and thus, the first such scheme that is believed to be quantum-resistant. In comparison with known lattice-based group signatures, while the schemes from [START_REF] Gordon | A Group Signature Scheme from Lattice Assumptions[END_REF], [START_REF] Camenisch | Fully Anonymous Attribute Tokens from Lattices[END_REF] and [START_REF] Laguillaumie | Lattice-Based Group Signatures with Logarithmic Signature Size[END_REF] follow the CPA-anonymity and CCA-anonymity notions from [START_REF] Boneh | Short Group Signatures[END_REF][START_REF] Bellare | Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions[END_REF], our construction satisfies the (weaker) notion of selfless-anonymity for VLR group signatures from [START_REF] Boneh | Group Signatures with Verifier-local Revocation[END_REF]. Nevertheless, our scheme has several remarkable advantages over the contemporary counterparts: 1. Functionality: Our scheme is the first lattice-based group signature that supports membership revocation. As discussed above, this is a desirable functionality for any group signature scheme. 2. Simplicity: Our scheme is conceptually very simple. The signature is basically an all-in-one proof of knowledge, made non-interactive using Fiat-Shamir paradigm [START_REF] Fiat | How to Prove Yourself: Practical Solutions to Identification and Signature Problems[END_REF]. Moreover, the scheme departs from the traditional paradigm, and is free of LWE-based encryptions. 3. Efficiency: For a security parameter n and for a group of N members, the group public key and the signature have bit-sizes O(n 2 ) • log N and O(n) • log N , respectively. This result is comparable to that of [START_REF] Laguillaumie | Lattice-Based Group Signatures with Logarithmic Signature Size[END_REF], and is a noticeable improvement over those of [START_REF] Gordon | A Group Signature Scheme from Lattice Assumptions[END_REF] and [START_REF] Camenisch | Fully Anonymous Attribute Tokens from Lattices[END_REF]. 4. Security assumption: Our scheme is proved to be secure (in the random oracle model) based on the worst-case hardness of approximating the Shortest Independent Vectors Problem, for general lattices of dimension n, to within a factor γ = O(n 1.5 ). Surprisingly, this security assumption is as weak as those of state-of-the-art lattice-based standard signatures, such as [START_REF] Gentry | Trapdoors for Hard Lattices and New Cryptographic Constructions[END_REF], [START_REF] Cash | Bonsai Trees, or How to Delegate a Lattice Basis[END_REF], and [START_REF] Lyubashevsky | Lattice Signatures without Trapdoors[END_REF]. This is a non-trivial feature, because when constructing group signatures, which is a more eleborate primitive than standard signatures, one would expect to rely on a stronger security assumption.

Overview of Our Techniques. The main building block of our VLR group signature scheme is an interactive protocol allowing a prover to convince the verifier that he is a certified group member (i.e., he possesses a valid secret signing key), and that he has not been revoked (i.e., his "revocation token" is not in the verifier's blacklist). The protocol is repeated many times to make the soundness error negligibly small, and then is converted to a signature scheme via Fiat-Shamir heuristic. Roughly speaking, in the random oracle model, the traceability and anonymity of the resulting group signature are based on the facts that the underlying protocol is a proof of knowledge, and it can be simulated. We consider a group of N = 2 ℓ users, where each user is identified by a string d ∈ {0, 1} ℓ denoting the binary representation of his index in the group. Let n, m, β, and q ≥ 2 be integers (to be determined later). Our scheme operates within the structure of a Bonsai tree of hard random lattices [START_REF] Cash | Bonsai Trees, or How to Delegate a Lattice Basis[END_REF], namely, a matrix

A = A 0 A 0 1 A 1 1 . . . A 0 ℓ A 1 ℓ ∈ Z n×(2ℓ+1)m q
, and a vector u ∈ Z n q . Initially, the group user with identity d = d [START_REF] Ajtai | Generating Hard Instances of Lattice Problems (Extended Abstract)[END_REF] . . . d[ℓ] ∈ {0, 1} ℓ is issued a Bonsai signature of his identity, that is a small vector z ∈ Z (ℓ+1)m , such that z ∞ ≤ β and

A d • z = u mod q, where A d = A 0 A d[1] 1 . . . A d[ℓ] ℓ
a subtree defined by d. In other words, z is a solution to the Inhomogeneous Small Integer Solution (ISIS) instance (A d , u). To prove that he is a certified group member without leaking z, the user can perform a proof of knowledge (e.g., [START_REF] Micciancio | Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More[END_REF][START_REF] Lyubashevsky | Lattice-Based Identification Schemes Secure Under Active Attacks[END_REF][START_REF] Ling | Improved Zero-Knowledge Proofs of Knowledge for the ISIS Problem, and Applications[END_REF]) to convince the verifier that he knows such a vector z in zero-knowledge.

At this stage, one can obtain a secure identity-based identification scheme (as shown in [START_REF] Rückert | Adaptively Secure Identity-Based Identification from Lattices without Random Oracles[END_REF]), but it is insufficient for our purposes: to achieve anonymity, the group user also has to hide his identity d, and hence the matrix A d should not be explicitly given. This raises an interesting question: If the verifier does not know A d , how could he be convinced that A d • z = u mod q? To address this issue, we introduce the following extension: we add ℓ suitable zero-blocks of size m to vector z to obtain an extended vector x = x 0 x 0 1 x 1 1 . . .

x 0 ℓ x 1 ℓ ∈ Z (2ℓ+1)m
, where the added zero-blocks are x

1-d[1] 1 , . . . , x 1-d[ℓ] ℓ
. We then have x ∞ ≤ β, and A • x = u mod q. Namely x is a solution to the ISIS instance given by the whole Bonsai tree, with an additional condition: for each i = 1, . . . , ℓ, one of the two blocks x 0 i , x 1 i must be zero, where the arrangement of the zero-blocks is determined by d. To prove in zero-knowledge the possession of such a vector x, we adapt the 'Stern Extension' proof system from [START_REF] Ling | Improved Zero-Knowledge Proofs of Knowledge for the ISIS Problem, and Applications[END_REF], where the user identity d is hidden by a "one-time pad" technique. This technique is as follows. In each round of the protocol, the user samples a fresh uniformly random e ∈ {0, 1} ℓ and permutes the blocks of x to obtain the permuted vector v, whose zero-blocks are arranged according to d ⊕ e (where ⊕ denotes the bit XOR operation). Depending on the verifier's challenge, the user later will either reveal e, or reveal d ⊕ e and show that v has the correct shape determined by d ⊕ e. Since d ⊕ e is uniformly random over {0, 1} ℓ , the user identity d is completely hidden. As a result, the user can anonymously prove his group membership.

We now briefly review our revocation mechanism. For each group user's secret key x, consider the first block x 0 that corresponds to the "root" A 0 of the Bonsai tree, and let his revocation token be A 0 • x 0 mod q ∈ Z n q . We choose suitable parameters, and sample x 0 from a proper distribution, so that the token is statistically close to uniform over Z n q . At a high level, our revocation mechanism works as follows. The user is asked to sample a uniformly random vector r 0 ∈ Z m q , and to compute a commitment c 0 using a (lattice-based) statistically hiding and computationally binding string commitment scheme COM, for which the value A 0 • r 0 mod q is part of the committed string. Depending on the verifier's challenge, the user will either reveal r 0 or reveal x 0 + r 0 . In the former case, the verifier can check for honest computation of c 0 , while in the latter case, he can perform the revocation check using a list of tokens of revoked users RL = {u i } i ⊂ Z n q , as follows:

∀u i ∈ RL, check that c 0 = COM A 0 • (x 0 + r 0 ) -u i mod q .
Assuming that the user has been revoked, i.e., there exists i such that A 0 • x 0 mod q = u i . If he follows the protocol, then COM A 0 • (x 0 + r 0 )u i mod q = COM(A 0 • r 0 mod q) = c 0 , and thus, he gets rejected. If there is a false acceptance, then we can use it to break the computational binding property of COM. On the other hand, the probability of false rejection is negligibly small, since COM is statistically regular.

Putting everything together, we obtain a lattice-based VLR group signature that has several nice features, as mentioned earlier. In the process, we exploit the rich structure of the Bonsai tree [START_REF] Cash | Bonsai Trees, or How to Delegate a Lattice Basis[END_REF], and the versatility of the "Stern Extension" proof system [START_REF] Ling | Improved Zero-Knowledge Proofs of Knowledge for the ISIS Problem, and Applications[END_REF]. We also employ a special "one-time pad" technique, and a novel revocation mechanism.

Preliminaries

Notations. For a positive integer n, we let [n] denote the set {1, . . . , n}. Vectors will be denoted in bold lower-case letters and matrices will be denoted in bold upper-case letters. We assume that all vectors are column vectors. The concatenation of vectors x ∈ R m and y ∈ R k is denoted by (x y). We denote the column concatenation of matrices

A ∈ R n×m and B ∈ R n×k by A B . Let x = (x 1 , . . . , x n ), we denote by Parse(x, i 1 , i 2 ) the vector (x i 1 , x i 1 +1 . . . , x i 2 ) for 1 ≤ i 1 ≤ i 2 ≤ n. If S is a finite set, y $ ← -S
means that y is chosen uniformly at random from S. If D 1 and D 2 are two distributions over the same countable support S, then their statistical distance is defined as

∆(D 1 , D 2 ) = 1 2 x∈S |D 1 (x) -D 2 (x)|.
Two distributions are statistically close if their statistical distance is negligible.

VLR Group Signature

The presentation in this Section follows [START_REF] Boneh | Group Signatures with Verifier-local Revocation[END_REF]. A VLR group signature consists of 3 following algorithms: A secure VLR group signature scheme must satisfy the following 3 requirements:

1. Correctness: For all (gpk, gsk, grt) outputted by KeyGen, all d ∈ {0, 1, . . . , N -1}, and all M ∈ {0, 1} * , Verify(gpk, RL,

Sign(gpk, gsk[d], M ), M ) = Valid ⇔ grt[d] ∈ RL.
2. Selfless-anonymity: In the following selfless-anonymity game, the adversary's goal is to determine which of the two adaptively chosen keys generated a signature. He is not given access to either key. The adversary wins the game if: i. Verify(gpk, RL * , Σ * , M * ) = valid. ii. The (implicit) tracing algorithm fails or traces to a user outside of the coalition U \ RL * . iii. The signature Σ * is non-trivial, i.e., A did not obtain Σ * by making a signing query on M * . The probability that A wins the game, denoted by SuccPT A , is taken over the randomness of A, algorithms KeyGen and Sign. We say that a VLR group signature is traceable if SuccPT A is negligible.

Some Cryptographic Tools from Lattices

Lattices. Let n, m, and q ≥ 2 be integers. For matrix A ∈ Z n×m q , define the m-dimensional lattice:

Λ ⊥ (A) = x ∈ Z m : A • x = 0 mod q ⊆ Z m .
For any u in the image of A, define the coset Λ ⊥ u (A) = x ∈ Z m : A • x = u mod q . We recall the homogeneous and inhomogeneous Small Integer Solution problems (SIS and ISIS).

Definition 1. The SIS p n,m,q,β and ISIS p n,m,q,β problem in the ℓ p norm with parameters (n, m, q, β) are as follows: Given a uniformly random matrix A ∈ Z n×m q , and a uniformly random vector u ∈ Z n q ,

• SIS p n,m,q,β asks to find a non-zero vector x ∈ Λ ⊥ (A) such that x p ≤ β. • ISIS p n,m,q,β asks to find a vector x ∈ Λ ⊥ u (A) such that x p ≤ β. The hardness of the SIS and ISIS problems is given by a worst-case to average-case reduction from standard lattice problems, such as the Shortest Independent Vectors Problem (SIVP).

Theorem 1 ([18]

). For any m, β = poly(n), and for any q ≥ β • ω( √ n log n), solving a random instance of the SIS 2 n,m,q,β or ISIS 2 n,m,q,β problem with non-negligible probability is at least as hard as approximating the SIVP 2 γ problem on any lattice of dimension n to within certain

γ = β • O( √ n) factors.
It then follows from the relationship between the ℓ 2 and ℓ ∞ norms that the SIS ∞ n,m,q,β and ISIS ∞ n,m,q,β problems are at least as hard as SIVP 2 γ (in the ℓ 2 norm) for some γ = β • O(n). Gaussians over Lattices. For any positive real σ, the n-dimensional Gaussian function is defined as: ∀x ∈ R n , ρ σ (x)= exp(-π x 2 /σ 2 ). For any n-dimensional lattice Λ, define the discrete Gaussian distribution over Λ as: ∀x ∈ Λ, D Λ,σ (x) = ρσ(x) ρσ(Λ) . In the following lemma, we review several well-known facts about discrete Gaussian distribution: Lemma 1 ([18] [START_REF] Peikert | Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices[END_REF]). Let n and q ≥ 2 be integers. Let m ≥ 2n log q, and σ ≥ ω( √ log m).

1. For all but a 2q -n fraction of all A ∈ Z n×m q , for x ←֓ D Z m ,σ , the distribution of u = A • x mod q is statistically close to uniform over Z n q . Moreover, the conditional distribution of x given u is

D Λ ⊥ u (A),σ . 2. For β = ⌈σ • log m⌉, and x ←֓ D Z m ,σ , Pr x ∞ > β is negligible. 3. The min-entropy of D Z m ,σ is at least m -1.
We now recall the results about two fundamental tools in lattice-based cryptography: the trapdoor generation and the preimage sampling algorithms. The algorithms stated in the following theorem are improvements of those in the literature [START_REF] Ajtai | Generating Hard Instances of the Short Basis Problem[END_REF][START_REF] Gentry | Trapdoors for Hard Lattices and New Cryptographic Constructions[END_REF][START_REF] Peikert | An Efficient and Parallel Gaussian Sampler for Lattices[END_REF][START_REF] Alwen | Generating Shorter Bases for Hard Random Lattices[END_REF].

Theorem 2 ([28]

). Given integers n ≥ 1, q ≥ 2, and m ≥ 2n log q. There is a PPT algorithm GenTrap(n, m, q) that outputs a matrix A ∈ Z n×m q and a trapdoor R A , such that the distribution of A is negl(n)-far from uniform. Moreover, for any vector u in the image of A and σ = ω( √ n log q log n), there is a PPT algorithm SampleD(R A , A, u, σ) that outputs x ∈ Z m sampled from the distribution D Z m ,σ , conditioned on the event that A • x = u mod q.

The KTX String Commitment Scheme. Kawachi et al. [START_REF] Kawachi | Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems[END_REF] constructed a string commitment scheme COM : {0, 1} * × {0, 1} m/2 → Z n q , such that:

• If m > 2n(1 + δ) log q for some positive constant δ, then COM is statistically hiding.

• If the SIS ∞ n,m,q,1 problem is hard, then COM is computationally binding.

In this paper, we will extensively use the KTX commitment scheme. For simplicity, we will omit the randomness of the commitment. Also, we implicitly choose m sufficiently large, e.g., m = 4n log q, to make COM statistically hiding.

Preparations

We now describe the parameters and some specific constructions that will be used in our scheme.

Parameters

Our group signature scheme involves two main parameters: a security parameter n and a maximum expected number of group users N = 2 ℓ ∈ poly(n). Given n, we fix the other scheme parameters as in Table 3.1.

Parameter Value or Asymptotic bound

Modulus q ω(n 2 log n) Table 1. Parameters of our VLR group signature scheme. The sequence β1, β2, . . . , βp satisfies p j=1 βj = β, and every integer in the interval [-β, β] can be efficiently expressed as a subset sum of elements in the set {±β1, ±β2, . . . , ±βp}.

Dimension m ≥ 2n log q Gaussian parameter σ ω( √ n log q log n) Integer norm bound β ⌈σ • log m⌉

Some Specific Sets

We now define some specific sets of vectors and permutations that will be extensively used throughout this work. First, we denote by B 3m the set of all vectors in {-1, 0, 1} 3m having exactly m coordinates -1; m coordinates 0; and m coordinates 1. Given a binary string d = d [START_REF] Ajtai | Generating Hard Instances of Lattice Problems (Extended Abstract)[END_REF] . . . d[ℓ] ∈ {0, 1} ℓ , we define two sets:

• Secret β (d): The set of all vectors x = x 0 x 0 1 x 1 1 . . . x 0 ℓ x 1 ℓ ∈ Z (2ℓ+1
)m consisting of 2ℓ + 1 blocks of size m, such that x ∞ ≤ β, and the following ℓ blocks are zero-blocks 0 m : x

1-d[1] 1 , . . . , x 1-d[ℓ] ℓ . • SecretExt(d): The set of all vectors x = x 0 x 0 1 x 1 1 . . . x 0 ℓ x 1 ℓ ∈ {-1, 0, 1} (2ℓ+1)3m consisting of 2ℓ + 1 blocks of size 3m, such that the ℓ + 1 blocks x 0 , x d[1] 1 , . . . , x d[ℓ] ℓ
are elements of B 3m , and the remaining ℓ blocks x

1-d[1] 1 , . . . , x 1-d[ℓ] ℓ are zero-blocks 0 3m . Given a vector x = x 0 x 0 1 x 1 1 . . . x 0 ℓ x 1 ℓ ∈ Z (2ℓ+1
)3m consisting of 2ℓ + 1 blocks of size 3m, we define two sets of permutations of x:

• The set S of all permutations that keep the arrangement of the blocks. Specifically, if π ∈ S, then

π(x) = τ 0 (x 0 ) τ 0 1 (x 0 1 ) τ 1 1 (x 1 1 ) . . . τ 0 ℓ (x 0 ℓ ) τ 1 ℓ (x 1 ℓ ) ,
where τ 0 , τ 0 1 , τ 1 1 , . . . , τ 0 ℓ , τ 1 ℓ are certain permutations of 3m elements. • The set T = {T e e ∈ {0, 1} ℓ }, where for e = e [START_REF] Ajtai | Generating Hard Instances of Lattice Problems (Extended Abstract)[END_REF] . . . e[ℓ], T e ∈ T rearranges the blocks as follows:

T e (x) = x 0 x e[1] 1 x 1-e[1] 1 . . . x e[ℓ] ℓ x 1-e[ℓ] ℓ .
In particular, given d, e ∈ {0, 1} ℓ , π ∈ S, and x ∈ Z (2ℓ+1)3m , it can be checked that:

x ∈ SecretExt(d) ⇔ π(x) ∈ SecretExt(d) ⇔ T e • π(x) ∈ SecretExt(d ⊕ e).
(1)

The Decomposition -Extension Technique

Ling et al. [START_REF] Ling | Improved Zero-Knowledge Proofs of Knowledge for the ISIS Problem, and Applications[END_REF] proposed a Stern-type zero-knowledge proof of knowledge for the ISIS ∞ n,m,q,β problem that enjoys a strong security guarantee: the best way to break their protocol is to solve the underlying ISIS problem. They achieve this feature by using a versatile Decomposition-Extension framework. Adapting their technique, we construct the following procedures: Elementary Decomposition. On input a vector v = (v 1 , v 2 , . . . , v m ) ∈ Z m such that v ∞ ≤ β, the procedure EleDec outputs p = ⌊log β⌋+1 vectors w 1 , . . . , w p ∈ {-1, 0, 1} m , such that p j=1 β j • w j = v. This procedure works as follows:

1. For each i ∈ [m], express v i as v i = β 1 •v i,1 +β 2 •v i,2 +. . .+β p •v i,p , where ∀j ∈ [p] : v i,j ∈ {-1, 0, 1}.
It was noted in [START_REF] Ling | Improved Zero-Knowledge Proofs of Knowledge for the ISIS Problem, and Applications[END_REF] that for β 1 , β 2 , . . . , β p given in Table 3.1, this step can easily be done. 2. For each j ∈ [p], let w j := (v 1,j , v 2,j , . . . , v m,j ) ∈ {-1, 0, 1} m . Output w 1 , . . . , w p . Elementary Extension. On input a vector w ∈ {-1, 0, 1} m , the procedure EleExt extends w to a vector w ∈ B 3m . This procedure works as follows:

1. Let λ (-1) , λ (0) and λ (1) be the numbers of coordinates of w that equal to -1, 0, and 1 respectively. 2. Pick a random vector w ∈ {-1, 0, 1} 2m that has exactly (mλ (-1) ) coordinates -1, (mλ (0) ) coordinates 0, and (mλ (1) ) coordinates 1. Output w = w w ∈ B 3m .

Witness Decomposition and Extensions. On input x ∈ Secret β (d) for some d = d [START_REF] Ajtai | Generating Hard Instances of Lattice Problems (Extended Abstract)[END_REF] . . . d[ℓ] ∈ {0, 1} ℓ , the procedure WitnessDE outputs p vectors z 1 , . . . z p ∈ SecretExt(d). This procedure works as follows:

1. Write x as the concatenation of 2ℓ + 1 blocks of size m, namely:

x = x 0 x 0 1 x 1 1 . . . x 0 ℓ x 1 ℓ . 2. Run EleDec on each of the ℓ + 1 blocks x 0 , x d[1] 1 , . . . , x d[ℓ] ℓ
to obtained (ℓ + 1)p decomposed vectors. Then run EleExt on each of the decomposed vectors to obtain (ℓ + 1)p vectors in B 3m , denoted respectively by {w 0,j } p j=1 , {w

d[1] 1,j } p j=1 , . . . , {w d[ℓ]
ℓ,j } p j=1 . 3. Create ℓp zero-vectors of dimension 3m, and denote them by {w

1-d[1] 1,j } p j=1 , . . . , {w 1-d[ℓ] ℓ,j
} p j=1 . 4. For each j ∈ [p], let z j = w 0,j w 0 1,j w 1 1,j . . . w 0 ℓ,j w 1 ℓ,j . Output z 1 , . . . , z p ∈ SecretExt(d).

Matrix Extension. On input matrix

A ∈ Z n×(2ℓ+1)m q
, the following procedure MatrixExt outputs matrix A * ∈ Z n×(2ℓ+1)3m q 1. Write A as the concatenation of 2ℓ + 1 component-matrices in Z n×m q . 2. Append 2m zero-columns to each of the component-matrices, then output the extended matrix A * .

: A • x = u (mod q) x ∈ Secret β (d) d = (1 . . . 0) ∈ {0, 1} ℓ A0 A 0 1 A 1 1 A 0 ℓ A 1 ℓ • x0 x 0 1 = 0 m x 1 1 x 0 ℓ x 1 ℓ = 0 m u = n m A0 A * = 0 A 0 1 0 A 1 1 0 A 0 ℓ 0 A 1 ℓ 0 n 2m z T 1 = w0,1 w 0 1,1 = 0 3m w 1 1,1 w 0 ℓ,1 w 1 ℓ,1 = 0 3m
In particular, let {z j } p j=1 ← WitnessDE(x) and A * ← MatrixExt(A) then we have A•x = A * •( p j=1 β j • z j ). We illustrate our Decomposition-Extension technique in Figure 1.

Therefore, in the protocol in Section 4, in order to prove that x ∈ Secret β (d) for some d ∈ {0, 1} ℓ , and A • x = u mod q, one can instead prove that:

A * • ( p j=1 β j • z j ) = u mod q and ∀j ∈ [p], π ∈ S, e ∈ {0, 1} ℓ : T e • π(z j ) ∈ SecretExt(d ⊕ e),
where the latter relation follows from the fact that z j ∈ SecretExt(d) for all j ∈ [p], and from (1).

The Underlying Interactive Protocol

We recall that the main building block of our VLR group signature scheme is an interactive protocol that allows the prover to convince the verifier that he is a certified group member (i.e., he has a valid secret key), and that he has not been revoked (i.e., his revocation token is not in the verifier's list RL). In Section 5, the protocol is repeated t = ω(log n) times to make the soundness error negligibly small, and then is transform to a signature scheme via Fiat-Shamir heuristic. The interactive protocol is summarized as follows:

• The public parameters are A = A 0 A 0 1 A 1 1 . . . A 0 ℓ A 1 ℓ ∈ Z n×(2ℓ+1)m q and u ∈ Z n q . • The prover's witness is a x = x 0 x 0 1 x 1 1 . . . x 0 ℓ x 1 ℓ ∈ Secret β (d) for some d ∈ {0, 1} ℓ . The verifier's additional input is a set RL = {u i } i ⊂ Z n
q , whose cardinality is at most N -1. • The prover's goal is to convince the verifier in that:

1. A • x = u mod q and x ∈ Secret β (d), while keeping d secret.

2. A 0 • x 0 mod q ∈ RL.

Description of the Protocol

Let COM be the KTX commitment scheme [START_REF] Kawachi | Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems[END_REF]. Let A * ← MatrixExt(A). Prior to the interaction, the prover applies the Decomposition-Extension technique on his witness: Let z 1 , . . . , z p ← WitnessDE(x).

The protocol follows Stern's approach for three-pass zero-knowledge identification schemes [START_REF] Stern | A New Paradigm for Public Key Identification[END_REF], for which we employ an additional commitment c 0 to enable the revocation mechanism. The details are as follows:

1. Commitment: The prover samples a string e . For each j ∈ [p], let r j,0 = Parse(r j , 1, m). Then it sends the commitment CMT = c 0 , c 1 , c 2 , c 3 ∈ (Z n q ) 4 to the verifier, where

               c 0 = COM e, {π j } p j=1 , A 0 • p j=1 β j • r j,0 mod q , c 1 = COM e, {π j } p j=1 , A * • p j=1 β j • r j mod q , c 2 = COM {T e • π j (r j )} p j=1 , c 3 = COM {T e • π j (z j + r j )} p j=1 .
(2)

2. Challenge: The verifier sends a challenge Ch $ ← -{1, 2, 3} to the prover. 3. Response: Depending on the challenge, the prover computes the response RSP differently:

• Case Ch = 1: ∀ j ∈ [p], let v j = T e • π j (z j ), w j = T e • π j (r j ), d 1 = d ⊕ e
, and set: RSP = d 1 , {v j } p j=1 , {w j } p j=1 .

(3)

• Case Ch = 2: ∀ j ∈ [p], let φ j = π j , s j = z j + r j , d 2 = e, and set: RSP = d 2 , {φ j } p j=1 , {s j } p j=1 . ( 4
) • Case Ch = 3: ∀ j ∈ [p], let ψ j = π j , h j = r j , d 3 = e, and set: RSP = d 3 , {ψ j } p j=1 , {h j } p j=1 . (5)
Verification: Receiving the response RSP, the verifier proceeds as follows:

• Case Ch = 1: Parse RSP as in [START_REF] Alwen | Generating Shorter Bases for Hard Random Lattices[END_REF]. Check that ∀j ∈ [p] : v j ∈ SecretExt(d 1 ), and that: c 2 = COM {w j } p j=1 and c 3 = COM {v j + w j } p j=1 . • Case Ch = 2: Parse RSP as in [START_REF] Ateniese | A Practical and Provably Secure Coalition-Resistant Group Signature Scheme[END_REF]. ∀j ∈ [p], let s j,0 = Parse(s j , 1, m). Check that:

∀u i ∈ RL : c 0 = COM d 2 , {φ j } p j=1 , A 0 • p j=1 β j • s j,0 -u i mod q c 1 = COM d 2 , {φ j } p j=1 , A * • p j=1 β j • s j -u mod q ; c 3 = COM {T d 2 • φ j (s j )} p j=1 .
• Case Ch = 3: Parse RSP as in [START_REF] Bellare | Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions[END_REF]. ∀j ∈ [p], let h j,0 = Parse(h j , 1, m). Check that:

c 0 = COM(d 3 , {ψ j } p j=1 , A 0 • p j=1 β j • h j,0 ) mod q c 1 = COM d 3 , {ψ j } p j=1 , A * • ( p j=1 β j • h j ) mod q ; c 2 = COM {T d 3 • ψ j (h j )} p j=1 .
The verifier outputs Valid if and only if all the conditions hold. Otherwise, he outputs Invalid.

Witness Extraction

The following lemma says that in our protocol, one can extract a satisfying witness under specific conditions. Lemma 2. Assume that for a given commitment CMT, there exist 3 valid responses RSP (1) , RSP (2) , and RSP (3) corresponding to all 3 possible values of the challenge Ch. If COM is a computationally binding commitment scheme, then one can efficiently extract a vector y = y 0 y 0 1 y 1 1 . . . y 0 ℓ y 1 ℓ ∈ Z (2ℓ+1)m satisfying A • y = u mod q, y ∈ Secret β (d) for some d ∈ {0, 1} ℓ , and A 0 • y 0 mod q ∈ RL.

The proof of this lemma is given in Appendix A.

The VLR Group Signature Scheme

In this section we first describe our lattice-based VLR group signature scheme, and then we prove that the scheme satisfies the requirements defined in Section 2.1: correctness, selfless-anonymity and traceability.

Description of the Scheme

Keys Generation. The randomized algorithm KeyGen(n, N ), works as follows:

1. Run GenTrap(n, m, q) to get A 0 ∈ Z n×m q and trapdoor R.

Sample u

$ ← -Z n q , and A b i $ ← -Z n×m q
for all b ∈ {0, 1} and i ∈ [ℓ]. Then define the matrix

A = A 0 A 0 1 A 1 1 . . . A 0 ℓ A 1 ℓ ∈ Z n×(2ℓ+1)m q .
3. For group user with index d ∈ {0, 1, . . . , N -1}, let d [START_REF] Ajtai | Generating Hard Instances of Lattice Problems (Extended Abstract)[END_REF] . . . d[ℓ] ∈ {0, 1} ℓ denote the binary representation of d, and do the following:

(a) Sample vectors x

d[1] 1 , . . . , x d[ℓ] ℓ ←֓ D Z m ,σ . Compute z = ℓ i=1 A d[i] i • x d[i] i
mod q, and sample Remark 2. We have some observations on the behaviour of the above key generation algorithm:

x 0 ∈ Z m with x 0 ←֓ SampleD R, A 0 , u -z, σ . Let x 1-d[1] 1 , . . . , x 1-d[ℓ] ℓ be zero-vectors 0 m , and define x (d) = x 0 x 0 1 x 1 1 . . . x 0 ℓ x 1 ℓ ∈ Z (2ℓ+1)m . If x (d) ∞ ≤ β
• By Theorem 2, the distribution of matrix A 0 generated by GenTrap(n, m, q) is statistically close to uniform over Z n×m q . Thus, the distribution of gpk output by KeyGen(n, N ) is statistically close to uniform over Z n×(2ℓ+1)m q × Z n q . We note that the pair (A, u) resembles the Bonsai tree structure [START_REF] Cash | Bonsai Trees, or How to Delegate a Lattice Basis[END_REF], where A 0 is the "root" of the tree.

• In Step (3a), each coordinate of vector x (d) is either 0 or distributed according to the distribution D Z,σ (see Theorem 2 regarding the output distribution of algorithm SampleD). By setting β = ⌈σ • log m⌉, we ensure that x (d) ∞ ≤ β with overwhelming probability (see Lemma 1). Thus, the event that Step (3a) needs to be repeated only occurs with negligible probability. • The secret key x (d) of group user with index d satisfies A • x (d) = u mod q, and x (d) ∈ Secret β (d).

• By Lemma 1, the distribution of each user revocation token grt[d] is statistically close to uniform over Z n q . The trivial requirement is that the revocation tokens of two different group users must be different. In the very rare event of conflict (i.e., there exist

d 1 , d 2 ∈ {0, . . . , N -1} such that d 2 > d 1 and grt[d 1 ] = grt[d 2 ]
), the algorithm simply re-samples the key and token for user with index d 2 .

Signing Algorithm. Let H : {0, 1} * → {1, 2, 3} t be a hash function, modelled as a random oracle. Given gpk = (A, u), to sign a message M ∈ {0, 1} * using the secret key gsk[d] = x ∈ Secret β (d), the user runs the randomized algorithm Sign(gpk, gsk[d], M ), which performs the following steps:

1. Generate a proof that the user is a certified group members and that he has not been revoked. This is done by repeating t = ω(log n) times the basic protocol from Section 4 with public parameter (A, u) and prover's witness x, and then making it non-interactive with the Fiat-Shamir heuristic as a triple

{CMT (k) } t k=1 , CH, {RSP (k) } t k=1 , where CH = {Ch (k) } t k=1 = H M, {CMT (k) } t k=1 ∈ {1, 2, 3} t . 2.
Output the group signature:

Σ = M, {CMT (k) } t k=1 , {Ch (k) } t k=1 , {RSP (k) } t k=1 . (6)
Verification Algorithm. On input gpk = (A, u), a set of tokens RL = {u i } i ⊂ Z n q whose cardinality is at most N -1, a message M ∈ {0, 1} * , and a purported group signature Σ on M , the verifier runs the deterministic algorithm Verify(gpk, RL, Σ, M ), which performs the following steps:

1. Parse the signature Σ as in (6). 2. Check if Ch (1) , . . . , Ch (t) = H M, CMT (1) , . . . , CMT (t) . 3. For k = 1 to t, run the verification of the protocol from Section 4 to check the validity of RSP (k) with respect to CMT (k) and Ch (k) . If any of the verification conditions does not hold, then output Invalid and terminate. 4. Output Valid.

Analysis of the Scheme

Efficiency and Correctness. The parameters in Table 3.1 are set so that all of the algorithms in the VLR group signature in Section 5.1 can be implemented in polynomial time. Asymptotically, the group public key has bit-size ℓ • O(n 2 ) = log N • O(n 2 ), while the group signatures have bit-size ℓ • O(n) = log N • O(n). The revocation check, i.e., the check against c (k) 0 in the case Ch (k) = 2, runs in linear time in the number of revoked users, as it seems unavoidable for secure VLR group signature schemes.

Theorem 3. Our VLR group signature scheme is correct with overwhelming probability.

The proof of this Theorem is provided in Appendix B.1.

Selfless-Anonymity. We now prove that our VLR group signature scheme is selfless-anonymous. Theorem 4. If COM is a statistically hiding string commitment scheme, then the VLR group signature scheme in Section 5.1 is selfless-anonymous in the random oracle model.

Proof. We define two hybrid games G 0 and G 1 . Game G 0 is the original selfless-anonymity game (see Section 2). In game G 1 , we make the distribution of the challenger's output independent of the bit b ∈ {0, 1}. We then prove that these two games are statistically indistinguishable. Since the adversary's advantage in game G 1 is 0, this implies the selfless-anonymity of our scheme. Ch (k) is uniformly distributed in {1, 2, 3}, which satisfies the requirement on the output of the random oracle H. Then prepare CMT (k) , and the response RSP (k) to (CMT (k) , Ch (k) ) as follows: (a) Case Ch (k) = 1:

i. Use linear algebra to compute z ∈ Z (2ℓ+1)3m q such that A * • z = u mod q. Let g 0 = Parse(z, 1, m). If A 0 • g 0 ∈ RL then repeat this step. Otherwise, compute z

(k) 1 , . . . , z (k) p ∈ Z (2ℓ+1)3m q such that p j=1 β j • z (k) j = z mod q. ii. Sample e (k) $
← -{0, 1} ℓ , and for all j ∈ [p], sample π

(k) j $ ← -S and r (k) j $ ← -Z (2ℓ+1)•3m q
, and let

r (k) j,0 = Parse(r (k) j , 1, m). iii. Compute CMT (k) = c (k) 0 , c (k) 1 , c (k) 2 , c (k) 3 ∈ (Z n q ) 4 as in (2), from Section 4. iv. If Ch (k) = 2, then set RSP (k) = e (k) , {π (k) j } p j=1 , {z (k) j +r (k) j } p j=1 . (7)
If

Ch (k) = 3, then set RSP (k) = e (k) , {π (k) j } p j=1 , {r (k) j } p j=1 . ( 8
) (b) Case Ch (k) = 2: i. Sample d (k) , e (k) $ ← -{0, 1} ℓ . For all j ∈ [p], sample π (k) j $ ← -S, and r (k) j $ ← -Z (2ℓ+1)•3m q , and z (k) j $ ← -SecretExt(d (k) ). Let r (k) j,0 = Parse(r (k) j , 1, m). ii. Compute CMT (k) = c (k) 0 , c (k) 1 , c (k) 2 , c (k) 3 ∈ (Z n q ) 4 as in (2), from Section 4. iii. If Ch (k) = 1, then set RSP (k) = d (k) ⊕e (k) , T e (k) •π (k) j (z (k) j ) p j=1 , T e (k) •π (k) j (r (k) j ) p j=1 . (9)
If

Ch (k) = 3, then set RSP (k) = e (k) , {π (k) j } p j=1 , {r (k) j } p j=1 . ( 10
) (c) Case Ch (k) = 3: i. Sample d (k) , e (k) $ ← -{0, 1} ℓ . For all j ∈ [p] sample π (k) j $ ← -S and r (k) j $ ← -Z (2ℓ+1)•3m q
, and let

r (k) j,0 = Parse(r (k) j , 1, m). ii. For all j ∈ [p], sample z (k) j $ ← -SecretExt(d (k) ), and let z (k) j,0 = Parse(z (k) j , 1, m). If A 0 • ( p j=1 β j • z (k) j,0 ) ∈ RL, then repeat this step. iii. Compute CMT (k) = c (k) 0 , c (k) 1 , c (k) 2 , c (k) 3 ∈ (Z n q ) 4 , where c (k) 0 , c (k) 2
and c

(k) 3

are as in (2), from Section 4, while c

(k)

1 is computed as follows:

c (k) 1 = COM e (k) , {π (k) j } p j=1 , A * • p j=1 β j • (z (k) j + r (k) j ) -u . iv. If Ch (k) = 1, then set RSP (k) = d (k) ⊕e (k) , T e (k) •π (k) j (z (k) j ) p j=1 , T e (k) •π (k) j (r (k) j ) p j=1 . (11)
If

Ch (k) = 2, then set RSP (k) = e (k) , {π (k)
j } p j=1 , {z (k) j +r (k)
j } p j=1 . (12)
2. Program the random oracle: H M * , CMT (1) , . . . , CMT (t) = Ch (1) , . . . , Ch (t) .

3. Output the simulated signature Σ * = M * , CMT (k) t k=1 , Ch (k) t k=1 , RSP (k) t k=1 . We have the following observations on the above construction:

• For every k ∈ [t], the distribution of CMT (k) is statistically close to uniform over (Z n q ) 4 . This follows from the statistically hiding property of COM.

• The distribution of Ch (1) , . . . , Ch (t) is uniform over {1, 2, 3} t .

• For every k ∈ [t]:

1. If Ch (k) = 1, the view of A on CMT (k) and RSP (k) is either (3(b)iB) and (??), or (3(b)iC) and (10). 2. If Ch (k) = 2, the view of A on CMT (k) and RSP (k)

. We remark that, in every case, RSP (k) is intentionally designed to be a valid "response" to CMT (k) and Ch (k) , and to be statistically close to that produced by Step (3(b)iD) in Game G 0 .

These observations imply that Σ * is a valid group signature, i.e., Verify (A, u), RL, Σ * , M * = Valid, and that Σ * is statistically indistinguishable from the legitimate signature Σ produced by Game G 0 (for a more detailed analysis, see Lemma 4 in Appendix B.2). It then follows that Game G 0 and Game G 1 are statistically indistinguishable. Moreover, Σ * is independent of the bit b ∈ {0, 1}, thus, the adversary's advantage in Game G 1 is 0. As a result, the adversary's advantage in Game G 0 is negligible. In other words, our VLR group signature is selfless-anonymous.

⊓ ⊔

Traceability. We now prove that, in the random oracle model, our VLR group signature scheme is traceable if the SIS ∞ n,(ℓ+1)•m,q,2β problem is hard. Theorem 5. If there is a traceability adversary A with success probability ǫ and running time T , then there is an algorithm F that solves the SIS ∞ n,(ℓ+1)•m,q,2β problem with success probability ǫ ′ > 1 -(7/9) t • 1 2N , and running time T ′ = 32 • T • q H /(ǫ -3 -t ) + poly(n, N ), where q H is the number of queries to the random oracle H : {0, 1} * → {1, 2, 3} t .

The results of Theorem 1 and Theorem 4 imply that our scheme is traceable in the random oracle model, based on the worst-case hardness of the SIVP γ problem (in the ℓ 2 norm), with γ

= 2β • O(n) = O(n 1.5 ).
Proof. First, suppose that adversary A can break the computational binding property of the commitment scheme COM with non-negligible probability. As mentioned earlier (see Section 2.2), we can use A to solve the SIS ∞ n,(ℓ+1)•m,q,2β problem. Therefore, without loss of generality, we assume that COM is computationally binding.

We construct a PPT algorithm F solving the SIS ∞ n,(ℓ+1)•m,q,2β problem with non-negligible probability, which works as follows:

Challenge: Algorithm F is given a uniformly random matrix C = C 0 C 1 . . . C ℓ ∈ Z n×(ℓ+1)•m q . It wins the challenge if it can produce a non-zero vector x ∈ Z (ℓ+1)•m such that x ∞ ≤ 2β and C • x = 0 mod q. Setup: F performs the following steps: 1. Sample vector z = z 0 z 1 . . . z ℓ ∈ Z (ℓ+1)•m , where each coordinate of z is sampled from D Z,σ .

If z ∞ > β, then repeat the sampling. Otherwise, compute u = C • z mod q. 2. Run TrapGen(n, m, q) algorithm ℓ times, and let the outputs be (F 1 , R 1 ), (F 2 , R 2 ), . . . , (F ℓ , R ℓ ) .

t (d) = u -A 0 • x 0 + i∈[ℓ],i =b A d[i] i • x d[i] i mod q.
• Sample x Algorithm F finally outputs the vector x, which is a valid solution to the given SIS ∞ n,(ℓ+1)•m,q,2β instance. We observe that the probability that F does not abort is at least 1/N , and conditioned on not aborting, it can solve the SIS ∞ n,(ℓ+1)•m,q,2β problem with probability larger than 1/2 • 1 -(7/9) t in time T • 32 • q H /(ǫ -3 -t ) + poly(n, N ).

This concludes the proof. ⊓ ⊔

•Remark 1 .

 1 KeyGen(n, N ): On input a security parameter n and the number of group users N , this PPT algorithm outputs a group public key gpk, a vector of user secret keys gsk = (gsk[0], gsk[START_REF] Ajtai | Generating Hard Instances of Lattice Problems (Extended Abstract)[END_REF], . . . , gsk[N -1]), and a vector of user revocation tokens grt = (grt[0], grt[START_REF] Ajtai | Generating Hard Instances of Lattice Problems (Extended Abstract)[END_REF], . . . , grt[N -1]). • Sign(gpk, gsk[d], M ): On input gpk, a user secret key gsk[d], and a message M ∈ {0, 1} * , this PPT algorithm outputs a signature Σ. • Verify(gpk, RL, Σ, M ): On input gpk, a set of revocation tokens RL ⊆ {grt[0], grt[1], . . . , grt[N -1]}, a signature Σ, and the message M , this algorithm outputs either Valid or Invalid. The output Valid indicates that Σ is a valid signature on message M under gpk, and the signer has not been revoked. Any VLR group signature has an implicit tracing algorithm using grt as the tracing key. The tracing algorithm works as follows: on input a valid signature Σ on a message M , it reveals the signer of Σ by running Verify(gpk, RL = grt[d], Σ, M ), for d = 0, 1, . . ., and outputting the first index d * ∈ {0, 1, . . . , N -1} for which the verification algorithm returns Invalid. The tracing algorithm fails if and only if the given signature is properly verified for all d.

  (a) Setup. The challenger runs KeyGen to generate (gpk, gsk, grt), then gives gpk to the adversary A. (b) Queries. Adversary A can make the following queries: • Signing: Query for signature of any user d on any message M ∈ {0, 1} * . The challenger returns the signature Σ = Sign(gpk, gsk[d], M ). • Corruption: Query for the secret key of any user d. The challenger returns gsk[d]. • Revocation: Query for the revocation token of any user d. The challenger returns grt[d]. (c) Challenge. Adversary A outputs a message M * and two indices d 0 and d 1 , such that A never made a corruption or revocation query for user d 0 or user d 1 . The challenger chooses a bit b $ ← -{0, 1}, computes a signature of user d b on M * as Σ * = Sign(gpk, gsk[d b ], M * ), and returns Σ * to A. (d) Restricted Queries. After the challenge phase, A can still make queries as before, but with the following restrictions: it is not allowed to make any corruption or revocation query for user d 0 or user d 1 . (e) Output. Eventually, A outputs a bit b ′ . It wins the game if b ′ = b. We define the adversary's advantage in winning the game as Adv A = Pr[b ′ = b] -1/2 . We say that the VLR group signature is selfless-anonymous if Adv A is negligible. 3. Traceability: The adversary's goal in the traceability game is to forge a signature that cannot be traced to one of the users in his coalition using the implicit tracing algorithm above. The traceability game is defined as follows: (a) Setup: Run KeyGen(n, N ) to obtain (gpk, gsk, grt). Adversary A is given (gpk, grt). Set U = ∅. (b) Queries: Adversary A can make queries to the following oracles: • Signing: On input a message M , and an index d, the oracle returns Σ = Sign(gpk, gsk[d], M ). • Corruption: On input an index d, the oracle adds d to the set U , and returns gsk[d]. (c) Forgery: Eventually, A outputs a message M * , a set of revocation tokens RL * and a signature Σ * .

Number of 'decompositions' p ⌊log β⌋ + 1

 1 Sequence of integers β1 = ⌈β/2⌉; β2 = ⌈(β -β1)/2⌉ β1, β2, β3, . . . , βp β3 = ⌈(β -β1 -β2)/2⌉; . . . ; βp = 1 Number of protocol repetitions t ω(log n)

Fig. 1 .

 1 Fig. 1. An illustration of our Decomposition-Extension technique, where the first bit of d is 1 and its last bit is 0. We denote by an element of B3m. After performing Decomposition-Extension, one has that zj ∈ SecretExt(d) for all j ∈ [p], and A * • p j=1 βj • zj = A • x = u mod q.

$←-

  {0, 1} ℓ , p permutations π 1 , . . . , π p $ ← -S, and p vectors r 1 , . . . , r p $

  then go to step (??); else, repeat step (3a). (b) Let the user secret key be gsk[d] = x (d) , and the revocation token be grt[d] = A 0 • x 0 ∈ Z n q . 4. Finally, the algorithm outputs (gpk, gsk, grt), where gpk = (A, u); gsk = gsk[0], gsk[1], . . . , gsk[N -1] ; grt = grt[0], grt[1], . . . , grt[N -1] .

Game G 0 : 1 . 1 .

 11 Run KeyGen(n, N ) to obtain gpk = (A, u); gsk = gsk[0], gsk[START_REF] Ajtai | Generating Hard Instances of Lattice Problems (Extended Abstract)[END_REF], . . . , gsk[N -1] ; grt = grt[0], grt[START_REF] Ajtai | Generating Hard Instances of Lattice Problems (Extended Abstract)[END_REF], . . . , grt[N -1] .Set RL := ∅, Corrupted := ∅, and give gpk to the adversary A.2. IfA queries the signature on any message M by user of index d, return Σ = Sign gpk, gsk[d], M . If A queries the corruption of user of index d, set Corrupted := Corrupted ∪ {d}, and return gsk[d]. If A queries the revocation of user d, set RL := RL ∪ {grt[d]}, and return grt[d]. 3. A outputs a message M * and d 0 , d 1 such that d b ∈ Corrupted and grt[d b ] ∈ RL for each b ∈ {0, 1}. 4. Pick a bit b $ ← -{0, 1}, generate a valid signature Σ = Sign gpk, gsk[d b ], M * = M * , CMT (k) t k=1 , Ch (k) t k=1 , RSP (k) t k=1 , and return Σ to A. 5. A can still make queries as before, but it is not allowed to ask for gsk[d b ] or grt[d b ], for each b ∈ {0, 1}. 6. Finally A outputs a bit b ′ . Game G 1 : In this game, we make the following modification with respect to Game G 0 : In Step 3(b)iD, instead of generating a legitimate signature, we simulate the signature generation. Our simulation algorithm is such that: • Input: The group public key gpk = A, u obtained from Step 3(b)iA, the set of user revocation tokens RL obtained at the end of Step 3(b)iB, and the message M * obtained from Step 3(b)iC. • Output: A valid group signature Σ * for message M * under gpk and RL. Moreover, Σ * is independent of the bit b, and it is statistically indistinguishable from the legitimate signature Σ in game G 0 . Let A = A 0 |A 0 1 |A 1 1 | . . . |A 0 ℓ |A 1 ℓ and A * ← MatrixExt(A). The simulation algorithm does the following: For each k ∈ [t], pick a "fake" challenge Ch (k) $ ← -{1, 2, 3}, that is a "prediction" of what the real challenge will not be. Then pick a real challenge Ch (k) $ ← -{1, 2, 3} \ {Ch (k) }. It turns out that

  is either (3(b)iC) and (7), or (3(b)iC) and (11). 3. If Ch (k) = 3, the view of A on CMT (k) and RSP (k) is either (3(b)iC) and (8), or (3(b)iB) and

3 .

 3 Pick a target index d * = d * [1] . . . d * [ℓ] $ ← -{0, 1} ℓ , and define A= A 0 |A 0 1 |A 1 1 | . . . |A 0 ℓ |A 1 ℓ ∈ Z n×(2ℓ+1)•m q, where A 0 = C 0 , and for each i ∈ [ℓ]:A d * [i] i = C i and A 1-d * [i] i = F i .4. Define the secret key and revocation token for user d * as follows:•gsk[d * ] = (x 0 x 0 1 x 1 1 . . . x 0 ℓ x 1 ℓ ) ∈ Z (2ℓ+1)•m , where x 0 = z 0 , ∀i ∈ [ℓ]: x d * [i] i = z i and x 1-d * [i] i = 0 m , • grt[d * ] = A 0 • x 0 mod q ∈ Z n q . 5.Generate the secret key and the revocation token for each user d = d * , where d = d[1] . . . d[ℓ], as follows: • Let d[b] (1 ≤ b ≤ ℓ) be the first bit from the left where d[b] = d * [b]. Since d = d * , such b must exist. It follows that A d[b] b = A 1-d * [b] b = F b . • Sample ℓ vectors x 0 , x d[1] 1 , . . . , x d[b-1] b-1 , x d[b+1] b+1 , . . . , x d[ℓ] ℓ ←֓ D Z m ,σ , and let

←֓x 1 1 . . . x 0 ℓ x 1 ℓ∈ 6 .

 116 SampleD(R b , F b , t (d) , σ). • For each i ∈ [ℓ], let x 1-d[i] i = 0 m , then let x (d) = x 0 x 0 1 Z (2ℓ+1)•m . If the very rare event that x (d) ∞ > β happens, then repeat the sampling. Otherwise, set gsk[d] = x (d) and grt[d] = A 0 • x 0 mod q ∈ Z n q . Let gpk = (A, u), gsk = gsk[0], gsk[1], . . . , gsk[N -1] , grt = grt[0], grt[1], . . . , grt[N -1]. We note that, by construction, the distribution of (gpk, gsk, grt) is statistically close to that of the real scheme, and the choice of d * is hidden from the adversary. Algorithm F then gives (gpk, grt) to A. • If the tracing algorithm outputs e ∈ U \ RL * , namely the following two facts simultaneously hold true: Verify(gpk, grt[e], Σ * , M * ) = Invalid and Verify(gpk, RL * , Σ * , M * ) = Valid. This leads to grt[e] ∈ RL * , and hence e ∈ U . Furthermore, the correctness of the revocation check and the computational binding property of COM imply that A 0 • y 0 mod q = grt[e]. Now consider 2 cases: 1. If A has never requested the secret key gsk[d * ], then z is unknown to A. In this case, because z has large min-entropy given u (see Lemma 1), we have z = y * with overwhelming probability. 2. If the adversary A has requested the secret key gsk[d * ] in the Queries phase, then d * ∈ U . In particular, it must be true that d * = e (because e ∈ U ) , and thus grt[d * ] = grt[e]. In other words, we have A 0 • y 0 = A 0 • z 0 mod q. This leads to y * = z. Now let x = zy * ∈ Z (ℓ+1)m , then x = 0; C • x = 0 mod q; and x ∞ ≤ z ∞ + y ∞ ≤ β + β = 2β.

Acknowledgements. The authors would like to thank D. Stehlé, B. Libert, R. Bhattacharyya, J. Chen, and the anonymous reviewers for their helpful comments. The research is supported in part by the Singapore Ministry of Education under Research Grant MOE2013-T2-1-041. Adeline Langlois is supported in part by ERC Starting Grant ERC-2013-StG-335086-LATTAC.

Queries: Algorithm F answers the queries of A as follows:

• Corruption queries: The corruption set U is initially set to be empty. If A queries the secret key of any user d ∈ {0, . . . , N -1}, then F adds d to the corruption set U , and returns gsk [d].

• Signatures queries: If A queries signature of user d on arbitrary message M , then F returns Σ = Sign gpk, gsk [d], M . Queries to the random oracle H are handled by consistently returning uniformly random values in {1, 2, 3} t . For each κ ≤ q H , we let r κ denote the answer to the κ-th query.

Forgery: Eventually, A outputs a message M * , a set of tokens RL * and a non-trivial forged signature

such that Verify(gpk, RL * , Σ * , M * ) = valid, and the implicit tracing algorithm fails or traces to a user outside of the coalition U \ RL * . Now algorithm F exploits the forgery as follows.

First, one can argue that A must have queried H on input M * , {CMT i } t i=1 , as otherwise, the probability that (Ch 1 , . . . , Ch t ) = H M * , {CMT i } t i=1 is at most 3 -t . Therefore, with probability at least ǫ -3 -t , there exists certain κ * ≤ q H such that the κ * -th oracle queries involves the tuple M * , {CMT i } t i=1 . Next, F picks κ * as the target forking point and replays A many times with the same random tape and input as in the original run. In each rerun, for the first κ * -1 queries, A is given the same answers r 1 , . . . , r κ * -1 as in the initial run, but from the κ * -th query onwards, F replies with fresh random values r ′ κ * , . . . , r ′ q H $ ← -{1, 2, 3} t . The Improved Forking Lemma of Pointcheval and Vaudenay [START_REF] Vaudenay | On Provable Security for Digital Signature Algorithms[END_REF]Lemma 7] implies that, with probability larger than 1/2, algorithm F can obtain a 3-fork involving the tuple M * , {CMT i } t i=1 after less than 32 • q H /(ǫ -3 -t ) executions of A. Now, let the answers of F with respect to the 3-fork branches be r (1)

A simple calculation shows that: Pr ∃i ∈ {1, . . . , t} : {Ch

Conditioned on the existence of such index i, one parses the 3 forgeries corresponding to the fork branches to obtain RSP

i , RSP

. They turn out to be 3 valid responses with respect to 3 different challenges for the same commitment CMT i . Since COM is assumed to be computationallybinding, we can apply Lemma 2 to extract a vector y = y 0 y 0 1 y 1 1 . . . y 0 ℓ y 1 ℓ ∈ Z (2ℓ+1)m satisfying A • y = u mod q, A 0 • y 0 mod q ∈ RL * , and y ∈ Secret β (d) for some d ∈ {0, 1} ℓ . Now consider two cases:

• If d = d * , which happens with probability at most N -1 N , then algorithm F declares Fail and aborts.

We will show that, over the randomness of all algorithms, y * = z with overwhelming probability. Recall that Σ * is a valid signature such that the implicit tracing algorithm either fails or outputs an index e ∈ U \ RL * .

• If the tracing algorithm fails, then, in particular, one has Verify(gpk, grt[d * ], Σ * , M * ) = Valid. It follows from the correctness of the VLR group signature that

This implies that y 0 = z 0 , and thus y * = z.

A Witness Extraction

The following lemma says that in our protocol, one can extract a satisfying witness under specific conditions.

Lemma 3. Assuming that for a given commitment CMT, there exist 3 valid responses RSP (1) , RSP (2) , and RSP (3) corresponding to all 3 possible values of the challenge Ch. If COM is a computationally binding commitment scheme, then one can efficiently extract a vector y = y 0 y 0 1 y 1 1 . . .

, and let RSP (1) , RSP (2) , RSP (3) as in ( 3), (4), and (5), respectively. Since all 3 responses satisfy the verification conditions, the followings are true:

Since COM is computationally binding, one can deduce that d 2 = d 3 , φ j = ψ j for all j ∈ [p], and that:

, since the permutation φ j ∈ S preserves the arrangements of the blocks of y ′ j . Now let

, and let y ∈ Z (2ℓ+1)m be the vector obtained from y ′ by removing the last 2m coordinates in each 3m-block. We note that y

are zero-blocks 0 m . Furthermore, we have that:

Finally, by construction, we have: Suppose that grt[d] ∈ RL. We will show that, for each k ∈ [t], all the checks performed by the verification algorithm hold true, except for negligible probability. For simplicity, we will not consider the trivial checks for correct computations, e.g., the case

). Note that if x = gsk[d] is outputted by KeyGen(n, N ) then x ∈ Secret β (d), and thus, all the vectors z 1 , . . . , z p outputted by the procedure WitnessDE(x) belong to the set SecretExt(d). It then follows from the special properties of the permutation sets S and T that ∀j ∈

for all i, and thus, α = α i . Moreover, over the randomness of all algorithms, the distributions of COM d 2 , {φ j } p j=1 , α) and COM d 2 , {φ j } p j=1 , α i ) are statistically close to uniform over Z n q (this follows from the statistically hiding property of COM). Hence, we have

. This is true, because

where the last equation follows from the fact that A * • p j=1 β j • z j = A • x = u mod q. Therefore, the verification algorithm outputs Valid with overwhelming probability, over the randomness of all algorithms.

2. We then prove that: Verify(gpk, RL, Sign(gpk, gsk

Assume by contradiction that grt[d] = A 0 • x 0 mod q ∈ RL, and fix any k ∈ [t]. Note that in the signing algorithm, we construct c (k) 0 so that:

On the other hand, since the verification algorithm outputs Valid, the following requirement must satisfy (in the case Ch (k) = 2):

be the signature outputted by Game G 1 . First of all, we observe that:

• For every k ∈ [t], the distribution of CMT (k) is statistically close to uniform over (Z n q ) 4 . This follows from the statistical regularity property of f B and the statistically hiding property of COM.

• The distribution of Ch (1) , . . . , Ch (t) is uniform over {1, 2, 3} t . Therefore, the distributions of CMT (k) t k=1 and Ch (k) t k=1 are statistically close to those of the legitimate signature Σ. We now will show that for every k ∈ [t], RSP (k) is statistically close to that of the legitimate signature, and it is valid 'response' to CMT (k) and Ch (k) . Indeed, for each k ∈ [t], we have:

and RSP (k) is one of the following two cases:

and

For all j ∈ [p], since z

). Thus RSP (k) satisfies the verification conditions for the case Ch (k) = 1 (since the checks with respect to c obviously hold true). Note that by construction,

. Therefore, the distribution of RSP (k) is identical to that of the legitimate signature.

and RSP (k) is computed as in [START_REF] Camenisch | Fully Anonymous Attribute Tokens from Lattices[END_REF]. The analysis for this case is similar to the above one.

If Ch

and RSP (k) is one of the following two cases: (a) CMT (k) is computed as in [START_REF] Camenisch | Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials[END_REF], and RSP

Observe that: • By construction, we have A 0 • g 0 ∈ RL. The correctness of the VLR group signature then implies that: the revocation check with respect to c (k) 0 holds true with overwhelming probability.

• By construction, we have A * • p j=1 β j • z (k) j = u mod q. This implies that the check with respect to c (k) 1 holds true.

• The check with respect to c (k) 3 obviously hold true. Hence RSP (k) satisfies the verification conditions for the case Ch (k) = 2. Moreover, RSP (k) is uniform over {0, 1} ℓ × S p × Z (2ℓ+1)3m q p , and thus, is identically distributed with that of the legitimate signature. (b) CMT (k) is computed as in [START_REF] Cash | Bonsai Trees, or How to Delegate a Lattice Basis[END_REF], and RSP (k) = e (k) , {π are checks for correct computations, and thus, they hold true. Moreover, the distribution of RSP (k) is uniform over {0, 1} ℓ × S p × Z (2ℓ+1)3m q p , as in the legitimate signature.

Hence, we have shown that the simulated signature Σ * produced by game G 1 is a valid signature of M * under gpk and RL, and it is statistically close to the legitimate signature Σ produced by game G 0 . ⊓ ⊔


Chlo É Mimeau
email: chloe.mimeau@imag.fr

Iraj Mortazavi
email: iraj.mortazavi@math.u-bordeaux1.fr

Georges-Henri Cottet
email: georges-henri.cottet@imag.fr

VORTEX PENALIZATION METHOD FOR SOLID-POROUS-FLUID MEDIA WITH APPLICATION TO PASSIVE FLOW CONTROL

In this work, a coupling of vortex methods with penalization methods is proposed in order to accurately and easily handle solid-fluid-porous media. This immersed boundary approach indeed maintains the efficiency and the robustness of vortex methods and allows to model the three different media without prescribing any boundary condition. In this paper, we propose an application of this immersed boundary method to passive flow control around a semi-circular cylinder, realized adding a porous sheath on the obstacle surface in order to smooth the flow dynamics.

NOMENCLATURE

C D drag coefficient D computational domain F, S fluid domain and solid domain F D drag force Re Reynolds number Z enstrophy d non-dimensional diameter h reference mesh size k intrinsic permeability l re f height of the obstacle u re f reference velocity u = (u, v) velocity field u s body rigid motion ū mean velocity magnitude u ∞ free stream velocity Γ D computational domain boundaries ∆t time step Φ porosity λ penalization parameter µ dynamic viscosity ν kinematic viscosity ρ density of the fluid τ porous layer thickness χ S characteristic function ω vorticity field

INTRODUCTION

Vortex methods and penalization methods have been separately used to simulate high Reynolds number recirculating flows around obstacles. In this work, a hybrid particle-penalization technique is proposed in order to cover the advantages of both approaches. Here, the vortex method is used to approximate the penalized Vorticity Transport Equations (VTE). On one hand this technique maintains the efficiency and the robustness of vortex methods for turbulent Reynolds numbers focusing the computational task on the rotational zones and solving the flow equations in a fast Lagrangian way. On the other hand the penalization technique overcomes the difficulty of the vortex methods to satisfy accurately the no-slip boundary conditions. Here, the idea is [START_REF] Chorin | Numerical Study of Slighly Viscous Flow[END_REF] Copyright c 2013 by ASME to extend the fluid velocity inside the solid body and to solve the flow equations with a penalization term, depending on the intrinsic permeability, to enforce rigid motion inside the solid using a vorticity formulation. Moreover, this method eases numerical implementation since it enables to consider the governing equations in the whole computational domain allowing the use of structural grids and avoiding the overhead and the complexity typical of body fitted grids. Finally, and this is the main issue of this paper, the penalization approach allows to handle solidfluid-porous media where the differentiation between the three different media is easily performed defining the value of the penalization parameter without prescribing a boundary condition at the solid boundary or a condition at the porous-fluid interface.

Here, the solid-porous-fluid configuration is applied to cover a semi-circular cylinder geometry with a porous coating in order to perform passive flow control. After performing convergence studies, a parametric study is carried out to determine the most efficient permeabilities in terms of flow control at transitional (Re = 550) and highly transitional regime (Re = 3000).

VORTICITY FORMULATION AND VORTEX METHODS

In this work, flow simulations are based on particle methods. The fluid particles which are displaced by convection and diffusion are characterized by their position and their vorticity. The vorticity transport is expressed by the Helmholtz equation (or Vorticity Transport Equation), obtained taking the curl of the incompressible Navier-Stokes equations and given in 2D by

∂ ω ∂t + u.∇ω = 1 Re ∆ω in D, (1)
where ω, u and Re respectively denote the vorticity, the velocity and the Reynolds number. The Poisson equation

∇ 2 u = -∇ × ω, (2)
obtained from continuity equation, enables to recover velocity field once the vorticity field is known. The previous equations are approximated using a Vortex method [START_REF] Chorin | Numerical Study of Slighly Viscous Flow[END_REF][START_REF] Cottet | Vortex Methods -Theory and Practice[END_REF]. These methods are very robust and low-cost to simulate high Reynolds number recirculating flows (see for example [START_REF] Ghoniem | Vortex Simulation of Laminar Recirculating Flows[END_REF][START_REF] Sethian | Validation Study of Vortex Methods[END_REF]). In this kind of approach, the VTE equation (Eq. 1) is solved using a two-fractional step (or viscous splitting) method. It relies on approximating separately the diffusion and convection terms at each time step. The convective part is solved using a "Vortex-In-Cell (VIC)" method (see e.g. [START_REF] Cottet | Vortex Methods -Theory and Practice[END_REF]) with a semi-Lagrangian resolution. In this fractional step a convective velocity is associated to each finite vortex element through a high order interpolation procedure, and the displacement is achieved using a Runge-Kutta method. In order to avoid Lagrangian distortion, particles are then remeshed on the original grid using the same interpolation kernel as the one used previously to interpolate grid velocity values onto the particles. Finally, for computational efficiency and accuracy, diffusion and Poisson equation are solved on the grid using Fast Fourier Transforms (FFT).

VORTEX PENALIZATION METHOD IN VORTICITY FOR-MULATION

Before all, we show how the penalization method can be used successfully to model the flow of an incompressible fluid around an obstacle [START_REF] Angot | A Penalization Method to Take Into Account Obstacles in Incompressible Viscous Flows[END_REF]. In the penalization technique the system is considered as a single flow, subject to the Navier-Stokes equation with a penalization term that enforces continuity at the solidfluid interface and rigid motion inside the solid. In this work, the penalization term is expressed using vorticity formulation. The main interest of the penalized vorticity formulation is that it replaces the usual vorticity creation algorithm in order to satisfy the no-slip boundary condition for vortex methods. This new technique avoids the convergence difficulties due to the particle creation on the solid boundaries (see [START_REF] Coquerelle | A Vortex Level Set Method for the Two-Way Coupling of an Incompressible Fluid with Collinding Rigid Bodies[END_REF] and [START_REF] Cottet | A Level-Set Formu-7 Copyright c 2013 by ASME lation of Immersed Boundary Methods for Fluid-Structure Interaction Problems[END_REF]). We solve simultaneously the Brinkman equations in the solid and the Navier-Stokes equations in the fluid, considering whole the domain as a porous medium with zero (solid) or infinite permeabilities (fluid). Thus, defining the Reynolds number as Re = u re f l re f /ν, the nondimensional penalized vorticity equation (or Brinkman-Navier-Stokes equation) reads

∂ ω ∂t + (u.∇)ω = 1 Re ∆ω + ∇ × [λ χ S (u s -u)], (3)
where χ S denotes the characteristic function that yields 0 in the fluid and 1 in the solid, u s indicates the rigid body velocity which is zero in all this work since the body is fixed and λ = µΦ l re f /ρk u re f is the non-dimensional penalization parameter, in inverse proportion to the permeability of the medium (with k the intrinsic permeability, µ the viscosity, Φ the porosity of the porous material, l re f the height of the obstacle, ρ the density and u re f the reference velocity). The main advantage of this method is that it needs neither the mesh to fit the boundaries nor to specify no-slip boundary conditions. In addition it allows to compute the pressure as a continuous field on the whole domain including the solids. The zone variation is realized changing the penalization coefficient that defines the permeability of each region. Numerically, the fluid is considered as a porous medium with a very high permeability (λ = 0) and the bodies are considered as porous media with a very small permeability (λ = 10 8 ).

To discretize the penalized vorticity equation (Eq. 3) in a vortex method, the equation is split in substeps. At each time 2

Copyright c 2013 by ASME step, one successively solves the following equations

∂ ω ∂t = ∇× (λ χ S (u s -u)) (4)
∂ ω ∂t

+ (u • ∇) ω = 0 (5) ∂ ω ∂t = 1 Re ∆ω (6)
To solve Eq. 4 we use an implicit scheme ( [START_REF] Coquerelle | A Vortex Level Set Method for the Two-Way Coupling of an Incompressible Fluid with Collinding Rigid Bodies[END_REF]) and we set

ω n+1 = ∇× u n + λ ∆tχ S u s n 1 + λ ∆tχ S . ( 7
)
where ∆t is the time step. The right hand side above is evaluated by second order centered finite differences. At this stage, grid vorticity above a certain cut-off is used to create particle at grid point locations and Eq. 5 is solved by a classical vortex-in-cell method [START_REF] Cottet | Vortex Methods -Theory and Practice[END_REF]. Particles are pushed with a RK4 time-stepping and are then remeshed on the original grid using the third order interpolation kernel M ′ 4 [START_REF] Monaghan | Extrapolating b-Splines for Interpolation[END_REF]. Then, diffusion (Eq. 6) and Poisson equation (Eq. 2) are solved on the grid using FFT-based evaluations as described in [START_REF] Chatelain | A Fourier-Based Elliptic Solver For Vortical Flows With Periodic and Unbounded Directions[END_REF]. Grid values for vorticity and velocity are now available for time t n+1 and a new cycle of iterations can start. Moreover, the no-slip boundary conditions are naturally satisfied penalizing the vorticity transport equations.

This hybrid vortex penalization method has already been successfully used to simulate transitional and turbulent flows past bluff bodies [START_REF] Cottet | A Vortex Immersed Boundary Method for Bluff Body Flows[END_REF][START_REF] Cottet | A Vortex Penalization Method for Flows with Moving Immersed Obstacles[END_REF].

VORTEX PENALIZATION METHOD FOR SOLID-POROUS-FLUID MEDIA

This section is devoted to the study of flows in solid-porousfluid media and aims to highlight the efficiency of the vortex penalization method to solve such problems. For three different solid, porous and fluid media configurations, it is of great importance to clearly understand the flow behavior at the fluid-porous interface in order to model the physics correctly. As described in [START_REF] Bruneau | Numerical Modelling and Passive Flow Control Using Porous Media[END_REF], we can consider five different flow regions from the solid to the free flow in the fluid. The first one is the boundary layer inside the porous medium, close to the solid wall. This one is very thin compared to the second region which is characterized by the homogeneous porous flow with Darcy velocity (numbers 1 and 2 in Fig. 1). In the vicinity of the porous-fluid interface, two transient layers can be recognized (numbers 3 and 4 in Fig. 1). The first one corresponds to the increase of the porous layer velocity reaching u i value at the interface and the second one to the fluid boundary layer standing from the interface to the free flow. The fluid boundary layer growth is then determined by u 0u i where u 0 denotes the velocity of the main fluid flow (number 5 in Fig. 1). The aim is thus to find out a way to solve the flow both in the porous medium, the fluid region and at the interface between the two media. Several approaches have already been proposed to handle this problem like avoiding to solve the porous flow enforcing appropriate porous-fluid boundary conditions [START_REF] Beavers | Boundary Conditons at a Naturally Permeable Wall[END_REF] or solving the governing equations of each region coupling Darcy equations and Navier-Stokes equations with a right treatment at the interface [START_REF] Breugem | The Laminar Boundary Layer Over a Permeable Wall[END_REF][START_REF] Hanspal | Numerical Analysis of Coupled Stokes/Darcy Flows in Industrial Filtrations[END_REF]. Nevertheless, these two approaches are not satisfactory since the first one neglects the porous medium physics and does not permit to have overall view of the problem and the second one is particularly difficult to handle especially because of the interface problem. The method presented here, based on the vortex-penalization technique, thus appears as a very good alternative since it involves a unique equation (Eq. 3) for the whole domain and ensures an accurate modeling of each of the different regions thanks to the dimensionless penalization factor λ . As mentioned in the previous section, λ is expressed as λ = µΦ l re f /ρk u re f where l re f , ρ, u re f = 1 in this study and the porosity Φ is close to 1 as imposed by Brinkman equations [START_REF] Nield | Convection in Porous Media[END_REF]. Therefore λ essentially depends, in the inverse proportion, on the intrinsic permeability k of the medium. Varying the λ value thus directly defines the different media according to the following equation obtained using implicit Euler scheme for the penalization velocity discretization

u n+1 = u n 1 + λ ∆tχ S . (8)
3

Copyright c 2013 by ASME Indeed, in the fluid, the intrinsic permeability coefficient k goes to infinity, thus the fluid can be considered numerically as a porous media with a very high permeability. We set λ = 0 in this region. As a consequence, according to Eq. 8, the velocity in the fluid is not penalized ( u n+1 = u n ) and since λ = 0, the penalization term vanishes in Eq. 3, and we naturally recover the Vorticity Transport Equation (Eq. 1). On the contrary, the solid has a permeability coefficient k which goes to zero, it can be consequently modeled setting the penalization parameter λ to a very high value. In this study λ equals 10 8 in the solid, which vanishes the flow velocity in this region according to Eq. 8 ( u n+1 → 0) . It was proved in [START_REF] Angot | A Penalization Method to Take Into Account Obstacles in Incompressible Viscous Flows[END_REF] that solving Eq. 3 with such a value of λ was equivalent to solve Darcy's law in the solid. Furthermore, setting the λ parameter to an intermediate value, reasonably chosen between these two extreme values (λ = 0 and λ = 10 8 ), would model a porous medium in which the flow has a Darcy velocity u D (Fig. 1). As a conclusion, the variation of λ corresponds to the variation of k that specifies the intrinsic porous material permeability. The accuracy and efficiency of the penalization method come from its capability to take into account these variations of λ and to capture the induced steep velocity variations at the different interfaces with a minimum number of discretization points.

APPLICATION TO PASSIVE FLOW CONTROL

Modeling the physics of three different regions enables one to deal with engineering problems involving porous media. In the following, this approach is validated for a simple but significant passive flow control problem.

Here, the solid-porous-fluid configuration is applied to cover a semi-circular cylinder geometry with a porous coating. The latter is settled on the obstacle external surface in order to modify the vorticity generation of the boundary layer and the vortex shedding. In fact, the presence of a porous medium at the solid-fluid interface imposes a kind of mixed boundary condition intermediate between the no-slip and the slip one on the solid boundary [START_REF] Carbou | Brinkmann Model and Double Penalization Method for the Flow Around a Porous Thin Layer[END_REF]. As a result, the shear forces are decreased and the flow dynamics is smoothed [START_REF] Bruneau | Numerical Modelling and Passive Flow Control Using Porous Media[END_REF][START_REF] Bruneau | Passive Control of the Flow Around a Square Cylinder Using Porous Media[END_REF][START_REF] Bruneau | Control of Vortex Shedding Around a Pipe Section Using a Porous Sheat[END_REF][START_REF] Bruneau | Passive Control Around a Two-Dimensional Square Back Ahmed Body Using Porous Media[END_REF]. This technique, which allows to keep the obstacle geometry unchanged, should reduce drag forces and vortex induced vibrations improving the aerodynamic properties of the obstacle. The semi-circular cylinder can be considered as a simplified section of an outside rear-view mirror of a car or a motor cycle. The mirrors, due to their spanwise position, indeed generate a non-negligible wake which interferes with the flow past vehicle sides. This accounts for a good motivation to perform flow control past such obstacles. As it was shown in [START_REF] Rouméas | Analysis and Control of the Near-Wake Flow Over a Square-Back Geometry[END_REF][START_REF] Bruneau | Coupling Active and Passive Techniques to Control the Flow Past the Square Back Ahmed Body[END_REF], a flow past a square back obstacle is not dominated by longitudinal and hairpin three-dimensional vortical structures, therefore a preliminary two-dimensional study can be useful to supply information on general trends for a control.

The subsequent flow control simulations are performed at transitional (Re = 550) and highly transitional regime (Re = 3000). As at these two regimes the flow is not turbulent, Direct Numerical Simulations (DNS) are performed to numerically solve Eq. 3. The semi-circular cylinder has a total dimensionless diameter of d = 1 including a porous layer of thickness τ and whose back wall is centered at (x, y) = (0, 0) in the computational domain D = [-4, 8] × [-5, 5] (Fig. 2). The whole computational domain is meshed by an equispaced Cartesian orthogonal grid. As we use FFT-based evaluations to solve diffusion and Poisson equation, periodic boundary conditions are considered on the box walls Γ D and a correction of velocity is performed at each time step in order to satisfy the free stream velocity u ∞ = (u re f , 0) = (1, 0) imposed at the inlet.

Grid convergence

First of all we perform a grid convergence study of the vortex-penalization method for flow past a solid semi-circular cylinder at Re=550 and Re=3000. This grid convergence is performed on three grid levels from res=1200 × 1000 to res=4800 × 4000 in computational domain D. The results are reported in Table 1, giving the mean values of drag and enstrophy Z = D |ω| 2 dx. At Re=550, as the results on the two finest consecutive grids are very close (Table 1), the resolution therefore adopted for the further flow control simulations is 2400 × 2000 (h = 0.005). The finest grid resolution 4800 × 4000 (h = 0.0025) is retained for the Re=3000 case.

Variation of the penalization parameter λ for medium definition

In this section, a λ -convergence study is carried out in order to determine the values of the penalization parameter corresponding to permeabilities at Re = 550 and Re = 3000. This study is performed ranging the value of λ inside the whole semi- Copyright c 2013 by ASME

|u| λ =10 8 (y) -|u|(y) (11)
As Fig. 3 shows, the method has a first order convergence. This result is in agreement with our numerics since the penalization term (Eq. 4) is integrated using an implicit Euler scheme (Eq. 7 and 8). Moreover, we can see on this figure that for both regimes the semi-cylinder reaches the solid state from λ = 10 5 , where e(y) ≤ 10 -4 . Thus, a porous area can be defined with λ -values between 1 and 10 4 with very low permeability for the latter one. We will respectively refer to the solid case and to the fluid case when λ = 10 8 and λ = 0 inside the layer.

Numerical results

This section relies on the influence of the added porous layer permeability on the flow control behaviour and the efficiency of such a passive control. This parametric study is performed at Re = 550 and Re = 3000 considering four consecutive values of the porous permeability inside the layer, namely λ = 1 (high permeability), 10, 10 2 , 10 3 (low permeability) and comparing the results to the solid (λ = 10 8 ) and fluid (λ = 0) cases. The thickness of the coating is set to τ = 10%d = 0.1 in each case (Fig. 4). According to the grid convergence (Table 1), the numerical simulations carried out at Re = 550 and Re = 3000 are respectively performed on grid 2400 × 2000 (h = 0.005) and grid 4800 × 4000 (h = 0.0025) in computational domain D.

In order to analyze the effects of our control approach we compare global flow quantities like the drag force (F D ), computed according to the momentum equation [START_REF] Noca | A Comparison of Methods for Evaluating Time-Dependent Fluid Dynamic Forces on Bodies, Using Only Velocity Fields and Their Derivatives[END_REF] and the enstrophy (Z), expressed as the integral of the square of the vorticity, allowing to measure the dissipation effects in the flow as well as the delay of transition to turbulence. Note that in this study we consider drag force (F D ) instead of drag coefficient (C D ) since the computation of the latter involves the diameter d of the obstacle which is not clearly defined because of the porous coating.

As can be seen in Fig. 5, which represents dimensionless time history of global flow quantities at Re=550, setting λ = 1 inside the layer clearly appears as the best solution in terms of flow regularization. Indeed, the mean value of drag force (Fig. 5 (up)) reaches for λ = 1 an optimum value close to the one of the fluid case, showing a drag reduction of about 30% compared to uncontrolled case. For all the other values of porous λ , the drag reduction effects are nearly nonexistent. Results of enstrophy evolution (Fig. 5 (bottom)) show a progressive reduction of the dissipation effects and the delay to transition with the decrease of the λ -value. Furthermore, we note that the result obtained with λ = 1 is even better than the one of fluid case and represents an improvement of nearly 40% compared to uncontrolled case. These quantitative results are confirmed by the mean vorticity and velocity fields showing the smoothing of wake dynamics generated by the presence of the highly permeable layer. Indeed, with λ = 1 the transversal dimension of the wake is smaller, the back recirculation zone is sharply reduced (Fig. 6) and the vortices swirl with lower velocity (Fig. 7). At Re = 3000 the best solution for global flow regularization is also achieved setting the λ parameter to 1 inside the porous coating. This configuration leads to a drag and enstrophy reduction of respectively 21% and 44% compared to the uncontrolled case (Fig. 8) and shows a drastic decrease of the flow particles velocity (Fig. 10). In terms of control effects, the main difference one can notice here in comparison to the parameter study performed at transitional regime concerns the flow behaviour observed when λ = 10 inside the layer. Contrary to the other λvalues, the flow obtained with the latter is non-periodic (Fig. 8). This flow irregularity impacts the mean drag value, which is increased of about 10% compared to the uncontrolled case. Figure 10 also confirms the negative effects of the non-periodicity of the flow showing high particles velocity with a chaotic distribution of the vortices as well as an extension of the transversal dimension of the wake (Fig. 9).

CONCLUSION

In this work, a hybrid vortex-penalization method was proposed in order to easily handle solid-fluid-porous media. The differentiation between the three different media is indeed performed defining the value of the penalization parameter in the Brinkman-Navier-Stokes equations without prescribing a boundary condition at the solid boundary or a condition at the porousfluid interface. An application to passive flow control past a semi-circular cylinder was performed at transitional and highly transitional regimes, consisting in adding a porous sheath on the obstacle surface in order to smooth the flow dynamics. The para-

FIGURE 1 :

 1 FIGURE 1: VELOCITY PROFILE IN THE VICINITY OF A POROUS MEDIUM.

FIGURE 2 :

 2 FIGURE 2: COMPUTATIONAL DOMAIN.

4

 4

FIGURE 3 :

 3 FIGURE 3: λ -CONVERGENCE STUDY FOR FLOW PAST A SEMI-CIRCULAR CYLINDER : THE ERRORS e L ∞ , e L 1 AND e L 2 ARE PLOTTED AGAINST λ VALUES AT Re = 550 (LEFT) AND Re = 3000 (RIGHT)

FIGURE 4 :

 4 FIGURE 4: (LEFT) UNCONTROLLED/SOLID CASE, (CEN-TER) POROUS CASE, (RIGHT) FLUID CASE.

  porous λ = 1000 porous λ = 100 porous λ = 10 porous λ = 1 fluid λ = 0

FIGURE 5 :

 5 FIGURE 5: EFFECTS OF VARIOUS LAYER PERMEABILI-TIES ON DRAG FORCE (UP) AND ENSTROPHY (BOTTOM) RELATED TO FLOW PAST A SEMI-CIRCULAR CYLINDER AT Re = 550.

FIGURE 6 :

 6 FIGURE 6: ZOOM OF THE MEAN VORTICITY FIELDS AND ISOLINES FOR THE FLOW PAST A SEMI-CIRCULAR CYLINDER AT Re = 550.

FIGURE 7 :

 7 FIGURE 7: FIELDS AND ISOLINES OF MEAN VELOCITY MAGNITUDE FOR THE FLOW PAST A SEMI-CIRCULAR CYLINDER AT Re = 550.

  porous λ = 1000 porous λ = 100 porous λ = 10 porous λ = 1 fluid λ = 0

FIGURE 8 :

 8 FIGURE 8: EFFECTS OF VARIOUS LAYER PERMEABILI-TIES ON DRAG FORCE (UP) AND ENSTROPHY (BOTTOM) RELATED TO FLOW PAST A SEMI-CIRCULAR CYLINDER AT Re = 3000.

FIGURE 9 :

 9 FIGURE 9: ZOOM OF THE MEAN VORTICITY FIELDS AND ISOLINES FOR THE FLOW PAST A SEMI-CIRCULAR CYLINDER AT Re = 3000.

FIGURE 10 :

 10 FIGURE 10: FIELDS AND ISOLINES OF MEAN VELOCITY MAGNITUDE FOR THE FLOW PAST A SEMI-CIRCULAR CYLINDER AT Re = 3000.

TABLE 1 :

 1 MEAN VALUES OF DRAG COEFFICIENT (C D ) AND ENSTROPHY (Z) FOR FLOW PAST A SEMI-CIRCULAR CYLINDER AT Re=550 AND Re=3000.

			Re = 550	Re = 3000
	Grid	C D	Z	C D	Z
	1200 × 1000 (h = 0.01)	1.49 122	1.39 216
	2400 × 2000 (h = 0.005)	1.91 158	1.64 294
	4800 × 4000 (h = 0.0025)	1.98 161	1.86 301