Hashing and signature verification in the high-level language

[nasko25]

Hello, What would be the best way of using hashing functions (at least sha1, sha256, sha512) and signature verification functions (rsa, ecdsa) on secret variables (sint/sbits/sbitvec)?

I found the SCALE-MAMBA circuits and have been trying to run the sha256 function on some input, but is there any other way to run such functions, or are there any plans of adding them? If not, what would be the best and most efficient way of implementing them now?

Thank you.

[mkskeller]

I'm not working on this at the moment. Running cryptographic algorithms in secure computation is an entire subfield sometimes called threshold cryptography. My guess would be that the most efficient way of running SHA* is using binary circuits as done by the circuits in SCALE-MAMBA. There is some work on a low-level implementation of ECDSA in the directory of the same name. RSA might be harder because the group order is part of the key. In any case, I don't think either is captured well by the high-level language as there is no notion of group elements as opposed to exponents.

[nasko25]

I see. Thank you.

I have been trying to run the sha-256 circuit, but I am not quite sure what the types of the message and state input variables should be. Assuming state refers to the initial sha256 hash state I have tried with:

sha256 = Circuit('sha256')
sb32 = sbits.get_type(32)
siv256 = sbitintvec.get_type(256)
state = siv256([sb32(0x6a09e667),sb32(0xbb67ae85),sb32(0x3c6ef372),sb32(0xa54ff53a),sb32(0x510e527f),sb32(0x9b05688c),sb32(0x1f83d9ab),sb32(0x5be0cd19)])
# or state = siv256(0x6a09e667bb67ae853c6ef372a54ff53a510e527f9b05688c1f83d9ab5be0cd19)
secret = siv512(sb512(0x1))
sha256(secret, state).elements()[0].reveal().print_reg()

(0x1 being the secret), but the hashes produced are not correct. (0x385888cbdb8a75d5c94d8844c8f97f134529bafa8588227fd66b5e5a12a291c1 and 0xb40f7ca600e9693557a6a01a2a9288c200d14c5e76329d4d0d069cae776a096d)

Do you have any suggestions on what the types of the input variables should be?

[mkskeller]

Do you intend to hash the empty string with secret 0x1? You need to use 0x1 << 511 as the first top corresponds to the MSB of the value as in the state. The following works for me:

state = siv256(0x6a09e667bb67ae853c6ef372a54ff53a510e527f9b05688c1f83d9ab5be0cd19)
siv512 = sbitintvec.get_type(512)
secret = siv512(sb512(0x1 << 511))
sha256(secret, state).elements()[0].reveal().print_reg()

as it outputs the hash of an empty string:

Reg[0] = 0xe3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 #     

[nasko25]

This is exactly what I needed. Thank you!

[nasko25]

What would be the easiest way of implementing modular exponentiation?

[nasko25]

And if that would be too difficult, what about modular exponentiation with a fixed exponent like 65537 as a start?

Or do you know of any circuits that might implement this operation, or maybe RSA? I have found one circuit implementation for ZK-SNARKs (r1cs), but I don't know whether I can convert it to be used for MPC. Do you think it is possible?

[mkskeller]

I'm not aware of a circuit or a conversion from r1cs. MP-SPDZ doesn't implement modular reduction (other than the one implicit in the computation), so that would be the starting point I think.