Paper 2017/781

Lattice-Based Techniques for Accountable Anonymity: Composition of Abstract Stern’s Protocols and Weak PRF with Efficient Protocols from LWR

Rupeng Yang, Man Ho Au, Junzuo Lai, Qiuliang Xu, and Zuoxia Yu

Abstract

In an accountable anonymous system, a user is guaranteed anonymity and unlinkability unless some well-defined condition is met. A line of research focus on schemes that do not rely on any trusted third party capable of de-anonymising users. Notable examples include $k$-times anonymous authentication ($k$-TAA), blacklistable anonymous credentials (BLAC) and linkable ring signatures (LRS). All instances of these schemes are based on traditional number theoretic assumptions, which are vulnerable to quantum attacks. One common feature of these schemes is the need to limit the number of times a key can be (mis-)used. Traditionally, it is usually achieved through the use of a pseudorandom function (PRF) which maps a user's key to a pseudonym, along with a proof of correctness. However, existing lattice-based PRFs do not interact well with zero-knowledge proofs. To bridge this gap, we propose and develop the following techniques and primitives: We formalize the notion of weak PRF with efficient protocols, which allows a prover to convince a verifier that the function $\mathsf{F}$ is evaluated correctly. Specifically, we provide an efficient construction based on the learning with rounding problem, which uses abstract Stern's Protocol to prove $y = \mathsf{F}_k(x)$ and $y \neq \mathsf{F}_k(x)$ without revealing $x$, $y$ or $k$. We develop a general framework, which we call extended abstract Stern's protocol, to construct zero-knowledge arguments system for statements formed by conjunction and disjunction of sub-statements, who (or whose variants) are provable using abstract Stern's Protocol. Specifically, our system supports arbitrary monotonic propositions and allows a prover to argue polynomial relationships of the witnesses used in these sub-statements. As many existing lattice-based primitives also admit proofs using abstract Stern's protocol, our techniques can easily glue different primitives together for privacy-enhancing applications in a simple and clean way. Indeed, we propose three new schemes, all of which are the first of its kind, in the lattice setting. They also enjoy additional advantages over instances of the number-theoretic counterpart. Our $k$-TAA and BLAC schemes support concurrent enrollment while our LRS features logarithmic signature size without relying on a trusted setup. Our techniques enrich the arsenal of privacy-enhancing techniques and could be useful in the constructions of other schemes such as e-cash, unique group signatures, public key encryption with verifiable decryption, etc.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Lattice-Based CryptographyZero-Knowledge Arguments of KnowledgePrivacy-Preserving ProtocolAccountable Anonymity
Contact author(s)
orbbyrp @ gmail com
History
2017-08-16: received
Short URL
https://ia.cr/2017/781
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/781,
      author = {Rupeng Yang and Man Ho Au and Junzuo Lai and Qiuliang Xu and Zuoxia Yu},
      title = {Lattice-Based Techniques for Accountable Anonymity: Composition of Abstract Stern’s Protocols and Weak PRF with Efficient Protocols from LWR},
      howpublished = {Cryptology ePrint Archive, Paper 2017/781},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/781}},
      url = {https://eprint.iacr.org/2017/781}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.