babygiant-alt-bn128

这是一个Rust库，实现了在Baby Jubjub曲线（其基域是alt-bn-128（又称bn254）的标量域）上的多线程版本的baby-step giant-step算法，用于解密u40整数。这是Noir包noir-elgamal的配套库。

如果您想在前端使用此算法的WASM版本，请参阅配套的npm包。

⚠️ 警告：当前的实现容易受到时间攻击，因为运行时间取决于输入。请记住这一点，如果您在生产中使用它，请格外小心。

如何使用

首先，使用来自noir-elgamal的exp_elgamal_decrypt函数解密嵌入形式的点。

例如，此电路应输出嵌入在Baby Jubjub曲线上的明文值42

use dep::elgamal::{priv_to_pub_key,exp_elgamal_encrypt,exp_elgamal_decrypt};
use dep::std;

fn main(){
  let plaintext = 42;
  let private_key = 0x04d73359c9166e49aafaf9a4852eaa4dceb2c26878196b10e9048004ff5cc20c;
  let pub_key = priv_to_pub_key(private_key);
  let randomness = 0x03f90f366f9fd55bb1335eac3b11f2190f2ce9ff1769db241edaa7774136099b;
  let encrypted_point = exp_elgamal_encrypt(pub_key, plaintext, randomness);
  let decrypted_point = exp_elgamal_decrypt(private_key, encrypted_point);
  std::println(decrypted_point);
}

确实，运行nargo execute应在终端返回以下点

Point { x: 0x06184da392a17823e9c1d38cb50980b17150ffa411965b03f0b0200d9557daa9, y: 0x244a710118db92636e46e3f97bd80093ba7026ff97ca32d387145337e250549c }

对于解密的最后一步，即从先前的嵌入形式恢复原始明文（作为大小为40位的无符号整数），您可以通过在Cargo.toml中添加以下依赖项在Rust项目中导入此库

[dependencies]
babygiant-alt-bn128 = "0.1.1"

然后在src/main.rs中使用以下代码

use babygiant_alt_bn128::do_compute_dlog;

fn main() {
    let num_threads = 5;
    let dlog = do_compute_dlog("0x06184da392a17823e9c1d38cb50980b17150ffa411965b03f0b0200d9557daa9",
    "0x244a710118db92636e46e3f97bd80093ba7026ff97ca32d387145337e250549c",num_threads);
    assert!(42== dlog);
}

通过运行，您可以验证baby-step giant-step算法确实能够恢复原始明文值42

cargo run --release

Rust程序应在现代计算机上运行少于2秒。

技术描述

此库与Noir包https://github.com/jat9292/noir-elgamal/配套。

do_compute_dlog 是本crate中的主函数，它应该在解密的最后一步被调用，作为输入使用 exp_elgamal_decrypt Noir函数返回的值。

这段代码深受 zkay 的启发，并使用 arkworks crate 作为其主要依赖。

与zkay相比，主要有两个区别

1/ 我们将baby steps循环中的标量乘法替换为点加法，这平均提高了7倍的速度，并通过多线程进一步提高了2.5倍，使得解密 u40 而不是仅仅 u32 的时间缩短到6秒以下（在Mac M1芯片上），这就是为什么我们在 baby_giant 调用中将最大位数参数从 32 替换为 40 的原因。即使在浏览器中（参见配套的 npm包），当使用 num_threads 在 5 和 8 之间时，最坏情况下现在也实用地在9秒以内解密 u40（WASM开销）。

2/ 另一个很大的区别是，导入的arkworks库使用的是Edwards形式，而不是Noir中Baby Jubjub曲线使用的Twisted Edwards形式，因此我们进行了坐标变换，将点编码在Twisted Edwards形式而不是Edwards形式，以便使用与Noir实现相同的格式。

以下是函数签名

pub fn do_compute_dlog(x: &str, y: &str, num_threads: u64) -> u64

此函数将计算Baby Jubjub曲线上的点的离散对数，以Twisted Edwards形式表示。嵌入的明文应该是 u40（即小于 1099511627775 的无符号整数），否则程序将找不到有效的离散对数并引发恐慌。

x 和 y 是表示嵌入明文坐标的字符串，应与 noir-elgamal 包中 exp_elgamal_decrypt 返回的值具有相同的格式，即 x 和 y 应该是表示大小最多为 32 的两个字节数组的十六进制字符串。有效输入示例：x="0xbb77a6ad63e739b4eacb2e09d6277c12ab8d8010534e0b62893f3f6bb957051" 和 y="0x25797203f7a0b24925572e1cd16bf9edfce0051fb9e133774b3c257a872d7d8b"。还要记住，如果 (x,y) 不是Twisted Edwards形式的Baby Jubjub曲线上的有效点，程序将引发恐慌。