puzzle-chaos-theory

puzzle-chaos-theory.md

In this puzzle, the sender and receiver each hold a pair of (sk, pk) for cryptographic operations. ElGamal encryption and BLS signatures are performed to generate a set of encrypted values represented as "blob," and the goal is to identify which message in the "blob" was the original value that was encrypted.

Let's first review the two key operations involved:

1. ElGamal Encryption

pub fn send(&self, m: Message, r: &Receiver) -> ElGamal {
    let c_2: G1Affine = (r.pk.mul(&self.sk) + m.0).into_affine();
    ElGamal(self.pk, c_2)
}

In ElGamal encryption, the sender combines the receiver's public key (r.pk), their own secret key (self.sk), and the message (m) to compute c_2. This encrypted value is then stored in the ElGamal struct along with the sender's public key (self.pk).

2. BLS Signature

pub fn authenticate(&self, c: &ElGamal) -> G2Affine {
    let hash_c = c.hash_to_curve();
    hash_c.mul(&self.sk).into_affine()
}

The sender further signs the encrypted message c using BLS signatures. The value sign is obtained by hashing c and then exponentiating it with the sender's secret key self.sk.

The final Blob structure contains the following components:

pub struct Blob {
    pub sender_pk: G1Affine,  // Sender's public key
    pub c: ElGamal,          // Encrypted data
    pub s: G2Affine,         // BLS signature for c
    pub rec_pk: G1Affine,    // Receiver's public key
}

Additionally, an auditor can verify the correctness of the signature using the check_auth function.

To determine the index of the original message in the blob, you can observe that $blob.c.1 = receiver.pk^{sender.sk} + m$. Therefore, by iterating through all 10 possible messages and subtracting each message from blob.c.1, you can obtain re_sender_pk, which should be equal to $receiver.pk^{sender.sk}$ if the message is correct.

Here's the code snippet to achieve this:

let hash_c = blob.c.hash_to_curve();
for (i, m) in messages.iter().enumerate() {
    let re_sender_pk = (blob.c.1 - m.0).into_affine();
    let lhs = { Bls12_381::pairing(re_sender_pk, hash_c) };
    let rhs = { Bls12_381::pairing(blob.rec_pk, blob.s) };
    if lhs == rhs {
        println!("index = {}", i);
    }
}

In summary, by iterating through all possible messages and computing re_sender_pk as $c_2 - message$, we can determine which message in the blob corresponds to the original value. Verification is done by checking if the pairings of re_sender_pk and $hash_c$, as well as blob.rec_pk and blob.s, are equal. If they match, we have successfully identified the index of the original message.