Here we give a detailed example of a hypothetical (and miniature, or "toy") challenge, for discretized Ring-RLWE (rlwed) over the 3rd cyclotomic ring (m = 3), modulo 7 (q = 7). The error parameter (or "width") is r = 1.414 = 2/sqrt(n) (where n = phi(m) = 2 is the degree of the ring), which corresponds to "scaled variance" svar = r^2 = 2, and is classified as "short" in our taxonomy. The challenge has two instances (numInstances = 2), with three samples per instance (numSamples = 3). We have arbitrarily assigned the challenge ID 9999 (challengeID = 9999).
Each of the six samples in the instances is a pair (a,b=a*s+e), where s is the secret and e is a (discretized) error term drawn from the error distribution. With high probability, each error term satisfies gSqNorm(e) < bound = 66. (See our paper for more information.)
To give some confidence that the instances are properly generated, we "spoil" all but one of them by revealing the secret; the choice of which one remains unspoiled is made by the NIST randomness beacon. In this example there are only two instances, so we need only one random bit. We use the least-significant bit of the 16th byte (0-indexed) of the NIST beacon at epoch 1378395540 (beaconEpoch = 1378395540, beaconOffset = 16). The 16th byte of the beacon is 0x86 = 0 mod 2, so the instance with instanceID = 0 is the "unspoiled," official challenge instance. The cryptanalytic goal is to recover the secret of this instance.
This challenge would appear in a directory called chall-id9999-rlwed-m3-q7-l3-short-toy. That directory would contain four files:
Below we show the contents and format of the data contained in the various files. Note that this is merely a description of the data; it does not necessarily reflect how this data is represented in any particular language. However, like the description below, messages parsed using a generated parser typically have member names similar to those given in the RLWE and Challenges message definitions. See the example parsers for C++, Java, Python, or Haskell for concrete syntax for accessing parsed messages in those languages.
(The xs in the data below are lists of mod-7 integer coefficients with respect to the decoding basis of 3rd cyclotomic ring.)
Challenge {challengeID = 9999,
numInstances = 2,
beaconEpoch = 1378395540,
beaconOffset = 16,
dparams = DiscParams {m = 3,
q = 7,
svar = 2.0,
bound = 66,
numSamples = 3}}
InstanceDisc {challengeID = 9999,
instanceID = 0,
params = DiscParams {m = 3,
q = 7,
svar = 2.0,
bound = 66,
numSamples = 3},
samples = [SampleDisc {a = Rq {m = 3,
q = 7,
xs = [-1,-3]},
b = Rq {m = 3,
q = 7,
xs = [-2,0]}},
SampleDisc {a = Rq {m = 3,
q = 7,
xs = [-3,-2]},
b = Rq {m = 3,
q = 7,
xs = [3,-3]}},
SampleDisc {a = Rq {m = 3,
q = 7,
xs = [-3,-3]},
b = Rq {m = 3,
q = 7,
xs = [2,1]}}]}
InstanceDisc {challengeID = 9999,
instanceID = 1,
params = DiscParams {m = 3,
q = 7,
svar = 2.0,
bound = 66,
numSamples = 3},
samples = [SampleDisc {a = Rq {m = 3,
q = 7,
xs = [3,-2]},
b = Rq {m = 3,
q = 7,
xs = [-1,3]}},
SampleDisc {a = Rq {m = 3,
q = 7,
xs = [-2,-2]},
b = Rq {m = 3,
q = 7,
xs = [1,-2]}},
SampleDisc {a = Rq {m = 3,
q = 7,
xs = [1,-2]},
b = Rq {m = 3,
q = 7,
xs = [-3,1]}}]}}]
Secret {challengeID = 9999,
instanceID = 1,
m = 3,
q = 7,
seed = "N\155t5\173,\219\182\GSy\170\204r\168yV\240\&4\135\159\242\&0\DC1\FS\208\202\132\&5\"\n\145\244",
s = Rq {m = 3,
q = 7,
xs = [-1,-1]}}
Secret {challengeID = 9999,
instanceID = 0,
m = 3,
q = 7,
seed = "",
s = Rq {m = 3,
q = 7,
xs = [1,2]}}
(The "seed" field can remain empty; it is used only as an extra
verification mechanism for our spoiled instances.)