1
$\begingroup$

The Universal Accumulator paper mentions the following for updating non-membership witness upon member deletion.

Choose $r$ such that $a\hat x − rx ∈ Z$$2^l$

What is Z$2^l$ and how can we efficiently evaluate $r$?

I suppose we need to brute force search by guessing values of r, is there any room for optimization here? Perhaps by making an educated guess about the value of r.

Update:

Can it be that $a\hat x − rx$ can be construed as $a\hat x$ $mod x$? If yes, then we can find

$\hat a = a\hat x$ $modx$

And,

$r = (a\hat x - \hat a)/x$

Am I right in assuming this?

Improve this question
$\endgroup$
2
  • $\begingroup$ Does this answer help? $\endgroup$
    – ckamath
    Commented Jul 12, 2020 at 22:05
  • $\begingroup$ thanks for your response @Occams_Trimmer, I looked at it before but that answer mentions about Update during addition only. I was able to follow that successfully but the update on deletion seems trickier. $\endgroup$
    – smedury
    Commented Jul 12, 2020 at 22:38

1 Answer 1

Reset to default
1
$\begingroup$

The updated Non-Membership Witness ($\hat a, \hat d$) upon deleting a member $\hat x$ can be calculated as follows:

$\hat a = a\hat x\mod x$

$r = (a\hat x - \hat a)/x$

$ \hat d = (d\hat c$ -r )$\mod n$

Hope this is useful to future developers trying to deconstruct these equations.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.