Undeniable signature

Last updated

An undeniable signature is a digital signature scheme which allows the signer to be selective to whom they allow to verify signatures. The scheme adds explicit signature repudiation, preventing a signer later refusing to verify a signature by omission; a situation that would devalue the signature in the eyes of the verifier. It was invented by David Chaum and Hans van Antwerpen in 1989. [1]

Contents

Overview

In this scheme, a signer possessing a private key can publish a signature of a message. However, the signature reveals nothing to a recipient/verifier of the message and signature without taking part in either of two interactive protocols:

The motivation for the scheme is to allow the signer to choose to whom signatures are verified. However, that the signer might claim the signature is invalid at any later point, by refusing to take part in verification, would devalue signatures to verifiers. The disavowal protocol distinguishes these cases removing the signer's plausible deniability.

It is important that the confirmation and disavowal exchanges are not transferable. They achieve this by having the property of zero-knowledge; both parties can create transcripts of both confirmation and disavowal that are indistinguishable, to a third-party, of correct exchanges.

The designated verifier signature scheme improves upon deniable signatures by allowing, for each signature, the interactive portion of the scheme to be offloaded onto another party, a designated verifier, reducing the burden on the signer.

Zero-knowledge protocol

The following protocol was suggested by David Chaum. [2]

A group, G, is chosen in which the discrete logarithm problem is intractable, and all operation in the scheme take place in this group. Commonly, this will be the finite cyclic group of order p contained in Z/nZ, with p being a large prime number; this group is equipped with the group operation of integer multiplication modulo n. An arbitrary primitive element (or generator), g, of G is chosen; computed powers of g then combine obeying fixed axioms.

Alice generates a key pair, randomly chooses a private key, x, and then derives and publishes the public key, y = gx.

Message signing

  1. Alice signs the message, m, by computing and publishing the signature, z = mx.

Confirmation (i.e., avowal) protocol

Bob wishes to verify the signature, z, of m by Alice under the key, y.

  1. Bob picks two random numbers: a and b, and uses them to blind the message, sending to Alice:
    c = magb.
  2. Alice picks a random number, q, uses it to blind, c, and then signing this using her private key, x, sending to Bob:
    s1 = cgq and
    s2 = s1x.
    Note that
    s1x = (cgq)x = (magb)xgqx = (mx)a(gx)b+q = zayb+q.
  3. Bob reveals a and b.
  4. Alice verifies that a and b are the correct blind values, then, if so, reveals q. Revealing these blinds makes the exchange zero knowledge.
  5. Bob verifies s1 = cgq, proving q has not been chosen dishonestly, and
    s2 = zayb+q,
    proving z is valid signature issued by Alice's key. Note that
    zayb+q = (mx)a(gx)b+q.

Alice can cheat at step 2 by attempting to randomly guess s2.

Disavowal protocol

Alice wishes to convince Bob that z is not a valid signature of m under the key, gx; i.e., z ≠ mx. Alice and Bob have agreed an integer, k, which sets the computational burden on Alice and the likelihood that she should succeed by chance.

  1. Bob picks random values, s ∈ {0, 1, ..., k} and a, and sends:
    v1 = msga and
    v2 = zsya,
    where exponentiating by a is used to blind the sent values. Note that
    v2 = zsya = (mx)s(gx)a = v1x.
  2. Alice, using her private key, computes v1x and then the quotient,
    v1xv2−1 = (msga)x(zsgxa)−1 = msxz−s = (mxz−1)s.
    Thus, v1xv2−1 = 1, unless z ≠ mx.
  3. Alice then tests v1xv2−1 for equality against the values:
    (mxz−1)i for i ∈ {0, 1, …, k};
    which are calculated by repeated multiplication of mxz−1 (rather than exponentiating for each i). If the test succeeds, Alice conjectures the relevant i to be s; otherwise, she conjectures random value. Where z = mx, (mxz−1)i = v1xv2−1 = 1 for all i, s is unrecoverable.
  4. Alice commits to i: she picks a random r and sends hash(r, i) to Bob.
  5. Bob reveals a.
  6. Alice confirms that a is the correct blind (i.e., v1 and v2 can be generated using it), then, if so, reveals r. Revealing these blinds makes the exchange zero knowledge.
  7. Bob checks hash(r, i) = hash(r, s), proving Alice knows s, hence z ≠ mx.

If Alice attempts to cheat at step 3 by guessing s at random, the probability of succeeding is 1/(k + 1). So, if k = 1023 and the protocol is conducted ten times, her chances are 1 to 2100.

See also

Related Research Articles

The Digital Signature Algorithm (DSA) is a public-key cryptosystem and Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular exponentiation and the discrete logarithm problem. DSA is a variant of the Schnorr and ElGamal signature schemes.

<span class="mw-page-title-main">Digital signature</span> Mathematical scheme for verifying the authenticity of digital documents

A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature on a message gives a recipient confidence that the message came from a sender known to the recipient.

<span class="mw-page-title-main">David Chaum</span> American computer scientist and cryptographer

David Lee Chaum is an American computer scientist, cryptographer, and inventor. He is known as a pioneer in cryptography and privacy-preserving technologies, and widely recognized as the inventor of digital cash. His 1982 dissertation "Computer Systems Established, Maintained, and Trusted by Mutually Suspicious Groups" is the first known proposal for a blockchain protocol. Complete with the code to implement the protocol, Chaum's dissertation proposed all but one element of the blockchain later detailed in the Bitcoin whitepaper. He has been referred to as "the father of online anonymity", and "the godfather of cryptocurrency".

<span class="mw-page-title-main">Blind signature</span> Form of digital signature

In cryptography a blind signature, as introduced by David Chaum, is a form of digital signature in which the content of a message is disguised (blinded) before it is signed. The resulting blind signature can be publicly verified against the original, unblinded message in the manner of a regular digital signature. Blind signatures are typically employed in privacy-related protocols where the signer and message author are different parties. Examples include cryptographic election systems and digital cash schemes.

A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value while keeping it hidden to others, with the ability to reveal the committed value later. Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes are binding. Commitment schemes have important applications in a number of cryptographic protocols including secure coin flipping, zero-knowledge proofs, and secure computation.

In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic-curve cryptography.

In cryptography, a Schnorr signature is a digital signature produced by the Schnorr signature algorithm that was described by Claus Schnorr. It is a digital signature scheme known for its simplicity, among the first whose security is based on the intractability of certain discrete logarithm problems. It is efficient and generates short signatures. It was covered by U.S. Patent 4,995,082 which expired in February 2008.

In cryptography, blinding is a technique by which an agent can provide a service to a client in an encoded form without knowing either the real input or the real output. Blinding techniques also have applications to preventing side-channel attacks on encryption devices.

A cryptographic protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods, often as sequences of cryptographic primitives. A protocol describes how the algorithms should be used and includes details about data structures and representations, at which point it can be used to implement multiple, interoperable versions of a program.

A replay attack is a form of network attack in which valid data transmission is maliciously or fraudulently repeated or delayed. This is carried out either by the originator or by an adversary who intercepts the data and re-transmits it, possibly as part of a spoofing attack by IP packet substitution. This is one of the lower-tier versions of a man-in-the-middle attack. Replay attacks are usually passive in nature.

KCDSA is a digital signature algorithm created by a team led by the Korea Internet & Security Agency (KISA). It is an ElGamal variant, similar to the Digital Signature Algorithm and GOST R 34.10-94. The standard algorithm is implemented over , but an elliptic curve variant (EC-KCDSA) is also specified.

The Cramer–Shoup system is an asymmetric key encryption algorithm, and was the first efficient scheme proven to be secure against adaptive chosen ciphertext attack using standard cryptographic assumptions. Its security is based on the computational intractability of the decisional Diffie–Hellman assumption. Developed by Ronald Cramer and Victor Shoup in 1998, it is an extension of the ElGamal cryptosystem. In contrast to ElGamal, which is extremely malleable, Cramer–Shoup adds other elements to ensure non-malleability even against a resourceful attacker. This non-malleability is achieved through the use of a universal one-way hash function and additional computations, resulting in a ciphertext which is twice as large as in ElGamal.

The ElGamal signature scheme is a digital signature scheme which is based on the difficulty of computing discrete logarithms. It was described by Taher Elgamal in 1985.

In public-key cryptography, the Station-to-Station (STS) protocol is a cryptographic key agreement scheme. The protocol is based on classic Diffie–Hellman, and provides mutual key and entity authentication. Unlike the classic Diffie–Hellman, which is not secure against a man-in-the-middle attack, this protocol assumes that the parties have signature keys, which are used to sign messages, thereby providing security against man-in-the-middle attacks.

In cryptography, a Lamport signature or Lamport one-time signature scheme is a method for constructing a digital signature. Lamport signatures can be built from any cryptographically secure one-way function; usually a cryptographic hash function is used.

In cryptography, a ring signature is a type of digital signature that can be performed by any member of a set of users that each have keys. Therefore, a message signed with a ring signature is endorsed by someone in a particular set of people. One of the security properties of a ring signature is that it should be computationally infeasible to determine which of the set's members' keys was used to produce the signature. Ring signatures are similar to group signatures but differ in two key ways: first, there is no way to revoke the anonymity of an individual signature; and second, any set of users can be used as a signing set without additional setup.

Digital credentials are the digital equivalent of paper-based credentials. Just as a paper-based credential could be a passport, a driver's license, a membership certificate or some kind of ticket to obtain some service, such as a cinema ticket or a public transport ticket, a digital credential is a proof of qualification, competence, or clearance that is attached to a person. Also, digital credentials prove something about their owner. Both types of credentials may contain personal information such as the person's name, birthplace, birthdate, and/or biometric information such as a picture or a finger print.

In cryptography, implicit certificates are a variant of public key certificate. A subject's public key is reconstructed from the data in an implicit certificate, and is then said to be "implicitly" verified. Tampering with the certificate will result in the reconstructed public key being invalid, in the sense that it is infeasible to find the matching private key value, as would be required to make use of the tampered certificate.

In cryptography, the Niederreiter cryptosystem is a variation of the McEliece cryptosystem developed in 1986 by Harald Niederreiter. It applies the same idea to the parity check matrix, H, of a linear code. Niederreiter is equivalent to McEliece from a security point of view. It uses a syndrome as ciphertext and the message is an error pattern. The encryption of Niederreiter is about ten times faster than the encryption of McEliece. Niederreiter can be used to construct a digital signature scheme.

Digital signatures are a means to protect digital information from intentional modification and to authenticate the source of digital information. Public key cryptography provides a rich set of different cryptographic algorithms the create digital signatures. However, the primary public key signatures currently in use will become completely insecure if scientists are ever able to build a moderately sized quantum computer. Post quantum cryptography is a class of cryptographic algorithms designed to be resistant to attack by a quantum cryptography. Several post quantum digital signature algorithms based on hard problems in lattices are being created replace the commonly used RSA and elliptic curve signatures. A subset of these lattice based scheme are based on a problem known as Ring learning with errors. Ring learning with errors based digital signatures are among the post quantum signatures with the smallest public key and signature sizes

References

  1. ↑ Chaum, David; van Antwerpen, Hans (1990). "Undeniable Signatures". Advances in Cryptology — CRYPTO' 89 Proceedings. Lecture Notes in Computer Science. Vol. 435. pp. 212–216. doi:10.1007/0-387-34805-0_20. ISBN   978-0-387-97317-3.
  2. ↑ Chaum, David (1991). "Zero-Knowledge Undeniable Signatures (Extended abstract)". Advances in Cryptology — EUROCRYPT '90. Lecture Notes in Computer Science. Vol. 473. pp. 458–462. doi: 10.1007/3-540-46877-3_41 . ISBN   978-3-540-53587-4.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.