This is the first half of my 2 blog posts.
- Part1: Signal app, ABC, Lightning, and the future of the web ... This post
- Part2: Techblog: How Signal group chat works and how it integrates with Lightning ... Comming soon.
Background
Recently, the chat app Signal has been getting a lot of attention. It seems to have started when Elon Mask tweeted "Use Signal", but Jack Dorsey and Edward Snowden have also been recommending it for some time.
Signal is a chat app created by members including the founders of Whatsapp, but more than the app itself, the Signal protocol is what makes it worth it.
It focuses on anonymity and security, which are interesting features that are not present in other applications.
Anonymity is an excellent feature because it not only hides information from the server (operator), but also reduces the security cost for the operator by not exposing the user to unnecessary risk of information leakage.
The mechanism for maintaining anonymity in group chats is particularly interesting, and this article will explain why it deserves attention. The actual protocol will be explained in the next article.
But before that, I will explain about Attribute-Based Credentials as a prerequisite knowledge.
This is a technical explanation, so please skip it if you are not interested in it.
Attribute Based Credential (ABC)
Most of the explanation here is based on the explanation by Brands.
The most widely used digital credential format today is x.509, which is used in SSL/TLS.
It is basically used only to prove the authenticity of the subject's public key, which is done by having the public key (and metadata) signed in advance by a trusted certification authority.
The subject's attributes (e.g., what country is the subject from? What is their age? Name?) are either not encoded or are encoded as plain texts.
This is fine if you are trying to verify that the web service you are communicating with is the intended one, but it becomes problematic in scenarios where individuals are using it for authentication.
For example, suppose a municipality issues a digital credential as an identification card to its residents, and the user uses the credential to authenticate to another service.
In this case, we need to encode attributes in addition to the public key. In simple terms, this can be accomplished by checking the attributes at the time of issuing the digital credential and embedding the data in the document to be signed.
However, this is not enough to achieve anonymity. If a resident wants to prove his identity to another service, he will have to reveal all his information to the other party.
To prevent this, we use elliptic curve cryptography to encode the information as follows
- $Hash()$ ... Any suitable cryptographic Hash function
- || ... Concatenation of a sequence of bytes
- $G, G_1, G_2, G_3$... Elliptic Curve Shape NUMS
- $G_1$ ... Corresponding to "age".
- $G_2$ ... Corresponding to "Number of dependents".
- $G_3$ ... Corresponding to "Area of residence"
- $m_1, m_2, m_3$ ... Messages to be encoded.
- $m_1$ contains, for example, 18 if you are 18 years old.
- $m_2$ contains 2 if you have two children.
- $m_3$ is the serial number of the area of residence (a separate table is required for associating the serial number to the name of the area of residence).
- $a$ ... User's private key
- $A$ ... Corresponding public key
$$ H = G_1 * m_1 + G_2 * m_2 + G_3 * m_3 + G * a $$
and take this $H$ as the element of the credential to be signed. (This is called the Pedersen multi-Commitment of the message.)
What's nice about expressing it this way is that when you present the credential, by passing following items to a verifier,
- $H$
- the signature of the Certification Authority(issuer) on $H$ and any other information you wish to reveal
- zero-knowledge proof of knowledge about attributes and $a$.
You can reveal only the minimum necessary information you want to to the verifier. (Note that you cannot see any information about attributes just by looking at $H$.)
For zero-knowledge proofs, for example, the non-interactive Schnorr protocol can be used. It can be calculated as follows.
- Create nonce with number of messages + 1 ($w_1, w_2, w_3, w_4$)
- Compute nonce point $R := w_1 * G_1 + w_2 * G_2 + w_3 * G_3 + w_4 * G$.
- Challenge $c := Hash(R || H)$.
- $s_1 := c * m_1+ w_1$ and compute $s_2, s_3$ in the same way
- Compute $s_4 := c * a + w_4$.
- Let $(R, s_1, s_2, s_3, s_4)$ be a signature.
- The verification is done by using the public information nonce point $R$ and the credential $H$, and checking whether the following equation holds.
$$s_1 * G_1 + s_2 * G_2 + s_3 * G_3 + G * s_4 = R + cH$$.
This way, without revealing any information to the other party, you can prove 1. that $H$ is approved by the CA 2. that you know the secret values ($m_1, m_2, m_3, a$) needed to construct $H$.
In most cases, you will want to reveal certain information and then prove that it is included in the credential.
For example, if you want to prove that you are 18 years old, but do not want to divulge any other information, you can exclude$m_1 * G_1$ when calculating the nonce point above, and prove that you know the secret value corresponding to "$H - 18 * G_1$" with zero knowledge.
You can also prove that attributes are equal (without revealing each attribute), or that attributes are in a certain range (e.g., you have more than three dependents, you are more than 18 years old, etc.).
Such an authentication method using attribute-based credentials has the property of minimizing the risk of information leakage by allowing users to control their own information, and is superior to current mainstream authentication methods such as OpenID Connect.
These properties are in line with US government guidelines and [EU guidelines](https ://en.wikipedia.org/wiki/General_Data_Protection_Regulation).
Why are they not widely used?
If attribute-based credentials are so good, why haven't they become more popular?
There are many reasons, but one of the most important is that if they are to be used as an authentication infrastructure, they must be implemented as a public protocol.
If the certification authority and the verifier are different entities, it makes no sense for each of them to use whatever protocol they want.
Therefore, it is necessary to create a common protocol, but it is difficult to do this from the bottom up, so it is necessary for government agencies (or similarly influential entities) to take the lead.
MicroSoft has developed a similar framework called U-Prove. The reason why this is not so popular is probably because of this reason (and the difficulty in proving security). (For more information on security issues, see here.)
However, protecting user privacy was not considered a high priority mission for such entities. This is especially true if there is no direct way to generate revenue.
In recent years, the situation has changed with the growing need to protect personal information in web services, and the EU has placed particular emphasis on the right to control one's own information as a fundamental human right. And they have funded the creation of the Attribute-Based Credential protocol and developed Guidelines.
Hiding information from Certification Authorities
The above scheme is a simplification of the actual scheme as much as possible, and can be improved in many ways with respect to anonymity. For example
- Define the protocol in the way that when the CA looks the credential again, they cannot link the credential to the one they signed before.
- Run the protocol in the way that the CA does not see
attributes they are signing. - Define the protocol in the way that no matter how many times a credential is shown to a verifier, they will appear to be different each time.
The details are too complex to go into here, but in the case of 3 in particular, instead of presenting the credential itself, the credential is randomized with a secret value, and then it is verified that 1. the value was originally derived from another valid credential, 2. the original credential meets the authentication requirements, and 3. the value used to randomize it is known to the prover.
The credential used in the Signal also has property 3, and is called multi-show unlinkable credential.
Use anonymous credential as a commercial service.
For use cases where it is not possible to tie them together even if they are presented multiple times, it makes sense to consider a scheme where "the signer and the verifier are identical".
This is because even in a service where the server grants some rights to the user in the form of a credential, and the user then exercises those rights by presenting it, the server cannot tie the user, and thus maximum anonymity is achieved.
In fact, this is the kind of mechanism that the Signal utilizes. By making the assumption that there is no need for others to verify, computational efficiency can be increased by several to several dozen times.
It is worth noting that when credentials are used in this way, unlike the use of credentials as an identity service as explained in the previous section, the service provider does not need to cooperate with another entity for protocol compatibility, i.e., it can be released as a service on its own.
In addition, it can be easily combined with a similar mechanism for identity services when such credential schemes become popular in the future (e.g., "issue a new anonymous credential for this service only to those who have proven that they are 18 years old or older with an attribute-based credential issued by a public authority").
Thus, it can facilitate the adoption of a new authentication infrastructure in the whole society.
For those who are interested in "blockchain" applications, it may be more appealing to say that anonymous credential can be used to instantiate "tokens".
In fact, anonymous credential were originally proposed as a way to realize digital currencies.
BTC-backed stablecoins, tokens for ownership of goods, coupons, and many other possible applications of blockchains can be realized with anonymous credential, which offer advantages over blockchains in terms of anonymity, fees, and performance.
And -- here comes the important part -- traditionally there has been no incentive to provide such anonymous services.
This is because for a long time, there were only two major ways to monetize a web service.
- Offer ads to users
- Charge by credit card or PayPal
For the first option, there is a drawback that it is difficult to do so anonymously because there is a great advantage to personalizing ads with personal information. (There is an interesting exception to this, DuckDuckGo is attempting to display ads anonymously.)
In the case of the second option, anonymity is greatly compromised when linked to credit card information, making it unsuitable for anonymous services.
However, the third method is now becoming a reality.
This is, of course, billing with cryptocurrencies, especially Lightning Network (LN).
At the same time, LN billing has the great advantage of preventing spam requests.
In general, anonymous services cannot ban users who make a large number of requests, which is a major problem that strains server resources.
By issuing anonymous credentials and more generally charging for API requests with LNs, it is possible to address this problem.
Since most web services do not actually need to access to personal information (as long as you pay for it), I expect to see the rise of such anonymous web services as LN become more popular option for a payment.
The Signal is attracting attention as a forerunner of such new age web applications (at least for me).
In the next article, I will explain how Signal actually enhances the anonymity of group chats by using anonymous credentials.
Summary
- Attribute-based credentials provide excellent anonymity and security to users, but are difficult to deploy.
- By applying the mechanism of attribute-based credentials to commercial services, it is possible to build applications with high anonymity.
- In the past, there was no advantage in creating such services, but with cryptocurrency, the possibility of making it a business is beginning to be anticipated.
- Signal is attracting attention as a pioneer of such services.
