snarkyJS compatible encryption algorithm

encryption.markdown

If you need a public key encryption system compatible with snarkyJS, I would suggest a hybrid cryptosystem using the Pallas curve (the Group type in snarkyJS) for the public key part, and Poseidon for the symmetric part.

To give a bit more detail:

• a private key would be a scalar field element x
• the corresponding public key would be the group element Group.generator.scale(x).

Let's say a message is an array of field elements msg: Array<Field> against a public key h: Group. In pseudcode:

type CipherText = {
  c1: Group,
  c2: Group,
  m: Array<Field>
}

function encrypt(msg: Array<Field>, h: Group) -> CipherText {
  const r = Group.random();
  const y = Scalar.random();

  const c1 = Group.generator.scale(y);
  // c2 is a "blinded" version of r. r can be recovered from [c1, c2]
  // if you have the private key corresponding to h
  const c2 = r.add(h.scale(y));

  // Now, r is a secret known only to the posessor of h's private key,
  // so, we can use it to initialize a Poseidon sponge expand r out into
  // a stream of field elements known only to the posessor of h's private key.
  //
  // We then use that stream of field elements to mask the message by adding
  // them together.

  let sponge = new Poseidon.Sponge();
  sponge.absorb(r.x);
  sponge.absorb(r.y);

  let m = [];
  for (let i = 0; i < msg.length; ++i) {
    let x = sponge.squeeze();
    m.push(msg[i].add(x));
  }

  return { c1, c2, m };
}

function decrypt({ c1, c2, m } : CipherText, s: Scalar) -> Array<Field> {
  // recover r from c1, c2
  let r = c2.sub(c1.scale(s));

  // We can now compute the same stream of field elements used in encryption
  let sponge = new Poseidon.Sponge();
  sponge.absorb(r.x);
  sponge.absorb(r.y);

  // Unmask m to get msg
  let msg = []
  for (let i = 0; i < msg.length; ++i) {
    let x = sponge.squeeze();
    msg.push(m[i].sub(x));
  }

  return msg;
}

We would have to add APIs for Group.random(), Scalar.random(), and Poseidon.Sponge.

this looks like elgamal encryption of a symmetric key to me. I think deriving the symmetric key from the key exchange is simpler:

function encrypt(msg: Array<Field>, other_pubkey: Group) -> CipherText {
  // key exchange
  const privkey = Scalar.random();
  const pubkey = Group.generator.scale(privkey);
  const shared_secret = other_pubkey.scale(privkey);

  let sponge = new Poseidon.Sponge();
  sponge.absorb(shared_secret.x); // don't think we need y, that's enough entropy

  // encryption
  let ciphertext = [];
  for chunk in msg {
    let key_stream = sponge.squeeze();
    let encrypted_chunk = key_stream.add(chunk);
    sponge.absorb(encrypted_chunk);  // don't forget to absorb for the auth tag
    ciphertext.push(encrypted_chunk);
  }

  // authentication tag
  let authentication_tag = sponge.squeeze();
  return (pubkey, ciphertext.extend(authentication_tag))
}

without the auth tag, if you know part of the message you can forge a new message as:

ciphertext[i] = ciphertext[i].add(message[i]).add(malicious_chunk);

This is basically what similar constructions do. For example, Strobe, or Xoodyak:

@mimoo Where does absorbing the encrypted data come from? It doesn't look like they do that in the attached construction

in strobe it's a bit hard to understand it as the specification hides a lot of the logic, for xoodyak I think the only clue is this sentence:

Encrypt(P ) works similarly, but it also absorbs P block per block as it is being encrypted.

or look at the spec that follows:

with CRYPT defined here:

I never looked at the spec of Xoodyak before so it's a bit hard to parse. I reckon they renamed squeezing "up" and absorbing "down".
What I'm reading is:

for chunk in m {
  encrypted_chunk = chunk XOR squeeze()
  absorb(encrypted_chunk)
  ciphertext.push(encrypted_chunk)
}
return encrypted_chunk

with DECRYPT = false and not taking into account the encoding of the operation (0x80) and the padding