L3 · FUNCTIONALMEASURED

Encrypted Parity

encrypted-parity · spec v0.1.0 · 0 implementations · 6 runners

Create implementationSpecification

DESCRIPTION

Computes

parity(x) = x mod 2

for an encrypted integer, or for many at once.

The function returns the least significant bit, and it is the doorway to bit extraction: given a way to peel off one bit, the binary representation x = Σ 2ⁱbᵢ follows, and with it comparisons, range checks and exact integer arithmetic over schemes that natively do neither.

It is not a polynomial, and on an approximate scheme it is worse than that: parity oscillates between adjacent integers, so noise that would be harmless elsewhere flips the answer. Accuracy has to hold at every integer in the declared range, not on average.

INTERFACE

encrypted_parity(
  in  ct     : Ciphertext  // an encrypted integer — one or many
  out ct     : Ciphertext  // the encrypted least significant bit of each
  ...               // anything else the realization needs — keys, context, encoding — is its own concern
)

PARAMETER SCHEMA

NAMETYPERANGE

value_countinteger1 – 2^16

max_valueinteger1 – 2^32

target_precisionnumber0.5 – 1

The schema belongs to the kernel. Each implementation declares which part of it it supports.

CORRECTNESS

01The output encodes 0 for even inputs and 1 for odd inputs.

02The requirement holds at every integer in the declared range; an answer that is right on average is wrong.

03Adjacent integers must be distinguished, which is the whole difficulty on an approximate scheme.

SECURITY PROPERTIES

No secrecy requirement beyond that of the scheme in use.

ASSUMPTIONS

Inputs are integers held exactly at the point of encryption. Bootstrapping, if the realization needs it, is part of the operation.

REFERENCES

repoFHERMA participation guide

otherChallenge contributed by IBM Research