Paper 2021/1385

BlindOR: An Efficient Lattice-Based Blind Signature Scheme from OR-Proofs

Nabil Alkeilani Alkadri, Helmholtz Center for Information Security
Patrick Harasser, TU Darmstadt
Christian Janson, TU Darmstadt

An OR-proof is a protocol that enables a user to prove the possession of a witness for one of two (or more) statements, without revealing which one. Abe and Okamoto (CRYPTO 2000) used this technique to build a partially blind signature scheme whose security is based on the hardness of the discrete logarithm problem. Inspired by their approach, we present BlindOR, an efficient blind signature scheme from OR-proofs based on lattices over modules. Using OR-proofs allows us to reduce the security of our scheme from the MLWE and MSIS problems, yielding a much more efficient solution compared to previous works.

Note: We would like to note that a subsequent work by Kastner et al. ( revisits the proof of the one-more unforgeability (OMUF) property by Abe and Okamoto (CRYPTO 2000). It provides a comprehensive analysis of the OMUF property, achieving similar bounds as in the original proof and showing that the reduction can extract the desired witness from two forking runs of the adversary with high probability. This turns out to be non-trivial to prove in the context of OR-proofs. Therefore, the success probability of our proof requires further analysis, as it uses a similar approach.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. 20th International Conference on Cryptology and Network Security (CANS 2021)
Blind signaturesOR-proofLattice-based cryptography
Contact author(s)
nabil alkadri @ cispa de
patrick harasser @ tu-darmstadt de
christian janson @ tu-darmstadt de
2023-01-10: last of 2 revisions
2021-10-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nabil Alkeilani Alkadri and Patrick Harasser and Christian Janson},
      title = {BlindOR: An Efficient Lattice-Based Blind Signature Scheme from OR-Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1385},
      year = {2021},
      doi = {10.1007/978-3-030-92548-2_6},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.