I am implementing ring signatures as a part of an authorization system. Since the number of users could get high enough to make computation on end-user devices infeasible, I am thinking of "subgrouping" them.

My idea is the following: There are $n$ users and there is an untrusted third party, the server $S$ which regularly publishes a random seed $s$ with a list of user identities $L$ for a new period of time. During this time, every user (there are malicous users) should base their actions on $(L, s)$: They deterministically (and preferably efficiently) determine some $k$ subgroups $L_{sub}$ they eventually use for their ring signatures. Every $L_{sub}$ should roughly contain the same number of users $n_{sub}$ and users can (and should) be part of multiple subgroups.

Furthermore, the "subgroup derival algorithm" should ensure that every user gets an equal amount of "mention", i.e. the number a user occurs in each subgroup should be roughly the same for all users. Ideally, a user would not have to first calculate all subgroups in order to retrieve just one.

The actual idea is to cut down the size of the subgroup lists $S$ would have transmit (and first build). With this approach, he would just have to transmit the member list (which he could later delta patch) and $s$.

Could such a subgroup derival algorithm be efficiently constructed? If so, how should one best proceed?

PS: I am not quite sure if this totally fits Crypto SE, but since I am asking for hints towards a secure algorithm and not a program (StackOverflow) or a generic security question (Security), I think this should be OK.

  • $\begingroup$ At a brief glance, your problem looks similar to shared secrets. Have you looked at Shamir's Secret Sharing algorithm? $\endgroup$ – John Deters May 14 '14 at 3:00
  • $\begingroup$ @netcrusher what is the point in having multiple sublists per user? Wouldnt it be ok to publish a seed to pseudorandomly permute the list per interval and then simply make sublists of $k$ succesive elements each and a user takes always the same sublist within an interval (clearly $k$ has to be chosen that the last sublist is not too small)? $\endgroup$ – DrLecter May 14 '14 at 20:16
  • $\begingroup$ Thinking about it another time, the system I've proposed above would actually harm my goal of anonymity: Each users basically posts data to a specific identifier that will stay the same. An adversary can easily deanonymize a user by checking which public keys were included in all ring signatures for posts to a specific id. $\endgroup$ – netcrusher May 14 '14 at 20:57
  • $\begingroup$ @netcrusher yes, thats definitely not good for anonymity. If you have a fixed group per user you will be fine with anonymity and if you randomly permute the list in every intervall, malicious users can not use a meaningful strategy to place themselves in specific locations in the list. $\endgroup$ – DrLecter May 14 '14 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.