david wong

Hey! I'm David, the author of the Real-World Cryptography book. I'm a crypto engineer at O(1) Labs on the Mina cryptocurrency, previously I was the security lead for Diem (formerly Libra) at Novi (Facebook), and a security consultant for the Cryptography Services of NCC Group. This is my blog about cryptography and security and other related topics that I find interesting.

Creating cryptographic protocols with multiplications posted last month

A lot of cryptographic protocols can be reduced to computing some value. Perhaps the value obtained is a shared secret, or it allows us to verify that some other values match (if it's 0). Since we're talking about cryptography, computing the value is most likely done by adding and multiplying numbers together.

Addition is often free, but it seems like multiplication is a pain in most cryptographic protocols.

If you're multiplying two known values together, it's OK. But if you want to multiply one known value with another unknown value, then you will most likely have to reach out to the discrete logarithm problem. With that in hand, you can multiply an unknown value with a known value.

This is used, for example, in key exchanges. In such protocols, a public key usually masks a number. For example, the public key X in X = [x] G masks the number x. To multiply x with another number, we do this hidden in the exponent (or in the scalar since I'm using the elliptic curve notation here): [y] X = [y * x] G. In key exchanges, you use this masked result as something useful.

If you're trying to multiply two unknown values together, you need to reach for pairings. But they only give you one multiplication. With masked(x) and masked(y) you can do pairing(masked(x), masked(y)) and obtain something that's akin to locked_masked(x * y). It's locked as in, you can't do these kind of multiplications anymore with it.

Well done! You've reached the end of my post. Now you can leave a comment or read something else.

Comments

jones

I didn't realize that multiplication is often a pain in these protocols.

marisa

It's interesting that pairings can only give you one multiplication.

leave a comment...