You get a bonus - 1 coin for daily activity. Now you have 1 coin

Blind Signature Blind Signature

Lecture



Blind Signature ( Blind Signature ) is a type of EDS, a feature of which is that the signer cannot know the exact contents of the document being signed. The concept of a blind signature was invented by David Chaum ( Eng. ) [1] in 1982, he also proposed the first implementation through the RSA algorithm. The security of the blind signature scheme was based on the difficulty of factoring large compound numbers. Since then, a large number of other schemes have been proposed [2] [3].

Content

  • 1Description
  • 2 Blind signature algorithms
    • 2.1 Fully blind signature
    • 2.2 Blind signature
      • 2.2.1 RSA Protocol
      • 2.2.2 Blind signature based on EDS Schnorr
      • 2.2.3 Blind signature based on GOST R 34.10-94
        • 2.2.3.1 Parameters:
        • 2.2.3.2Calculation:
        • 2.2.3.3 Verification:
      • 2.2.4 Blind signature based on STB 1176.2-99 standard
    • 2.3 Collective blind signature
      • 2.3.1 Check collective blind signature
  • 3Application
    • 3.1Bank systems
    • 3.2Secret Vote
  • 4Speak of Blind Signature
  • 5Notes
  • 6 Literature

Description

The main idea of ​​blind signatures is as follows:

  • Sender A encrypts the document and sends it to Side B.
  • Side B, without seeing the contents of the document, signs it and returns back to side A.
  • Side A removes its cipher, leaving only the signature of side B on the document.

Upon completion of this protocol, Party B does not know anything about the message t, nor about the signature of this message.

This scheme can be compared with the envelope in which the document and the copying sheet are placed. If you sign an envelope, the signature will be imprinted on the document, and when the envelope is opened, the document will already be signed.

The purpose of a blind signature is to prevent the signer B from reading the message of party A, which he signs, and with the corresponding signature under this message. Therefore, in the future, the signed message cannot be associated with party A.

The secure blind signature scheme should satisfy 3 properties, namely:

1) Zero disclosure . This property helps the user to get a signature on this message without disclosing the message to the signer.

2) non-traceability . The signer cannot track a signature-message pair after the user has published a signature on his message.

3) The simplicity . Only the signer can generate a valid signature. This property is the most important and must be satisfied for all signature schemes.

Due to the properties of zero disclosure and non-traceability, the blind signature scheme can be widely used in applications that require confidentiality, for example, in electronic voting systems [4] [5] [6] [7].

Blind signature algorithms

Fully blind signature

Given the situation: Bob - notary. Alice needs him to sign the document, having no idea about its content. Bob only assures that the document is notarized at the indicated time. Then they act according to the following algorithm:

  Blind Signature Blind Signature

In this scheme, Alice wants Bob to blindly sign the message {\ displaystyle m}   Blind Signature Blind Signature . For this:

  1. Alice encrypts message {\ displaystyle m}   Blind Signature Blind Signature function {\ displaystyle f}   Blind Signature Blind Signature receiving the encrypted message {\ displaystyle c = f (m)}   Blind Signature Blind Signature .
  2. Alice sends an encrypted message to Bob.
  3. Bob blindly (because he does not know what is inside) signs the message {\ displaystyle c}   Blind Signature Blind Signature function {\ displaystyle g}   Blind Signature Blind Signature , getting {\ displaystyle c ^ {'} = g (c) = g (f (m))}   Blind Signature Blind Signature .
  4. Bob sends {\ displaystyle c ^ {'}}   Blind Signature Blind Signature back to Alice.
  5. Alice gets {\ displaystyle c ^ {'}}   Blind Signature Blind Signature and removes its encryption by getting: {\ displaystyle c ^ {''} = g (f (m)) * f ^ {- 1} = g (m)}   Blind Signature Blind Signature .

This protocol works only if the signature and encryption functions are commutative.

Blind signature

  1. Bob prepares n documents on each of which is written some unique word (the more n, the less Bob has chances to cheat).
  2. Bob masks each document with a unique masking factor and sends them to Alice.
  3. Alice receives all the documents and randomly selects n-1 of them.
  4. Alice asks Bob to send masking factors for selected documents.
  5. Bob does it.
  6. Alice opens the n-1 documents and makes sure that they are correct.
  7. Alice signs the remaining document and sends it to Bob.
  8. Now Bob has a document signed by Alice with a unique word that Alice does not know.

RSA protocol

The first implementation of blind signatures was carried out by Chaum using the RSA cryptosystem:

Suppose that initially Bob has a public key {\ displaystyle (p, e)}   Blind Signature Blind Signature where {\ displaystyle p}   Blind Signature Blind Signature is a module, and {\ displaystyle e}   Blind Signature Blind Signature - public key exponent.

  1. Alice selects random masking factor {\ displaystyle r}   Blind Signature Blind Signature mutually simple with {\ displaystyle p}   Blind Signature Blind Signature , and computes {\ displaystyle m ^ {'} \ equiv mr ^ {e} {\ bmod {p}}}   Blind Signature Blind Signature .
  2. Alice sends {\ displaystyle m ^ {'}}   Blind Signature Blind Signature through the open channel to Bob.
  3. Bob computes {\ displaystyle s ^ {'} \ equiv (m ^ {'}) ^ {d} {\ bmod {p}}}   Blind Signature Blind Signature using your private key {\ displaystyle (p, d)}   Blind Signature Blind Signature .
  4. Bob sends {\ displaystyle s ^ {'}}   Blind Signature Blind Signature back to Alice.
  5. Alice removes her original disguise and gets the original message signed by Bob {{displaystyle m}   Blind Signature Blind Signature as follows: {\ displaystyle s \ equiv s ^ {'} * r ^ {- 1} {\ bmod {p}} \ equiv m ^ {d} {\ bmod {p}}}   Blind Signature Blind Signature .

Chaum invented a whole family of more complex blind signature algorithms under the general name unexpected blind signatures . Their schemes are even more complicated, but they provide more opportunities [1].

Blind signature based on EDS Schnorr

Let Alice want to sign the message {\ displaystyle m}   Blind Signature Blind Signature in Bob so that, firstly, Bob could not get acquainted with the message during the signature, secondly, so that Bob could not subsequently receive the message {\ displaystyle m}   Blind Signature Blind Signature and the corresponding signature to identify the user who initiated the blind signature protocol for this particular message (Alice). This protocol is implemented as follows:

  1. Alice initiates interaction with Bob.
  2. Bob sends the value of {\ displaystyle R = a ^ {k} \ mod p} to Alice   Blind Signature Blind Signature .
  3. Alice calculates the values ​​{\ displaystyle R ^ {'} = Ra ^ {- w} y ^ {- t} \ mod y}   Blind Signature Blind Signature (w and t are random numbers not exceeding {\ displaystyle y}   Blind Signature Blind Signature ), {\ displaystyle E ^ {'} = H (m || R ^ {'})}   Blind Signature Blind Signature and {\ displaystyle E = E ^ {'} + t \ mod y}   Blind Signature Blind Signature and then sends Bob the value {\ displaystyle E}   Blind Signature Blind Signature .
  4. Bob calculates the value of {\ displaystyle S}   Blind Signature Blind Signature such that {\ displaystyle R = a ^ {S} y ^ {E} \ mod p}   Blind Signature Blind Signature and sends {\ displaystyle S}   Blind Signature Blind Signature Alice
  5. Alice calculates the signature {\ displaystyle (E ^ {'}, S ^ {'})}   Blind Signature Blind Signature where {\ displaystyle E ^ {'} = E ^ {- t} \ mod y}   Blind Signature Blind Signature and {\ displaystyle S ^ {'} = Sw \ mod y}   Blind Signature Blind Signature which is genuine with respect to the message {\ displaystyle m}   Blind Signature Blind Signature [eight].

Evidence

The authenticity of the signature is proved as follows. From {\ displaystyle R = a ^ {S} y ^ {E} \ mod p}   Blind Signature Blind Signature should {\ displaystyle Ra ^ {- w} y ^ {- t} = a ^ {Sw} y ^ {Et} modp}   Blind Signature Blind Signature and {\ displaystyle R ^ {'} = a ^ {S ^ {'}} y ^ {E ^ {'}} \ mod p}   Blind Signature Blind Signature . In this case, the problem of anonymity is solved, since any triple {\ displaystyle (R, S, E)}   Blind Signature Blind Signature from the set of such triples that were formed by Bob, can be matched with the signature {\ displaystyle (E ^ {'}, S ^ {'})}   Blind Signature Blind Signature to this document {\ displaystyle m}   Blind Signature Blind Signature . Indeed, we have: {\ displaystyle R = a ^ {S} y ^ {E} \ mod p}   Blind Signature Blind Signature and {\ displaystyle R ^ {'} = a ^ {S ^ {'}} y ^ {E ^ {'}} \ mod p}   Blind Signature Blind Signature {\ displaystyle \ Rightarrow}   Blind Signature Blind Signature {\ displaystyle R ^ {'} / R \ equiv a ^ {S ^ {'} - S} y ^ {E ^ {'} - E} \ mod p \ equiv a ^ {- w} y ^ {- t } \ mod p}   Blind Signature Blind Signature i.e. with an equiprobable random selection of the terms {\ displaystyle w}   Blind Signature Blind Signature and {\ displaystyle t}   Blind Signature Blind Signature signature {\ displaystyle (E ^ {'}, S ^ {'})}   Blind Signature Blind Signature with equal probability, it was generated from any triplet included in the set of triples formed by the signer. Note also that Bob does not even have the opportunity to prove that at the time of the signature of this document {\ displaystyle m}   Blind Signature Blind Signature he was not acquainted with him.

Blind signature based on GOST R 34.10-94

Options:

p is a prime number, 510 ≤ | p | ≤ 512 (or 1022 ≤ | p | ≤ 1024), where | p | - the bit width of the binary representation of the number p.

q is a large prime divisor of p-1, 255 ≤ | q | ≤ 256 (or 511 ≤ | q | ≤ 512)

α ≠ 1, α < p , {\ displaystyle \ alpha ^ {q}}   Blind Signature Blind Signature mod p = 1.

Calculation:

  1. It is necessary to generate random k , 1 < k < q ;
  2. R = ({\ displaystyle \ alpha ^ {k}}   Blind Signature Blind Signature mod p ) mod q is the first part of the signature;
  3. H = Hash (m) , where Hash is the hash function described in the standard GOST R 34.11-94, m is the message to be signed;
  4. S = kH + zR mod q , where z is the private key.
  5. If S = 0, then repeat steps 1-4.

Check:

  1. If R <q or S <q, then the signature is invalid. Otherwise:
  2. R '= ({\ displaystyle \ alpha ^ {R / H} y ^ {S / H}}   Blind Signature Blind Signature mod p ) mod q , where y is the public key;
  3. If R = R ' , then the signature is valid [9].

Blind signature based on STB 1176.2-99 standard

The Belarus standard provides the following protocol for generating a blind signature to the document M :

  1. It is necessary to generate a random k such that 1 < k < q and calculate {\ displaystyle R = a ^ {k}}   Blind Signature Blind Signature . These actions are performed by the signer. Next, it passes the number R to the user;
  2. The user generates random numbers ε and τ such that 1 < ε, τ < q and then calculates {\ displaystyle R '= R * y ^ {\ tau} * a ^ {\ epsilon}}   Blind Signature Blind Signature , {\ displaystyle E '= F_ {H} (R' || M)}   Blind Signature Blind Signature and E = E ' - τ mod q ; E - the first element of the signature - sent to the signer;
  3. The signer computes the second element of the signature S = (k - xE) mod q and passes it to the user;
  4. The user calculates S '= S + ε mod q .

In this description, the following parameters are used: q - the module used for calculations is simple; a is the generating element; x - private key; y is the public key [9].

Collective blind signature

Let {\ displaystyle {\ overline {y_ {1}, y_ {s}}}}   Blind Signature Blind Signature - public keys owned by s users. Suppose there is a message M that m of them want to sign. In this case, all the signatures can be combined into one, the length of which is equal to the length of the signature of one user and does not depend on m . This is implemented according to the rules of the following protocol:

  1. Each of the m users generates a random number {\ displaystyle t _ {\ alpha _ {j}}}   Blind Signature Blind Signature < p , where j = {\ displaystyle {\ overline {1, m}}}   Blind Signature Blind Signature , p is a large prime number. Then each of the m users calculates {\ displaystyle R _ {\ alpha _ {j}} = (t _ {\ alpha _ {j}}) ^ {k}}   Blind Signature Blind Signature mod p ( k is a large simple degree) and sends this number to all other users from this group.
  2. Each user calculates {\ displaystyle R = \ prod _ {j = 1} ^ {m} R _ {\ alpha _ {j}}}   Blind Signature Blind Signature mod p . Next, e = f (R, M) = RH mod q is calculated, where q is a large prime number other than p , H = Hash (M) is a hash function. The number e will be the first element of the collective signature.
  3. {\ displaystyle S _ {\ alpha _ {j}} = x _ {\ alpha _ {j}} ^ {e} t _ {\ alpha _ {j}}}   Blind Signature Blind Signature mod p - user share. Each user calculates and shares this share.
  4. Each user then computes {\ displaystyle S = \ prod _ {j = 1} ^ {m} S _ {\ alpha _ {j}}}   Blind Signature Blind Signature mod p . This is the second element of the collective signature.

Collective blind signature verification

{\ displaystyle y = \ prod _ {j = 1} ^ {m} y _ {\ alpha _ {j}}}   Blind Signature Blind Signature mod p is a shared public key. Based on this, a collective blind signature is verified using the following algorithm:

  1. Calculates {\ displaystyle R = S ^ {k} y ^ {- e}}   Blind Signature Blind Signature mod p .
  2. Calculated e '= f (R, M) = RH mod q
  3. If e ' = e , then the signature is valid. [9]

Application

Banking systems

The most widely used protocol for blind signatures found in the field of digital money. For example, in order for the depositor not to deceive the bank, such a protocol can be used: the depositor writes the same denomination of bills on a hundred documents with different numbers and deposits it in encrypted form with the bank. The bank chooses at random and demands to open 99 (or n-1) envelopes, makes sure that $ 10 is written everywhere, not $ 1000, then signs the remaining envelope blindly, without seeing the bill number.

A simpler option may be provided: for each denomination of a banknote, a bank has its own pair of public keys. Then, only the bill number is sent under the signature, and the need to verify the nominal value before the signature disappears [1].

Secret ballot

Blind signatures are used for secret voting. In the protocol of Fujioka, Okamoto and Ohta, the voter prepares a ballot paper with his choice, which he made, encrypts it with a secret key, and disguises it. Then the voter signs the ballot and sends it to the validator. The validator verifies that the signature belongs to a registered voter who has not yet voted.

If the ballot is valid, the validator signs the ballot and returns it to the voter. The voter removes the disguise, thus revealing the encrypted ballot signed by the validator. Next, the voter sends the resulting signed, encrypted ballot to the counter, which verifies the signature on the encrypted ballot.

If the ballot is valid, the counter places it on the list that will be issued after the entire vote. After the list is issued, voters verify that their ballots are on the list and send the decryption keys necessary for opening their ballots to the counter. The counter uses these keys to decrypt ballots and adds a voice to the total. After the election, the counter issues decryption keys along with encrypted ballots so that voters can independently verify the choice [10].

Blind signature vulnerabilities

The RSA algorithm can be the object of an attack, thanks to which it becomes possible to decrypt a previously signed blind message, passing it off as a message that has yet to be signed. Based on the fact that the signature process is equivalent to deciphering by the signer (using its secret key), an attacker can attach to the signature an already signed blind version of the message {\ displaystyle m}   Blind Signature Blind Signature encrypted with the signer's public key, i.e. enclose message {\ displaystyle m '}   Blind Signature Blind Signature .

{\ displaystyle {\ begin {aligned} m '' & = m'r ^ {e} {\ pmod {n}} \\ & = (m ^ {e} {\ pmod {n}} \ cdot r ^ { e}) {\ pmod {n}} \\ & = (mr) ^ {e} {\ pmod {n}} \\\ end {aligned}}}   Blind Signature Blind Signature

where {\ displaystyle m '}   Blind Signature Blind Signature - This is an encrypted version of the message. When the message is signed, the plaintext {\ displaystyle m}   Blind Signature Blind Signature easy to extract:

{\ displaystyle {\ begin {aligned} s' & = m '' ^ {d} {\ pmod {n}} \\ & = ((mr) ^ {e} {\ pmod {n}}) ^ {d } {\ pmod {n}} \\ & = (mr) ^ {ed} {\ pmod {n}} \\ & = m \ cdot r {\ pmod {n}} {\ mbox {, since}} ed \ equiv 1 {\ pmod {\ phi (n)}} \\\ end {aligned}}}   Blind Signature Blind Signature

where {\ displaystyle \ phi (n)}   Blind Signature Blind Signature - This is Euler's function. Now the message is easy to get.

{\ displaystyle {\ begin {aligned} m = s' \ cdot r ^ {- 1} {\ pmod {n}} \ end {aligned}}}   Blind Signature Blind Signature

The attack works because in this scheme the signer directly signs the message itself. In contrast, in conventional signature schemes, the signer typically signs, for example, a cryptographic hash function. Therefore, because of this multiplicative property of RSA, one key should never be used simultaneously for encryption and blind signing [8].

Notes

  1. 1 2 3 Bruce Schneier, Applied Cryptography. 2nd Edition. Protocols, algorithms and source texts in C, Triumph Publishing House, 2002.
  2. Jean Kamenic, Jean-Marc Piveto, Markus Stadler, "Blind signatures based on the discrete logarithm problem", Eurocrypt magazine, pages 428-432, Springer-Verlag, 1995.
  3. Kalyan Chakrabortu, Jean Mehta, "A stamped blind discrete logarithm problem", Journal of International Journal of Network Security, Issue 14, pages 316-319, 2012.
  4. Lung-Chang Lin, Min-Shiang Hang, Chin-Chang Chang "Enhancing Security for Anonymous Electronic Voting Through the Network", Computer Standards and Interfaces, Issue 25, pages 131-139, 2003.
  5. Tatsuaki Okamoto, "Effective blind and partially blind signatures without random predictions," Cryptography Theory, pages 80-99, Springer-Verlag, 2006.
  6. Markus Ruckert, "Blind signature on the basis of lattices", collection of articles of the conference Asiacrypt, pages 413-430, published by Springer-Verlag, 2010.
  7. Даниэль Ортис-Арройо, Клаудия Гарсия-Самора, "Очередное улучшение протокола электронного голосования Му-Варадараджана", журнал "Computer Standards and Interfaces", выпуск 29, страницы 471-480 , 2007г.
  8. 1 2 Молдовян Н.А. Практикум по криптосистемам с открытым ключом. — 2007. — 304 с. — ISBN 5-9775-0024-6.
  9. 1 2 3 Н.А. Молдовян. Теоретический минимум и алгоритмы цифровой подписи. — БВХ-Петербург, 2010. — 304 с. — ISBN 978-5-9775-0585-7.
  10. Анисимов В.В. Протоколы двух агентств Фудзиока-Окамото-Охта и Sensus. Криптографические методы защиты информации .

Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Probability theory. Mathematical Statistics and Stochastic Analysis

Terms: Probability theory. Mathematical Statistics and Stochastic Analysis