microsoft / picnic Goto Github PK

Reference implementation of the Picnic post-quantum signature scheme

Home Page: https://microsoft.github.io/Picnic/

License: MIT License

C 99.82% Makefile 0.03% C++ 0.15%

picnic's Introduction

Picnic: Post Quantum Signatures

The Picnic signature scheme is a family of digital signature schemes secure against attacks by quantum computers. This is a reference implementation of these schemes. The scheme and parameter sets are specified in the Picnic Specification Document.

Research papers describing the signature scheme are also available on the Picnic website.

The library is provided under the MIT License. The authors are Steven Goldfeder and Greg Zaverucha.

The library builds a static library. The public API surface is defined in picnic.h.

Linux Build Instructions

Tested on Ubuntu Linux, and the Windows Subsystem for Linux on Windows 10 (build 1709).

make
This will build the project. make debug will build with symbols.
./example
Runs an example program that exercises the keygen, sign, verify and serialization APIs. See example.c.

Windows Build Instructions

Tested on Windows 10 with Visual Studio 2017.

Open the solution in VisualStudio\picnic.sln, and build the projects.

The project libpicnic creates a .lib file, containing the functions defined in picnic.h.
See the example project for a simple application that calls functions in the library.

Acknowledgments

Thanks to Christian Paquin for providing feedback on picnic.h and for adding support for a Windows build.

Contributing

This project has adopted the Microsoft Open Source Code of Conduct. For more information see the Code of Conduct FAQ or contact [email protected] with any additional questions or comments.

picnic's People

Contributors

Stargazers

Watchers

picnic's Issues

Add example for deterministic sign specifying a nonce

Hi, I'm working with this piece of code currently:

bool CKey::Sign(const uint256 &hash, std::vector<unsigned char>& vchSig, uint32_t test_case) const {
    if (!fValid)
        return false;
    vchSig.resize(72);
    RFC6979_HMAC_SHA256 prng(begin(), 32, (unsigned char*)&hash, 32);
    do {
        uint256 nonce;
        prng.Generate((unsigned char*)&nonce, 32);
        nonce += test_case;
        int nSigLen = 72;
        int ret = secp256k1_ecdsa_sign((const unsigned char*)&hash, 32, (unsigned char*)&vchSig[0], &nSigLen, begin(), (unsigned char*)&nonce);
        nonce = 0;
        if (ret) {
            vchSig.resize(nSigLen);
            return true;
        }
    } while(true);
}

Where secp256k1_ecdsa_sign prototype is:

int secp256k1_ecdsa_sign(const unsigned char *msg, int msglen, unsigned char *sig, int *siglen, const unsigned char *seckey, const unsigned char *nonce)

And, im trying to replace EC with Picnic, but I can't find a way to specify a noce in the code, I saw it in the signature2 struct but there is not example of the use of this structure.

Replacing LowMC

What would it take to replace LowMC with say AES, SHA, etc?
Could you replace
runMPC(views[k], &tape, plaintext, (uint32_t*)tmp, params); and it's implementation: void mpc_LowMC(randomTape_t* tapes, view_t views[3], const uint32_t* plaintext, uint32_t* slab, paramset_t* params)
or is there other assumptions in the algorithm about LowMC being used?

Soundness parameters for V2 (KKW18)

In ZKBoo, computing soundness parameters is straightforward - (1/3) ^ FSrounds. However in V2, I'm getting somewhat odd numbers. Script as follows:

import math

def calc(bits,mpcRounds,opened,parties):
    # V1
    # * soundness fixed to 1/3 as adversary controls 2 of 3 values
    soundness=3/2
    # V2
    # * adversary has to to embed his party into half of all mpcRounds,
    #   to maximize hit rate of the sampler.
    # * 50% chance to hit the correct sample
    #   if it hits, it must also meet adversarial party, chance 1-in-n?
    if parties > 3:
        soundness = 2 * parties
    invP = soundness**opened
    return "bits=%d, mpcRounds=%d, opened=%d, parties=%d, soundness=%d" % (bits,mpcRounds,opened,parties,int(math.log2(invP)))

print("== PicnicV1 parameters, 3 party => soundness")
print("L1",calc(128, 219, 219, 3))
print("L3",calc(192, 329, 329, 3))
print("L5",calc(256, 438, 438, 3))
print()


print("== PicnicV2 parameters, 64 party => soundness")
print("L1",calc(128, 343, 27, 64))
print("L3",calc(192, 570, 39, 64))
print("L5",calc(256, 803, 50, 64))
print()

Results:

== PicnicV1 parameters, 3 party => soundness
L1 bits=128, mpcRounds=219, opened=219, parties=3, soundness=128
L3 bits=192, mpcRounds=329, opened=329, parties=3, soundness=192
L5 bits=256, mpcRounds=438, opened=438, parties=3, soundness=256

== PicnicV2 parameters, 64 party => soundness
L1 bits=128, mpcRounds=343, opened=27, parties=64, soundness=189
L3 bits=192, mpcRounds=570, opened=39, parties=64, soundness=273
L5 bits=256, mpcRounds=803, opened=50, parties=64, soundness=350

The soundness values seem overshot, and I'm not sure why that is. Compensation for birthday paradox (from where?). Or multitarget attacks? Or is my fault chance formula plain wrong?
In the unlikely event the values are indeed overshot, one could do something like:

print("== Tight parameters, 64party => soundness")
print("X1",calc(128, 256, 19, 64))
print("X3",calc(192, 384, 28, 64))
print("X5",calc(256, 512, 37, 64))
print()

print("== Tight parameters, 256party => soundness")
print("Y1",calc(128, 256, 15, 256))
print("Y3",calc(192, 384, 22, 256))
print("Y5",calc(256, 512, 30, 256))
print()


print("== Tight+64bit slack, 256party => soundness")
print("Z1",calc(128, 256, 22, 256))
print("Z3",calc(192, 384, 30, 256))
print("Z5",calc(256, 512, 36, 256))
print()

Resulting:

== Tight parameters, 64party => soundness
X1 bits=128, mpcRounds=256, opened=19, parties=64, soundness=133
X3 bits=192, mpcRounds=384, opened=28, parties=64, soundness=196
X5 bits=256, mpcRounds=512, opened=37, parties=64, soundness=259

== Tight parameters, 256party => soundness
Y1 bits=128, mpcRounds=256, opened=15, parties=256, soundness=135
Y3 bits=192, mpcRounds=384, opened=22, parties=256, soundness=198
Y5 bits=256, mpcRounds=512, opened=30, parties=256, soundness=270

== Tight+64bit slack, 256party => soundness
Z1 bits=128, mpcRounds=256, opened=22, parties=256, soundness=198
Z3 bits=192, mpcRounds=384, opened=30, parties=256, soundness=270
Z5 bits=256, mpcRounds=512, opened=36, parties=256, soundness=324

256-party variant might be worth pursuing in any case to save roughly 20% signature size.

This repo is missing important files

There are important files that Microsoft projects should all have that are not present in this repository. A pull request has been opened to add the missing file(s). When the pr is merged this issue will be closed automatically.

Microsoft teams can learn more about this effort and share feedback within the open source guidance available internally.

Merge this pull request

microsoft / picnic Goto Github PK

picnic's Introduction

Picnic: Post Quantum Signatures

Linux Build Instructions

Windows Build Instructions

Acknowledgments

Contributing

picnic's People

Contributors

Stargazers

Watchers

Forkers

picnic's Issues

Add example for deterministic sign specifying a nonce

Replacing LowMC

Soundness parameters for V2 (KKW18)

This repo is missing important files

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent