Proof-of-Randomness with an EC Public Key

WindowCleaner

12/9/23, 9:24 PM

I will be using a tRNG to generate EC keypairs on a Secure Integrated Controller.

I need to demonstrate I, the issuer, can not know the private key without colluding with the user to obtain it, even if the tRNG is weak. I also don't want to reveal the private key to the user, only the public key.

I'm thinking a scheme along these lines:

Data from an external (user-provided) source of randomness is concatenated with data from the tRNG. The result is hashed and used as an EC private key. The EC public key is calculated from the private key, and a zero-knowledge proof is used to demonstrate that the external randomness was used to generate the private secret that corresponds to that public key.

I prefer the solution with the lowest implementation complexity that will work within my performance constraints. Preferably, I want to use the standard EC operations and common hash functions as much as possible.

1 + 1

elliptic-curves

verifiable-random-function

Pegasus

12/11/23, 12:19 PM

why not use zero-knowledge proof ?

Score:-2

Crypto

Paul Uszak

12/9/23, 11:08 PM

Excellent question. "prove that the RNG process is not somehow backdoored"

You can't. Robert A. Heinlein said “Love your country, but never trust its government.”

It's mathematically impossible and thus called computational indistinguishability. The NSA/MSS can feed you numbers that look truly random from sources/devices they control and yet are entirely predictable given their secret designs. It is not in their national interest to allow people access to true randomness as that facilitates private conversations. And no security service wants that.

The only way to prove that a TRNG is not backdoored is to build it yourself. It's not that hard. Zener diodes and webcams are your friends. If you're serious, there are online articles that can help you, or there is reallyreallyrandom.com.

And how can you trust "Data from an external (user-provided) source of randomness"? Is that under the influence of NSA/MSS? How would you know?

Buy diodes.

+ 3

WindowCleaner

12/9/23, 11:16 PM

I imagine that what I'm asking for is possible with ZK, what I want to create is a scenario where both the user and the device would need to be compromised for the randomness to be unsafe. There's a very specific context to this that I can't disclose. I've updated for clarity, I apologise for the initial wording.

poncho

12/9/23, 11:22 PM

I don't believe it is impossible; the external device would need to provide the secret entropy to the Secure Integrated Controller and publish a commitment to that secret entropy; the Secure Integrated Controller would provide a proof that the private value it used was a function of the secret entropy (and other inputs). The stumbling block may be proving that the Secure Integrated Controller didn't leak the secret entropy via some side channel (but if you limit the number of ways the SIC can interact with the outside world, possibly doable)

Paul Uszak

12/10/23, 8:04 AM

@WindowCleaner Understood. Just remember that if you didn't make it, you don't know what it does. Your device is compromised because you can't prove that it isn't. But, what are you hiding? The US isn't interested in your food diet or porn preferences. ROT13 will secure comms from 99% of the population. If this is important, devote funds and build yourself a TRNG.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Proof-of-Randomness with an EC Public Key

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.