A Literature Review of the Schnorr Identification Protocol

Table of ContentsClose Close

Description
Papers
RFCs
Other interesting links

Description

One of the first things I like to do when learning a new subfield is to get a rough overview of its history and development, for a multitude of reasons - it can be informative to see what applications motivated people in the past, the form that ideas take are often contingent on the path they were developed in, and sometimes there are useful older results that get forgetten or glossed over. And of course, it it doesn’t need to be said why a summary of more recent research can be useful.

The past month I’ve been playing around with the idea of doing comprehensive literature reviews of different areas of cryptography, going over each paper published on a specific protocol or topic and summarizing its results and significance, adding interesting historical details or implementations as appropriate. I’m hoping to build this out on my site over the next few years to create a really incredible resource for researchers and engineers to draw from, by creating a comprehensive indexing of everything in the field of cryptography of significance, and probably a few things of insignificance as well. This is very ambitious, and I might not finish it! But the idea seemed too fun and useful not to try.

So far I’ve only done this one post on the Schnorr identification protocol, which of course extends to include the Schnorr signature scheme. I’ve compiled every noteworthy paper here I could find. Over time I am planning to fill in the details of each paper and add other little notes that might be useful or interesting.

Note this is still a work in progress! If I missed anything, my DMs are open on X - feel free to send me a message.

Papers

Preceding Work

A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (1985)

In 1986, Fiat and Shamir published How To Prove Yourself: Practical Solutions to Identification and Signature Problems.

In their 1988 paper An Improved Protocol for Demonstrating Possession of Discrete Logarithms and Some Generalizations, Chaum, Evertse and Graaf describe a novel protocol for proving knowledge of a discrete log value.

Schnorr’s original paper

In his 1990 paper Efficient Signature Generation for Smart Cards, C.P. Schnorr invented the Schnorr signature scheme, described above, in order to “minimize the message dependent amount of computation the smart card has to perform to generate a signature”. Critically, relative to the previous state of the art in RSA signatures, the main portion of the work in computing a Schnorr signature is not dependent on the message size, making it more ideal for environments limited in computational power.

Directly related work

Provably secure and practical identification schemes and corresponding signature schemes (1993) - Blind schnorr signatures, apparently

Security Proofs for Signature Schemes (1996) - security analysis of Schnorr under discrete logarithm

Provably Secure Blind Signature Schemes (1996) - security of blind schnorr

Security Arguments for Digital Signatures and Blind Signature (2000) - security analysis of schnorr blind sigs

Proxy signatures, Revisited. (1997)

Strengthened Security for Blind Signatures (1998)

Security of Discrete Log Cryptosystems in theRandom Oracle and the Generic Model (2000) - uses RO + generic group model to prove schnorr is secure against one more forgery and blind schnorr

Provably Secure Distributed Schnorr Signatures and a (t, n) Threshold Scheme for Implicit Certificates (2001)

Securely Combining Public-Key Cryptosystems (2001)

Strong Proxy Signature and its Applications (2002)

Fully Distributed Proxy Signature Schemes (2002)

Forking Lemmas in the Ring Signatures’ Scenario (2003)

Efficient Extension of Standard Schnorr/RSA signatures into Universal Designated-Verifier Signatures (2003)

Adaptively Secure Feldman VSS and Applications to Universally-Composable Threshold Cryptography (2004) - develops a UC secure Schnorr threshold signature scheme

Another Look at “Provable Security” (2004) - discussion of Schnorr vs. DSA security

Discrete-Log-Based Signatures May Not Be Equivalent to Discrete Log (2005) - security analysis

Tamper-Evident Digital Signatures: Protecting Certification Authorities Against Malware (2005)

Revisiting Oblivious Signature-Based Envelopes (2005)

Deterministic Identity-Based Signatures for Partial Aggregation (2006)

Efficient ID-based Threshold Signature Schemes without Pairings (2006) - ID threshold sig without pairings

Two-Tier Signatures, Strongly Unforgeable Signatures, and Fiat-Shamir without Random Oracles (2007) - schnorr two tier signatures, and one time signatures

Improved Bounds on Security Reductions for Discrete Log Based Signatures (2008) - improved security analysis

On the Portability of Generalized Schnorr Proofs (2009) - seems to provide a more composable version of Schnorr identification proofs

Hash Function Requirements for Schnorr Signatures (2009) - show properties needed for hash for Schnorr sig to be secure

A Schnorr-Like Lightweight Identity-Based Signature Scheme (2009)

A supplement to Liu et al.’s certificateless signcryption scheme in the standard model (2010) - uses one time schnorr signature for something

Attacking M&M Collective Signature Scheme (2010) - finds security flaws with a collective Schnorr signature scheme

Identity Based Partial Aggregate Signature Scheme Without Pairing (2010) - based on schnorr

Limits of Provable Security From Standard Assumptions (2011) - proves schnorr cannot be proven secure in standard model using discrete log

On the Joint Security of Encryption and Signature in EMV (2011)

How not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios (2012)

Galindo-Garcia Identity-Based Signature, Improved (2012)

Digital Signatures from Challenge-Divided Σ-Protocols (2012) - new offline/online efficient variant of Schnorr signatures

On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model (2012) - proves best security bound for schnorr sigs

On the Security of One-Witness Blind Signature Schemes (2012) - proves current techniques for proving security in the RO model don’t work for schnorr blind signatures

A Non-delegatable Identity-based Designated Verifier Signature Scheme without Bilinear Pairings (2012)

Galindo-Garcia Identity-Based Signature, Revisited (2012) - new security analysis of identity schnorr

A Robust and Plaintext-Aware Variant of Signed ElGamal Encryption (2012) - adds schnorr sig to elgamal encryption

Non Observability in the Random Oracle Mode (2012) - gives security reduction when security proof can’t “observe” adversary random oracle queries

Limitations of the Meta-Reduction Technique: The Case of Schnorr Signatures (2013)

On Tight Security Proofs for Schnorr Signatures (2013)

A Secure Obfuscator for Encrypted Blind Signature Functionality (2013)

LCPR: High Performance Compression Algorithm for Lattice-Based Signatures (2014) - lossless compression for schonrr-like signatures

Short Schnorr signatures require a hash function with more than just random-prefix resistance (2015) - shows flaw with earlier hash function security result

Attribute-Based Versions of Schnorr and ElGamal (2015)

A flaw in a theorem about Schnorr signatures (2015) - flaw in “hash function requirements for schnorr signatures”

Adaptive Proofs of Knowledge in the Random Oracle Model (2015) - proves schnorr is not adaptively knowledge secure