Cryptographic Test Correction

Template:Wikify Cryptographic Test Correction is a technique, published in 2008 by Eric Levieil and David Naccache 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 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, who used a somewhat similar encryption process ($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.
$v_{i,j}=pr_{i,j}+((a_i+k \tau_i+g\epsilon_{i,j})e \mod p)$	$c_i=pq_i+2r_i+m_i$	encryption formula
$\tau_i$	$m_i$	the message
$v_{i,j}$	$c_i$	ciphertexts (and public keys)
$\{a_i,e,k,g\}$	$\{0,1,1,2\}$	$\{k,g\}=\{1,2\}$ means that $m_i$ is a bit.
$\epsilon_{i,j}$	$r_i$	first randomizer
$r_{i,j}$	$q_i$	second randomizer
$p$	$p$	secret key