TV tuned to a dead channel

Posted on by John

The opening line of William Gibson’s novel Neuromancer is famous:

The sky above the port was the color of a television, tuned to a dead channel.

When I read this line, I knew immediately what he meant, and thought it was a brilliant line. Later I learned that younger readers didn’t know what he was saying.

TV tuned to a dead channel circa 1960

My mind went to an old black-and-white television, one that received analog broadcasts, and that displayed “snow” when tuned to a channel that had no broadcast signal. Someone whose earliest memories of television are based on digital color broadcast might imagine the sky above the port was solid blue rather than crackly gray.

Gibson discusses how his book has aged in a preface to a recent edition. He says that science fiction that is too prescient would be received poorly.

Imagine a novel from the sixties whose author had somehow fully envisioned cellular telephony circa 2004, and had worked it, exactly as we know it today, into the fabric of her imaginary future. Such a book would have seemed highly peculiar in the sixties … in ways that would quickly overwhelm the narrative.

He then goes on to say

I suspect that Neuromancer owes much of its shelf life to my almost perfect ignorance of the technology I was extrapolating from. … Where I made things up from whole cloth, the colors remain bright.

I find it odd that many judge a work of science fiction by what it “got right.” I don’t read science fiction as a forecast;  read it to enjoy a story. I don’t need a book to be prescient, but until reading Gibson’s remarks it hadn’t occurred to me that fiction that is too prescient might not be enjoyable fiction, at least for its first readers.

How stealth addresses work in Monero

Posted on by John

Suppose Alice runs a confidential restaurant. Alice doesn’t want there to be any record of who visited her restaurant but does want to get paid for her food. She accepts Monero, and instead of a cash register there are two QR codes on display, one corresponding to her public view key A and the other corresponding to her public spend key S.

How Bob buys his burger

A customer Bob walks into the restaurant and orders a burger and fries. When Bob pays Alice, here’s what’s going on under the hood.

Bob is using software that generates a random integer r and multiplies it by a point G on an elliptic curve, specifically ed25519, obtaining the point

R = rG

on the curve. The software also multiplies Alice’s view key A, a point on the same elliptic curve, by r, then runs a hash function H on the produce rA that returns an integer k.

k = H(rA).

Finally, Bob’s software computes the point

P = kG + S

and sends Alice’s cash register, i.e. her crypto wallet, the pair of points (P, R). The point P is a stealth address, an address that will only be used this one time and cannot be linked to Alice or Bob [1]. The point R is additional information that helps Alice receive her money.

How Alice gets paid

Alice and Bob share a secret: both know k. How’s that?

Alice’s public view key A is the product of her private view key a and the group generator G [2]. So when Bob computes rA, he’s computing r(aG). Alice’s software can multiply the point R by a to obtain a(rG).

rA = r(aG) = a(rG) = aR.

Both Alice and Bob can hash this point—which Alice thinks of as aR and Bob thinks of as rA—to obtain k. This is ECDH: elliptic curve Diffie-Hellman key exchange.

Next, Alice’s software scans the blockchain for payments to

P = kG + S.

Note that P is on the blockchain, but only Alice and Bob know how to factor P into kG + S because only Alice and Bob know k. And only Alice can spend the money because only she knows the private key s corresponding to the public spend key S where

S = sG.

She knows

P = kG + sG = (k + s)G

and so she has the private key (k + s) corresponding to P.

Related posts

[1] Bob sends money to the address P, so there could be some connection between Bob and P on the Monero blockchain. However, due to another feature of Monero, namely ring signatures, someone analyzing the blockchain could only determine that Bob is one of 16 people who may have sent money to the address P, and there’s no way to know who received the money. That is, there is no way, using only information on the blockchain, who received the money. A private investigator who saw Bob walk into Alice’s restaurant would have additional information outside the blockchain.

[2] The key assumption of elliptic curve cryptography is that it’s computationally infeasible to “divide” on an elliptic curve, i.e. to recover a from knowledge of G and aG. You could recover a by brute force if the group were small, but the elliptic curve ed25519 has on the order of 2255 points, and a is some integer chosen randomly between 1 and the size of the curve.

Weddle integration rule

Posted on by John

I was reading about Shackleton’s incredible expedition to Antarctica, and the Weddell Sea features prominently. That name sounded familiar, and I was trying to remember where I’d heard of Weddell in math. I figured out that it wasn’t Weddell exactly but Weddle I was thinking of.

The Weddell Sea is named after James Weddell (1787–1834). Weddle’s integration rule is named after Thomas Weddle (1817–1853).

I wrote about Weddle’s integration rule a couple years ago. Weddle’s rule, also known as Bode’s rule, is as follows.

\begin{align*} \int_{x_0}^{x_6} f(x)\, dx = \frac{h}{140}&\Big(41 f(x_0) + 216f(x_1) + 27 f(x_2) +272 f(x_3) \\ &+ 27 f(x_4) + 216 f(x_5) + 41 f(x_6) \Big) \\ &-\frac{9 f^{(8)}(\xi) h^9}{1400} \end{align}

Let’s try this on integrating sin(x) from 1 to 2.

If we divide the interval [1, 2] into 6 subintervals, h = 1/6. The 8th derivative of sin(x) is also sin(x), so it is bounded by 1. So we would expect the absolute value of the error to be bounded by

9 / (69 × 1400).

Let’s see what happens in practice.

import numpy as np

x = np.linspace(1, 2, 7)
h = (2 - 1)/6
weights = (h/140)*np.array([41, 216, 27, 272, 27, 216, 41])
approx = np.dot(weights, np.sin(x))
exact = np.cos(1) - np.cos(2)
print("Error:          ", abs(approx - exact) )
print("Expected error: ", 9/(1400*6**9))

Here’s the output:

Error:           6.321198009473505e-10
Expected error:  6.379009079626363e-10

Related posts

Solving H_n = 100

Posted on by John

The previous post includes code for solving the equation

Hn = m

i.e. finding the value of n for which the nth harmonic number is the closest to m. It works well for small values of m. It works for large m in the sense that the solution is very close to m, but it’s not necessarily the best solution.

For example, set m = 100. The code returns

n = 15092688622113830917200248731913020965388288

and indeed for that value of n,

Hn − 100 ≈ 3 × 10−15

and that’s as much as we could hope for with IEEE 754 floats.

The approximation

n = exp(m −γ)

is very good for large values of m. Using Mathematica we can find the exact value of n.

f[n_] := Log[n] + EulerGamma + 1/(2 n) - 1/(12 n^2)
n = Floor[Exp[100 - EulerGamma]];
N[f[n], 50]
100.00000000000000000000000000000000000000000000900
N[f[n - 1], 50]
99.999999999999999999999999999999999999999999942747

So

n = 15092688622113788323693563264538101449859497

A similar process can find the solution to

Hn = 1000

is

n = 110611511026604935641074705584421138393028001852577373936470952377218354575172401275457597579044729873152469512963401398362087144972181770571895264066114088968182356842977823764462179821981744448731785408629116321919957856034605877855212667092287520105386027668843119590555646814038787297694678647529533718769401069269427475868793531944696435696745559289326610132208504257721469829210704462876574915362273129090049477919400226313586033

For this calculation you’ll need to increase the precision from 50 digits to something like 500 digits, something more than 435 because n is a 435-digit number.

In case you’re wondering whether my function for computing harmonic numbers is accurate enough, it’s actually overkill, with error O(1/120n4).

Closest harmonic number to an integer

Posted on by John

I mentioned in the previous post that the harmonic numbers Hn are never integers for n > 1. In the spirit of that post, I’d like to find the value of n such that Hn is closest to a given integer m.

We have two problems to solve. First, how do we accurately and efficiently compute harmonic numbers? For small n we can directly implement the definition. For large n, the direct approach would be slow and would accumulate floating point error. But in that case we could use the asymptotic approximation

H_n \approx \log n + \gamma + \frac{1}{2n} - \frac{1}{12n^2}

from this post. As is often the case, the direct approach gets worse as n increases, but the asymptotic approximation gets better as n increases. Here γ is the Euler-Mascheroni constant.

The second problem to solve is how to find the value of n so that Hn comes closest to m without trying too many possible values of n? We can discard the higher order terms above and see that n is roughly exp(m − γ).

Here’s the code.

import numpy as np

gamma = 0.57721566490153286

def H(n):
    if n < 1000:
        return sum([1/k for k in range(1, n+1)])
    else:
        n = float(n)
        return np.log(n) + gamma + 1/(2*n) - 1/(12*n**3)
    
# return n such that H_n is closest harmonic number to m
def nearest_harmonic_number(m):
    
    if m == 1:
        return 1

    guess = int(np.exp(m - gamma))    
    if H(guess) < m:
        i = guess
        while H(guess) < m: guess += 1 j = guess else: j = guess while H(guess) > m:
            guess -= 1
        i = guess
        
    x = np.array([abs(H(k) - m) for k in range(i, j+1)])
    return i + np.argmin(x)

We can use this, for example, to find the closest harmonic number to 10.

>>> nearest_harmonic_number(10)
12366
>>> H(12366)
9.99996214846655

I wrote the code with integer values of m in mind, but the code works fine with real numbers. For example, we could find the harmonic number closest to √20.

>>> nearest_harmonic_number(20**0.5)
49
>>> H(49)**2
20.063280462918804

Related posts

Closest consecutive reciprocal sum to an integer

Posted on by John

József Kürschák proved in 1908 that the function

f(m, n) = \sum_{k = m}^n \frac{1}{k}

is never an integer for 0 < m < n. In particular, the harmonic numbers

H_n = f(1, n)

are never integers for n > 1.

The function f(m, n) can get arbitrarily close to any integer value by taking m and n large enough, but it can never exactly equal an integer.

For this post, I’d like to look at how close  f(m, n) comes to an integer value when 0 < m < n ≤ N for some large N, say N = 100,000.

Computation strategy

The most naive way to approach this would be to compute f(m, n) for all m and n and keep track of which values were closest to integers. This would be wasteful since it would recompute the same terms over and over. Instead, we could take advantage of the fact that

f(m, n + 1) = f(m, n) + \frac{1}{n+1}

Instead of working with f(m, n), it will be convenient to work with just its fractional part

g(m, n) = f(m, n) - \lfloor f(m, n) \rfloor

because it won’t hurt to throw away the integer parts as we go. The values of m and n minimizing g(m, n) will be the values for which f(m, n) comes closest to an integer from above. The values of m and n maximizing g(m, n) will be the values for which f(m, n) comes closest to an integer from below.

We could calculate a matrix with all values of g(m, n), but this would take O(N²) memory. Instead, for each n we will calculate g(m, n), save the maximum and minimum values, then overwrite that memory with g(m, n + 1). This approach will only take O(N) memory.

Floating point error

When we compute f(m, n) for large values of n, can we rely on floating point arithmetic?

If N = 100,000, f(m, n) < 16 = 24. A floating point fraction has 53 bits, so we’d expect each addition to be correct to within an error of 2−49 and so we’d expect our total error to be less than 2−49 N.

Python code

The following code computes the values of g(m, n) closest to 0 and 1.

import numpy as np

N = 100_000
f_m = np.zeros(N+1) # working memory

# best values of m for each n
min_fm = np.zeros(N+1)
max_fm = np.zeros(N+1)

n = 2
f_m[1] = 1.5

for n in range(3, N+1):
    f_m[n-1] = 1/(n-1)
    f_m[1:n] += 1/n
    f_m[1:n] -= np.floor(f_m[1:n])
    min_fm[n] = np.min(f_m[1:n])
    max_fm[n] = np.max(f_m[1:n])    

print(min(min_fm[3:]))
print(max(max_fm))

This reports a minimum value of 5.2841953035454026e-11 and a maximum value of 0.9999999996613634. The minimum value is closer to 0 than our (pessimistic) error estimate, though the maximum value is further from 1 than our error estimate.

Modifying the code a bit shows that the minimum occurs at (27134, 73756), and this the input to g that is within our error estimate. So we can be confident that it is the minimum, though we can’t be confident of its value. So next we turn to Mathematica to find the exact value of g(27133, 73756) as a rational number, a fraction with 32024 digits in the numerator and denominator, and convert it to a floating point number. The result agrees with our estimate in magnitude and to four significant figures.

So in summary

\sum_{k = 27134}^{73756} \frac{1}{k} \approx 1

with an error on the order of 10−11, and this is the closest value of f(m, n) to an integer, for 0 < m < n ≤ 100,000.

Related posts

RSA as a pairing

Posted on by John

The last couple posts have been about group pairings, specifically Tate pairings as they’re used in cryptography. This post will show that RSA encryption can be seen as a special case of pairing-based cryptography.

The idea comes from Ben Lynn’s 2007 dissertation. Lynn is the “L” in BLS signatures—one of the topics in his dissertations—and in BLS elliptic curves.

A pairing is a bilinear mapping from two groups to a third group

e: G1 × G2 → GT.

Here bilinear means that if P is an element of G1 and Q is an element of G2, and a and b are nonnegative integers, then

e(aP, bQ) = e(P, Q)ab.

There are more criteria for a pairing to be useful in cryptography, but we won’t need those for this post.

Ben Lynn’s dissertation mentions that exponentiation is a special case of pairing if you let G1 and GT be the multiplicative group of the integers mod r and let G2 be the additive group of integers mod (r − 1). Then you can define a pairing by

e(g, a) = ga.

Typically you can’t just write down a simple expression for a pairing, but in this case you can.

RSA encryption corresponds to r = pq where p and q are large primes. The product pq is made public but the factorization into p and q is held secret. A message [1] is encrypted by exponentiation mod n where the exponent is the public key. In Lynn’s notation, the message is g and the public key is a.

The security of RSA encryption depends on the fact that you can’t recover g from ga mod n unless you know a trapdoor, the factorization of n [2]. This is true of pairings more generally: it is not practical to recover the inputs to a pairing from the output unless you know a trapdoor.

Related posts

[1] In practice, RSA isn’t used to encrypt entire messages. Instead, it is used to encrypt a key for a symmetric encryption algorithm such as AES, and that key is used to encrypt the message. This is done for efficiency.

[2] Or, more specifically, a private key that can easily be computed if you know the factorization of n. It’s conceivable that breaking RSA encryption is easier than factoring, but so far that does not appear to be the case.

Three-party Diffie-Hellman in one shot

Posted on by John

Elliptic curve Diffie-Hellman

Given a point P on an elliptic curve E, and a random number a, aP means to add P to itself a times, using the addition on E. The point aP can be computed efficiently, even if a is a very large number [1]. However, if E has a large number of points, and if a is chosen at random from a large range, then it is not practical to compute a given P and aP.

This is the elliptic curve version of the discrete logarithm problem, and its presumed difficulty is the basis of the security of Diffie-Hellman key exchange.

Two-party Diffie-Hellman

With two-party Diffie-Hellman key exchange, two parties, Alice and Bob, generate random private keys a and b respectively. They agree on a point P on an elliptic curve E. Alice computes aP and sends it to Bob. Simultaneously Bob computes bP and sends it to Alice. Then Alice can compute

a(bP) = (ab)P

and Bob can compute

b(aP) = (ba)P = (ab)P.

Then both Alice and Bob know a shared secret, the point (ab)P on E, but neither party has revealed a private key.

Three-party Diffie-Hellman

You could extend the approach above to three parties, say adding Carol, but this would require extra communication: Alice could send (ab)P to Carol, which she could multiply by her private key c to obtain abcP. Similarly, everyone else could arrive at abcP. Each person has to do a computation, send and receive a message, do another computation, and send an receive another message.

Joux [2] came up with a way to do Diffie-Hellman key exchange with three people and only one round of sending and receiving messages. The set up uses a pairing e( , ) of two elliptic curve subgroups, G1 and G2, as in the previous post. Fix generators P ∈ G1 and Q ∈ G2. Each party multiplies P and Q by their private key and sends the results to the other two parties.

Alice receives bP from Bob and cQ from Carol. This is enough for her to compute

e(bP, cQ)a = e(P, Q)abc.

Similarly, Bob receives aP from Alice and cQ from Carol, enabling him to compute

e(aP, cQ)b = e(P, Q)abc.

And finally, Carol receives aP from Alice and bQ from Bob, enabling her to compute

e(aP, bQ)c = e(P, Q)abc.

So all three parties can compute the shared secret e(P, Q)abc. but no party knows the other parties’ private keys.

Footnotes

[1] If you want to multiply a point by 2100, for example, you don’t carry out 2100 additions; you carry out 100 doublings. Of course not every positive integer is a power of 2, but every positive integer is the sum of powers of 2, i.e. it can be written in binary. So as you’re doing your doublings, sum the terms that correspond to 1s in the binary representation of the number you’re multiplying by.

[2] Antoine Joux. A One Round Protocol for Tripartite Diffie–Hellman. Journal of Cryptology (2004) 17: 263–276.

Elliptic curve pairings in cryptography

Posted on by John

Pairings can mean a variety of related things in group theory, but for our purposes a pairing is a bilinear mapping from two groups to a third group.

e: G1 × G2 → GT

Typically the group operation on G1 and G2 is written addititvely and the group operation on GT is written multiplicatively. In fact, GT will always be the multiplicative group of a finite field, i.e. GT consists of the non-zero elements of a finite field under multiplication. (The “T” stands for “target.”)

Here bilinear [1] means that if P is an element of G1 and Q is an element of G2, and a and b are nonnegative integers,

e(aP, bQ) = e(P, Q)ab.

There are a few provisos …

Robin Williams imitating William F. Buckley

First, the pairing must be non-degenerate, i.e. e(P, Q) ≠ 1 for some P and Q.

Second, the pairing must be efficiently computable.

Third, the embedding degree must not be “too high.” This means that if GT is the multiplicative group of a field with pk elements, k is not too big. We will look at two examples in which k = 12.

The second and third provisos are important even though they’re not stated rigorously.

Cryptography often speaks of pairing elliptic curves, but in fact it uses pairings of prime-order subgroups of the additive groups of elliptic curves. Because the subgroups have prime order, they are cyclic, and so the pairing is determined by its value on a generator from each subgroup.

Example: BN254

The previous post briefly mentioned a pairing between two elliptic curves, BN254 and alt_bn128, that is used in Ethereum and was used in Zcash in the original Sprout shielded protocol.

The elliptic curve BN254 is defined over the field Fp, the integers mod p, where

p = 21888242871839275222246405745257275088696311157297823662689037894645226208583.

and the elliptic curve alt_bn128 is defined over the field Fp[i], i.e. the field Fp, with an imaginary element i adjoined.

Both elliptic curves have a subgroup of order

r = 21888242871839275222246405745257275088548364400416034343698204186575808495617,

which is prime. So in the pairing the groups G1 and G2 are isomorphic to the integers mod r. The target group GT has order p12 − 1 and so the embedding degree k equals 12, and so the embedding degree is “not too high.”

Example: BLS12-381

Another example also comes from Ethereum and Zcash. Ethereum uses BN254 in smart contracts, but it uses BLS12-381 in its consensus layer. Zcash switched from BN254 to BLS12-381 in the Sapling release.

BLS12-381 is defined over a prime order field with on the order of 2381 elements and has embedding order 12, hence 12-381. The BLS stands for Paulo Barreto, Ben Lynn, and Michael Scott. Elliptic curve names often look mysterious, but they’re actually pretty descriptive. I discuss BLS12-381 in more detail here. As in the example above, BLS12-381 is defined over a field Fp and is paired with a curve over Fp[i], i.e. the same field with an imaginary element adjoined. The equation for BLS12-381 is

y² = x³ + 4

and the equation for the curve it is paired with is

y² = x³ + 4(1 + i)

As before the target group is the multiplicative group of a finite field of order p12.

Related posts

[1] You’ll also see bilinearity defined by

e(P + Q, R) = e(P, R) e(Q, R)

and

e(P, R + S) = e(P, R) e(P, S).

These definitions are equivalent. To see that the definition here implies the definition at the top, write out aP as P + P + … + P etc.

Since we’re working in subgroups of prime order, there is a generator for each subgroup. Write out each element as a multiple of a generator, then the definition at the top implies the definition here.