positive-thinking — uiuc2026

Description

Here when adventuring, we like positive thinking, even when you can't know the thoughts of others. We'll let you put other's thoughts through something that gets you something positive!

The service generated a uniformly random integer s in [0, 2^50), encrypted it as a one-slot TenSEAL CKKS vector, and published both the encrypted value and an encryption-only context. For each of at most 100 chosen ciphertexts x, it revealed one bit:

[ \operatorname{sign}\left(T_8\left(\frac{x}{2^{49}}\right)\right), ]

where Positive meant that the decrypted polynomial result was greater than zero. After every sign response, the client could submit one exact integer guess. The goal was therefore to turn the oscillating Chebyshev sign into a reliable comparison oracle without exhausting the CKKS modulus chain.

Analysis

1. Exact oracle and CKKS parameters

The relevant challenge parameters were:

Parameter	Value
Polynomial modulus degree	16384
Coefficient-modulus bit sizes	[60, 40, 40, 40, 40, 40, 40, 60]
Global CKKS scale	2^40
Secret interval	[0, 2^50)
Query limit	100

The server evaluated the submitted object exactly as follows:

normalized = ciphertext * (1.0 / 2**24) * (1.0 / 2**25)
result = normalized.polyval(
    [1, 0, -32, 0, 160, 0, -256, 0, 128]
).decrypt()[0]
positive = result > 0

The two normalization multiplications together divide by

[ D=2^{24}2^{25}=2^{49}. ]

Until the interval became a singleton, the solver sent -1 at each guess prompt, which could never equal the nonnegative secret.

2. The outer Chebyshev root is locally monotone

For

[ T_8(y)=128y^8-256y^6+160y^4-32y^2+1, ]

the roots are

[ \cos\left(\frac{(2k-1)\pi}{16}\right),\qquad k=1,\ldots,8. ]

Following the solver's notation, the two largest positive roots are

[ r_4=\cos(\pi/16)\approx0.9807852804, \qquad r_3=\cos(3\pi/16)\approx0.8314696123. ]

...