Paper 2024/285
Mirrored Commitment: Fixing ``Randomized Partial Checking'' and Applications
Abstract
Randomized Partial Checking (RPC} was proposed by Jakobsson, Juels, and Rivest and attracted attention as an efficient method of verifying the correctness of the mixing process in numerous applied scenarios. In fact, RPC is a building block for many electronic voting schemes, including Prêt à Voter, Civitas, Scantegrity II as well as votingsystems used in realworld elections (e.g., in Australia). Mixing is also used in anonymous transfers of cryptocurrencies. It turned out, however, that a series of works showed, however, subtle issues with analyses behind RPC. First, that the actual security level of the RPC protocol is way off the claimed bounds. The probability of successful manipulation of $k$ votes is $(\frac{3}{4})^k$ instead of the claimed $\frac{1}{2^k}$ (this difference, in turn, negatively affects actual implementations of the notion within existing election systems. This is so since concrete implemented procedures of a given length were directly based on this parameter). Further, privacy guarantees that a constant number of mixservers is enough turned out to also not be correct. We can conclude from the above that these analyses of the processes of mixing are not trivial. In this paper, we review the relevant attacks, and we present MirroredRPC  a fix to RPC based on ``mirrored commitment'' which makes it optimally secure; namely, having a probability of successful manipulation of $k$ votes $\frac{1}{2^k}$. Then, we present an analysis of the privacy level of both RPC and mRPC. We show that for $n$ messages, the number of mixservers (rounds) needed to be $\varepsilon$close to the uniform distribution in total variation distance is lower bounded by: \[ r(n, \varepsilon) \geq \log_{2}{n \choose 2}/\varepsilon. \] This proof of privacy, in turn, gives insights into the anonymity of various cryptocurrencies (e.g., Zerocash) using anonymizing pools. If a random fraction $q$ of $n$ existing coins is mixed (in each block), then to achieve full anonymity, the number of blocks one needs to run the protocol for, is: \[ rb(n, q, \varepsilon) \geq  \frac{\log n + \log (n1)  \log (2\varepsilon)}{ {\log({1q^2}})}. \]
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. Minor revision. ACNS'24
 Keywords
 randomized partial checkingmixinganonymityvotingintegrityrapid mixingMarkov Chaincryptocurrencies
 Contact author(s)

Pawel Lorek @ math uni wroc pl
motiyung @ gmail com
filip zagorski @ gmail com  History
 20240223: approved
 20240220: received
 See all versions
 Short URL
 https://ia.cr/2024/285
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/285, author = {Paweł Lorek and Moti Yung and Filip Zagórski}, title = {Mirrored Commitment: Fixing ``Randomized Partial Checking'' and Applications}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/285}, year = {2024}, url = {https://eprint.iacr.org/2024/285} }