One way to protest is to file and collectively sign various kinds of petitions. But since the list of signatories of the petition is open, there are often situations when people who disagree with the “party course” are threatened and repressed by the administration.

Is it possible to make a system that allows an anonymous collection of signatures, but at the same time giving the opportunity to verify each vote? I offer you my solution to this problem.

Formulation of the problem

There is a limited circle of people, for example, students of an institute, employees of an organization, or citizens of a country. Some of them sign some message (petition, collective appeal, etc.). The proposed signing algorithm has the following properties:

1. It is possible to make sure that each signatory belongs to the specified circle of persons.
2. It is possible to verify that the majority of signatures belong to different persons.
3. It is not possible to determine who owns this or that signature.
4. It is not possible to determine whether this particular person left their signature or not.
5. Any signer can, at his request, put in place of an anonymous signature personalized.
6. Any anonymous signatory may later, at his own request, provide evidence that it was he who signed it.

')
The system is based on asymmetric cryptography , digital signature algorithms and key certification .

Preparatory stage

Each participant (in Figure 1 - A, B, ... Z ) generates a pair of keys, public and private. Let's call these keys personalized . The public key is published and confirmed by a certification authority, which may be the institute’s dean, the personnel department of an enterprise, or the state’s administrative apparatus. The task of the certificate is to confirm that the given key really belongs to the specified person and that this person has the right to participate in collective signing.


Fig. 1. Public key certification scheme

This stage is carried out once, regardless of the number of messages signed in the future. Database of certified keys can be stored centrally or distributed.

Formation of votes

Each signer generates another pair of keys - the so-called. anonymous keys Using the private key, he signs the message, and the public one publishes anonymously. Electronic signature (EDS) and the corresponding public key constitute one vote .


Fig. 2. Scheme of the formation of votes

If the signer wants to refuse anonymity, he can use his personalized key for signing and not generate anonymous keys at all.

Voice check

The primary verification of votes is that the observer (in the role of which anyone can act) verifies the signature of each vote with the help of the corresponding open anonymous key. Thus, the observer makes sure that the given voice is formed for this particular message. But so far nothing can be said either about the uniqueness of the signatories or about their belonging to the specified circle of persons.


Fig. 3. Scheme of primary voice check

Signer Verification

Further verification of the signatories. This check can be either selective or complete, depending on the number of signatories and technical capabilities.

The observer publishes a request to verify a particular voice, using an anonymous public key as an identifier. The signatory, whose key is published in the request (in Figure 4 - A ), generates a random control message and publishes it anonymously. In principle, this message can also be generated by an observer by attaching it to the request.

Then, A signs the control message with his anonymous private key. Then A chooses a certain group of individuals, including himself (in Fig. 4 - A, B, C ). It does not matter whether the signer is someone from the group, except A , besides, it is impossible to establish. And it breaks the EDS of the control message into fragments, in accordance with the number of participants in the group, and distributes these fragments among them.

The splitting into fragments is shown conditionally in the figure. Simply cutting text, even with permutation of characters, is a bad decision. It is better to use one of the secret sharing algorithms .

Each member of the group (including A himself) signs his fragment with his personalized private key and then publishes it.


Fig. 4. Signer verification scheme

Thus, the observer receives evidence that the voice was formed by someone from the group {A, B, C} , but who exactly is impossible to say. This makes it very difficult to apply repression to the signatories on the part of the administration. The size of the group can be chosen arbitrarily, the higher it is, the higher the reliability, but the more difficult (technically) to organize the distribution of fragments. It is necessary to prohibit re-verification of the voice, otherwise it is possible to calculate the signer, looking for intersections of the groups participating in each verification. Or require that the re-verification of the composition of the group has not changed.

If the signer wishes to de-anonymize, he performs all the same actions, only does not assemble the group, but simply signs the control message with his private keys: anonymous and personalized.

Distribution and signing of fragments

Let us dwell on the fragment distribution algorithm. The following requirements are imposed on it:

1. None of the group members and outside observers should not be able to find out who initiated the procedure.
2. Even if all members of the group, except A , collude, they should not be able to prove that it is A who is the initiator.
3. A person outside the group should not be able to initiate the procedure.

The latter requirement makes a simple anonymous list of fragments unusable. After all, then it becomes possible for a person “from the outside” to generate a voice and go through verification, sending fragments to the others and not signing with his personalized key.

The distribution of the fragments is shown in Fig.6. Suppose A is the initiator. He signs a random fragment with his private personalized key, and then forwards all the fragments to B. First of all, B verifies the signature A with a certified public key, and, after making sure that A is the one who claims to be, publishes the signed fragment.

B then removes the signature A from the message, signs the next fragment with his private personalized key and sends all the fragments C. Similarly, C verifies the signature B , publishes this fragment and signs the following.

At the end of the conversation, the message is again sent to A , who verifies the signature of the last participant ( C ) and publishes the last fragment.


Fig. 5. Scheme of distribution and signing of fragments

For each participant, except the initiator, the procedure looks exactly the same and there is no way to determine where the beginning of the chain is and where its end is. Even if B and C conspire and determine the sequence of shipments, A will be able to claim that he is in the chain after C (respectively, B is the initiator), and B and C will not have a way to prove the opposite.

To prevent timing attacks, the publication of signed fragments must be performed after the procedure is completed, or random delays before publication are introduced. Also, all members of the group must pre-cache public keys and certificates so that the sequence cannot be set according to the time of access to the certification server.

Verification completion

The observer, having received the signed fragments, verifies each signature using the public keys A , B and C. Then, it collects from the fragments the signature of the control message and verifies it using the original control message and the anonymous public key from the voice to be verified. If verification of all EDS is successful, verification is considered as passed.


Fig. 6. Scheme of the final stage of verification

All operations performed by an observer can be repeated by any other party, since the original data (voice, control message and signed fragments) are published in the public domain.

Conclusion

Despite the fact that the two-day search for the already existing analogues of the proposed algorithm did not give any results, I would not be surprised if it turns out that he invented another bicycle. If this is true, I will be grateful for the links. In the end, cycling is a great exercise for the brain. I will also be extremely grateful to the community for searching for inaccuracies, vulnerabilities and those places where the algorithm can be improved.

Thank you for attention!

UPD.

I really invented the bike. To solve this problem, the class of algorithms Group / Ring signatures is intended. Thanks grich for the tip!