The SOK protocol  proposes the only known practical method for non-interactive
authenticated key exchange. As originally described it is based on a type-1
pairing  on a supersingular elliptic curve. A type-1 pairing operates as
is a group of points
of prime order on
the curve, and
is a finite extension field of the same order, whose extension is the so-called embedding
associated with the curve. The SOK inventors were one of the first to
realise that by carefully matching the field size with the embedding
degree, that the discrete logarithm problem could remain hard in both
hence that the pairing was a suitable vehicle for cryptography.
A type-1 pairing has the property of symmetry, and it turns out that this property
is quite important to the SOK protocol as originally described. However time has not
been kind to type-1 pairings over the intervening years. For required levels of security
greater than strictly necessary due to the restricted choice of embedding degree possible
on supersingular curves, leading to inefficiencies. And for some of the most promising
families of supersingular curves, it turns out that the discrete logarithm problem in
much easier than originally expected .
The most efficient pairing is the asymmetric type-3 pairing, which
works with non-supersingular pairing-friendly curves. These operate as
is a particular group of
points, again of the order ,
but on a twisted elliptic curve defined over an extension which is a divisor of
These curves can be constructed to be a near perfect fit at any required level of
security . For example the BN curves , with an embedding degree of
an exact fit for the AES-128 equivalent level of security. But the loss of symmetry
causes a problem for the SOK protocol.
Pairings are usually written as functions of the form
, and for a
and for type-3 .
There are various ways in which a pairing may be calculated, but that is not an issue here.
It is assumed that there is no problem with hashing an arbitrary string to an element
the details are omitted.
We should also mention the type-2 pairing, which allows a pairing between a pair of
elements in .
But to preserve the symmetry property for the SOK protocol it would have
to be possible to hash arbitrary strings into the same group of order
there is no known way to do this .
2 The SOK protocol
The SOK protocol showcases the bilinearity property of the pairing
For a type-1 pairing there is also the property of symmetry
We first assume a type-1 pairing is being used. A Trusted Authority generates a master
Alice and Bob separately visit the trusted authority, and present their identities and
prove their right to those identities in some way. Alice is issued with her secret
and the hash function
hashes the identity string to a point of order
trusted authority calculation is simply the well known operation of multiplication by the
of a point on an elliptic curve. Similarly Bob is issued with the secret
Now Alice and Bob can communicate using a shared key, calculated by Alice as
Bob as .
These keys will be the same due to bilinearity and symmetry. Note that by convention
each can put their own secret as the left-hand argument of the pairing, and the
hashed identity of the other as the right-hand argument.
2.1 An application
Consider now an application of this protocol to an imagined Internet of Things (IoT)
setting . Each Thing is issued with a serial number and its own SOK secret based
on that serial number as an identity. These SOK secrets may be embedded at
the time of manufacture, by the manufacturer acting as a naturally trusted
When a Thing needs to communicate with another Thing, an action which
requires knowing only the identity of the other, both parties can activate SOK to
calculate the same key to encrypt their communication.
However in reality this description is probably a massive simplification of a real
world IoT deployment. Are the Things capable of protecting their secrets from an
attacker, do they support secure storage? Are they capable of calculating a pairing?
Do they communicate on a peer-to-peer basis, or client-server? Are the things mobile
or stationary, what is the network topology of their communication links, and
are they fixed or fluid? Are all Things created equal or do some have more
resources than others? Since we do not have a particular application in mind,
we merely suggest that SOK might be a nice fit for at least some of these
One question we can help to answer - a pairing on a BN curve at the AES-128
level of security on a Raspberry Pi computer (Version 1, 700MHz), which is often
touted as an IoT platform, can be calculated using our own software in just 86ms.
While it has to accepted that on a very low power device any pairing-based solution
may be impracticable, it may be posssible to offset poor performance by caching
keys and/or by using the SOK mechanism to bootstrap into something more
3 Migrating to a type-3 pairing
Take away the symmetry property, and things get a bit more complicated. One thing
we can exploit – in any communication context there is an initiator and a responder.
Therefore the obvious solution is to issue each entity with two secrets, one in
other in ,
as proposed by Dupont and Enge . So Alice is issued with
We call these Alice’s lefthand and righthand secrets respectively, as this
describes where they can appear in the pairing. Similarly Bob is issued with
Now if Alice initiates and Bob responds, Alice calculates the key as
and Bob can calculate
the same key as ,
where by convention the initiator uses their lefthand secret and the responder uses
their righthand secret.
That seems an appropriate and workable solution. However maybe we can do
better. Consider again the IoT setting. Now Things are divided into two categories,
Talkers and Listeners. Some Things might have only one of these attributes, some
may have both. But now this division of capabilities can be cryptographically
enforced, by issuing lefthand secrets only to talkers and righthand secrets only to
listeners. Perhaps a listener-only Thing might be lower powered, and perhaps its
secret does not need to be so vigorously defended, as a hacked listener secret may be
of less significance.
At first glance it may appear that a listener secret could still
be used to talk by exploiting bilinearity – if we cannot calculate
because we do not
possess , we could instead
calculate . But these
are not the same as
Without making any dogmatic claims, we suggest that this attribute of SOK on a
type-3 pairing may in fact be considered as a useful feature in many IoT
1. P.S.L.M. Barreto and M. Naehrig. Pairing-friendly elliptic curves of prime order.
In Selected Areas in Cryptography – SAC’2005, volume 3897 of Lecture Notes in
Computer Science, pages 319–331. Springer-Verlag, 2006.
2. R. Dupont and A. Enge. Practical non-interactive key distribution
based on pairings. Cryptology ePrint Archive, Report 2002/136, 2002.
3. D. Freeman, M. Scott, and E. Teske. A taxonomy of pairing-friendly elliptic
curves. Journal of Cryptography, 23:224 – 280, 2010.
4. S. Galbraith, K. Paterson, and N. Smart. Pairings for cryptographers. Discrete
Applied Mathematics, 156:3113–3121, 2008.
5. R. Granger, T. Kleinjung, and J. Zumbragel. Breaking 128-bit secure
supersingular binary curves. In Advances in Cryptology – Crypto 2014, volume 8617
of Lecture Notes in Computer Science, pages 126–145. Springer-Verlag, 2014.
6. L.B. Oliveira, D.F. Aranha, C.P.L. Gouvea, M. Scott, D.F. Camara, J. Lopez,
and R. Dahab. TinyPBC: Pairings for authenticated identity-based non-interactive
key distribution in sensor networks. Computer Communications, 34:485–493, 2011.
7. R. Sakai, K. Ohgishi, and M. Kasahara. Cryptosystems based on pairing. The
2000 Symposium on Cryptography and Information Security, Okinawa, Japan, 2000.