A question about Montgomery representation

[xhsinxmu]

Hello, In my project I plan on generating secret shares in another application. So I wonder how the shares are generated in "Montgomery representation in blocks of eight bytes". Could you help locate the source code?

Looking forward to your response and support

[mkskeller]

You can find the relevant Python code here: https://github.com/data61/MP-SPDZ/blob/2919d781c9bb607ea04d9aa305a1f2fd2afb9914/ExternalIO/domains.py#L63C1-L77C1 The relevant C++ code can be found here instead: https://github.com/data61/MP-SPDZ/blob/2919d781c9bb607ea04d9aa305a1f2fd2afb9914/Math/modp.hpp#L176C1-L197C1

[xhsinxmu]

Hello, thank you for your previous answer! We referred to https://github.com/data61/MP-SPDZ/blob/2919d781c9bb607ea04d9aa305a1f2fd2afb9914/ExternalIO/domains.py#L63C1-L77C1 and implement it in java, trying to generate secret shares in the form of Transactions-Px. However, MPSPDZ could not parse the shares generated.

[xhsinxmu]

`try { int modulus = 1000000007;

        int modulus_words = getBitCount(modulus) ;
        /** compute R with Bigintegers*/
        BigInteger Big_modulus = BigInteger.valueOf(modulus);
        BigInteger exponent = BigInteger.valueOf(modulus_words);
        BigInteger two = BigInteger.valueOf(2);
        BigInteger R = two.modPow(exponent, Big_modulus);
        //BigInteger R_inv = R.modInverse(Big_modulus);

        /**write the fixed header of  Transactions-Px (I guess the header is fixed for my compile argument ./compile.py -F 16 -P 1000000007  xhs-test -M)*/
        FileOutputStream fileOutputStream = new FileOutputStream("C:\\Users\\13268\\Desktop\\seipa_output\\Transactions-P"+myAlphaIndex+".data");
        DataOutputStream dataOutputStream = new DataOutputStream(fileOutputStream);
        String header =  "13000000000000005368616D69722067667000040000003B9ACA07";
        //String header =  "12000000000000005368616D6972206766700003000000F0F5BF";
        byte[] hexString = hexStringToByteArray(header);
        dataOutputStream.write(hexString);

        /**compute value*R
         */
        for (long value : commonIntegerShare) { //(commonIntegerShare is an array of generated shares from shamir's secret sharing
            ByteBuffer buffer = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN);

            BigInteger Big_value =  BigInteger.valueOf(value);
            BigInteger res = R.multiply(Big_value);
            //BigInteger last16Bits = res.and(new BigInteger("FFFF", 16));
            BigInteger lastBits = res.mod(Big_modulus);
            buffer.putLong(lastBits.longValue());
            dataOutputStream.write(buffer.array());
        }

    } catch (IOException e) {
        e.printStackTrace();
    }`

[xhsinxmu]

I wonder if MP-SPDZ generates secret shares in a different way.

[mkskeller]

R should be a power of 2^64. I don't think that's the case in your code.

[xhsinxmu]

                    int modulus = 1000000007;
        int modulus_words = (getBitCount(modulus) + 63) / 64;
        int modulus_bytes = 8 * modulus_words;
        BigInteger exponent = BigInteger.valueOf(64 * modulus_words);

        /**using Bigintegers to compute R*/
        BigInteger Big_modulus = BigInteger.valueOf(modulus);
        BigInteger two = BigInteger.valueOf(2);
        BigInteger R = `two.modPow(exponent,Big_modulus);`

I have modified the R value so that it is quite close to that in the python code in https://github.com/data61/MP-SPDZ/blob/2919d781c9bb607ea04d9aa305a1f2fd2afb9914/ExternalIO/domains.py#L63C1-L77C1. However, this didn't work for me. My code gathered secret shares on the framework SEPIA: https://www.usenix.org/legacy/event/sec10/tech/full_papers/Burkhart.pdf

[mkskeller]

What do you mean when you say it doesn't work? Have you tried using constant shares (all shares being 0 or 1 for example)?

[xhsinxmu]

I have tried to generate an array of shares of constant values (say, [1,2...8]), however after input these data became unreadable. In contrast, the shares generated by MPSPDZ was readable after input.

[xhsinxmu]

Oh, I see what you mean; I'm now trying constant shares.

[xhsinxmu]

the input of constant shares (all shares are set to 1 before Montgomery representation) was successfully parsed.

[mkskeller]

So the next step would be to use a simple sharing, for example 1 for party 1, 2 for party 2, 3 for party 3. This should result in a sharing of 0 because it follows the polynomial p(x)=x.

[qqy11111]

Hello, I plan on generating secret shares in another application. So I wonder how mp-spdz generates Shamir secret sharing. Could you help locate the source code?

Looking forward to your response and support

[mkskeller]

The code is in this function: https://github.com/data61/MP-SPDZ/blob/d7f2c318041d943f230edb9ea2cd5f26f04577b3/Protocols/ShamirInput.hpp#L65

For interoperability, I think the most important point is that the secret is p(0), party 0 receives p(1), party 1 receives p(2) etc, where p is the sharing polynomial.

[xhsinxmu]

Thank you so much for your advice! They are quite helpful for us. I found the bug that our program assumes each party holds F(2),F(3)...F(x) of the polynomial in Shamir's sharing, while MP-SPDZ assumes F(1),F(2)...F(x).