sunblaze-ucb / virgo Goto Github PK

I'm trying to run CMake but it gives this error

CMake Error at CMakeLists.txt:2 (project):
No CMAKE_CXX_COMPILER could be found.

Tell CMake where to find the compiler by setting either the environment
variable "CXX" or the CMake cache entry CMAKE_CXX_COMPILER to the full path
to the compiler, or to the compiler name if it is in the PATH.

Currently, protocols based on subfield VOLE, such as QuickSilver, are designated-verifier without an "s". Therefore, to prove to N verifiers, the prover's work is essentially N times. Note that this may improve in the future, but now subfield VOLE seems to be still subject to this limitation.

Virgo, however, is publicly verifiable and non-interactive. In some applications, it may be useful to consider an interactive version of Virgo, where it is designated-verifiers (by having the verifiers agree on some public randomness, such as sampling fresh randomness via commit-and-open of PRG seed shares).

There is a possibility that an interactive version of Virgo would be faster if getting rid of the extension field is beneficial.

Note that in Virgo, the extension field serves two purposes:

1. enabling the low-degree testing, which requires some two-arity, but Mersenne primes do not offer that
2. providing sufficient soundness for non-interactive use cases

An interactive Virgo does not need 2 but still needs 1. That is, Virgo would not need an extension field, but would also need to replace the Mersenne prime with something else. It, therefore, is uncertain whether the performance can be improved twice or more dramatically, or not significantly.

This note is left here for information purposes for someone else who may plan to change the prime number for certain applications.

The current implementation uses the complex number for the extension field F_{p^2}. This works if x^2+1 is an irreducible polynomial in F_p.

For all the Mersenne primes except 2, using the Rabin Irreducibility Test, complex numbers work fine. This is also the case considered by Virgo.

For all the primes p where p-1 has two-arity greater than 1, complex numbers would not work.

in conclusion, if one wants to change the prime number, such as for high two-arity, a different irreducible polynomial needs to be chosen. Luckily, one can try from x^2 + {-1, 0, 1} x + {-1, 1} to see if there is an easily computable one. If not, x^2 + 2, x^2 + 3 are also not hard to compute.

I'm guessing this doesn't support anything other than x86-64 builds, due to the use of AVX256 and inline assembly. Would be nice if it was also possible to build on aarch64/arm64 cpus.

In file included from /Users/tobias/repos/Virgo/src/VPD/fft_circuit_GKR.cpp:3:
/Users/tobias/repos/Virgo/include/linear_gkr/prime_field.h:9:10: fatal error: immintrin.h: No such file or directory
    9 | #include <immintrin.h>
      |          ^~~~~~~~~~~~~
compilation terminated.
make[2]: *** [CMakeFiles/fft_gkr.dir/build.make:76: CMakeFiles/fft_gkr.dir/src/VPD/fft_circuit_GKR.cpp.o] Error 1
make[1]: *** [CMakeFiles/Makefile2:85: CMakeFiles/fft_gkr.dir/all] Error 2
make: *** [Makefile:91: all] Error 2