Template:Wikify Cryptographic Test Correction is a technique, published in 2008 by Eric Levieil and David Naccache [1] for shifting the burden of correcting Multiple Choice Questionnaires (MQC) to examinees. Because the corrector is only interested in the number of correct answers and not in knowing the examinee's answers to each and every question an ad-hoc cryptosystem was purposely engineered to be additively homomorphic. Levieil-Naccache scheme is multiplicatively homomorphic but only for evaluating functions with a constant depth of operations (a fact not mentioned in Levieil and Naccache's paper).

Levieil and Naccache's encryption method is very closely related to an encryption scheme proposed by Bram Cohen[2] in 1998.

This cryptosystem is also related to an encryption scheme published in 2009 by Marten van Dijk, Craig Gentry, Shai Halevi and Vinod Vaikuntanathan[3], who used a somewhat similar encryption process (${\displaystyle c_i=pq_i+2r_i+m_i}$, using van Dijk et al.'s notations) and extended it using techniques of Gentry to get a fully homomorphic encryption scheme.

The following variable renamings and assignments transform Levieil and Naccache's notations into van Dijk et al.'s notations.

Levieil-Naccache van Dijk et al. description.
${\displaystyle v_{i,j}=pr_{i,j}+((a_i+k \tau_i+g\epsilon_{i,j})e \mod p)}$ ${\displaystyle c_i=pq_i+2r_i+m_i}$ encryption formula
${\displaystyle \tau_i}$ ${\displaystyle m_i}$ the message
${\displaystyle v_{i,j}}$ ${\displaystyle c_i}$ ciphertexts (and public keys)
${\displaystyle \{a_i,e,k,g\}}$ ${\displaystyle \{0,1,1,2\}}$ ${\displaystyle \{k,g\}=\{1,2\}}$ means that ${\displaystyle m_i}$ is a bit.
${\displaystyle \epsilon_{i,j}}$ ${\displaystyle r_i}$ first randomizer
${\displaystyle r_{i,j}}$ ${\displaystyle q_i}$ second randomizer
${\displaystyle p}$ ${\displaystyle p}$ secret key

## References

1. Template:Cite web
2. Template:Cite web
3. Template:Cite web