tweedle - GitLite

KO | EN

gitlite — search

#awesome #json #video #mcp #svg #css #computer-vision #kubernetes #html #web

tweedle

(★ 20)

Generator and supporting evidence for security of the Tweedledum/Tweedledee pair of elliptic curves suitable for Halo

File Explorer

ZIP Download

- a
- b
- l
- p
- rigid
- shape
- x0
- x1
- y0
- y1
- a
- b
- l
- p
- rigid
- shape
- x0
- x1
- y0
- y1
.gitignore
amicable.sage
animation-p.webm
animation-q.webm
animation.sh
checksumsets.py
clean.sh
injectivitylemma.py
LICENSE
README.md
run.sh
verify.sage

# Use via CDN

jsDelivr

jsDelivr serves any public GitHub repository as a CDN with zero setup. Pick a version and a file to get a ready-to-paste link and snippet.

Version

File

Link

Example

Command Glossary

Commands referenced in this DOCs, explained below.

🔍

`pip3`

View Details ▼

This command is an alias of `pip`.

tldr pip

View documentation for the original command:

🔍

`python3`

View Details ▼

This command is an alias of `python`.

tldr python

View documentation for the original command:

🔍

`apt-get`

View Details ▼

Debian and Ubuntu package management utility.
Search for packages using `apt-cache`.
It is recommended to use `apt` when used interactively in Ubuntu versions 16.04 and later.

sudo apt-get update

Update the list of available packages and versions (it's recommended to run this before other `apt-get` commands):

sudo apt-get install {{package}}

Install a package, or update it to the latest available version:

sudo apt-get remove {{package}}

Remove a package:

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

Tweedledum/Tweedledee supporting evidence
-----------------------------------------

This repository contains supporting evidence that the amicable pair of
prime-order curves:

* Ep : y^2 = x^3 + 5 over GF(p) of order q, called Tweedledum;
* Eq : y^2 = x^3 + 5 over GF(q) of order p, called Tweedledee;

with

* p = 2^254 + 4707489545178046908921067385359695873
* q = 2^254 + 4707489544292117082687961190295928833

satisfy *some* of the [SafeCurves criteria](https://safecurves.cr.yp.to/index.html).

The criteria that are *not* satisfied are, in summary:

* large-magnitude CM discriminant (both curves have CM discriminant of absolute value 3,
  as a consequence of how they were constructed);
* completeness (complete formulae are possible, but not according to the Safe curves
  criterion);
* ladder support (not possible for prime-order curves);
* Elligator 2 support (indistinguishability is possible using
  [Elligator Squared](https://ifca.ai/pub/fc14/paper_25.pdf), but not using Elligator 2).

Tweedledum/Tweedledee is the first cycle output by
``sage amicable.sage --sequential --nearpowerof2 255 32``.

(The `--sequential` option makes the output completely deterministic and so resolves
ambiguity about which result is "first". For exploratory searches it is faster not to
use `--sequential`.)

**The cycle we call Tweedledum/Tweedledee has changed from the initial (September 2019) draft of the Halo paper.**

Note that although there is no known security problem with the Tweedle cycle, there are efficiency
and interoperability reasons to prefer the [Pasta cycle](https://github.com/zcash/pasta), as
explained in [this blog post](https://electriccoin.co/blog/the-pasta-curves-for-halo-2-and-beyond/).

Prerequisites:

* ``apt-get install sagemath``

Run ``sage verify.sage Ep`` and ``sage verify.sage Eq``; or ``./run.sh`` to run both
and also print out the results.

``amicable.sage`` also outputs isogenies (of degree up to ``ISOGENY_DEGREE_MAX``) suitable
for use with the "simplified SWU" method for hashing to an elliptic curve. This is based
on code from Appendix A of [Wahby and Boneh 2019](https://eprint.iacr.org/2019/403.pdf).
Note that simplified SWU is not necessarily the preferred method to hash to a given curve.
In particular it probably is not for the Tweedle curves; they only have suitable isogenies
of degree 23, which is rather large.

To check the correctness of the endomorphism optimization described in the Halo paper, run
``python3 injectivitylemma.py`` and ``python3 checksumsets.py``. To also generate animations
showing the minimum distances between multiples of ζ used in the proof, run ``./animation.sh``.

``animation.sh`` has the following prerequisites:

* ``apt-get install ffmpeg ffcvt``
* ``pip3 install bintrees Pillow``

``checksumsets.py`` on its own only requires the ``bintrees`` Python package.