COMPUTER-IMPLEMENTED METHOD FOR MANAGING USER-SUBMITTED REVIEWS USING ANONYMOUS REPUTATION SYSTEM

Abstract

The disclosure relates to implementing an anonymous reputation system for managing user reviews. In one arrangement, an anonymous reputation system is constructed from a group of group signature schemes run in parallel. Each item of a plurality of items is associated uniquely with one of the group signature schemes. A user is allowed to join the group signature scheme associated with the item when information indicating that the user has performed a predetermined operation associated with the item is received. The user can submit a review of the item when the user has joined the group signature scheme associated with the item (6). The anonymous reputation system is publicly linkable and non-frameable (8a, 8b).

Claims

1. A computer-implemented method for managing user-submitted reviews of items of goods or services, comprising: maintaining an anonymous reputation system constructed from a group of group signature schemes run in parallel, wherein: each item of a plurality of items of goods or services is associated uniquely with one of the group signature schemes; the anonymous reputation system allows a user to join the group signature scheme associated with the item when the anonymous reputation system receives information indicating that the user has performed a predetermined operation associated with the item; the anonymous reputation system allows the user to submit a review of the item when the user has joined the group signature scheme associated with the item; the anonymous reputation system is publicly linkable, such that where multiple reviews are submitted by the same user for the same item, the reviews are publicly linked to indicate that the reviews originate from the same user; and the anonymous reputation system is configured to be non-frameable, wherein non-frameability is defined as requiring that it is unfeasible for one user to generate a valid review that traces or links to a different user.

2. The method of claim 1, wherein the anonymous reputation system is constructed so as to implement security based on lattice-based hardness assumptions rather than number-theoretic hardness assumptions.

3. The method of claim 1, wherein the anonymous reputation system assigns a public key and a secret key to each user.

4. The method of claim 3, wherein the allowing of a user to join the group signature scheme associated with an item comprises assigning a position in a Merkle-tree, the Merkle-tree corresponding to the item in question, and accumulating the public key of the user in the Merkle-tree.

5. The method of claim 4, wherein positions in the Merkle-tree are hashed to the top of the Merkle-tree using an accumulator instantiated using a lattice-based hash function.

6. The method of claim 5, wherein: a path from the assigned position to the root of the Merkle-tree is provided by the anonymous reputation system to the user; the root of the Merkle-tree is public; and in order to be able to submit a review by generating a signature, the anonymous reputation system requires the user to prove in zero-knowledge that the user knows the pre-image of a public key that has been accumulated in the Merkle-tree and that the user knows of a path from the corresponding position in the Merkle-tree to the root of the Merkle-tree.

7. The method of claim 4, wherein the anonymous reputation systems allows a user to submit a review by generating a signature corresponding to the review by encrypting the assigned position in the Merkle-tree and computing a tag for the item.

8. The method of claim 7, wherein the computed tags are such as to be extractable from corresponding signatures and usable to determine whether any multiplicity of reviews for the same item originate from the same user.

9. The method of claim 7, wherein the computed tags are represented by vectors.

10. The method of claim 9, wherein the determination of whether any multiplicity of reviews for the same item originate from the same user comprises determining a degree of similarity between computed tags extracted from signatures corresponding to the reviews.

11. The method of claim 10, wherein the degree of similarity is determined based on whether a distance or difference between the computed tags is bounded by a predetermined scalar.

12. The method of 1, wherein the predefined operation comprises one or more of the following: purchasing the item, experiencing the item.

13. The method of 1, wherein the anonymous reputation system dynamically allows users to join and/or leave at any moment.

14. The method of claim 1, wherein the non-frameability of the anonymous reputation system is such that for any probabilistic polynomial time adversary it is unfeasible to generate a valid review that traces or links to an honest user even if the probabilistic polynomial time adversary is able to corrupt all other users and chose keys of a Group Manager and Tracing Manager of the anonymous reputation system.

15. The method of claim 1, wherein the anonymous reputation system is configured to be correct, where correctness is defined as requiring that reviews produced by honest, non-revoked users are always accepted by the anonymous reputation system, that an honest Tracing Manager of the anonymous reputation system can always identify the honest non-revoked user corresponding to such reviews, and that two reviews produced by the same user on the same item always link.

16. The method of claim 1, wherein the anonymous reputation system is configured to be anonymous, where anonymity is defined as requiring that for any probabilistic polynomial time adversary the probability of distinguishing between two reviews produced by any two honest users is negligible even if a Group Manager of the anonymous reputation system and all other users are corrupt and the adversary has access to a Trace oracle.

17. The method of claim 1, wherein the anonymous reputation system is configured to be traceable, where traceability is defined as requiring that for any probabilistic polynomial time adversary it is infeasible to output two reviews for the same item that trace to the same user but do not link, even if the adversary chose keys of a Group Manager and Tracing Manager of the anonymous reputation system.

18. The method of claim 1, wherein the public linkability of the anonymous reputation system is such that for any adversary it is unfeasible to output two reviews for the same item that trace to the same user but do not link, even if the adversary chose keys of a Group Manager and Tracing Manager of the anonymous reputation system.

19. The method of claim 1, wherein the anonymous reputation system is configured to be tracing sound, where tracing soundness is defined as requiring that no adversary can output a review that traces back to two different users even if the adversary can corrupt all user and chose keys of a Group Manager and Tracing Manager of the anonymous reputation system.

20. A computer program comprising instructions that when executed by a computer system cause the computer system to perform the method of claim 1.

21. A computer program product comprising the computer program of claim 20.

22. A computer system programmed to perform the method of claim 1.

Description

[0013] The invention will now be further described, by way of example, with reference to the accompanying drawings, in which:

[0014] FIG. 1 depicts an experiment defining tag-indistinguishability;

[0015] FIG. 2 depicts a description of a tag oracle;

[0016] FIG. 3 depicts an experiment defining linkability;

[0017] FIG. 4 depicts experiments defining anonymity (top), non-frameability (middle), and public-linkability (bottom);

[0018] FIG. 5 depicts security experiments for correctness (top), trace (middle) and trace-soundness (bottom);

[0019] FIG. 6 depicts a security game for accumulators;

[0020] FIG. 7 depicts a Merkle-tree for an anonymous reputation system;

[0021] FIG. 8 depicts a Stern-like protocol;

[0022] FIG. 9 schematically depicts example interactions between users of an anonymous reputation system, the anonymous reputation system, and an entity from which users can purchase items of goods or services; and

[0023] FIG. 10 schematically depicts a group signature scheme associated with an item, users who have purchased the item as members of the group, and an example user who has generated multiple reviews on the same item.

1 INTRODUCTION TO DETAILED DESCRIPTION, EXAMPLES AND PROOFS

[0024] In the present disclosure, the terms reputation systems and anonymous reputation systems are used interchangeably.

[0025] The contribution of the present disclosure includes the following. First, in some embodiments, we strengthen and re-formalize known security models for reputation systems to capture more accurately real-life threats. In particular, our security model captures all possible framing scenarios including when the adversary tries to produce a review that links to another review produced by an honest user. Without this security notion, an adversary can exploit this vulnerability in order to revoke or partially de-anonymize a particular user. Second, in some embodiments, our reputation system is fully dynamic so that users and items can be added and revoked at any time. This is an attractive and should possibly be a default feature for reputations systems to have, since the system manager will not know the users/items in the time of setup of the system. Finally, in some embodiments, we propose the first construction of a reputation system based on lattice assumptions that are conjectured to be resistant to quantum attacks by incorporating a lattice-based tag scheme.

[0026] In the present disclosure, we choose to move forward and strengthen the state-of-the-art of reputation systems built from group signatures presented in [BJK15]. Group signatures are considered to be one of the most well-established type of anonymous digital signatures, with a huge effort being made to generically formalize such an intriguing tool (see for instance, [CV91, C97, AT99, BMW03, BBS04, BS04, CG04, BSZ05, BW06, BCCGG16, LNWX17]).

[0027] Although anonymous reputation systems share some of their security properties with group signatures, they do have their unique setting that requires a different and more challenging security model. For instance, a unique security property that is required by reputation systems is public-linkability; adding public-linkability will surely effect the way we would define the anonymity and non-frameability properties. For example, public-linkability can be seen to harm the standard anonymity notion for group signatures. Furthermore, a new framing threat arises when using any linking technique within an anonymous system (see details in Section 3.2).

[0028] In the present disclosure, we substantially boost the line of work of reputation systems built from group signatures by providing a reputation system that affirmatively addresses three main challenges simultaneously; namely, we give a rigorous security model, achieve full dynamicity (i.e. users can join and leave at any moment), and equip this important topic with an alternative construction to be ready for the emerging post-quantum era.

[0029] In an embodiment, we first strengthen and re-formalize the security model for anonymous reputation systems presented in [BJK15] to fully capture all the real-life threats. In particular, we identify a security notion uncalled in the presentation of [BJK15] (although we would like to emphasize that the scheme of [BJK15] is secure according to their formalization, and we do not assert that their scheme is wrong in their proposed security model. We view one of our contributions as identifying a security hole which was not captured by the previous security model for reputation systems [BJK15], and providing a more complete treatment of them by building on the ideas of the most up-to-date security model for group signatures ([BCCGG16]): namely, we capture and formalize the framing scenario where the adversary tries to produce a review that links to another review produced by an honest user. We believe this to be one of the central security notions to be considered in order to maintain a reliable anonymous reputation system, as an adversary otherwise can exploit this vulnerability for the purpose of revoking or partially de-anonymizing a particular user. Also, our security model captures the notion of tracing soundness. It is indeed an important security property as it ensures that even if all parties in the system are fully corrupt, no one but the actual reviewer/signer can claim authorship of the signature. Additionally, in our security model, we are able to put less trust in the managing authorities, namely, the tracing manager does not necessarily have to be honest as is the case with [BJK15]. Second, our reputation system is fully dynamic where users/items can be added and revoked at any time. This is an attractive and should possibly be a default feature for a reputation system to have, due to its dynamic nature, i.e. the system manager will not have the full list of users and items that will be participating in the system upon the setup of the system. Finally, we give a construction of a reputation system that is secure w.r.t our strong security model based on lattice assumptions. To the best of our knowledge, this is the first reputation system that relies on non number-theoretic assumptions, and thereby not susceptible to quantum attacks.

[0030] Embodiments of the disclosure comprise computer-implemented methods. The methods may be implemented using any general purpose computer system. Such computer systems are well known in the art and may comprise any suitable combination of hardware (e.g. processors, motherboards, memory, storage, input/output ports, etc.), firmware, and/or software to carry out the methods described. The computer system may be located in one location or may be distributed between multiple different locations. A computer program may be provided to implement the methods when executed by the computer system. The computer program may be provided to a user as a computer program product. The computer program product may be distributed by download or provided on a non-transitory storage medium such as an optical disk or USB storage device.

[0031] Computer-implemented methods of the disclosure manage user-submitted reviews of items of goods or services. An example architecture is depicted schematically in FIG. 9. The management of user-submitted reviews is implemented using an anonymous reputation system ARS. The ARS may be implemented using a computer system, as described above. The ARS is thus maintained by a suitably programmed computer system. Users U1-U3 interact with the ARS, for example via a data connection such as the internet, in order to submit reviews about items they have purchased. In the example shown, the users U1-U3 also interact with a vendor server V, for example via a data connection such as the internet, to purchase items that can be subjected to review. The vendor server V processes the purchases and provides purchased items to the users (e.g. via download or traditional postage, depending on the nature of the items being purchased). The nature of the items is not particularly limited. Any item for which a review by a user would be relevant may be used in conjunction with embodiments. The item may be a product or service. When the purchasing procedure is completed with respect to a given user and a given item, the vendor server V informs the computing system running the anonymous reputation system ARS. The anonymous reputation system ARS is thus able to determine when a given user has purchased a given item and can therefore be permitted to write a review about that item. The anonymous reputation system ARS may be maintained at the same location as the vendor server V, optionally using the same computer system, or may be implemented at different locations (as depicted in FIG. 9) using different computer systems.

[0032] In some embodiments, the anonymous reputation system ARS is constructed from or comprises a group of group signature schemes run in parallel. The computer system maintaining the ARS may thus run a group of group signature schemes in parallel. Group signature schemes per se are well known in the art. The anonymous reputation system ARS is implemented in such a way that each item of a predetermined plurality of items (which may comprise all items for which reviews are to be managed by the anonymous reputation system ARS) is associated uniquely with one of the group signature schemes of the group of group signature schemes. Reviews associated with the item are managed by the group signature scheme associated with that item. Users can belong to any number of different group signature schemes, according to the number of different items that they have purchased.

[0033] As depicted schematically in FIG. 10, the anonymous reputation system ARS allows a user (U1, U76, U5, U4, U38, U26) to join the group signature scheme 6 associated with a particular item It1 when the anonymous reputation system ARS receives information (e.g. from a vendor V, as depicted in FIG. 9) indicating that the user (U1, U76, U5, U4, U38, U26) has performed a predetermined operation associated with the item It1. The predetermined operation may comprise purchasing the item It1 or verifiably experiencing the item It1. In the example of FIG. 9, six users (U1, U76, U5, U4, U38, U26) have purchased the particular item It1 and have therefore been allowed to join the group signature scheme 6 associated with the item It1.

[0034] The anonymous reputation system ARS is configured to allow the user (U1, U76, U5, U4, U38, U26) to submit a review of the item It1 when the user has joined the group signature scheme 6 associated with the item It1. The review may be implemented by the user generating a signature corresponding to the group signature scheme, as described in detail below.

[0035] The anonymous reputation system ARS is configured so as to be publicly linkable. Public linkability requires that where multiple reviews 8A and 8B are submitted by the same user U4 for the same item It1 as depicted schematically in FIG. 10, the reviews are publicly linked to indicate that the reviews originate from the same user It1. The anonymous reputation system ARS may be configured to detect occurrences of such multiple reviews and take suitable corrective action, such as revoking the user It1 from the group signature scheme or rejecting all but one of the multiple reviews submitted for the same item It1 by the same user U4.

[0036] The anonymous reputation system ARS is further configured to be non-frameable. Non-frameability is defined as requiring that it is unfeasible for one user to generate a valid review that traces or links to a different user. Thus, for example, it is not possible for user U5 to generate the reviews 8A and 8B in such a way that they seem to trace back to user U4 when they have in fact been submitted by user U5. It is not possible for a user to frame another user in this way, which could lead to honest users being unnecessarily revoked and their legitimate reviews being removed.

[0037] In the detailed examples described below, an anonymous reputation system ARS is described which implements security using lattice-based hardness assumptions. Lattice-based hardness assumptions are valid even for attacks using quantum computers. Thus, problems that are considered computationally hard (and therefore secure against attack) are hard both for classical computers and quantum computers. This is not necessarily the case where number-theoretic hardness assumptions are made (e.g. based on assuming that certain calculations based on determining factorials are computationally hard). Quantum computers may find such calculations relatively easy and thereby compromise the security of any scheme that is based on such number-theoretic hardness assumptions.

[0038] Details about how the security can be implemented using lattice-based hardness assumptions are provided below, together with formal proofs that the approach is possible and works as intended. Some broad features are introduced first here.

[0039] In some embodiments, the anonymous reputation system ARS assigns a public key and a secret key to each user. The anonymous reputation system ARS then allows a user to join the group signature scheme 6 associated with an item It1 by assigning a position in a Merkle-tree, the Merkle-tree corresponding to the item It1 in question, and accumulating the public key of the user in the Merkle-tree. The concept of a Merkel-tree is well known in cryptography and computer science. A Merkle-tree may also be referred to as a hash tree. The procedure is described in further detail in Section 4 below.

[0040] The anonymous reputation system ARS allows a user U4 to submit a review by generating a signature corresponding to the review by encrypting the assigned position in the Merkle-tree and computing a tag 10A, 10B for the item It1 . In an embodiment, the computed tags 10A, 10B are such as to be extractable from corresponding signatures and usable to determine whether any multiplicity of reviews for the same item It1 originate from the same user U4. If, as in FIG. 10, a user U4 attempts to write multiple reviews for a given item It1, the tags 10A,10B will thus behave in a certain way, for example similarly or identically, if the user U4 and item It1 are the same for the multiple reviews. In some embodiments, the tags 10A and 10B will be identical. In the context of a lattice-based implementation such as that described in detail below, the computed tags 10A, 10B may be represented by vectors. In such embodiments, the deter mination of whether any multiplicity of reviews for the same item It1 originate from the same user U4 may comprise determining a degree of similarity between the multiple computed tags 10A, 10B. In an embodiment, the degree of similarity relates to similarity of mathematical behaviour. In an embodiment, the degree of similarity is determined based on whether a distance or difference between the computed tags is bounded by predetermined scalar.

[0041] In some embodiments, the anonymous reputation system ARS dynamically allows users to join and/or leave at any moment. The anonymous reputation system ARS is thus a fully dynamic system rather than a static system. In the context of a lattice-based implementation such as that described in detail below, this fully dynamic behaviour may be made possible via the update mechanism for the Merkle-tree (which allows users to join group signature schemes associated with items when they purchase those items) introduced above and discussed in further detail below. The discussion below also provides proof that the non-frameability can be achieved in combination with the full dynamicity.

[0042] In some embodiments, the maintaining of the anonymous reputation system comprises implementing a Group Manager (GM). The GM uses GM keys to generate tokens to users to allow the users to submit reviews. The GM may be thought of as a system manager, i.e. the entity (or entities working in collaboration, as this can be generalised to have multiple managers in order to enforce decentralisation) that manages the whole reviewing system. In some embodiments, in order to enforce a proper separation of duties, a separate entity called a Tracing Manager (TM) is also implemented. The TM may be thought of as a troubleshooting manger that is only called to troubleshoot the system in case of misuse/abuse. The TM may use TM keys to review the identity of a user who has a written a particular review in case of any misuse/abuse of the system.

2 Preliminaries

2.1 Lattices

[0043] For positive integers n, m such that nm, an integer n-dimensional lattice in .sup.m is a set of the form {.sub.i[n].sub.ib.sub.i|.sub.i }, where B={b.sub.1, . . . , B.sub.n} are n linearly independent vectors in .sup.m. Let , be the discrete Gaussian distribution over .sup.m with parameter >0. In the following, we recall the definition of the Short Integer Solution (SIS) problem and the Learning with Errors (LWE) problem.

[0044] Definition 1 (SIS). For integers n(),m=m(n), q=q(n)>2 and positive real , we define the short integer solution problem SIS.sub.n,m,q,as the problem of finding a vector x .sup.m such that Ax=0 mod q and x when given A.sub.q.sup.nm m as input.

[0045] When m,=poly(n) and q>{square root over (n)}, the SIS.sub.n,m,q,problem is at least as hard as SIVP.sub.for some =.Math.({square root over (nm)}). See [GPV08, MP13].

[0046] Definition 2 (LWE). For integers n=n(),m=m(n), t=t(n), a prime integer q=q(n)>2 such that t<n and an error distribution over =.sup.(n) over we define the decision learning with errors problem LWE.sub.n,m,q,as the problem of distinguishing between (A, A.sup.Ts+x) from (A, b), where A.sub.q.sup.nm, s.sup.n, x.sup.m and b.sub.q.sup.m. We also define the search first-are-errorless learning with errors problem faeLWE.sub.n,t,m,q,as the problem of finding a vector s.sub.q.sup.n when given b=A.sup.Ts+x mod q as input, where A.sub.q.sup.nm, s.sup.n and x{0}.sup.t.sup.mt, i.e., the first t samples are noise-free.

[0047] [ACPS09] showed that one can reduce the standard LWE problem where s is sampled from .sub.q.sup.n to the above LWE problem where the secret is distributed according to the error distribution. Furthermore, [ALS16] showed a reduction from LWE.sub.nt,m,q,to faeLWE.sub.n,t,m,q,that reduces the advantage by at most 2.sup.nt1. When = and q>2{square root over (2n)}, the LWE.sub.n,m,q,is at least as (quantumly) hard as solving SIVP.sub.for some =(n/). See [Reg05, Pei09, BLP.sup.+13]. We sometimes omit the subscript m from LWE.sub.n,m,q,, faeLWE.sub.n,m,q,X,, since the hardness of the problems hold independently from m=poly(n). In the following, in case =D.sub.,, we may sometimes denote LWE.sub.n,m,q,, faeLWE.sub.n,m,q,.

2.2 Tag Schemes

[0048] We recall here the lattice-based linkable indistinguishable tag (LWE-LIT) scheme presented in [EE17]. Let m,w,q be positive integers with m=3w and q>2 a prime. Assume they are all implicitly a polynomial function of the security parameter n, where we provide a concrete parameter selection in our construction (See Section 4). Let : {0, 1}*.fwdarw..sub.q.sup.mw be a hash function modeled as a random oracle in the security proofs. Let =Z.sub.q.sup.m[,].sup.m be the key space for some positive integer <q, =.sub.q.sup.m be the tag space, and ={0, 1}* be the message space. Finally, let be some positive real such that >w({square root over (log n)}). Then, the lattice-based linkable indistinguishable tag scheme is defined by the following three PPT algorithms LIT=(KeyGen.sub.LIT, TAG.sub.LIT, Link.sub.LIT):

[0049] KeyGen.sub.LIT(1.sup.n): The key generation algorithm takes as input the security parameter 1.sup.n, it samples a secret key sk,.sub.until sk.sup.1. It then outputs sk. .sup.1 The expected number of samples required will be a constant due to our parameter selection. In particular, we have Pr[||>w({square root over (log n)})]=negl(n) for .

[0050] TAG.sub.LIT(I, sk): The tag generation algorithm takes as input a message I and a secret key sk, and samples an error vector e,.sub.. It then outputs a tag =(I).sup.Tsk=e .

[0051] Link.sub.LIT(): The linking algorithm takes as input two tags , and outputs 1 if 2and 0 otherwise.

[0052] We require one additional algorithm only used during the security proof.

[0053] IsValid.sub.LIT(sk, I): This algorithm takes as input a tag , a secret key sk and a message I, and outputs 1 if (I).sup.Tsk and 0 otherwise.

[0054] The tag scheme (LIT) must satisfy two security properties, namely, the tag-indistinguishability and linkability. Informally speaking, tag-indistinguishability ensures that an adversary cannot distinguish between two tags produced by two users (of his choice) even given access to a tag oracle. Linkability means that two tags must link together if they are produced by the same user on the same message. In the context of reputation systems, the messages associated to the tag will correspond to the items that the users buy. Therefore, when the users write two anonymous reviews on the same item, the tags will help us link the two reviews.

[0055] Tag-indistinguishability. A tag-indistinguishability for a LIT scheme is defined by the experiment in FIG. 1. We define the advantage of an adversary breaking the tag-indistinguishability as follows:

(n)=|Pr[(n)=1]Pr[(n)=1]|

[0056] We say that a LIT scheme is tag-indistinguishable if for all polynomial time adversary the advantage is negligible.

[0057] The proof of the following Theorem 1 is provided in Appendix A.

[0058] Theorem 1 (tag-indistinguishability). For any efficient adversary against the tag-indistinguishability experiment of the LWE-LIT scheme as defined above, we can construct an efficient algorithm solving the LW problem with advantage:

(n)(n)negl(n),

where Q denotes the number of random oracle queries made by . In particular, assuming the hardness of LW, the advantage of any efficient adversary is negligible.

[0059] Linkability. A linkability of a LIT scheme is defined by the experiment in FIG. 3. We define the advantage of an adversary breaking the linkability as (n)=Pr[(n)=1]. We say that a LIT scheme is non-linkable if for all adversary the advantage is negligible.

[0060] Theorem 2 (Linkability). For any adversary against the linkability experiment of the LWE-LIT scheme as defined above, the advantage (n) is negligible.

[0061] Proof. Suppose, towards a contradiction, that all adversary wins the linkability experiment. In particular, outputs (.sub.0,.sub.1,I,sk) such that the following three conditions hold: .sub.0(I).sup.Tsk,.sub.1(I).sup.Tsk, and >. From the first two inequalities, we have

=(.sub.0(I).sup.Tsk)+(.sub.1(I).sup.Tsk.sub.0(I).sup.Tsk+.sub.1(I).sup.Tsk2,

by the triangular inequality. However, this contradicts the third inequality.

2.3 Group Signatures

[0062] In a group signature, a group member can anonymously sign on behalf of the group, and anyone can then verify the signature using the group's public key without being able to tell which group member signed it. A group signature has a group manager who is responsible for generating the signing keys for the group members. There arc two types of group signatures; the static type [BMW03] where the group members are fixed at the setup phase. In this case, the group manager can additionally trace a signature and reveal which member has signed it. The second type is the dynamic type [BSZ05, BCC.sup.+16], where users can join/leave the system at anytime. Now a group has two managers; the group manager and a separate tracing manager who can open signatures in case of misuse/abuse. Briefly speaking, a group signature has three main security requirements; anonymity, non-frameability, and traceability. Anonymity ensures that an adverary cannot tell which group member has signed the message given the signature. Non-frameability ensures that an adversary cannot produce a valid signature that traces back to an honest user. Finally, traceability ensures that an adversary cannot produce a valid signature that does not trace to an any user. In our work, we build on the recent lattice-based fully dynamic group signature scheme of [LNWX17] to construct our reputation system. We briefly sketch how the group signature scheme of [LNWX17] works; a group manager maintains a Merkle-tree in which he stores members' public keys in the leaves where the exact position are given to the signers at join time. The leaves will be hashed to the top of the tree using an accumulator instantiated using a lattice-based hash function (see details in Appendix D). The relevant path to the top of the tree will be given to each member where the top of the tree itself is public. In order to sign, a group member has to prove in zero-knowledge that; first, he knows the pre-image of a public key that has been accumulated in the tree, and that he also knows of a path from that position in the tree to its root. Additionally, they apply the Naor-Yung double-encryption paradigm [NY90] with Regev's LWE-based encryption scheme [Reg05] to encrypt the identity of the signer (twice) w.r.t the tracer's public key to prove anonymity. To summarize, a group signature would be of the form (II, c.sub.1, c.sub.2), where II is the zero-knowledge proof that the signer is indeed a member of the group (i.e., his public key has been accumulated into the Merkle-tree), and the encrypted identity in both c.sub.1 and c.sub.2 is a part of the path that he uses to get to the root of the Merkle-tree. Note that this implies that the ciphertexts (c.sub.1, c.sub.2) are bound to the proof II.

3 Syntax and Security Definitions

[0063] We formalize the syntax of reputation systems following the sate-of-the-art formalization of dynamic group signatures of [BCC.sup.+16]. We briefly explain the two major differences that distinguish between a reputation system from a group signature scheme. First, a reputation system is in essence a group of group signature schemes run in parallel, where we associate each item uniquely to one instance of the group signature scheme. Second, we require an additional algorithm Link in order to publicly link signatures (i.e., reviews), which is the core functionality provided by reputation systems. We now define reputation systems by the following PPT algorithms:

[0064] RepSetup(1.sup.n).fwdarw.pp: On input of the security parameter 1.sup.n, the setup algorithm outputs public parameters pp.

[0065] KeyGen.sub.GM(pp).Math.KeyGen.sub.TM(pp): This an interactive protocol between the group manager GM and the tracing manager TM. If completed successfully, KeyGen.sub.GM outputs the GM's key pair (mpk, msk) and KeyGen.sub.TM outputs the TM's key pair (tpk, tsk). Set the system public key to be gpk:=(pp, mpk,tpk).

[0066] UKgen(1n).fwdarw.(upk, usk): On input of the security parameter 1.sup.n, it outputs a key pair (upk, usk) for a user. We assume that the key table containing the various users' public keys upk is publicly available.

[0067] Join(info.sub.t.sub.current, gpk, upk, usk, item).Math.Issue(info.sub.t.sub.current, msk, upk, item): This is an interactive protocol between a user upk and the GM. Upon successful completion, the GM issues an identifier uid.sub.item associated with item to the user who then becomes a member of the group that corresponds to item.sup.2. The final state of the Issue algorithm, which would always include the user public key upk, is stored in the user registration table reg at index (item, uid.sub.item) which is made public. Furthermore, the final state of the Join algorithm is stored in the secret group signing key gsk[item][uid.sub.item]. .sup.2 Here our syntax assumes that the items to be reviewed have been already communicated to the GM from the respective service providers. We merely do this to make our presentation simple and we emphasize that our construction is general in the sense that the GM does not need to know neither the number of items nor the items themselves ahead of time. Items can dynamically be added/removed from the system by GM when it is online.

[0068] RepUpdate(gpk, msk, R, info.sub.t.sub.current, reg).fwdarw.(info.sub.t.sub.new, reg): This algorithm is run by the GM to update the system info. On input of the group public key gpk, GM's secret key msk, a list R of active users' public keys to be revoked, the current system info info.sub.t.sub.current, and the registration table reg, it outputs a new system info info.sub.t.sub.new while possibly updating the registration table reg. If no changes have been made, output .

[0069] Sign(gpk, gsk[item][uid.sub.item], info.sub.t.sub.current, item, M).fwdarw.: On input of the system's public key gpk, user's group signing key gsk[item][uid.sub.item], system info.sub.t.sub.current at epoch t.sub.current, an item, and message M, it outputs a signature . If the user owning gsk[item][uid.sub.item] is not an active member at epoch t.sub.current, the algorithm outputs .

[0070] Verify(gpk, info.sub.t.sub.current, item, M, ).fwdarw.1/0: On input of the system's public key gpk, system info info.sub.t.sub.current, an item, a message M, and a signature , it outputs 1 if is valid signature on M for item at epoch t.sub.current, 0 otherwise.

[0071] Trace(gpk, tsk, info.sub.t.sub.current, reg, item, M, )&43 (uid.sub.item, II.sub.Trace): On input of the system's public key gpk, the TM's secret key tsk, the system information info.sub.t.sub.current, the user registration table reg, an item, a message M, and a signature , it outputs the identifier of the user uid.sub.item who produced and a proof II.sub.Trace that attests to this fact. If the algorithm cannot trace the signature to a particular group member, it returns .

[0072] Judge(gpk, uid.sub.item, II.sub.Trace, info.sub.t.sub.current, item, M, )1/0: On input of the system's public key gpk, a user's identifier uid.sub.item, a tracing proof II.sub.Trace from the Trace algorithm, the system info info.sub.t.sub.current, an item, a message M and signature , it outputs 1 if II.sub.Trace is a valid proof that uid.sub.item produced and 0 otherwise.

[0073] Link(gpk, item, (m.sub.0, .sub.0),(m.sub.1, .sub.1)).fwdarw.1/0: On input of the system's public key gpk, an item, and two message-signature pairs, it returns 1 if the signatures were produced by the same user on behalf of the group that corresponds to item, 0 otherwise.

[0074] IsActive(info.sub.t.sub.current, uid.sub.item, reg, item).fwdarw.1/0: this algorithm will only be used in the security games. On input of the system info.sub.t.sub.current, a user's identifier uid.sub.item, the user registration table reg, and an item, it outputs 1 if uid.sub.item is an active member of the group for item at epoch t.sub.current and 0 otherwise.

3.1 Discussion on the Security Model of FC15 Reputation System

[0075] Blmer et al. [BJK15] constructed an anonymous reputation system from group signatures based on number-theoretical assumptions. In their work, they claim to formalize reputation systems following the formalization of partially dynamic group signature schemes presented by Bellare et al. [BSZ05], i.e., they have two managers, the group manger and key issuer.sup.3. However, one can notice that the security model is in fact strictly weaker than that of [BSZ05]; the major difference being the assumption that the opener/tracer is always honest. Furthermore, in their public-linkability property, the key issuer (the GM in our case) is assumed to be honest. Another observation, which we believe to be of much bigger concern, is that their security notion for reputation systems does not fully capture all the real-life threats. In particular, their strong-exculpability property (which is essentially the notion of non-frameability), does not capture the framing scenario where the adversary outputs a signature that links to an honest user; it only captures the scenario where the adversary outputs a signature that traces to an honest user. Note that the former attack scenario does not exist in the context of group signatures since no tag schemes are being used there, i.e., the whole notion of linkability does not exist. However, it is a vital security requirement in the reputation system context as an adversary could try to generate a review that links to an honest user's review so that the GM may decide to revoke or de-anonymize the honest user. In our work, we provide a formal definition of reputation systems that models more accurately these real-life threats, which in particular, solve the aforementioned shortcomings of [BJK15]. .sup.3 Note that [BJK15] does not completely follow the notation used in [BSZ05], i.e., their group manager is in fact the tracer in [BSZ05].

3.2 Security Definitions

[0076] We provide a formal security definition following the experiment type definition of [BCC.sup.+16, LNWX17] for fully dynamic group signatures, which originates to [BSZ05]. Anonymity, non-frameability and public-linkability are provided in FIG. 4, and the rest are provided in FIG. B.1. The oracles used during the security experiments are provided in Appendix B. One of the main differences between theirs and ours is that, we require the public-linkability property, which does not exist in the group signature setting. Moreover, the existence of the tag scheme further affects the anonymity and non-frameability properties, which are depicted in FIG. 4; for the former, an adversary should not be allowed to ask for signatures by the challenge users on the challenge item, otherwise he could trivially win the game by linking the signatures. In the latter, an additional attack scenario is taken into consideration, i.e., when an adversary outputs a review that links to an honest user's review. the game. Also, our public linkability holds unconditionally, and therefore, GM can be assumed to be corrupt there. We now present the security properties of our reputation system.

[0077] Correctness A reputation system is correct if reviews produced by honest, non-revoked users are always accepted by the Verify algorithm and if the honest tracing manager can always identify the signer of such signatures where his decision will be accepted by a Judge. Additionally, two reviews produced by the same user on the same item should always link.

[0078] Anonymity A reputation system is anonymous it for any PPT adversary the probability of distinguishing between two reviews produced by any two honest signers is negligible even if the GM and all other users are corrupt, and the adversary has access to the Trace oracle.

[0079] Non-frameability A reputation system is non-frameable if for any PPT adversary it is unfeasible to generate a valid review that traces or links to an honest user even if it can corrupt all other users and chose the keys for GM and TM.

[0080] Traceability A reputation system is traceable if for any PPT adversary it is infeasible to produce a valid review that cannot be traced to an active user at the chosen epoch, even if it can corrupt any user and can choose the key of TM.sup.4. .sup.4 The group manager GM is assumed to be honest in this game as otherwise the adversary could trivially win by creating dummy users.

[0081] Public-Linkability A reputation system is publicly linkable if for any (possibly inefficient) adversary it is unfeasible to output two reviews for the same item that trace to the same user but dose not link. This should hold even if the adversary can chose the keys of GM and TM.

[0082] Tracing Soundness A reputation system has tracing soundness if no (possibly inefficient) adversary can output a review that traces back to two different signers even if the adversary can corrupt all users and chose the keys of GM and TM.

4 Our Lattice-Based Reputation System

[0083] Intuition behind our scheme. It is helpful to think of our reputation system as a group of group signatures managed by a global group manager (or call it a system manager), whom we refer to as a group manager GM for simplicity. This group manager shares the managerial role with the tracing manager TM who is only called for troubleshooting, i.e., to trace users who misused the system. The group manager maintains a set of groups, each corresponds to a product/item owned by a certain service provider. Users who bought a certain item are eligible to become a member of the group that corresponds to this item, and can therefore write one anonymous review for this item. Every user in the system will have his own pair of public-secret key (upk, usk). When he wants to join the system for a particular item, he would engage in the Join-Issue protocol with GM. after which, he would be assigned a position uid=bin(j){0,1} in the Merkle-tree that corresponds to the item in question, and his public key will be accumulated in that tree. Here, j (informally) denotes the j-th unique user to have bought the corresponding item. The user can now get his witness w.sub.j that attests to the fact that he is indeed a consumer of the item, on which he is then ready to write a review for that item. Technically speaking, he needs to provide a non-interactive zero-knowledge argument of knowledge for a witness to the following relation.sub.Sign:

R.sub.Sign={(A, u, z,69 .sub.Tag(item ),, c.sub.1, c.sub.2, B, P.sub.1, P.sub.2), (p, w.sub.j, x, e, uid.sub.item, r.sub.1, r.sub.2): p0.sup.nkTVerify.sub.A(p,w.sub.j,u)=1A.Math.x=G.Math.p mod q (Enc.sub.Regev((B,P.sub.1,P.sub.2),uid.sub.item;(r.sub.1,r.sub.2))=(c.sub.1,c.sub.2)=.sub.Tag(item).sup.Tx+e}.

[0084] As it can be seen, the signer encrypts his uid and computes a tag for the item in question. This tag ensures that he can only write one review for each item, otherwise his reviews will be publicly linkable and therefore detectable by GM. Regarding the verification, anyone can then check the validity of the signature by simply running the verify algorithm of the underlying NIZKAoK proof system. In any misuse/abuse situation, TM can simply decrypt the ciphertext attached to the signature to retrieve the identity of the signer. TM also needs to prove correctness of opening (to avoid framing scenarios) via the generation of a NIZKAoK for the following relation .sub.Trace:

R.sub.Trace={(c.sub.1,c.sub.2,uid.sub.item, B,P.sub.1),(S.sub.1,E.sub.1):Dec.sub.Regev((S.sub.1,E.sub.1),(c.sub.1,c.sub.2))=uid.sub.item}

[0085] Finally, for public linkability, we require that any two given signatures (.sub.0, .sub.1) for the same item can be publicly checked to see if they are linkable, i.e., check that were produced by the same reviewer. This can be done simply by feeding the tags and of the two signatures, to the Link.sub.LIT algorithm of the underlying LIT scheme. If Link.sub.LIT returns 0, then .sub.0 and .sub.1 were not produced by the same user, and therefore are legitimate reviews from two different users. Otherwise, in the case it returns 0, we know that some user reviewed twice for the same item; the GM asks TM to trace those signatures and find out who generated them and GM will then revoke the traced user from the system.

4.1 Our Construction

[0086] Underlying Tools. In our construction, we use the multi-bit variant of the encryption scheme of Regev [KTX07, PVW08] provided in Appendix D.4, which we denote by (KeyGen.sub.Regev, Enc.sub.Regev, Dec.sub.Regev). We also employ the lattice-based tag scheme (KeyGen.sub.LIT, TAG.sub.LIT, Link.sub.LIT) provided in Section 2.2. We assume both scheme share the same noise distribution (See below). We also use a lattice-based accumulator (TSetup, TAcc.sub.A, TVerify.sub., TUpdate.sub.) provided in Appendix D.3. Finally, we use a Stern-like zero-knowledge proof system provided in Appendix E.2, where the commitment scheme of [KTX08] is used internally.

[0087] Construction. The proposed reputation system consists of the following PPT algorithms:

[0088] RepSetup(1.sup.n): On input of the security parameter 1.sup.n, it outputs the public parameters,

pp=(N,n,q,k,m,m.sub.E;w,,,,,.sub.Tag, .sub.Sign, .sub.Trace, A).

[0089] Where, N==poly(n) is the number of potential users, q=(n.sup.1.5), k=[log.sub.2q], m=2nk, m.sub.E=2(n+)k,w=3m,={square root over (n)}.Math.w(log n), and a /{square root over (2)}-bounded noise distribution . Moreover, .sub.Tag: {0,1}*.fwdarw..sub.q.sup.mw is the hash function used for the tag scheme, and .sub.Sign, .sub.Trace:{0,1}*.fwdarw.{1, 2, 3}.sup.are two hash functions used for the NIZKAoK proof systems for .sub.Sign and .sub.Trace, where =w(log n). Finally, A.sub.q.sup.nm.

[0090] KeyGen.sub.GM(pp).Math.KeyGen.sub.TM(pp): This is for the group manager and tracing manager to set up their keys and publish the system's public information. The group manager samples msk{0,1}.sup.m, and sets mpk:=A.Math.msk mod q. On the other hand, TM runs (pk.sub.Enc,sk.sub.Enc)KeyGen.sub.Regev(1.sup.n) and sets tpk:=pk.sub.Enc=(B, P.sub.1, P.sub.2) and tsk:=sk.sub.Enc=(S.sub.1, E.sub.1). GM receives tpk from TM and creates an empty reg table. Namely, reg[item][bin(j)][1]=0.sup.nk and reg[item][bin(j)][2]=0 for j=1, . . . ,N1 and all item in the system, i.e., it is epoch 0 and no users have joined the system yet.sup.5. Here, GM maintains multiple local counters c.sub.item to keep track of the registered users for each item, which are all set initially to 0. Finally, GM outputs gpk=(pp, mpk, tpk) and info=. .sup.5 Recall that for simplicity of presentation, we assume the all items are provided to the GM. Our scheme is general enough so that the items can dynamically be added/removed from the system by GM.

[0091] UKgen(1.sup.n): This algorithm is run by the user. It samples xKeyGen.sub.LIT(1.sup.n) where x[, ].sup.m and sets usk:=x. It then computes upk:=p=bin(Ax mod q){0,1}.sup.nk. Hereafter, the user is identified by his public key upk.

[0092] Join.Math.Issue: A user (upk, usk)=(p, x) requests to join the group that corresponds to item at epoch t. He sends p to GM. If GM accepts the request, it issues an identifier for this user, i.e., uid.sub.item=bin(c.sub.item){0,1. The user's signing key for item is then set to gsk[uid.sub.item][item]=(uid.sub.item, p, x). Now, GM updates the Merkle tree via TUpdate.sub.item,A(uid.sub.item, p).sub.6, and sets reg[item][uid.sub.item][1]:=p, reg[item][uid.sub.item][2]:=t. Finally, it increments the counter c.sub.item:=c.sub.item+1. .sup.6 See details in Section D.3.

[0093] RepUpdate(gpk, msk, R, info.sub.t.sub.current, reg): This algorithm is be run by GM. Given a set R of users to be revoked, it first retrieves all the uid.sub.item associated to each upk=pR. It then runs TUpdate.sub.item,A(reg[item][uid.sub.item][1],0.sup.nk) for all the retrieved uid.sub.item. It finally recomputes u.sub.t.sub.new,.sub.item and publishes

info.sub.new={(u.sub.t.sub.new,.sub.item , W.sub.item)}.sub.item,

where, W.sub.item={w.sub.i,item}.sub.i and w.sub.i,item{0, 1}({0, 1}.sup.nk) is the witness that proves that upk.sub.i=p.sub.i is accumulated in u.sub.t.sub.new,.sub.item. Here, the first -bit string term of the witness refers to the user identifier uid.sub.item associated to item.

[0094] Sign(gpk,gsk[item][uid.sub.item],info.sub.t.sub.current,item, M): If info.sub.t.sub.current does not contain a witness w.sub.i,item with the first entry being uid.sub.item{0, 1}, return . Otherwise, the user downloads u.sub.t.sub.current,item and his witness w.sub.i,item from info.sub.t.sub.current. Then, it computes (c.sub.1, c.sub.2)Enc.sub.Regev (tpk, uid.sub.item) and the tag TAG.sub.LIT(item,x), where recall usk=x. Finally, it generates a NIZKAoK II.sub.sign=({CMT.sub.i}.sub.i=1, CH, {RSP}.sub.i=1) for the relation R.sub.Sign, where

CH=.sub.Sign(M,{CMT.sub.i}.sub.i=1, A, u, .sub.Tag(item),,c.sub.1,c.sub.2,B,P.sub.1, P.sub.2){1,2,3}.sup.z,24 ,

and outputs the signautre =(II.sub.Sign,.sub.,c.sub.1.sub., c.sub.2).

[0095] Verify(gpk,info.sub.t.sub.current,item,M,): It verifies if II.sub.Sign is a valid proof. If so it outputs 1 and otherwise it outputs 0.

[0096] Trace(gpk, tsk, info.sub.t.sub.current,reg,item,M,): It first runs uid.sub.itemDec.sub.Regev((S.sub.1,E.sub.1,(c.sub.1, c.sub.2)). Then, it generates a NIZAoK proof II.sub.Trace for the relation R.sub.Trace.

[0097] Judge(gpk,uid.sub.item,II.sub.Trace,info.sub.t.sub.current,item,M,): It verifies if II.sub.Trace is a valid proof. If so it outputs 1 and otherwise it outputs 0.

[0098] Link(gpk,item,(M.sub.0,.sub.0),(M.sub.1,.sub.1)): It parses .sub.0 and .sub.1 and outputs bLink.sub.LIT(), where b=1 when it is linkable and 0 otherwise.

4.2 Security Analysis

[0099] We show that our reputation system is secure. Each of the following theorems correspond to the security definitions provided in Section 3.2, except for the correctness which can be easily checked to hold. Here, we only provide the high-level overview of some of the proofs that we believe to be of interest, and omit the formal proofs to Appendix C. The parameters that appear in the theorems are as provided in the above construction.

[0100] Theorem 3 (Anonymity). Our reputation system is anonymous, assuming the hardness of the decision LWE.sub.n,q,x problem.

[0101] Proof Overview. We proceed in a sequence of hybrid experiments to show that (n)(n)|neg|for any PPT algorithm. The high level strategy is similar to the anonymity proof for the dynamic group signature scheme provided in [LNWX17], Lemma 2. Namely, for the challenge signature, we swap the user identifier uid.sub.item embedded in the ciphertexts (c.sub.1,c.sub.2) and the user's secret key usk embedded in th tag . The main difference between the proof of [LNWX17] is that for our reputation system we have to swap the tag in the challenge signature. For this, we use the tag indistinguishability property of the underlying tag scheme LWE-LIT presented in Theorem 1. This modification in the experiments are provided in Exp.sub.5 of our proof.

[0102] Theorem 4 (Non-Frameability). Our Reputation System is non-frameable, assuming the hardness of the SIS.sub.n,m,q,1 problem of the search faeLWE.sub.m,n,q,(or equivalently the search LWE.sub.mn,q,) problem.

[0103] Proof Overview. For an adversary to win the experiment, he must output a tuple (uid*.sub.item*,II*.sub.Trace,info.sub.t*,item*,M*,*) such that (informally): (i) the pair (M*,*) links to some other message-signature pair (M,) corresponding to item* of an honest non-corrupt user or (ii) the proof II*.sub.Trace traces the signature * back to some honest non-corrupt user. Since the latter case (ii) essentially captures the non-frameability of fully dynamic group signatures, the proof follows similarly to [LNWX17], Lemma 3. However, for case (i), we must use a new argument, since this is a security notion unique to reputation systems. In particular, we aim to embed a search LWE problem into the tag of the message-signature pair (M,) of an honest non-corrupt user (where the simulator does not know the secret key usk) for which the adversary outputs a linking signature forgery (M*,*). Due to the special nature of our LWE tag scheme, we can prove that if the signatures link, then the two secret keys usk, usk* embedded in the tags must be the same. Therefore, by extracting usk* from the adversary's forgery, we can solve the search LWE problem. However, the problem with this approach is that since the simulator does not know usk, he will not be able to provide the adversary with this particular user's public key upk, which is defined as A.Math.usk mod q. Our final idea to overcome this difficulty is by relying on the so called first-are-error-less LWE problem [BLP.sup.+13, ALS16], which is proven to be as difficult as the standard LWE problem. Namely, the simulator will be provided with A.Math.usk as the error-less LWE samples and uses the remaining non-noise-less LWE samples to simulate the tags.

[0104] Theorem 5 (Public Linkability). Our reputation system is unconditionally public-linkable.

[0105] Proof Overview. We show that no such (possibly inefficient) adversary exists by assuming the linkability property of our underlying tag scheme LWE-LIT presented in Theorem 2, which holds unconditionally. Our strategy is to prove by contradiction. Assuming that an adversary winning the public-linkability experiment exists, we obtain two signatures .sub.0, .sub.1 on item such that the two tags associated with the signatures does not link, but the two tags embed the same user secret key usk (which informally follows from the II.sub.Trace,b provided by the adversary). Then, by extracting the usk from the signatures produced by the adversary, we can use (,I=item,sk=usk) to win the linkability experiment of the tag scheme. Thus a contradiction.

[0106] The following two theorems follow quite naturally from the proofs of the dynamic group signatures schemes of [LNWX17]. At a high level, this is because the following security notions captures threats that should hold regardless of the presence of tags.

[0107] Theorem 6 (Traceability). Our reputation system is traceable assuming the hardness of the SIS.sub.n,m,q,1 problem.

[0108] Theorem 7 (Tracing Soundness). Our reputation system is unconditionally tracing sound.

REFERENCES

[0109] ACBM08. Elli Androulaki, Seung Choi, Steven Bellovin, and Tal Malkin. Reputation systems for anonymous networks. In Privacy Enhancing Technologies, pages 202-218. Springer, 2008. 2

[0110] ACPS09. Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In CRYPTO, pages 595-618. Springer, 2009. 4

[0111] ALS16. Shweta Agrawal, Benot Libert, and Damien Stehl. Fully secure functional encryption for inner products, from standard assumptions. In Crypto, pages 333-362. Springer, 2016. 4, 15

[0112] AT99. Giuseppe Ateniese and Gene Tsudik. Some open issues and new directions in group signatures. In International Conference on Financial Cryptography, pages 196-211. Springer, 1999. 2

[0113] BBS04. Dan Boneh, Xavier Boyen, and Hovav Shacham. Short group signatures. In Crypto, volume 3152, pages 41-55. Springer, 2004. 2

[0114] BCC.sup.+16. Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Essam Ghadafi, and Jens Groth. Foundations of fully dynamic group signatures. In ACNS, pages 117-136. Springer, 2016. 2, 3, 7, 10

[0115] BJK15. Johannes Blmer, Jakob Juhnke, and Christina Kolb. Anonymous and publicly linkable reputation systems. In Financial Cryptography, pages 478-488. Springer, 2015. 2, 3, 9

[0116] BLP.sup.+13. Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehl. Classical hardness of learning with errors. In STOC, pages 575-584, 2013. 4, 15

[0117] BMW03. Mihir Bellare, Daniele Micciaucio, and Bogdan Warinschi. Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions. In EUROCRYPT, pages 614-629. Springer, 2003. 2, 7

[0118] BSO4. Dan Boneh and Hovav Shacham. Group signatures with verifier-local revocation. In Proceedings of the 11th ACM conference on Computer and communications security, pages 168-177. ACM, 2004. 2

[0119] BSS10. John Bethencourt, Elaine Shi, and Dawn Song. Signatures of reputation. pages 400-407. Springer, 2010. 2

[0120] BSZ05. Mihir Bellare, Haixia Shi, and Chong Zhang. Foundations of group signatures: The case of dynamic groups. In CT-RSA, pages 136-153. Springer, 2005. 2, 7, 9, 10

[0121] BW06. Xavier Boyen and Brent Waters. Compact group signatures without random oracles. In Eurocrypt, volume 4004, pages 427-444. Springer, 2006. 2

[0122] C.sup.+97. Jan Camenisch et al. Efficient and generalized group signatures. In Eurocrypt, volume 97, pages 465-479. Springer, 1997. 2

[0123] CG04. Jan Camenisch and Jens Groth. Group signatures: Better efficiency and new theoretical aspects. In SCN, volume 3352, pages 120-133. Springer, 2004. 2

[0124] CSK13. Sebastian Clau, Stefan Schiffner, and Florian Kerschbaum. k-anonymous reputation. In ACM SIGSAC, pages 359-368. ACM, 2013. 2

[0125] CVH91. David Chaum and Eugne Van Heyst. Group signatures. In EUROCRYPT, pages 257-265. Springer, 1991. 2

[0126] Del00. Chrysanthos Dellarocas. Immunizing online reputation reporting systems against unfair ratings and discriminatory behavior. In ACM conference on Electronic commerce, pages 150-157. ACM, 2000. 2

[0127] DMS03. Roger Dingledine, Nick Mathewson, and Paul Syverson. Reputation in p2p anonymity systems. In Workshop on economics of peer-to-peer systems, volume 92, 2003. 2

[0128] EE17. Rachid El Bansarkhani and Ali El Kaafarani. Direct anonymous attestation from lattices. IACR Cryptology ePrint Archive, 2017. 4

[0129] FS86. Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In CRYPTO, pages 186-194. Springer, 1986. 33

[0130] GK11. Michael T Goodrich and Florian Kerschbaum. Privacy-enhanced reputation-feedback methods to reduce feedback extortion in online auctions. In ACM conference on Data and application security and privacy, pages 273-282. ACM, 2011. 2

[0131] GPV08. Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, pages 197-206. ACM, 2008. 4

[0132] JI02. Audun Josang and Roslan Ismail. The beta reputation system. In Proceedings of the 15th bled electronic commerce conference, volume 5, pages 2502-2511, 2002. 2

[0133] Ker09. Florian Kerschbaum. A verifiable, centralized, coercion-free reputation system. In ACM workshop on Privacy in the electronic society, pages 61-70. ACM, 2009. 2

[0134] KSGM03. Sepandar D Kamvar, Mario T Schlosser, and Hector Garcia-Molina. The eigentrust algorithm for reputation management in p2p networks. In Proceedings of the 12th international conference on World Wide Web, pages 640-651. ACM, 2003. 2

[0135] KTX07. Akinori Kawachi, Keisuke Tanaka, and Keita Xagawa. Multi-bit cryptosystems based on lattice problems. In PKC, pages 315-329. Springer, 2007. 12, 20

[0136] KTX08. Akinori Kawachi, Keisuke Tanaka, and Keita Xagawa. Concurrently secure identification schemes based on the worst-case hardness of lattice problems. In ASIACRYPT, volume 5350, pages 372-389. Springer, 2008. 13, 26, 33

[0137] LLNW14. Adeline Langlois, San Ling, Khoa Nguyen, and Huaxiong Wang. Lattice-based group signature scheme with verifier-local revocation. In PKC, pages 345-361. Springer, 2014. 26

[0138] LLNW16. Benot Libert, San Ling, Khoa Nguyen, and Huaxiong Wang. Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors. In EUROCRYPT, pages 1-31. Springer, 2016. 30

[0139] LNSW13. San Ling, Khoa Nguyen, Damien Stehl, and Huaxiong Wang. Improved zero-knowledge proofs of knowledge for the isis problem, and applications. In PKC, volume 7778, pages 107-124. Springer, 2013. 33

[0140] LNWX17. San Ling, Khoa Nguyen, Huaxiong Wang, and Yanhong Xu. Lattice-based group signatures: Achieving full dynamicity with ease. In ACNS, pages 293-312. Springer, 2017. 2, 7, 10, 14, 15, 26, 27, 28, 29, 30, 31, 33

[0141] MK14. Antonis Michalas and Nikos Komninos. The lord of the sense: A privacy preserving reputation system for participatory sensing applications. In IEEE Symposium on Computers and Communication (ISCC), pages 1-6. IEEE, 2014. 2

[0142] MP13. Daniele Micciancio and Chris Peikert. Hardness of sis and Iwe with small parameters. In CRYPTO, pages 21-39. Springer, 2013. 4

[0143] NY90. M. Naor and M. Yung. Public-key cryptosystems provably secure against chosen ciphertext attacks. In STOC, pages 427-437. ACM, 1990. 7, 30

[0144] Pei09. Chris Peikert. Public-key cryptosystems from the worst-case shortest vector problem. In STOC, pages 333-342. ACM, 2009. 4

[0145] Pei10. Chris Peikert. An efficient and parallel gaussian sampler for lattices. CRYPTO, pages 80-97. Springer, 2010. 19

[0146] PVW08. Chris Peikert, Vinod Vaikuntanathan, and Brent Waters. A framework for efficient and composable oblivious transfer. In CRYPTO, pages 554-571. Springer, 2008. 12, 30

[0147] Reg05. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In STOC, pages 84-93. ACM Press, 2005. 4, 7, 19, 30

[0148] RKZF00. Paul Resnick, Ko Kuwabara, Richard Zeckhauser, and Eric Friedman. Reputation systems. Communications of the ACM, 43(12):45-48, 2000. 1

[0149] RZ02. Paul Resnick and Richard Zeckhauser. Trust among strangers in internet transactions: Empirical analysis of ebay's reputation system. In The Economics of the Internet and E-commerce, pages 127-157. Emerald Group Publishing Limited, 2002. 2

[0150] SKCD16. Kyle Soska, Albert Kwon, Nicolas Christin, and Srinivas Devadas. Beaver: A decentralized anonymous marketplace with secure reputation. Cryptology ePrint Archive, Report 2016/464, 2016. 2

[0151] Ste96. Jacques Stern. A new paradigm for public key identification. IEEE Transactions on Information Theory, 42(6):1757-1768, 1996. 33

[0152] Ste06. Sandra Steinbrecher. Design options for privacy-respecting reputation systems within centralised internet communities. Security and Privacy in Dynamic Environments, pages 123-134, 2006. 2

[0153] ZWC.sup.+16. Ennan Zhai, David Isaac Wolinsky, Ruichuan Chen, Ewa Syta, Chao Teng, and Bryan Ford. Anonrep: Towards tracking-resistant anonymous reputation. In NSDI, pages 583-596, 2016. 2

A Proof of Theorem 1

[0154] Proof. Provided with an adversary 6z,91 for the tag-indistinguishability experiment with advantage that makes at most Q random oracle queries, we construct an algorithm for the LW problem having advantage negl. In particular, is given ((A.sub.i, b.sub.i).sub.q.sup.mw.sub.q.sup.w).sub.i[Q]as the LWE challenge, where b.sub.i=A.sub.i.sup.Ts+e.sub.i for some s and e.sub.i or b.sub.i.sub.q.sup.w. First, samples vectors s.sub.i for i[Q] and prepares vectors of the form (b.sub.i.sup.(0),b.sub.i.sup.(1))=(b.sub.i+A.sub.i.sup.Ts+.sub.i,b.sub.iA.sub.i.sup.Tse.sub.i). Then, using standard discrete Gaussian techniques (See. [Reg05, Pei10]), in case b.sub.i is of the form A.sub.i.sup.Ts+e.sub.i, we can prove that the distributions of (b.sub.i.sup.(0),b.sub.i.sup.(1)) are statistically close to (A.sub.i.sup.Ts.sup.(0)+e.sub.i.sup.(0), A.sub.i.sup.Ts.sup.(1)+e.sub.i.sup.(1)) where s.sup.(j).sub.,and e.sub.i.sup.(j).sub.,for all j{0,1},i[Q]. We emphasize that all secret vectors s.sup.(j) and error vectors e.sub.i.sup.(j) are distributed independently..sup.7 Here, due to our parameter selection, with all but negligible probability we would have s.sup.(0),s.sup.(1). Below, we describe how simulates the tag-indistinguishability experiment for . Without loss of generality, we assume for simplicity that the messages queried to the tag oracle and the challenge message I* outputted by are always queried to the random oracle (.Math.) beforehand. .sup.7 If these vectors were distributed according to the continuous Gaussian distributions, this would trivially follow from the convolution property of the continuous Gaussian distributions. However, in the case for discrete Gaussian distribution, we have to take care of some subtleties, since in general the convolution property does not hold.

[0155] At the beginning of the experiment initializes the two sets V.sub.0,V.sub.1 and also a counter c:=1. When submits a random oracle query on I, it checks wether I has already been queried. If so, it outputs the previously returned matrix. Otherwise, it returns A.sub.c and programs the random oracle so that (i)=A.sub.c. Finally, it increments c:=c+1. When A queries the tag oracle on (j,I), proceeds with the two If statements depicted in FIG. 1 as done by the real tag oracle. For the Else statement, retrieves A.sub.c=(I) for some c[Q] and sets the corresponding LWE vector b.sub.c.sup.(j) as the tag . Finally it appends (I,) to V.sub.j and returns . For the challenge tag, first retrieves A.sub.c*=(I*) for some c*[Q]. Then, if is simulating the) tag-indistinguishability experiment for b{0, 1}, it returns b.sub.c*.sup.(b) as the challenge tag * to . The rest is the same.

[0156] In case is given valid LWE samples, perfectly simulates the two tag-indistinguishability experiment for with all but negligible probability. Therefore, the advantage of for this simulated experiment would be negl. On the other hand, when is given random LWE samples, the challenge tag *b.sub.c*.sup.(b) is distributed uniformly random from all the tags has received via the tag oracle, since will not obtain b.sub.c*.sup.1b by definition of the experiment. Therefore, the advantage of for this simulated experiment would be exactly 0. Thus, will be able to distinguish between valid LWE samples and random LWE samples with probability negl. This concludes the proof.

B Security Experiments

[0157] We present the rest of the security experiments in FIG. 5 , but first we will define the lists/tables and oracles that are used in the security experiments. The lists/tables are defined as follows where all of them are initialized to be the empty set: table HUL for honest users and their assigned user identifier associated with some item, list BUL for users whose secret signing keys are known to the adversary, table CUL for users whose public keys are chosen by the adversary and their assigned user identifier associated with some item, list SL for all signatures that are generated by the Sign Oracle, and finally list CL for signatures that are generated by the oracle Chal.sub.b. Since every user possess a unique public key upk, whenever it is clear from context, we describe users by their associating upk. The oracles are defined as follows:

[0158] RUser(item,uid.sub.item) : It returns , if reg[item][uid.sub.item] is not defined. Otherwise, it returns the unique user upk stored in reg[item][uid.sub.item].

[0159] AddU ): This oracle does not take any inputs, and when invoked, it adds an honest user to the reputation system at the current epoch. It runs (upk, usk)UKgen(1.sup.n) and returns the user public key upk to the adversary. Finally, it initializes an empty list HUL[upk] at index upk.

[0160] CrptU(upk): It returns , if HUL[upk] is already defined. Otherwise, it creates a new corrupt user with user public key upk and initializes an empty list CUL[upk] at index upk.

[0161] SndToGM(item,upk,.Math.): It returns , if CUL[upk] is not defined or has been already queried upon the same (item,upk). Otherwise, it engages in the (Join .Math.Issue) protocol between a user upk (corrupted by the adversary) and the honest group manager. Finally, it adds the newly created user identifier uid.sub.item associated with item to list CUL[upk].

[0162] SndToU(item,upk,.Math.): It returns , if HUL[upk] is not defined or has been already queried upon the same (upk,item). Otherwise, it engages in the (Join .Math.Issue) protocol between the honest user upk and the group manager (corrupted by the adversary). Finally, it adds the newly created user identifier uid.sub.item associated with item to list HUL[upk].

[0163] RevealU (item,upk): It returns if HUL[upk] is not defined or empty. Otherwise, it returns the secret signing key gsk[itern][uid.sub.item] for all uid.sub.itemHUL[upk] to the adversary, and adds upk to BUL.

[0164] Sign(uid.sub.item,info.sub.t,item,M): It first runs XRUser(item,uid.sub.item) and returns in case X=. Otherwise, set upk=X. Then, it checks if there exists a tuple of the form (upk,uid.sub.item,-,item,-,-)SL, where denotes an arbitrary string. If so it returns . Otherwise it returns a signature on message M for item signed by the user upk assigned with the identifier uid.sub.item at epoch t. It then adds (upk,uid.sub.itemt,item,M,) to the list SL.

[0165] Chal.sub.b(info.sub.t,uid.sub.0,uid.sub.1,item,M).sup.8: It first checks that RUser(item,uid.sub.0), RUser(item,uid.sub.1) are not , and that users uid.sub.0 and uid.sub.1 are active at epoch t. If not it returns . Otherwise, it returns a signature on M by the user uid.sub.b for item at epoch t, and adds (uid.sub.0,uid.sub.1,item,M,) to the list CL. .sup.8 Here, we omit the item from the subscript of uid for better readability.

[0166] Trace(info.sub.t,item,M,): If .Math.CL, it returns the user identifier uid.sub.item, of the user who produced the signature together with a proof, with respect to the epoch t.

[0167] RepUpdate(R): It updates the groups at current epoch t.sub.current, where R is a set of active users at the current epoch to be revoked.

[0168] RReg(item,uid.sub.item): It returns reg[item][uid.sub.item]. Recall, the unique identity of the user upk is stored at this index.

[0169] MReg(item,uid.sub.item,): It modifies reg[item][uid.sub.item] to any chosen by the adversary.

C Security Proofs

C.1 Anonymity

[0170] Theorem 8 (Anonymity). Our reputation system is anonymous, assuming the hardness of the decision LWE.sub.n,q,problem.

[0171] Proof. We show that (n)(n)|negl through a series of indistinguishable intermediate experiments. In the following let E.sub.i be the event that the adversary outputs 1 in the i-th experiment Exp.sub.i. Further, let T.sub.i,1 and T.sub.i,2 denote the event that the adversary queries the Trace oracle on a valid signature (II.sub.Sign,.sub.,c.sub.1.sub.,c.sub.2), where c.sub.1 and c.sub.2 are ciphertexts of different plaintexts, in Exp.sub.i. Note that since Pr[T.sub.i,1]+Pr[T.sub.i,2]=1, we have Pr[E.sub.i]=Pr[E.sub.iT.sub.i,1]+Pr[E.sub.iT.sub.i,2].

[0172] Exp.sub.0 : This is the real experiment (n). By definition, we have Pr[E.sub.1]=Pr[(n)=1].

[0173] Exp.sub.1: This experiment is the same as Exp.sub.1 except that we add (S.sub.2, E.sub.2) to the tracing secret key tsk. Since this does not change the view of the adversary, we have Pr[E.sub.1]=Pr[E.sub.2].

[0174] Exp.sub.2: In this experiment, we change the way the Trace oracle answers to . Instead of creating an actual zero-knowledge proof II.sub.Trace, it simulates a zero-knowledge proof by programming the random oracle .sub.Trace. Due to the zero-knowledge property, this changes the view of the adversary negligibly. In particular, we have

|Pr[E.sub.1]Pr[E.sub.2]|Adv.sub.II.sub.Trace.sup.zero-knowledge=negl.

[0175] Exp.sub.3: In this experiment, we further change the way the Trace oracle answers to . Namely, when submitted a signature (II.sub.sign,,c.sub.1,c.sub.2), the Trace oracle uses S.sub.2 to decrypt c.sub.2, instead of using S.sub.1 to decrypt c.sub.1. Therefore, the view of the adversary is unchanged unless c.sub.1 and c.sub.2 are ciphertexts of different plaintexts. In particular,

[00001]$.Math.\mathrm{Pr}\left[E_2\right]-\mathrm{Pr}\left[E_3\right].Math.=.Math.\left(\mathrm{Pr}\left[E_2.Math.T_{2,1}\right]+\mathrm{Pr}\left[E_2.Math.T_{2,2}\right]\right)-\left(\mathrm{Pr}\left[E_3.Math.T_{3,1}\right]+\mathrm{Pr}\left[E_3.Math.T_{3,2}\right]\right).Math.=.Math.\mathrm{Pr}\left[E_2.Math.T_{2,2}\right]-\mathrm{Pr}\left[E_3.Math.T_{3,2}\right].Math.\max .Math.\left\{\mathrm{Pr}\left[T_{2,2}\right],\mathrm{Pr}\left[T_{3,2}\right]\right\}.$

[0176] Now, due to the soundness of our NIZKAoK for the relation II.sub.Sign, Pr[T.sub.2,2] and Pr[T.sub.3,2]are negligible. Hence, |Pr[E.sub.2]Pr[E.sub.3]|Adv.sub.II.sub.Sign.sup.zk-soundness=negl.

[0177] Exp.sub.4: In this experiment, we change the way the Chal.sub.0 oracle responds to the challenge query. Instead of creating an actual zero-knowledge proof II.sub.Sign, it simulates a zero-knowledge proof by programming the random oracle .sub.Sign. Due to the zero-knowledge property, this changes the view of the adversary negligibly. In particular, we have

|Pr[E.sub.3]Pr[E.sub.4]|Adv.sub.II.sub.Sign.sup.zero-knowledge=negl.

[0178] Exp.sub.5: In this experiment, we change the response to the challenge query so that it uses a tag instead of tag . Then, we have the following, assuming tag indistinguishability of the underlying tag scheme:

|Pr[E.sub.4]Pr[E.sub.5]|Adv.sub.LIT.sup.Tag-Ind=negl.

[0179] In particular, we construct an adversary for the tag-indistinguishability experiment, which simulates the view of . In particular, when queries the signing oracle for uid.sub.item,j on item, it invokes its tag oracle .sub.Tag(j,item) and uses the returned tag to generate a valid signature for . When queries the challenge oracle on item*, submits item* as its own challenge message and receives *, which is either a valid tag for uid.sub.0 or uid.sub.1, and simulates the challenge signature as in Exp.sub.4 using *. Since, queries the signing oracle at most n times, can successfully simulate the experiment to . It is then clear that we have the above inequality. Note that this reduction works as long as invokes the random oracle .sub.Tag a polynomial number of times, which is exactly the case we have. Due to Theorem 1, tag indistinguishability of the underlying tag scheme LWE-LIT holds assuming decision LWE.sub.m,q,.

[0180] Exp.sub.6: In this experiment, we further change the response to the challenge query so that c.sub.1 now encrypts uid.sub.item,1. By the semantic security of the encryption scheme for public key (B, P.sub.1), this change is negligible to the adversary. Note that the Trace oracle uses secret key S.sub.2 and does not require S.sub.1 in this experiment. Therefore, we have

|Pr[E.sub.5]Pr[E.sub.6]|Adv.sub.Encrypt.sup.sem-security=negl.

[0181] Exp.sub.7: This experiment is the same as the previous experiment except that the Trace oracle switches back to using secret key S.sub.1 and discards S.sub.2 as in the original experiment. Following the same argument made at Exp.sub.3, the view of the adversary is unchanged unless queries the Trace oracle on a valid signature such that c.sub.1 and c.sub.2 are cipliertexts of different plaintexts. Using the same argument as before, we obtain the following:

|Pr[E.sub.6]Pr[E.sub.7]|Adv.sub.II.sub.sign.sup.zk-soundness=negl.

[0182] Exp.sub.8: In this experiment, we change the response to the challenge query so that c.sub.2 encrypts uid.sub.1. Observe that due to the change we made in Exp.sub.5 and Exp.sub.6, (c.sub.1,c.sub.2,.sub.1) are now associated of uid.sub.item. In particular, this is the same as the Chal.sub.1 oracle. Now as done in Exp.sub.6, by the semantic security of the encryption scheme for public key (B, P.sub.2), this change is negligible to the adversary. Therefore, we have

|Pr[E.sub.7]Pr[E.sub.8]|Adv.sub.Encrypt.sup.sem-security=negl.

[0183] Exp.sub.9: In this experiment, we change back the Chal.sub.1 oracle to generate a real zero-knowledge proof for II.sub.Sign instead of generating a simulated proof. Due to the zero-knowledge property, this changes the view of the adversary negligibly. In particular, we have

|Pr[E.sub.8]Pr[E.sub.9]|Adv.sub.II.sub.Sign.sup.zero-knowledge=negl.

[0184] Exp.sub.10: This is the final experiment, where the Trace oracle answers to by a real zero-knowledge proof II.sub.Trace instead of a simulated zero-knowledge proof. Due to the zero-knowledge property, this changes the view of the adversary negligibly. In particular, we have

|Pr[E.sub.9]Pr[E.sub.10]|Adv.sub.II.sub.Trace.sup.zero-knowledge=negl.

[0185] Here, observe that Exp.sub.10 is identical to the real experiment 6(n). Namely, we have Pr[E.sub.10]=Pr[(n)=1].

[0186] Combining everything together, we have the following as desired:

|(n)(n)|negl.

C.2 Non-Frameability

[0187] Theorem 9 (Non-Frameability). Our Reputation. System is non-frameable, assuming the hardness of the SIS.sub.n,m,q,1 problem of the search faeLWE.sub.m,n,q,(or equivalently the search LWE.sub.mn,q,) problem.

[0188] Proof. Assume there exists an adversary that has a non-negligible advantage in the non-frameability experiment. For to win the experiment, he must output a tuple (uid*.sub.item*,II*.sub.Trace,info.sub.t*,item*,M*,*) such that (informally): (i) the pair (M*,*) links to some other message-signature pair (M,) corresponding to item* of an honest non-corrupt user or (ii) the proof II*.sub.Trace traces the signature * back to some honest non-corrupt user. We denote the event that case (i) (resp. (ii)) happens by E.sub.1 (resp. E.sub.2). By definition, we must have that either Pr[E.sub.1] or Pr[E.sub.2] is non-negligible. Below, we show that by using , we can construct an adversary that can either solve the search faeLWE.sub.m,n,q,problem (in case event E.sub.1 occurs) or the SIS.sub.n,m,q,problem (in case event E.sub.2 occurs) with non-negligible probability. At a high level, for either cases, runs the forking algorithm on to extract the witness from the signature *, which he would use to win either the faeLWE or SIS problem. In the following, we assume without loss of generality that guesses correctly which event E.sub.1 or E.sub.2 occurs on the first run of ; we run three times to apply the forking lemma.

[0189] In case of event E.sub.l: Assume is provided (, v).sub.q.sup.mn.sub.q.sup.n and ((B.sub.i, v.sub.i).sub.q.sup.mw.sub.q.sup.w).sub.i[Q]as the search faeLWE.sub.m,n,q,problem, where Q denotes the number of random oracle queries makes to .sub.Tag. Here, we assume (, v are the LWE samples that are noise-free and the other ((B.sub.i, v.sub.i)).sub.i[Q]are standard LWE samples, i.e., A.sup.Ts=v and B.sub.i.sup.Ts+e.sub.i=v.sub.i for some sD.sub.m.sub.,and e.sub.iD.sub.w.sub.,. Now, simulates the non-frameability experiment for by first generating the public parameters pp as in the real experiment, with the only exception that he uses the matrix provided by the faeLWE problem instead of sampling a random matrix. Namely, sets A:=.sup.T.sub.q.sup.nm. As for the random oracle queries, when is queried on .sub.Tag on the k-th (k[Q]) unique item, it programs the random oracle as .sub.Tag(item)=B.sub.i and returns B.sub.i. Here, returns the previously programmed value in case it is queried on the same item. For the other random oracles .sub.Sign, .sub.Trace, answers them as done in the real experiment. Furthermore, samples a critical user t*[N], where N denotes the number of honest users generated by via the AddU oracle, which we can assume to be polynomial. In other words, N denotes the number of upk such that a list HUL[upk] is created. Recall that may further invoke the oracles SndToU and RevealU for the users that he had added via the AddU oracle. Finally, provides pp to and starts the experiment. During the experiment, in case queries the RevealU on user t*, aborts the experiment. Since is a valid adversary, there must be at least one upk such that HUL[upk] is non-empty and upk.Math.BUL. Therefore, the probability of not aborting is at least 1/N. In the simulation, deals with all the noncritical users [N]\{t*} as in the real experiment, i.e., properly generates a new pair of (upk,usk)UKgen(1.sup.n) when queried the oracle AddU and uses upk, usk to answer the rest of the oracles. Below, we provide details on how deals with the critical user t*.

[0190] At a high level, aims to simulate the experiment so that the secret key usk.sub.t* associate to the user t* will be the solution to the search faeLWE problem, i.e., upk.sub.t*=v.sub.q.sup.n, usk.sub.t*=s.sub.q.sup.m. There are two oracle queries on which must deviate from the real experiment: AddU and Sign. In case runs the AddU to add the t*-th unique user to the reputation system, sets the user public key as upk.sub.t*=bin(vv){0, 1}.sup.nk. By this, implicitly sets the user secret key usk.sub.t*=s. Now, to answer Sign queries for user upk.sub.t*.sup.9 on item, it first retrieves B.sub.i=.sub.Tag(item) for some i[Q] and the corresponding LWE sample v.sub.i, which is essentially a valid tag . Finally, 6z,147 runs the ZKAoK simulator for the relation .sub.Sign and returns the signature =(II.sub.Sign,.sub.,c.sub.1.sub.c.sub.2) to . It also adds (uid.sub.item,t*,m,item,t,) to the list SL, where uid.sub.item,t* is the user identifier issued to user t* for item. Note that for to have queried a signature by user upk.sub.t* for item, it must have queried SndToU(item,upk.sub.t*), at which the user identifier uid.sub.item,t* is defined. Now, assuming the hardness of the underlying encryption scheme (whose security is based on a strictly weaker LWE problem than our assumption), the experiment thus far is computationally indistinguishable from the real experiment. Therefore, at some point outputs with probability .Math.Pr[E.sub.1] a tuple (uid*.sub.item*,II*.sub.Trace,info.sub.t*,item*,M*,*) such that the signature * is valid, (upk,uid.sub.item*,t,item*,M,)SL such that uid.sub.item*HUL[upk]upk.Math.BUL, and Link(gpk,item*,(M*, *), (M,))=1. Since simulates upk.sub.t* and the other .sup.9 Note that we now specify the critical user by its defined user public key. user public keys perfectly, the probability that upk.sub.t*=upk is at least 1/N. Now, if we let ,* be the two tags associated with the signatures ,*, respectively, we have

Link(gpk,item*,(M*,*),(M,))=1Link.sub.LIT(*,)=1

[0191] Now, we use the forking algorithm on to extract a witness which includes the secret key usk*=x* used to create the tag *. For a more formal and thorough discussion refer [LNWX17], Lemma 3. Here, observe that since we are using a statistically binding commitment scheme of [KTX08], x* is the actual must be the actual secret key used to construct the signature (i.e., zero-knowledge proof). Therefore, assuming that =.sub.Tag(item).sup.Ts+e.sub.i=B.sub.iTs+e.sub.i for some i[Q], we can rewrite Eq. (1) as

B.sub.i.sup.T(x*s)+e*e.sub.i2,

where e* is the noise vector used to create *. Furthermore, since the noise vectors where sampled from a -bounded distribution, we have

B.sub.i.sup.T(x*s)4.

[0192] Finally, we prepare the following lemma presented in [LLNW14].

[0193] Lemma 1 ([LLNW14], Lemma 4). Let =poly(n), q(4+1).sup.2 and w3m. Then, over the randomness of B.sub.q.sup.mw, we have

Pr[non-zero s.sub.q.sup.m:B.sup.Ts4]=negl(n).

[0194] Then, due to our parameter selections, we have s=x* with overwhelming probability. Hence, we can solve search faeLWE with non-negligible probability. In case of event E.sub.2: In this case, we can use the same argument made in the non-frameability proof of the group signature scheme of [LNWX17], i.e., we can construct an algorithm that solves the SIS.sub.n,m,q,1 problem with non-negligible probability. The reason why the same proof works for our reputation system, which is essentially a group of group signature, is because all users are assigned a unique user public key upk and all the user identifiers {uid.sub.item}.sub.item are uniquely bound to upk. In addition, it can easily be checked that the presence of the tags do not alter the proof in anyway. For the full detail, refer to [LNWX17], Lemma 3.

C.3 Public Linkability

[0195] Theorem 10 (Public Linkability). Our reputation system is unconditionally public-linkable.

[0196] Proof. We show that no such (possibly inefficient) adversary exists by assuming the linkability property of our underlying tag scheme LWE-LIT presented in Theorem 2, which holds unconditionally. Let us prove by contradiction and assume an adversary that wins the public-linkability experiment with non-negligible advantage. In particular, will at some point during the experiment output a tuple of the form (item,uid.sub.item,info.sub.t,{(M.sub.b,.sub.b,II.sub.Trace,b)}.sub.b=0,1). By the winning condition, the two tags associated with the signatures does not link. At a high level, the simulator needs to extract the secret keys usk.sub.0, usk.sub.1 embedded in the tags and check whether if usk.sub.0=usk.sub.1 actually holds as the adversary claims with the tracing proofs II.sub.Trace.sub.0,II.sub.Trace.sub.1. If the two extracted secret keys are indeed equivalent, i.e., usk.sub.0=usk.sub.1, then the simulator can use (,I=item,sk=usk.sub.0) to win the linkability experiment of the tag scheme, which is a contradiction. Therefore, the proof boils down to whether we can extract the witnesses from the two signatures .sub.0, .sub.1, which should be in contrast to the usual setting where the simulator is only required to extract a witness from a single signature , e.g., proof of non-frameability. In fact, we can extract both witnesses by in a sense running the forking lemma. twice. By standard arguments, there must be two critical random oracle queries that are used as the challenge for the NIZK proof to create the signatures .sub.0,.sub.1. Assume without a loss of generality that the critical random oracle query concerning .sub.0occurred before that of .sub.1. Then the simulator first runs the forking lemma on , where the fork is set to the point where submits the second critical random oracle query. Then, by the forking lemma, the simulator would be able to extract the witness, which includes usk.sub.1, used to create .sub.1. Then, keeping the same random tape for , the simulator further runs the forking lemma on , where the fork is now set to the point where submits the first critical random oracle query. By the same argument, the simulator will obtain usk.sub.0.

[0197] The following two theorems follow quite trivially from the proofs of the dynamic group signatures schemes of [LNWX17]. This is mainly because traceability and tracing soundness are somewhat security notions irrelevant to tags, and the proofs work similarly regardless of the presence of the tag inside the signature.

C.4 Traceability

[0198] Theorem 11 (Traceability). Our reputation system is traceable assuming the hardness of the SIS.sub.n,m,q,1 problem.

[0199] Proof. The adversary wins the traceability game in two cases; the first when he manages to output a signature that traces back to an inactive user; this only happen with negligible probability based on the security of the accumulator being used. The second winning case, is when the adversary outputs a signature that traces to an active user, but the tracer can't generate a proof of correct opening that will be accepted by the Judge; this clearly reduces to the completeness property of II.sub.Trace.

C.5 Tracing Soundness

[0200] Theorem 12 (Tracing Soundness). Our reputation system is unconditionally tracing sound.

[0201] Proof. Briefly, if the adversary manages to output a signature that traces to two different users, with two valid proofs of correct opening, then starting from this hypothesis, one can easily reach a contradiction by finding two different solutions to an LWE sample, that supposedly has, at most, one solution.

D Building Blocks

D.1 Accumulators

[0202] An accumulator scheme consists of the following PPT algorithms:

[0203] TSetup(n): On input the security parameter n, it returns the public parameter pp.

[0204] TAcc.sub.pp(R): On input the public parameter and a set R={d.sub.0, . . . , d.sub.N1}, it accumulates the data points into a value u. It then outputs u.

[0205] TWitness.sub.pp(R, d): On input the public parameter, the set R and a data point d, this algorithm outputs if d.Math.R, and outputs a witness w for the statement that d is accumulated into u otherwise.

[0206] TVerify.sub.pp(d, w, u): On input, the public parameter, the value d, the witness and the accumulated value u, it outputs 1 if w is a valid witness. Otherwise it outputs 0.

[0207] Correctness. An accumulator scheme Accum is correct if, for all ppTSetup(n), we have

TVerify.sub.pp(d,TWitness.sub.pp(R, d), TAcc.sub.pp(R))=1,

for all dR.

[0208] Security of an accumulator Consider the experiment presented in FIG. 6,

[0209] Definition 3. An accumulator scheme Accum is secure if for all PPT we have

Pr[(n)=1]negl(n).

D.2 A Lattice-Based Hash Function

[0210] Lemma 2 ([LNWX17]).

[0211] Given A=[A.sub.0|A.sub.1], .sub.q.sup.nm with A.sub.0,A.sub.1.sub.q.sup.nnk. Define the function h.sub.A as follows; h.sub.A: {0,1}.sup.nk{0,1}.sup.nk.fwdarw.{0,1}.sup.nk where

h.sub.A()=bin(A.sub.0.Math.+A.sub.1.Math. mod q){0,1}.sup.nk.

[0212] If SIS.sub.n,m,q,1 is hard, then ={h.sub.A:A.sub.q.sup.nm} is a family of collision-resistant hash functions.

[0213] Remark 1. One can easily verify that, h.sub.A(u.sub.0,u.sub.1)=u if and only if A.sub.0.Math.u.sub.0+A.sub.1.Math.u.sub.1=G.Math.u mod q. where,

[00002]$G=\left[\begin{array}{ccc}124.Math.{\mathrm{.Math.2}}^{k-1}& & \\ & \mathrm{.Math.}& \\ & & 124.Math.{\mathrm{.Math.2}}^{k-1}\end{array}\right]{}_q^{n\mathrm{nk}},$

D.3 An Accumulator Scheme from Lattices

[0214] Using this previously defined family of lattice based hash functions, we now recall the accumulator scheme presented in [LNWX17]. It consists of the following PPT algorithms:

[0215] TSetup(n): Output pp=A.sub.q.sup.nm.

[0216] TAcc.sub.A(R): Given R={d.sub.0{0,1}.sup.nk, . . . ,d.sub.N1{0,1}.sup.nk}. These values will be fed to the tree at the leaves level. For each j[0, . . . ,N1], let bin(j)=(j.sub.1, . . . ,j.sub..Math.){0,1} be the binary representation of j, and let d.sub.j=u.sub.j1, . . . ,j.Math.. Let =log N be the depth of the tree, it constructs the tree as follows; [0217] (a) At tree depth i[], we define the node value u.sub.b.sub.1, . . . ,b.sub.i as follows;

u.sub.b.sub.1, . . . ,b.sub.i=h.sub.A(u.sub.b.sub.1, . . . ,b.sub.i,0,u.sub.b.sub.1, . . . ,b.sub.i,1) (2) [0218] (b) At the top of the tree, we have the root u defined as h.sub.A(u.sub.0,u.sub.1). It finally outputs u.

[0219] TWitness.sub.A(R, d): It outputs if d.Math.R. Otherwise, there exists a j[0,N1] with binary representation given by (j.sub.1. . . ,j.sub..Math.), s.t. d=d.sub.j, it computes the witness w as follows;

w=((j.sub.1, . . . , ), (, . . . ,)){0,1({0,1(3)

for (.sub., . . . ,) calculated by algorithm TAcc.sub.A(R).

[0220] TVerify.sub.A(d, w, u): Given a witness w, where

w=((j.sub.1, . . . ,),(. . . ,w.sub.1)){0,1({0,1, (4)

the algorithm sets =d and recursively computes v.sub.i for i {1, . . . , 0}, as follows;

[00003]$\begin{array}{cc}{v}_i=\{\begin{array}{c}{h}_A\left(v_{i+1},w_{i+1}\right),\mathrm{for}.Math..Math.j_{i+1}=0,\\ h_A\left(w_{i+1},v_{i+1}\right),\mathrm{for}.Math..Math.j_{i+1}=1.\end{array}& \left(5\right)\end{array}$

[0221] If v.sub.0=u, return 1. Otherwise, return 0.

[0222] TUpdate.sub.A(bin(j),d*): Let d.sub.j be the current value at the leaf of position determined by bin(j), and let ((j.sub.1, . . . ,, (, . . . ,w.sub.j,1)) be its associated witness. It sets :=d* and recursively computes the path . . . ,v.sub.1,v.sub.0{0,1}.sup.nk as in (5). Then, it sets u:=v.sub.0,u.sub.ji:=v.sub.1; . . . ;:=;:==d*.

[0223] Theorem 13 ([LLNW16]). If the SIS.sub.n,m,q,1 problem is hard, then the lattice-based accumulator scheme is correct and secure.

D.4 Underlying Regev's Encryption Scheme

[0224] We use the Naor-Yung paradigm [NY90] to prove anonymity of our reputation system. In particular, we encrypt the identity of the signer uid twice using Regev's encryption scheme and prove in zero-knowledge that the two ciphertexts encrypt the same identity. Below, we provide the multi-bit variant of the Regev's encryption scheme for encrypting the same message twice [Reg05, KTX07, PVW08].

[0225] KeyGen.sub.Regev(1.sup.n): It samples B.sub.q.sup.nm.sup.E,S.sub.i,E.sub.ifor i {1, 2}. It then computes two LWE samples as P.sub.i=S.sub.i.sup.TB+E and sets pk.sub.Enc:=(B,P.sub.1, P.sub.2) and sk.sub.Enc:=(S.sub.1,E.sub.1).

[0226] Enc.sub.Regev((B,P.sub.1,P.sub.2), m {0,1): It samples r{0,1}.sup.m.sup.E and computes

[00004]$\left(c_1,c_2\right)=\left(\left(B.Math.r,P_1.Math.r+.Math.\frac{q}{2}.Math..Math.m\right),\left(B.Math.r,P_2.Math.r+.Math.\frac{q}{2}.Math..Math.m\right)\right){\left({}_q^n{}_q^l\right)}^2.$

[0227] Dec.sub.Regev((S.sub.1,E.sub.1),c): it parses c into (c.sub.1,c.sub.2,c.sub.3) and outputs

m:=(c.sub.2S.sub.1.sup.T.Math.c.sub.1)/(q/2).

E Zero-Knowledge Arguments for our Reputation System

[0228] We will present the the stern-like zero-knowledge argument that we use for our reputation system. We start by explaining the change that we make to the Merkle-tree used in [LNWX17] to bind it to item associated to it, then we recall the abstracted Stern-like protocols for ISIS problem. Next, we will give a sketch of the NIZKAoK for the .sub.Sign used to generate a signature/review.

E.1 A Merkle-Tree for our Reputation System

[0229] This diagram illustrates the Merkle-tree accumulator given in Section (D.3). For instance, w={(011),u.sub.010,u.sub.00u.sub.1} is the witness that proves that p.sub.3 was accumulated in a Merkle-tree whose root is u.sub.item.

E.2 Abstracted Stern-Like Zero-Knowledge Proofs

[0230] Given the following relation,

[0231] R.sub.ISIS:={((M,y)z).sub.q.sup.xD.sub.q.sup.n{1,0,1}.sup.D:zVALID(M.Math.z=y mod q)}, where VALID is to be defined. For instance, VALID could be the set of vectors that have an infinity norm bounded by a positive integer if the vector z is a single vector that is a solution to an ISIS problem, but VALID could as well be a set of conditions to be satisfied by various parts of z, when z is the concatenation of several vectors that satisfy different equations, which is the case of our reputation system. Regardless of how complex the set VALID looks like, we can always use the Stern-like protocol given in FIG. 8 to prove knowledge of a witness zVALID and that satisfies the equation M.Math.z=y, where M and y are public.

[0232] Theorem14 ([LNWX17]). If SIVP.sub.(n) problem is hard, then the stern-like protocol described in FIG. 8 is a statistical ZKAoK with perfect completeness, soundness error 2/3, and communication cost (D log q). Moreover, there exists a polynomial-time knowledge extractor that, on input a commitment CMT and 3 valid responses (RSP.sub.1, RSP.sub.2, RSP.sub.3) to all 3 possible values of the challenge CH, outputs xVALID such that A.Math.x=u mod q.

E.3 NIZKAoK for our Reputation System

[0233] Recall the relation for the NIZKAoK used in the signing algorithm;

R.sub.Sign={(A,u.sub.Tagg(item),,c.sub.1,c.sub.2,B,P.sub.1,P.sub.2),(p,w.sub.j,x,e,uid,r.sub.1,r.sub.2): p0.sup.nkTVerify.sub.A(p,w.sub.j,u)=1A.Math.x=G.Math.p mod q,(Enc.sub.Regev((B,P.sub.i),bin(j))=c.sub.i,i=1,2)=.sub.Tag(item).sup.Tx+e}

[0234] We will deal with the equations one by one; regarding TVerify.sub.A, one can easily notice that the computations given in (5) are equivalent to the following computation; For all i{1, . . . ,0},

v.sub.i=j.sub.i+1.Math.h.sub.A(v.sub.i+1,w.sub.i+1)+j.sub.i+1h.sub.A(w.sub.i+1,v.sub.i+1). (6)

[0235] Using Remark (1), eqaution (6) is equivalent to

j.sub.i+1(A.sub.0.Math.v.sub.i+1+A.sub.1.Math.w.sub.i+1)+j.sub.i+1.Math.(A.sub.0.Math.w.sub.i+1+A.sub.1.Math.v.sub.i+1)mod q=G.Math.v.sub.i (7)

[0236] Let ext(b,v), for bit b and vector v denote the vector

[00005]$\left(\begin{array}{c}\stackrel{\_}{b}.Math.v\\ b.Math.v\end{array}\right),$

Now equation (7) can be rewritten as

A.Math.ext(j.sub.i+1,v.sub.i+1)+A.Math.ext(j.sub.i+1,w.sub.i+i)=G.Math.v.sub.i mod q. (8)

[0237] We can now state that proving that TVerify.sub.A (p,w.sub.j,u)=1 is equivalent to proving the satisfiability of the following equations;

[00006]$\begin{array}{cc}\{\begin{array}{c}A.Math.\mathrm{ext}\left(j_1,v_1\right)+A.Math.\mathrm{ext}\left({\stackrel{\_}{j}}_1,w_1\right)=G.Math.u_{\mathrm{item}}.Math..Math.\mathrm{mod}.Math..Math.q,.Math.\\ A.Math.\mathrm{ext}\left(j_2,v_2\right)+A.Math.\mathrm{ext}\left({\stackrel{\_}{j}}_2,w_2\right)-G.Math.v_1=0.Math..Math.\mathrm{mod}.Math..Math.q,.Math.\\ \mathrm{.Math.}.Math..Math.\mathrm{.Math.}.Math..Math.\mathrm{.Math.}.Math.\\ A.Math.\mathrm{ext}\left(j_l,p\right)+A.Math.\mathrm{ext}\left({\stackrel{\_}{j}}_l,w_l\right)-G.Math.v_{l-1}=0.Math..Math.\mathrm{mod}.Math..Math.q,\end{array}& \left(9\right)\end{array}$

[0238] We also have the equation

A.Math.xG.Math.p=0 mod q,

which corresponds to the third clause.

[0239] Regarding Enc.sub.Regev ((B,P.sub.i)bin(j))=c.sub.i, i=1,2, we have to prove satisfiability of the following equations;

[00007]$\begin{array}{cc}\{\begin{array}{c}B.Math.r_b=c_{b,1}.Math..Math.\mathrm{mod}.Math..Math.q,\mathrm{for}.Math..Math.b=1,2.Math.\\ P_b.Math.r_b+.Math.\frac{q}{2}.Math..Math.{\left(j_1,\mathrm{.Math.}.Math.,j_l\right)}^T=c_{b,2}.Math..Math.\mathrm{mod}.Math..Math.q,\mathrm{for}.Math..Math.b=1,2.\end{array}& \left(10\right)\end{array}$

[0240] Now that we have all the equations that we need to prove their satisfiability, we can simply use (decomposition) extension-permutation techniques [Ste96, LNSW13, LNWX17], to transform all the previous equations into one big equation of the form

M.Math.z=y (11)

where z is a valid witness. Note that, to prove that p0.sup.nk, one can use the same tweak originally given in [LNSW13]; namely, during the extension phase, we will extend p{0,1}.sup.nk to p*B.sub.nk.sup.2nk1, i.e., it has 2nk1 bit length of which nk are ones. This proves that p had a least a 1 in it.

[0241] We still need to prove satisfiability of =.sub.Tag(item).sup.Tx+e. Let H=.sub.Tag(item).sup.T.sub.q.sup.nm. The tag equation can be rewritten as

H.Math.x+I.Math.e=(12)

[0242] To combine the two equations (11) and (12), one can build a bigger equation that embeds both of them, for instance, we can construct the equation

[00008]$\begin{array}{cc}\hat{M}.Math.\hat{z}=\hat{y}.Math..Math.\mathrm{where};.Math..Math.\hat{M}=\left[\begin{array}{cc}M& 0\\ 0\left|H\right|0& I\end{array}\right];\hat{z}=\left[\begin{array}{c}\underset{\_}{\mathrm{.Math.}}\\ \underset{\_}{x^{*}}\\ \underset{\_}{\mathrm{.Math.}}\\ e^{*}\end{array}\right];\hat{y}=\left[\begin{array}{c}\underset{\_}{y}\\ \end{array}\right],& \left(13\right)\end{array}$

where z=( . . . |*|. . . ).sup.T, and x* is result of the decomposion-extension applied to x.

[0243] Finally, we can simply apply the abstracted Stern-like protocol given in Fig. (E.2) to equation (13) using the commitment scheme presented in [KTX08] to generate the argument of knowledge that we need for R.sub.ISIS, which will be made interactive using the Fiat-Shamir transformation [FS86]. Note that, as we stated in Theorem 14, we get a statistical zero-knowledge argument of knowledge with soundness error 2/3 (hence the repetition -times). This is true because the underlying commitment scheme is statistically hiding and computationally binding where the binding property relies on the hardness of SIV.