# To Schnorr and beyond (Part 1)

One

CARDINAL

of the hardest problems in applied cryptography (and perhaps all of computer science!) is explaining why our tools work the way they do. After all, we’ve been gifted an amazing basket of useful algorithms from those who came before us. Hence it’s perfectly understandable for practitioners to want to take those gifts and simply start to apply them. But sometimes this approach leaves us wondering why we’re doing certain things: in these cases it’s helpful to take a step back and think about what’s actually going on, and perhaps what was in the inventors’ heads when the tools were

first

ORDINAL

invented.

In this post I’m going to talk about signature schemes, and specifically the

Schnorr

PERSON

signature, as well as some related schemes like ECDSA. These signature schemes have a handful of unique properties that make them quite special among cryptographic constructions. Moreover, understanding the motivation of

Schnorr

PERSON

signatures can help understand a number of more recent proposals, including post-quantum schemes like Dilithium — which we’ll discuss in the

second

ORDINAL

part of this series.

As a motivation for this post, I want to talk about this tweet:

Instead of just dumping

Schnorr

PERSON

signatures onto you, I’m going to take a more circuitous approach. Here we’ll start from the very most basic building blocks (including the basic concept of an identification protocol) and then work our way gradually towards an abstract framework.

Identification protocols: our most useful building block

If you want to understand

Schnorr

PERSON

signatures, the very

first

ORDINAL

thing you need to understand is that they weren’t really designed to be signatures at all, at least not at

first

ORDINAL

. The

Schnorr

PERSON

protocol was designed as an interactive identification scheme, which can be “flattened” into the signature scheme we know and love.

An identification scheme consists of a key generation algorithm for generating a “keypair” comprising a public and secret key, as well as an interactive protocol (the “identification protocol”) that uses these keys. The public key represents its owners’ identity, and can be given out to anyone. The secret key is, naturally, secret. We will assume that it is carefully stored by its owner, who can later use it to prove that she “owns” the public key.

The identification protocol itself is run interactively between

two

CARDINAL

parties — meaning that the parties will exchange multiple messages in each direction. We’ll often call these parties the “prover” and the “verifier”, and many older papers used to give them cute names like “

Peggy

PERSON

” and “

Victor

WORK_OF_ART

”. I find this slightly twee, but will adopt those names for this discussion just because I don’t have any better ideas.

To begin the identification protocol,

Victor

PERSON

must obtain a copy of

Peggy

PERSON

’s public key.

Peggy

PERSON

for her part will possess her secret key. The goal of the protocol is for

Victor

PERSON

to decide whether he trusts

Peggy

PERSON

:

High level view of a generic interactive identification protocol. We’ll assume the public key was generated in a previous key generation phase. (No, I don’t know why the

Verifier

ORG

has a tennis racket.)

Note that this “proof of ownership” does not need to be

100%

PERCENT

perfect. We only ask that it is sound with extremely high probability. Roughly speaking, we want to ensure that if

Peggy

PERSON

really owns the key, then

Victor

PERSON

will always be convinced of this fact. At the same time, someone who is impersonating

Peggy

PERSON

— i.e., does not know her secret key — should fail to convince

Victor

PERSON

, except with some astronomically small (negligible) probability.

(Why do we accept this tiny probability of an impersonator succeeding? It turns out that this is basically unavoidable for any identification protocol. This is because the number of bits

Peggy

PERSON

sends to

Victor

PERSON

must be finite, and we already said there must exist

at least one

CARDINAL

“successful” response that will make

Victor

PERSON

accept. Hence there clearly exists an adversary who just guesses the right strings and gets lucky very ocasionally. As long as the number of bits

Peggy

PERSON

sends is reasonably large, then such a “dumb” adversary should almost never succeed, but they will do so with

non-zero

CARDINAL

probability.)

The above description is nearly sufficient to explain the security goals of an identification scheme, and yet it’s not quite complete. If it was, then there would be a very simple (and yet obviously bad) protocol that solves the problem: the Prover could simply transmit its secret key to the

Verifier

ORG

, who can presumably test that it matches with the public key:

This usually works, but don’t do this, please.

If all we cared about was solving the basic problem of proving ownership in a world with exactly one

Verifier

ORG

who only needs to run the protocol once, the protocol above would work fine! Unfortunately in the real world we often need to prove identity to multiple different Verifiers, or to repeatedly convince the same

Verifier

ORG

of our identity. The problem with the strawman proposal above is that at the end of a single execution,

Victor

PERSON

has learned

Peggy

PERSON

’s secret key (as does anyone else who happened to eavesdrop on their communication.) This means that

Victor

PERSON

, or any eavesdropper, will now be able to impersonate

Peggy

PERSON

in future interactions.

And that’s a fairly bad feature for an identification protocol. To deal with this problem, a truly useful identification protocol should add

at least one

CARDINAL

additional security requirement: at the completion of this protocol,

Victor

PERSON

(or an eavesdropper) should not gain the ability to mimic

Peggy

PERSON

’s identity to another

Verifier

ORG

. The above protocol clearly fails this requirement, since

Victor

PERSON

will now possess all of the secret information that

Peggy

PERSON

once had.

This requirement also helps to why identification protocols are (necessarily) interactive, or at least stateful: even if

Victor

PERSON

did not receive

Peggy

PERSON

’s secret key, he might still be able to record any messages sent by

Peggy

PERSON

during her execution of the protocol with him. If the protocol was fully non-interactive (meaning, it consists of exactly one message from

Peggy

PERSON

to

Victor

PERSON

) then

Victor

PERSON

could later “replay” his recorded message to some other

Verifier

ORG

, thus convincing that person that he is actually

Peggy

PERSON

. Many protocols have suffered from this problem, including older vehicle immobilizers.

The classical solution to this problem is to organize the identification protocol to have a challenge-response structure, consisting of multiple interactive moves. In this approach,

Victor

PERSON

first sends some random “challenge” message to

Peggy

PERSON

, and then

Peggy

PERSON

then constructs her response so that it is specifically based on

Victor

PERSON

’s challenge. Should a malicious

Victor

PERSON

attempt to impersonate

Peggy

PERSON

to a different

Verifier

ORG

, say

Veronica

PERSON

, the expectation is that

Veronica

ORG

will send a different challenge value (with high probability), and so

Victor

PERSON

will not be able to use

Peggy

PERSON

’s original response to satisfy

Veronica

ORG

’s new challenge.

(While interaction is generally required, in some instances we can seemingly “sneak around” this requirement by “extracting a challenge from the environment.” For example, real-world protocols will sometimes ‘bind’ the identification protocol to metadata such as a timestamp, transaction details, or the

Verifier

ORG

’s name. This doesn’t strictly prevent replay attacks — replays of

one

CARDINAL

-message protocols are always possible! — but it can help Verifiers detect and reject such replays. For example,

Veronica

PERSON

might not accept messages with out-of-date timestamps. I would further argue that, if

one

CARDINAL

squints hard enough, these protocols are still interactive. It’s just that the

first

ORDINAL

move of the interaction [say, querying the clock for a timestamp] is now being moved outside of the protocol.)

How do we build identification schemes?

Once you’ve come up with the idea of an identification scheme, the obvious question is how to build one.

The simplest idea you might come up with is to use some

one

CARDINAL

-way function as your basic building block. The critical feature of these functions is that they are “easy” to compute in

one

CARDINAL

direction (e.g., for some string x, the function F(x) can be computed very efficiently.) At the same time,

one

CARDINAL

-way functions are hard to invert: this means that given F(x) for some random input string x — let’s imagine x is something like a

128

CARDINAL

-bit string in this example — it should take an unreasonable amount of computational effort to recover x.

I’m selecting

one

CARDINAL

-way functions because we have a number of candidates for them, including cryptographic hash functions as well as fancier number-theoretic constructions. Theoretical cryptographers also prefer them to other assumptions, in the sense that the existence of such functions is considered to be one of the most “plausible” cryptographic assumptions we have, which means that they’re much likelier to exist than more fancy building blocks.

The problem is that building a good identification protocol from simple

one

CARDINAL

-way functions is challenging. An obvious starting point for such a protocol would be for

Peggy

PERSON

to construct her secret key by selecting a random string sk (for example, a

128

CARDINAL

-bit random string) and then computing her public key as pk = F(sk).

Now to conduct the identification protocol,

Peggy

PERSON

would… um… well, it’s not really clear what she would do.

The “obvious” answer would be for

Peggy

PERSON

to send her secret key sk over to

Victor

PERSON

, and then

Victor

PERSON

could just check that pk = F(sk). But this is obviously bad for the reasons discussed above:

Victor

PERSON

would then be able to impersonate

Peggy

PERSON

after she conducted the protocol with him even

one

CARDINAL

time. And fixing this problem turns out to be somewhat non-trivial!

There are, of course, some clever solutions — but each one entails some limitations and costs. A “folklore”1 approach works like this:

Instead of picking

one

CARDINAL

secret string,

Peggy

PERSON

picks N different secret strings to be her “secret key.” She now sets her “public key” to be . In the identification protocol,

Victor

PERSON

will challenge

Peggy

PERSON

by asking her for a random k-sized subset of

Peggy

PERSON

’s strings (here k is much smaller than

N.)

PERSON

Peggy

PERSON

will send back the appropriate list of k secret strings.

Victor

PERSON

will check each string against the appropriate position in

Peggy

PERSON

’s public key.

The idea here is that, after running this protocol

one

CARDINAL

time,

Victor

PERSON

learns some but not all of

Peggy

PERSON

’s secret strings. If

Victor

PERSON

was then to attempt to impersonate

Peggy

PERSON

to another person — say,

Veronica

PERSON

— then

Veronica

ORG

would pick her own random subset of k strings for

Victor

PERSON

to respond to. If this subset is identical to the

one

CARDINAL

Victor

PERSON

chose when he interacted with

Peggy

PERSON

, then

Victor

PERSON

will succeed: otherwise,

Victor

PERSON

will not be able to answer

Veronica

PERSON

’s challenge. By carefully selecting the values of

N and k

ORG

, we can ensure that this probability is very small.

2

CARDINAL

An obvious problem with this proposal is that it falls apart very quickly if

Victor

PERSON

can convince

Peggy

PERSON

to run the protocol with him multiple times.

If

Victor

PERSON

can send

Peggy

PERSON

several different challenges, he will learn many more than k of

Peggy

PERSON

’s secret strings. As the number of strings

Victor

PERSON

learns increases,

Victor

PERSON

’s ability to answer

Veronica

PERSON

’s queries will improve dramatically: eventually he will be able to impersonate

Peggy

PERSON

nearly all of the time. There are some clever ways to address this problem while still using simple

one

CARDINAL

-way functions, but they all tend to be relatively “advanced” and costly in terms of bandwidth and computation. (I promise to talk about them in some other post.)

Schnorr

PERSON

So far we have a motivation: we would like to build an identification protocol that is multi-use — in the sense that

Peggy

PERSON

can run the protocol many times with

Victor

PERSON

(or other verifiers) without losing security. And yet one that is also efficient in the sense that

Peggy

PERSON

doesn’t have to exchange a huge amount of data with

Victor

PERSON

, or have huge public keys.

Now there have been a large number of identity protocols.

Schnorr

PERSON

is not even the

first

ORDINAL

one to propose several of the ideas it uses. “

Schnorr

PERSON

” just happens to be the name we generally use for a class of efficient protocols that meet this specific set of requirements.

Some time back when

Twitter

PERSON

was still

Twitter

PERSON

, I asked if anyone could describe the rationale for the

Schnorr

PERSON

protocol in

two

CARDINAL

tweets or less. I admit I was fishing for a particular answer, and I got it from

Chris Peikert

PERSON

:

I really like

Chris

PERSON

’s explanation of the

Schnorr

PERSON

protocol, and it’s something I’ve wanted to unpack for while now. I promise that all you really need to understand this is a little bit of middle-school algebra and a “magic box”, which we’ll do away with later on.

Let’s tackle it

one

CARDINAL

step at a time.

First

ORDINAL

,

Chris

PERSON

proposes that

Peggy

PERSON

must choose “a random line.” Recalling our grade-school algebra, the equation for a line is y = mx + b, where “m” is the line’s slope and “b” its y-intercept. Hence,

Chris

PERSON

is really asking us to select a pair of random numbers (m, b). (For the purposes of this informal discussion you can just pretend these are real numbers in some range. However later on we’ll have them be elements of a very large finite field, which will eliminate many obvious objections.)

Here we will let “m” be

Peggy

PERSON

’s secret key, which she will choose

one

CARDINAL

time and keep the same forever.

Peggy

PERSON

will choose a fresh random value “b” each time she runs the protocol. Critically,

Peggy

PERSON

will put both of those numbers into a pair of

Chris

PERSON

’s magic box(es) and send them over to

Victor

PERSON

.

Finally,

Victor

PERSON

will challenge

Peggy

PERSON

to evaluate her line at one specific (random) point x that he selects. This is easy for

Peggy

PERSON

, who can compute the corresponding value y using her linear equation. Now

Victor

PERSON

possesses a point (x, y) that — if

Peggy

PERSON

answered correctly — should lie on the line defined by (m, b). He simply needs to use the “magic boxes” to check this fact.

Here’s the whole protocol:

Chris Peikert

PERSON

’s “magic box” protocol. The only thing I’ve changed from his explanation is that there are now

two

CARDINAL

magic boxes, one that contains “m” and one that contains “b“.

Victor

PERSON

can use them together to check

Peggy

PERSON

’s response y at the end of the protocol.

Clearly this is not a real protocol, since it relies fundamentally on magic. With that said, we can still observe some nice features about it.

A

first

ORDINAL

thing we can observe about this protocol is that if the final check is satisfied, then

Victor

PERSON

should be reasonably convinced that he’s really talking to

Peggy

PERSON

. Intuitively, here’s a (non-formal!) argument for why this is the case. Notice that to complete the protocol,

Peggy

PERSON

must answer

Victor

PERSON

’s query on any random x that

Victor

PERSON

chooses. If

Peggy

PERSON

, or someone impersonating

Peggy

PERSON

, is able to do this with high probability for any random point x that

Victor

PERSON

might choose, then intuitively it’s reasonable that she could (in her own head, at least) compute a similar response for a

second

ORDINAL

random point x’. Critically, given

two

CARDINAL

separate points (x,y), (x’, y’) all on the same line, it’s easy to calculate the secret slope m — ergo, a person who can easily compute points on a line almost certainly knows

Peggy

PERSON

’s secret key. (This is not a proof! It’s only an intuition. However the real proof uses a similar principle.2)

The question, then, is what

Victor

PERSON

learns after running the protocol with

Peggy

PERSON

.

If we ignore the magical aspects of the protocol, the only thing that

Victor

PERSON

“learns” by at end of the protocol is a single point (x, y) that happens to lie on the random line chosen by

Peggy

PERSON

. Fortunately, this doesn’t reveal very much about

Peggy

PERSON

’s line, and in particular, it reveals very little about her secret (slope) key. The reason is that for every possible slope value m that

Peggy

PERSON

might have chosen as her key, there exists a value b that produces a line that intersects (x, y). We can illustrate this graphically for a few different examples:

I obviously did not use a graphing tool to make this disaster.

Naturally this falls apart if

Victor

PERSON

sees

two

CARDINAL

different points on the same line. Fortunately this never happens, because

Peggy

PERSON

chooses a different line (by selecting a new b value) every time she runs the protocol. (It would be a terrible disaster if she forgot to do this!)

The existence of these magic boxes obviously makes security a bit harder to think about, since now

Victor

PERSON

can do various tests using the “boxes” to test out different values of m, b to see if he can find a secret line that matches. But fortunately these boxes are “magic”, in the sense that all

Victor

PERSON

can really do is test whether his guesses are successful: provided there are many possible values of m, this means actually searching for a matching value will take far too long to be useful.

Now, you might ask: why a line? Why not a plane, or a degree-8 polynomial?

The answer is pretty simple: a line happens to be one of the simplest mathematical structures that suits our needs. We require an equation for which we can “safely” reveal exactly

one

CARDINAL

solution, without fully constraining the terms of its equation. Higher-degree polynomials and planar equations also this capability (indeed we can reveal more points in these structures), but each has a larger and more complex equation that would necessitate a fancier “magic box.”

How do we know if the “magic box” is magic enough?

Normally when people learn

Schnorr

PERSON

, they are not taught about magic boxes. In fact, they’re typically presented with a bunch of boring details about cyclic groups.

The problem with that approach is that it doesn’t teach us anything about what we need from that magic box. And that’s a shame, because there is not one specific box we can use to realize this class of protocols. Indeed, it’s better to think of this protocol as a set of general ideas that can be filled in, or “instantiated” with different ingredients.

Hence: I’m going to try a different approach. Rather than just provide you with something that works to realize our magic box as a fait accompli, let’s instead try to figure out what properties our magical box must have, in order for it to provide us with a secure protocol.

Simulating Peggy

There are essentially

three

CARDINAL

requirements for a secure identification protocol.

First

ORDINAL

, the protocol needs to be correct — meaning that

Victor

PERSON

is always convinced following a legitimate interaction with

Peggy

PERSON

.

Second

ORDINAL

, it needs to be sound, meaning that only

Peggy

PERSON

(and not an impersonator) can convince

Victor

PERSON

to accept.

We’ve made an informal argument for both of these properties above. It’s important to note that each of these arguments relies primarily on the fact that our magic box works as advertised — i.e.,

Victor

PERSON

can reliably “test”

Peggy

PERSON

’s response against the boxed information.

Soundness

ORG

also requires that bad players cannot “unbox”

Peggy

PERSON

’s secret key and fully recover her secret slope m, which is something that should be true of any

one

CARDINAL

-way function.

But these arguments don’t dwell thoroughly on how secure the boxes must be. Is it ok if an attacker can learn a few bits of m and b? Or do they need to be completely ideal. To address these questions, we need to consider a

third

ORDINAL

requirement.

That requirement is that that

Victor

PERSON

, having run the protocol with

Peggy

PERSON

, should not learn anything more useful than he already knew from having

Peggy

PERSON

’s public key. This argument really requires us to argue that these boxes are quite strong — i.e., they’re not going to leak any useful information about the valuable secrets beyond what

Victor

PERSON

can get from black-box testing.

Recall that our basic concern here is that

Victor

PERSON

will run the protocol with

Peggy

PERSON

, possibly multiple times. At the end of each run of the protocol,

Victor

PERSON

will learn a “transcript”. This contents of this transcript are

1

CARDINAL

)

one

CARDINAL

magic box containing “b“,

2

CARDINAL

) the challenge value x that

Victor

PERSON

chose, and

3

CARDINAL

) the response y that

Peggy

PERSON

answered with. We are also going to assume that

Victor

PERSON

chose the value x “honestly” at random, so really there are

only two

CARDINAL

interesting values that he obtained from

Peggy

PERSON

.

A question we might ask is: how useful is the information in this transcript to

Victor

PERSON

, assuming he wants to do something creepy like pretend to be

Peggy

PERSON

?

Ideally, the answer should be “not very useful at all.”

The clever way to argue this point is to show that

Victor

PERSON

can perfectly “simulate” these transcripts without every even talking to

Peggy

PERSON

at all. The argument thus proceeds as follows: if

Victor

PERSON

(all by his lonesome) can manufacture a transcript that is statistically identical to the ones he’d get from talking to

Peggy

PERSON

, then what precisely has he “learned” from getting real ones from

Peggy

PERSON

at all? Implicitly the answer is: not very much.

So let’s take a moment to think about how

Victor

PERSON

might (all by himself) produce a “fake” transcript without talking to

Peggy

PERSON

. As a reminder, here’s the “magic box” protocol from up above:

One

CARDINAL

obvious (wrong) idea for simulating a transcript is that

Victor

PERSON

could

first

ORDINAL

select some random value b, and put it into a brand new “magic box”. Then he can pick x at random, as in the real protocol. But this straightforward attempt crashes pretty quickly:

Victor

PERSON

will have a hard time computing y = mx + b, since he doesn’t know

Peggy

PERSON

’s secret key m. His best attempt, as we discussed, would be to guess different values and test them, which will take too long (if the field is large.)

So clearly this approach does not work. But note that

Victor

PERSON

doesn’t necessarily need to fake this transcript “in order.” An alternative idea is that

Victor

PERSON

can try to make a fake transcript by working through the protocol in a different order. Specifically:

Victor

PERSON

can pick a random x, just as in the real protocol. Now he can pick the value y also at random.

Note that for every “m” there will exist a line that passes through (x, y). But now

Victor

PERSON

has a problem: to complete the protocol, he will need to make a new box containing “b”, such that b = y – mx.

There is no obvious way for

Victor

PERSON

to calculate b given only the information he has in the clear. To address this

third

ORDINAL

requirement, we must therefore demand a fundamentally new capability from our magic boxes. Concretely, we can imagine that there is some way to “manufacture” new magic boxes from existing ones, such that the new boxes contain a calculated value. This amounts to reversing the linear equation and then performing multiplication and subtraction on “boxed” values, so that we end up with:

What’s that, you say? This new requirement looks totally arbitrary? Well, of course it is. But let’s keep in mind that we started out by demanding magical boxes with special capabilities. Now I’m simply adding

one

CARDINAL

more magical capability. Who’s to say that I can’t do this?

Recall that the resulting transcript must be statistically identical to the ones that

Victor

PERSON

would get from

Peggy

PERSON

. It’s easy enough to show that the literal values (x, y, b) will all have the same distribution in both versions. The statistical distribution of our “manufactured magical boxes” is a little bit more complicated, because what the heck does it mean to “manufacture a box from another box,” anyway? But we’ll just specify that the manufactured ones must look identical to the ones created in the real protocol.

Of course back in the real world this matters a lot. We’ll need to make sure that our magical box objects have the necessary features, which are (

1

CARDINAL

) the ability to test whether a given (x, y) is on the line, and (

2

CARDINAL

) the ability to manufacture new boxes containing “b” from another box containing “m” and a point (x, y), while ensuring that the manufactured boxes are identical to magical boxes made the ordinary way.

How do we build a magical box?

An obvious idea might be to place the secret values m and b each into a standard

one

CARDINAL

-way function and then send over F(m) and

F(b

GPE

). This clearly achieves the goal of hiding the values of these

two

CARDINAL

values: unfortunately, it doesn’t let us do very much else with them.

Indeed, the biggest problem with simple

one

CARDINAL

-way functions is that there is

only one

CARDINAL

thing you can do with them. That is: you can generate a secret x, you can compute the

one

CARDINAL

-way function F(x), and then you can reveal x for someone else to verify. Once you’ve done this, the secret is “gone.” That makes simple

one

CARDINAL

-way functions fairly limiting.

But what if F is a different type of

one

CARDINAL

-way function that has some additional capabilities?

In

the early 1980s

DATE

many researchers were thinking about such

one

CARDINAL

-way functions. More concretely, researchers such as

Tahir Elgamal

PERSON

were looking at a then-new “candidate”

one

CARDINAL

-way function that had been proposed by

Whitfield Diffie

PERSON

and

Martin Hellman

PERSON

, for use in their eponymous key exchange protocol.

Concretely: let p be some large non-secret prime number that defines a finite field. And let g be the “generator” of some large cyclic subgroup of prime order q contained within that field.3 If these values are chosen appropriately, we can define a function F(x) as follows:

The nice thing about this function is that, provided g and p are selected appropriately, it is (

1

CARDINAL

) easy to compute this function in the normal direction (using square-and-multiply modular exponentiation) and yet is (

2

CARDINAL

) generally believed to be hard to invert. Concretely, as long x is randomly selected from the finite field defined by {

0

CARDINAL

, …, q-1}, then recovering x from F(x) is equivalent to the discrete logarithm problem.

But what’s particularly nifty about this function is that it has nice algebraic properties. Concretely, given F(a) and

F(b

GPE

) computed using the function above, we can easily compute F(a + b mod q). This is because:

Similarly, given F(a) and some known scalar c, we can compute F(a \cdot c):

We can also combine these capabilities. Given F(m) and

F(b

GPE

) and some x, we can compute F(y) where y = mx + b mod q. Almost magically means we can compute linear equations over values that have been “hidden” inside a

one

CARDINAL

-way function, and then we can compare the result to a direct (alleged) calculation of y that someone else has handed us:

Implicitly, this gives us the magic box we need to realize

Chris

PERSON

’s protocol from the previous section. The final protocol looks like this:

Appropriate cyclic groups can also be constructed within certain elliptic curves, such as

the NIST P-256

PRODUCT

and secp256k1 curve (used for

Schnorr

PERSON

signatures in

Bitcoin

GPE

) as well as the

EdDSA

ORG

standard, which is simply a

Schnorr

PERSON

signature implemented in the Ed25519

Edwards

PERSON

curve. Here the exponentiation is replaced with scalar point multiplication, but the core principles are exactly the same.

For most people, you’re probably done at this point. You may have accepted my claim that these “discrete logarithm”-based

one

CARDINAL

-way functions are sufficient to hide the values (m, b) and hence they’re magic-box-like.

But you shouldn’t! This is actually a terrible thing for you to accept. After all, modular-exponentiation functions are not magical boxes. They’re real “things” that might potentially leak information about the points “m” and “b”, particularly since

Victor

PERSON

will be given many different values to work with after several runs of the protocol.

To convince ourselves that the boxes don’t leak, we must use the intuition I discussed further above. Specifically, we need to show that it’s possible to “simulate” transcripts without ever talking to

Peggy

PERSON

herself, given only her public key . Recall that in the discussion above, the approach we used was to pick a random point (x, y)

first

ORDINAL

, and then “manufacture” a box as follows:

In our realized setting, this is equivalent to computing directly from and (x, y). Which we can do as follows:

(If you’re picky about things, here we’re abusing division as shorthand to imply multiplication by the multiplicative inverse of the final term.)

It’s easy enough to see that the implied value b = y – mx is itself distributed identically to the real protocol as long as (x, y) are chosen randomly. In that case it holds that will be distributed identically as well, since there is a

one

CARDINAL

-to-one mapping between between each b and the value in the exponent. This is an extremely convenient feature of this specific magic box. Hence we can hope that this primitive meets all of our security requirements.

From ID protocols to signatures:

Fiat-Shamir

ORG

While the post so far has been about identification protocols, you’ll notice that relatively few people use interactive ID protocols

these days

DATE

. In practice, when you hear the name “

Schnorr

PERSON

” it’s almost always associated with signature schemes. These

Schnorr

PERSON

signatures are quite common

these days

DATE

: they’re used in

Bitcoin

GPE

and form the basis for schemes like

EdDSA

ORG

.

There is, of course, a reason I’ve spent so much time on identification protocols when our goal was to get to signature schemes. That reason is due to a beautiful “trick” called the

Fiat

ORG

-Shamir heuristic that allows us to effortlessly move from

three

CARDINAL

-move identification protocols (often called “sigma protocols”, based on the shape of the capital

greek

NORP

letter) to non-interactive signatures.

Let’s talk briefly about how this works.

The key observation of

Fiat

ORG

and

Shamir

PERSON

was that

Victor

PERSON

doesn’t really do very much within a

three

CARDINAL

-move ID protocol: indeed, his major task is simply to select a random challenge. Surely if

Peggy

PERSON

could choose a random challenge on her own, perhaps somehow based off a “message” of her choice, then she could eliminate the need to interact with

Victor

PERSON

at all.

In this new setting,

Peggy

PERSON

would compute the entire transcript on her own, and she could simply hand

Victor

PERSON

a transcript of the protocol she ran with herself (as well as the message.) Provided the challenge value x could be bound “tightly” to a message, then this would convert an interactive protocol like the

Schnorr

PERSON

identification protocol into a signature scheme.

One

CARDINAL

obvious idea would be to take some message M and compute the challenge as x =

H(M

PERSON

).

Of course, as we’ve already seen above, this is a pretty terrible idea. If

Peggy

PERSON

is allowed to know the challenge value x, then she can trivially “simulate” a protocol execution transcript using the approach described in the previous section — even if she does not know the secret key. The resulting signature would be worthless.

For

Peggy

PERSON

to pick the challenge value x by herself, therefore, she requires a strategy for generating x that (

1

CARDINAL

) can only be executed after she’s “committed” to her

first

ORDINAL

magic box containing b, and (

2

CARDINAL

) does not allow her predict or “steer” the value x that she’ll get at the end of this process.

The critical observation made by

Fiat

ORG

and

Shamir

PERSON

was that

Peggy

PERSON

could do this if she possessed a sufficiently strong hash function H. Their idea was as follows.

First

ORDINAL

,

Peggy

PERSON

will generate her value b. Then she will place it into a “magic box” as in the normal protocol (as in the instantiation above.) Finally, she will feed her boxed value(s) for both m and b as well as an optional “message” M into the hash function as follows:

An evasive puzzle.

Finally, she’ll compute the rest of the protocol as expected, and hand

Victor

PERSON

the transcript which he can check by re-computing the hash function on the inputs to obtain x and verifying that y is correct (as in the original protocol.)

(A variant of this approach has

Peggy

PERSON

give

Victor

PERSON

a slightly different transcript: here she sends to

Victor

PERSON

, who now computes and tests whether . I will leave the logic of this equation for the reader to work out.)

For this entire idea to work properly, it must be hard for

Peggy

PERSON

to identify a useful input to the hash function that provides an output that she can use to fake the transcript. In practice, this requires a hash function where the “relation” between input and output is what we call evasive: namely, that it is hard to find

two

CARDINAL

points that have a useful relationship for simulating the protocol.

In practice we often model these hash functions in security proofs as though they’re random functions, which means the output is verifiably unrelated to the input. For long and boring reasons, this model is a bit contrived. We still use it anyway.

What other magic boxes might there be?

As noted above, a critical requirement of the “magic box

Schnorr

PERSON

” style of scheme is that the boxes themselves must be instantiated by some kind of

one

CARDINAL

-way function: that is, there must be no efficient algorithm that can recover

Peggy

PERSON

’s random secret key from within the box she produces, at least without exhaustively testing, or using some similarly expensive (super-polynomial time) attack.

The cyclic group instantiation given above satisfies this requirement provided that the discrete logarithm problem (DLP) is hard in the specific group used to compute it. Assuming your attacker only has a classical computer, this assumption is conjectured to hold for sufficiently-large groups constructed using finite-field based cryptography and in certain elliptic curves.

But nothing says your adversary has to be a classical computer. And this should worry us, since we happen to know that the discrete logarithm problem is not particularly hard to solve given an appropriate quantum computer. This is due to the existence of efficient quantum algorithms for solving the DLP (and

ECDLP

ORG

) based on

Shor

ORG

’s algorithm.

In my next post I’m going to talk

about one

CARDINAL

of those schemes, namely the Dilithium signature scheme, and show exactly how it relates to

Schnorr

PERSON

signatures.

To be continued in Part

2

CARDINAL

…

Notes:

“

Folklore

WORK_OF_ART

” in cryptography means that nobody knows who came up with the idea. In this case these ideas were proposed in a slightly different context (

one

CARDINAL

-time signatures) by folks like

Ralph Merkle

PERSON

. Since there are distinct subsets to pick from, the probability that

Veronica

ORG

will select exactly the same subset as

Victor

PERSON

did — allowing him to answer her challenge properly — can be made quite small, provided

N

ORG

and k are chosen carefully. (For example,

N=128

DATE

and

k=30

GPE

gives about and so Evil Victor will almost never succeed.) Some of these ideas date back to the

Elgamal

PERSON

signature scheme, although that scheme does not have a nice security reduction. In the real proof, we actually rely on a property called “rewinding.” Here we can make the statement that if there exists some algorithm (more specifically, an efficient probabilistic

Turing Machine

ORG

) that, given only

Peggy

PERSON

’s public key, can impersonate

Peggy

PERSON

with high probability: then it must be possible to “extract”

Peggy

PERSON

’s secret value m from this algorithm. Here we rely on the fact that if we are handed such a Turing machine, we can run it (at least) twice while feeding in the same random tape, but specifying

two

CARDINAL

different x challenges. If such an algorithm succeeds with reasonable probability in the general case, then we should be able to obtain

two

CARDINAL

distinct points (x, y), (x’, y’) and then we can just solve for (m, b). I’m specifying a prime-order subgroup here not because it’s strictly necessary, but because it’s very convenient to have our “exponent” values in the finite field defined by {

0

CARDINAL

, …, q-1} for some prime q. To construct such groups, you must select the primes q, p such that p =

2q

CARDINAL

+ 1. This ensures that there will exist a subgroup of order q within the larger group defined by the field

Fp

PERSON

.