Skip to content

A scheme to implement finite groups as oblivious data structures. The oblivious operations are defined by a set of secure multiparty computation (MPC) protocols. Practical protocols are presented for the group of quadratic residues, elliptic curves groups and class groups of imaginary quadratic orders.

License

Notifications You must be signed in to change notification settings

toonsegers/sec_groups

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

18 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Build Status

Secure Groups

This 'Secure Groups' Python package implements the Secure Group scheme for several mathematical groups.

Please note: This work is superseded by and integrated in MPyC since November 2021 (this commit). See the fingroups and secgroups modules in the MPyC-runtime in particular.

Secure Group scheme

The Secure Group scheme implements finite groups as oblivious data structures. For a given group, the scheme defines the oblivious representation of, and oblivious operations on group elements. Operations include the group law, exponentiation and inversion, random sampling and encoding/decoding.

The oblivious operations are defined by a set of secure multiparty computation (MPC) protocols. Practical protocols are presented for the group of quadratic residues, elliptic curves groups and class groups of imaginary quadratic orders. We demonstrate these protocols in a standard setting for information theoretically secure MPC, tolerating a dishonest minority of passively corrupt parties.

For our implementation we use the MPyC framework.

Please find the write-up of this work in Chapter 4 of this Horizon2020 deliverable (published on June 30, 2021).

Note: This implementation is work-in-progress. Expect bugs.

Constant-time extended gcd algorithm and protocol

We introduce a practical protocol to calculate the extended gcd (xgcd) of two secret-shared integers adapting a 2019 result by Bernstein and Yang from the p-adic setting to the finite field setting. This xgcd MPC protocol is a first and of independent interest. We apply it to implement the class group operation in MPC.

Conversion protocol for ciphertexts to secret shares

To demonstrate the application of secure groups, we extend a classical threshold cryptosystem with a protocol to convert ciphertexts to secret shares. This functionality enables in- and output to a multiparty computation by communicating one ciphertext over an insecure channel.

Installation

This implementation depends on MPyC (version 0.74 or above) and gmpy2.

Install latest version of MPyC:

git clone https://github.com/lschoe/mpyc
cd mpyc
python setup.py install

Install 'gmpy2':

pip install gmpy2   				# for Linux (first running `apt install libmpc-dev` may be necessary)
pip install gmpy2-[version etc].whl	# for Windows, see Gohlke's unofficial binaries [https://www.lfd.uci.edu/~gohlke/pythonlibs/]

Demos

The following demos are included:

  • demo_basic_examples.py to see examples of different groups (Elliptic curve groups, QR groups, Class groups, etc.);
  • demo_sec_gcd.py to compute the extended gcd of two (secret shared) integers in constant time;
  • demo_conversion_ed25519.py to convert ElGamal encryptions to Shamir shares, using the Ed25519 curve group;
  • demo_conversion_qr.py to convert ElGamal encryptions to Shamir shares, using subgroup of quadratic residues of 2048-bit prime;
  • demo_rubiks.py to sample random elements from a Rubik's Cube group;

Run the demos as follows:

cd demos
python demo_basic_examples.py

Testing

Run the following commands:

python -m unittest discover .

Acknowledgements

This work has received funding from the European Union's Horizon 2020 research and innovation program under grant agreements No 780477 (PRIViLEDGE).

About

A scheme to implement finite groups as oblivious data structures. The oblivious operations are defined by a set of secure multiparty computation (MPC) protocols. Practical protocols are presented for the group of quadratic residues, elliptic curves groups and class groups of imaginary quadratic orders.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages