Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

multiset equality checks in Triton-run code #202

Open
2 tasks
jan-ferdinand opened this issue Jun 1, 2023 · 0 comments
Open
2 tasks

multiset equality checks in Triton-run code #202

jan-ferdinand opened this issue Jun 1, 2023 · 0 comments
Labels
🕵 investigation This design change might improve the VM 🟡 prio: medium Not super urgent

Comments

@jan-ferdinand
Copy link
Member

Checking that two lists are equal up to permutation, also known as multiset equality, has many applications. For example, it allows non-deterministic sorting and verifying the result. Another application is to prove that two lists are indeed a permutation of each other without revealing the permutation, which is a useful primitive in privacy-preserving protocols.

  • Identify the best way to realize multiset equality checking in Triton VM.
  • Implement multiset equality checking.
@jan-ferdinand jan-ferdinand added 🕵 investigation This design change might improve the VM 🟡 prio: medium Not super urgent labels Jun 1, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
🕵 investigation This design change might improve the VM 🟡 prio: medium Not super urgent
Projects
None yet
Development

No branches or pull requests

1 participant