id stringlengths 18 18 | type stringclasses 1
value | topic stringlengths 16 28 | subtopic stringlengths 58 92 | difficulty stringclasses 1
value | problem_statement stringlengths 584 3.07k | solution_proof stringlengths 1.25k 4.98k | final_answer stringlengths 5 1.14k | python_verification stringlengths 611 4.63k |
|---|---|---|---|---|---|---|---|---|
MATH-CRYPTO-000049 | math_competition_problem | Block Cipher Cryptanalysis | Differential cryptanalysis: difference distribution tables (DDT) and truncated differentials | Research Level | Let n ≥ 2 and let GF(2^n) be the finite field of order 2^n. Define the inverse S-box F_n: GF(2^n) → GF(2^n) by F_n(0)=0 and F_n(x)=x^{-1} for x ≠ 0. For a,b ∈ GF(2^n), define the DDT entry D_n(a,b) = #{x ∈ GF(2^n): F_n(x+a)+F_n(x)=b}, where + is field addition (equivalently XOR). Let Tr: GF(2^n) → GF(2) be the absolute... | 1. Edge cases. If a=0, then F_n(x+0)+F_n(x)=0 for every x, so D_n(0,0)=2^n and D_n(0,b)=0 for b≠0. If a≠0 and b=0, suppose F_n(x+a)=F_n(x). For x=0 the left side is F_n(a)+F_n(0)=a^{-1}≠0; for x=a it is F_n(0)+F_n(a)=a^{-1}≠0; for x not in {0,a}, 1/(x+a)=1/x implies a=0, contradiction. Hence D_n(a,0)=0.
2. Nonzero a,b... | For a=0: D_n(0,0)=2^n and D_n(0,b)=0 for b≠0. For a≠0: D_n(a,0)=0, and for b≠0, D_n(a,b)=2([b=a^{-1}]+[Tr(1/(ab))=0]). For a≠0 and T_a={b∈GF(2^n)^×: Tr(1/(ab))=0}, P_n(a,T_a)=1 if n is even, and 1-2^{1-n} if n is odd. Hence P_n(a,T_a)→1 as n→∞. Direct row enumeration: O(2^n) field operations; full DDT: O(2^{2n}) time a... | import sys
POLY = {2:0b111, 3:0b1011, 4:0b10011, 5:0b100101}
def mul(a,b,n):
mod = POLY[n]
res = 0
while b:
if b & 1:
res ^= a
b >>= 1
a <<= 1
if a & (1 << n):
a ^= mod
return res & ((1 << n) - 1)
def pow_gf(a,e,n):
res = 1
base = a
... |
MATH-CRYPTO-000066 | math_competition_problem | Analytic Number Theory | Hardy-Littlewood circle method for ternary Goldbach and Waring problems | Research Level | For a positive integer $q$ and an integer $n$, define the Ramanujan sum $c_q(n)=\sum_{\substack{1\le a\le q\\ \gcd(a,q)=1}} e^{2\pi i a n/q}$ and the major-arc factor of the ternary Goldbach problem
$$A(q,n)=\frac{\mu(q)^3\,c_q(-n)}{\varphi(q)^3},$$
where $\mu$ is the M\"obius function and $\varphi$ is Euler's totient.... | Step 1 (Ramanujan sums). Since $a\mapsto -a$ permutes the reduced residues mod $q$, we have $c_q(-n)=c_q(n)$. For a prime $p$, $c_p(n)=\sum_{a=1}^{p-1}e^{2\pi i an/p}$ equals $p-1$ if $p\mid n$ and $-1$ otherwise, because the full sum over $a=0,\dots,p-1$ is $p\cdot[p\mid n]$ and the term $a=0$ contributes $1$.
Step 2... | $\mathfrak{S}(n)=\prod_{p\mid n}(1-(p-1)^{-2})\prod_{p\nmid n}(1+(p-1)^{-3})$; it vanishes for even $n$ and is $\ge 2C_3>0$ for odd $n$; $\mathfrak{S}(15)/\mathfrak{S}(1)=8/13$. | from fractions import Fraction
import cmath, math
def primes(N):
s=[True]*(N+1);s[0]=s[1]=False
for i in range(2,int(N**0.5)+1):
if s[i]:
for j in range(i*i,N+1,i):s[j]=False
return [i for i in range(N+1) if s[i]]
def mu(q):
r=1;x=q;p=2
while p*p<=x:
if x%p==0:
... |
MATH-CRYPTO-000053 | math_competition_problem | Protocol Security | ProVerif applied pi-calculus modeling of TLS 1.3 handshake secrecy and forward secrecy | Research Level | Consider a symbolic (Dolev-Yao) abstraction of the TLS 1.3 (EC)DHE handshake in the applied pi-calculus, as analyzed by ProVerif.
Signature. Constructors: $g$ (constant), $\exp(x,y)$, $\mathsf{pk}(k)$, $\mathsf{sign}(m,k)$, $\mathsf{hkdf}(x,y)$, $\mathsf{senc}(m,k)$, $\mathsf{pair}(x,y)$. Equational theory $E$: $\exp(... | Step 1 (Frame, ephemeral). After the honest run, $\phi_a=\{g,\mathsf{pk}(sk_S),X,Y,\sigma,c=\mathsf{senc}(s,K)\}$ and phase 1 adds $sk_S$. The names $x,y,s$ remain restricted.
Step 2 (Locality). For this theory (subterm convergent destructors plus DH commutation), deduction is decidable by saturation: closing the know... | (a) ephemeral (EC)DHE TLS 1.3 core: s not derivable — forward secrecy holds; (b) static DH: s derivable after sk_S compromise. Result: (False, True). | import itertools
def norm(t):
# canonical DH: ('exp', frozenset of exponents) over g
if isinstance(t,tuple) and t[0]=='exp':
b=norm(t[1]);e=t[2]
if b=='g': return ('dh',frozenset([e]))
if isinstance(b,tuple) and b[0]=='dh': return ('dh',b[1]|frozenset([e]))
return ('exp',b,e)
... |
MATH-CRYPTO-000127 | math_competition_problem | Algebraic Geometry | Grothendieck duality and Serre duality on coherent sheaves | Research Level | Let $k$ be a field and $X\subset \mathbb{P}^4_k$ a smooth complete intersection of two cubic hypersurfaces, so $X$ is a smooth projective surface. (a) Using Grothendieck duality for the closed immersion $i:X\hookrightarrow \mathbb{P}^4$, i.e. $\omega_X\cong \mathcal{E}xt^{2}_{\mathbb{P}^4}(\mathcal{O}_X,\omega_{\mathbb... | Step 1 (Koszul). Let $f,g$ be the cubics; they form a regular sequence, giving the exact Koszul resolution $0\to\mathcal{O}(-6)\to\mathcal{O}(-3)^2\to\mathcal{O}\to\mathcal{O}_X\to0$ on $P=\mathbb{P}^4$.
Step 2 (Grothendieck duality). Apply $\mathcal{H}om(-,\omega_P)$ with $\omega_P=\mathcal{O}(-5)$ to obtain the comp... | $\omega_X\cong\mathcal{O}_X(1)$; $(h^0,h^1,h^2)(\mathcal{O}_X)=(1,0,5)$, $(h^0,h^1,h^2)(\omega_X)=(5,0,1)$ (Serre dual); $\chi(\mathcal{O}_X)=6$, $K_X^2=9$, $c_2(X)=63$. | from math import comb
def h(i,m,n=4):
if i==0: return comb(m+n,n) if m>=0 else 0
if i==n: return h(0,-m-n-1,n)
return 0
def coh_ci(t,degs=(3,3),n=4):
# Koszul for CI of two hypersurfaces: terms O(t-a-b) -> O(t-a)+O(t-b) -> O(t)
a,b=degs
T0=[h(i,t) for i in range(5)]
T1=[h(i,t-a)+h(i,t-b) for... |
MATH-CRYPTO-000191 | math_competition_problem | Differential Geometry | Bochner-Weitzenbock formulas and Lichnerowicz-Obata eigenvalue bounds | Research Level | Let $(M^n,g)$ be a closed (compact, boundaryless) connected smooth Riemannian manifold of dimension $n\ge 2$. Assume $\mathrm{Ric}\ge (n-1)k\,g$ for some constant $k>0$. Let $\Delta = \mathrm{tr}\,\nabla^2$ be the (non-positive) Laplace-Beltrami operator, and let $\lambda_1>0$ be the first nonzero eigenvalue, so $\Delt... | (a) Work in normal coordinates at $p$ (so $g_{ij}=\delta_{ij}$, $\Gamma^k_{ij}(p)=0$). Then $\tfrac12\Delta|\nabla f|^2 = \sum_{i,j}\big(f_{ij}f_{ij} + f_j f_{jii}\big)$. By the Ricci identity, commuting covariant derivatives: $f_{jii}=f_{iji}$ (Hessian symmetric) and $f_{iji} = f_{iij} + R_{jl}f_l$ (since $f_{ijk}-f_{... | $\lambda_1\ge nk$, with equality forcing $\nabla^2 f=-kfg$ and $|\nabla f|^2+kf^2=k$; on $S^n(r)$, $\lambda_1=n/r^2$, so for $n=4,r=2$: $\lambda_1=1$. | import sympy as sp
# Verify spherical-harmonic eigenvalue on S^n(r) via radial decomposition in R^{n+1}
def check(n, r):
xs = sp.symbols('x0:%d' % (n + 1))
rho = sp.sqrt(sum(x**2 for x in xs))
# degree-1 homogeneous harmonic x0; Delta_S(phi) = r^2*(Lap(u) - u_rr - n/rho u_r) at rho=r
# For homogeneous ... |
MATH-CRYPTO-000005 | math_competition_problem | Analytic Number Theory | Selberg trace formula and spectral theory of Maass waveforms | Research Level | Let $\mathbb{H}=\{z=x+iy: y>0\}$ carry the hyperbolic metric $ds^2=(dx^2+dy^2)/y^2$, area measure $d\mu=dx\,dy/y^2$, and Laplacian $\Delta=-y^2(\partial_x^2+\partial_y^2)$. Let $\Gamma=\mathrm{PSL}_2(\mathbb{Z})$ act by M\"obius transformations. The standard fundamental domain is $\mathcal{F}=\{z\in\mathbb{H}: |x|\le 1... | **(a) Area of the fundamental domain.**
For fixed $x\in[-1/2,1/2]$, the domain $\mathcal{F}$ contains exactly those $y$ with $y\ge\sqrt{1-x^2}$. Hence
$$\mu(\mathcal{F})=\int_{-1/2}^{1/2}\int_{\sqrt{1-x^2}}^{\infty}\frac{dy}{y^2}\,dx=\int_{-1/2}^{1/2}\frac{dx}{\sqrt{1-x^2}}.$$
Evaluating the arcsine integral gives $2\... | $\mu(\mathcal{F})=\pi/3$; $I(t)=\dfrac{1}{12t}-\dfrac{1}{144}+O(t)$ as $t\to0^+$; and $N(T)\sim T^2/12$. | import math
def simpson(f, a, b, n=200000):
if n % 2:
n += 1
h = (b - a) / n
s = f(a) + f(b)
for k in range(1, n):
s += (4 if k % 2 else 2) * f(a + k * h)
return s * h / 3
# (a) area of fundamental domain: integrate 1/sqrt(1-x^2) over [-1/2,1/2]
area = simpson(lambda x: 1.0 / math.... |
MATH-CRYPTO-000193 | math_competition_problem | Complex Analysis | Nevanlinna defect relations and value distribution of meromorphic functions | Research Level | Let $q\ge 2$ be an integer and $f_q(z)=\int_0^z e^{-t^q}\,dt$, an entire function of order $q$. For $a\in\mathbb{C}$ define the proximity function $m(r,a)=\frac{1}{2\pi}\int_0^{2\pi}\log^+\frac{1}{|f(re^{i\theta})-a|}d\theta$, $m(r,\infty)=\frac{1}{2\pi}\int_0^{2\pi}\log^+|f(re^{i\theta})|d\theta$, the characteristic $... | Step 1 (asymptotic values). Let $\omega=e^{2\pi i/q}$ and $S_k=\{|\arg z-2\pi k/q|<\pi/(2q)\}$. On the ray $\arg t=2\pi k/q$ we have $t^q=|t|^q$, so $a_k:=\int_0^{\infty\omega^k}e^{-t^q}dt=\omega^k\Gamma(1+1/q)$. In $S_k$, $\mathrm{Re}(z^q)>0$; deforming the contour, $f(z)-a_k=-\int_z^{\infty}e^{-t^q}dt$. Integrating b... | $T(r,f_q)\sim r^q/\pi$; $\delta(\infty)=1$, $\delta(\omega^k\Gamma(1+1/q))=1/q$ for $k=0,\dots,q-1$, all other values non-deficient; $\sum\delta=2$. For $q=4$: $\delta(i^k\Gamma(5/4))=1/4$, total $2$. | import mpmath as mp
mp.mp.dps=30
q=4
G=mp.gamma(1+mp.mpf(1)/q)
def f(z):
return mp.quad(lambda s: z*mp.e**(-(s*z)**q),[0,0.5,1])
def prox(r,a,n=400):
tot=0
for j in range(n):
th=2*mp.pi*(j+0.5)/n
z=r*mp.e**(1j*th)
if a is None:
v=abs(f(z)); tot+=max(0,mp.log(v))
e... |
MATH-CRYPTO-000118 | math_competition_problem | Side-Channel Resistance | Constant-time cryptographic arithmetic: avoiding timing leaks in field inversions | Research Level | Let p=2^{255}-19, a known prime, and let F_p be the field with p elements. For x in F_p define Inv_0(x)=x^{p-2} mod p. For x not equal to 0 this equals x^{-1}; also Inv_0(0)=0. Treat F_p multiplication and squaring as atomic operations of unit cost in a leakage model where the observable trace is the ordered list of op... | 1. Reduction to fixed exponentiation. Since p is prime, Fermat's little theorem gives a^{p-1}=1 for every nonzero a in F_p. Hence a^{p-2}=a^{-1} for a nonzero. For a=0, a^{p-2}=0. Therefore Inv_0 is a total function and is computed by the single fixed public exponent e=p-2, with no secret-dependent branch or exception.... | Inv_0(x)=x^{2^{255}-21} mod p. The constant-time Montgomery ladder processes 255 public exponent bits; each iteration performs exactly one multiplication and one squaring, so the fixed trace has 255 multiplications plus 255 squarings = 510 F_p operations, independent of x. It returns x^{-1} for x not equal to 0 and ret... | import random
p = (1 << 255) - 19
e = p - 2
bits = [int(c) for c in bin(e)[2:]]
def inv0_ladder(x):
x %= p
r0 = 1
r1 = x
ops = 0
for b in bits:
if b == 0:
r1 = (r0 * r1) % p
r0 = (r0 * r0) % p
else:
r0 = (r0 * r1) % p
r1 = (r1 * r1) %... |
MATH-CRYPTO-000144 | math_competition_problem | Combinatorics & Graph Theory | Lovász Local Lemma: algorithmic Moser-Tardos constructive formulations | Research Level | Let $\mathcal{X}=\{x_1,\dots,x_n\}$ be mutually independent random variables, each uniform on $\{0,1\}$. Let $\mathcal{A}=\{A_1,\dots,A_m\}$ be bad events. Each $A_i$ is determined by a variable set $\mathrm{vbl}(A_i)\subseteq\mathcal{X}$ of size exactly $k\ge 2$, and $A_i$ is the event that a fixed $k$-clause (a disju... | (a) Witness trees.
Fix a log $C:\mathbb{N}\to\mathcal{A}$ recording the event resampled at each step. For step $t$, build the witness tree $\tau(t)$ as follows:
- Start with a root labelled $C(t)$.
- For $s=t-1$ down to $1$, if some vertex $v$ has label $[v]$ with $C(s)\in\Gamma^+([v])$, attach a new child labelled $C... | Expected number of resamplings is at most $\sum_A x(A)/(1-x(A))$. Under $e2^{-k}(d+1)\le1$ this is at most $m/d$, or exactly $m/(2^k-1)$ when $d=0$. Expected time is $O(k(n+m))$. The $2^k$ clauses on $k$ variables (unsatisfiable, $d=2^k-1$) show tightness up to the factor $e$. | import random, itertools, math
def mt(n, clauses, rng):
a = [rng.randint(0, 1) for _ in range(n)]
viol = lambda c: all(a[v] != s for v, s in c)
cnt = 0
while True:
bad = [c for c in clauses if viol(c)]
if not bad:
return a, cnt
for v, _ in bad[0]:
a[v] = ... |
MATH-CRYPTO-000204 | math_competition_problem | Combinatorics & Graph Theory | Lovász Local Lemma: algorithmic Moser-Tardos constructive formulations | Research Level | Let $\Phi$ be a $k$-CNF formula ($k\ge 2$) on Boolean variables $x_1,\dots,x_n$ with $m$ clauses. Each clause contains exactly $k$ literals on $k$ distinct variables. Two distinct clauses $C\ne C'$ are neighbors, written $C\sim C'$, if they share a variable, regardless of sign. Let $\Gamma(C)$ be the set of neighbors o... | Setup. Index the resampling steps $t=1,2,\dots$ and let $C_t$ be the clause resampled at step $t$.
Witness trees. For step $t$, the witness tree $\tau_t$ is built backward from $C_t$. Its root is labeled $C_t$. For $s=t-1,\dots,1$, look for nodes whose label $L$ satisfies $C_s\in\Gamma^+(L)$. If such nodes exist, atta... | Under $e2^{-k}(d+1)\le1$ with $d\ge1$: $\mathbb{E}[\text{total resamplings}]\le m/d$. For $d=0$, the bound is $m/(2^k-1)$, which is tight. The largest admissible $d$ is $d_{\max}(k)=\lfloor 2^k/e\rfloor-1$, giving $1,4,10,375$ for $k=3,4,5,10$. | import math, random
def dmax(k):
return math.floor(2**k/math.e)-1
assert [dmax(k) for k in (3,4,5,10)]==[1,4,10,375]
for k in range(2,20):
d=dmax(k)
assert math.e*(d+1)<=2**k and math.e*(d+2)>2**k
if d>=1:
assert (1/(d+1))*(1-1/(d+1))**d>=2**-k
def mt(clauses,n,rng):
x=[rng.randint(0,1) f... |
MATH-CRYPTO-000189 | math_competition_problem | Algebraic Geometry | Intersection theory, Chow rings, and Riemann-Roch-Hirzebruch theorem | Research Level | Let $k$ be an algebraically closed field and $e\ge 0$ an integer. Let $\pi:\mathbb{F}_e=\mathbb{P}(\mathcal{O}_{\mathbb{P}^1}\oplus\mathcal{O}_{\mathbb{P}^1}(-e))\to\mathbb{P}^1$ be the Hirzebruch surface. Use the Grothendieck convention $\pi_*\mathcal{O}(1)=\mathcal{O}\oplus\mathcal{O}(-e)$. Let $C_0$ be the section w... | **Step 1 (intersection numbers).** In $A^*$ we have $C_0^2=-e$, $C_0f=1$ and $f^2=0$. For $D=aC_0+bf$ this gives $D^2=-ea^2+2ab$.
**Step 2 (canonical class).** The relative Euler sequence gives $K_{\mathbb{F}_e}=\pi^*(K_{\mathbb{P}^1}+\det\mathcal{E})-2C_0$ with $\det\mathcal{E}=\mathcal{O}(-e)$. Hence $K=-2C_0-(e+2)f... | $K=-2C_0-(e+2)f$, $K^2=8$, $\mathrm{td}=1+C_0+\tfrac{e+2}{2}f+[\mathrm{pt}]$, and for all $(a,b)\in\mathbb{Z}^2$: $\chi(\mathbb{F}_e,\mathcal{O}(aC_0+bf))=(a+1)(b+1)-\tfrac{e\,a(a+1)}{2}$. Edge case: $\chi=0$ for $a=-1$. Asymptotics: $\chi(nL)\sim\tfrac{2ab-ea^2}{2}n^2$. The closed form costs $O(1)$ ring operations ver... | from fractions import Fraction as F
def inter(D1, D2, e):
a1, b1 = D1; a2, b2 = D2
return a1*a2*(-e) + a1*b2 + a2*b1
def chi_hrr(a, b, e):
D = (a, b); K = (-2, -(e+2))
return F(inter(D, D, e), 2) - F(inter(D, K, e), 2) + 1
def closed(a, b, e):
return (a+1)*(b+1) - e*a*(a+1)//2
def chi_P1(k):
... |
MATH-CRYPTO-000026 | math_competition_problem | Post-Quantum Cryptography | Module-LWE and Ring-LWE error distribution parameter tuning (ML-KEM/Kyber) | Research Level | Let $\eta\ge 1$ be an integer. The centered binomial distribution $B_\eta$ is the law of $X=\sum_{i=1}^{\eta}(a_i-b_i)$, where $a_1,\dots,a_\eta,b_1,\dots,b_\eta$ are independent and uniform on $\{0,1\}$. Let $n\ge 1$ and $R=\mathbb{Z}[x]/(x^n+1)$. For $k\ge 1$, let $\mathbf{s}=(s^{(1)},\dots,s^{(k)})\in R^k$ and $\mat... | Step 1 (moments of $B_\eta$). Write $Y_i=a_i-b_i$. Then $Y_i$ takes the values $-1,0,1$ with probabilities $1/4,1/2,1/4$. Hence $\mathbb{E}[Y_i]=\mathbb{E}[Y_i^3]=0$ and $\mathbb{E}[Y_i^2]=\mathbb{E}[Y_i^4]=1/2$. The $Y_i$ are independent, and $X=\sum_i Y_i$ is symmetric, so all odd moments of $X$ vanish. In particular... | $\mathrm{Var}(W)=N\eta^2/4$ and $\mathbb{E}[W^4]=N\left(\frac{3\eta^2-\eta}{4}\right)^2+\frac{3N(N-1)\eta^4}{16}$ with $N=kn$. For ML-KEM-768 ($n=256$, $k=3$, $\eta=2$): $\mathrm{Var}(W)=768$, $\mathbb{E}[W^4]=1771968$, and excess kurtosis $\kappa=13/3072$. | from fractions import Fraction as F
from itertools import product
import random
def cbd(eta):
d = {}
for bits in product([0, 1], repeat=2 * eta):
x = sum(bits[:eta]) - sum(bits[eta:])
d[x] = d.get(x, 0) + F(1, 4 ** eta)
return d
def mom(d, p):
return sum(v * x ** p for x, v in d.items(... |
MATH-CRYPTO-000162 | math_competition_problem | Homomorphic Encryption | CKKS approximate arithmetic homomorphic encryption and rescaling analysis | Research Level | Let $N$ be a power of two, $R=\mathbb{Z}[X]/(X^N+1)$, and $R_q=R/qR$. Let $q=p\cdot q'$, where $p\ge 3$ is odd. For $a\in\mathbb{Z}$, let $[a]_p$ denote the centered residue of $a$ modulo $p$. It is the unique integer in $\{-\tfrac{p-1}{2},\dots,\tfrac{p-1}{2}\}$ congruent to $a$ modulo $p$. Extend $[\cdot]_p$ coeffici... | **(a) The rescaling error.**
Write $r_i=[c_i]_p\in R$. By definition, $p c_i' = c_i - r_i$ over $\mathbb{Z}$ coefficient-wise. Hence
$$p(c_0'+c_1's)=(c_0+c_1s)-(r_0+r_1s)$$
holds in $R$. Reducing modulo $q=pq'$ and dividing by $p$ is legitimate, since $p\cdot(\cdot)$ maps $q'R$ onto $qR$. This gives
$$c_0'+c_1's\equiv... | $e_{\mathrm{rs}}=-([c_0]_p+[c_1]_p s)/p$, and $\mathbb{E}\|\sigma(e_{\mathrm{rs}})\|_2^2=\dfrac{N^2(h+1)(p^2-1)}{12p^2}$. | import itertools, cmath, random
from fractions import Fraction
def negamul(a,b,N):
c=[0]*N
for i in range(N):
for j in range(N):
k=i+j
if k<N: c[k]+=a[i]*b[j]
else: c[k-N]-=a[i]*b[j]
return c
def emb(a,N):
return [sum(a[j]*cmath.exp(1j*cmath.pi*(2*k+1)*j/N) ... |
MATH-CRYPTO-000117 | math_competition_problem | Side-Channel Resistance | Higher-order boolean masking schemes against Differential Power Analysis (DPA) | Research Level | Let n,d\in\mathbb{Z}_{>0} with d\ge 1 and set F=\mathbb{F}_2^n. For y\in F let \operatorname{wt}(y)=\sum_{j=1}^n y_j and \psi(y)=(-1)^{\operatorname{wt}(y)}. A (d+1)-share Boolean d-th order masking of a secret X\in F is the following joint distribution: choose U_0,\ldots,U_{d-1} i.i.d. uniform on F, independent of X; ... | 1. Conditional law. Fix x\in F. The map \Phi_x:F^d\to H_x, (u_0,\ldots,u_{d-1})\mapsto(u_0,\ldots,u_{d-1},x\oplus u_0\oplus\cdots\oplus u_{d-1}), is a bijection because the last coordinate is forced by the xor relation. Hence, under the masking distribution conditioned on X=x, every element of H_x has probability 2^{-n... | For every A\subseteq\{0,\ldots,d\}, \rho_A=1 if A=\{0,\ldots,d\}, and \rho_A=0 otherwise. Hence any subset of at most d shares is independent of X, so all lower-order centered Hamming-weight products have zero signed correlation with \psi(X); the full d+1-share product satisfies D_{\{0,\ldots,d\}}=\psi(X) and has unit ... | import itertools
from collections import Counter
from fractions import Fraction
def wt(y):
return bin(y).count('1')
def psi(y):
return 1 if wt(y) % 2 == 0 else -1
def make_ys(x, u_tuple):
y = list(u_tuple)
z = 0
for u in u_tuple:
z ^= u
y.append(x ^ z)
return y
def check(n, d):
... |
MATH-CRYPTO-000123 | math_competition_problem | Algebraic Number Theory | Chebotarev density theorem applications to Galois group determination | Research Level | Let $f(x) = x^5 - x - 1 \in \mathbb{Z}[x]$. Let $K$ be the splitting field of $f$ over $\mathbb{Q}$, and let $G = \mathrm{Gal}(K/\mathbb{Q})$. View $G$ as a subgroup of $S_5$ through its action on the five roots of $f$.
For a prime $p \nmid \mathrm{disc}(f)$, let $\lambda_p$ denote the factorization pattern of $f \bmo... | Step 0 (Irreducibility and the discriminant).
For a trinomial $x^5 + ax + b$, the discriminant is $\mathrm{disc} = 5^5 b^4 + 4^4 a^5$.
With $a = b = -1$ this gives $\mathrm{disc}(f) = 3125 - 256 = 2869 = 19 \cdot 151$.
This value is squarefree and positive, but it is not a perfect square. Hence $f$ is separable, and th... | $G = \mathrm{Gal}(K/\mathbb{Q}) \cong S_5$, certified by the following witnesses: $\mathrm{disc}(f) = 2869 = 19 \cdot 151$ (not a square), $\mathrm{Frob}_5$ is a 5-cycle, and $\mathrm{Frob}_2$ has type $(2,3)$. The Chebotarev densities are $\delta(\mathcal{P}_{\mathrm{root}}) = 19/30$, $\delta(\mathcal{P}_{\mathrm{irr}... | import itertools
from fractions import Fraction
from collections import Counter
def norm(a):
while a and a[-1] == 0:
a.pop()
return a
def dm(a, b, p):
a = norm([x % p for x in a]); b = norm([x % p for x in b])
q = [0] * max(len(a) - len(b) + 1, 1)
inv = pow(b[-1], p - 2, p)
while a and... |
MATH-CRYPTO-000112 | math_competition_problem | Formal Verification | Dafny / Separation Logic for heap-manipulating program memory safety verification | Research Level | Consider a first-order imperative language with variables \(\mathrm{Var}\), locations \(\mathrm{Loc}=\mathbb{N}\), values \(\mathrm{Val}=\mathrm{Loc}\cup\{\mathrm{nil}\}\), and a finite partial heap \(h:\mathrm{Loc}\rightharpoonup\mathrm{Val}\). A state is \((\sigma,h)\). Separation conjunction \(P\ast Q\) denotes disj... | We prove partial correctness, memory safety, and termination.
Definitions and elementary lemmas. The predicate \(ll\) is well founded on the length of the finite sequence \(\alpha\). Lemma 1 (unfolding): \(ll(x,\varepsilon)\) holds iff \(x=\mathrm{nil}\) and the heap is \(\mathrm{emp}\); and \(ll(x,a::\alpha')\) holds... | The procedure is total-correct and memory-safe. The valid verification triple is \[\{ll(x_0,\alpha)\land x=x_0\}\ \mathrm{reverse}(x)\ \{ll(r,\mathrm{rev}\,\alpha)\}.\] A sufficient inductive loop invariant is \[I\equiv \exists \alpha_1,\alpha_2.\; ll(p,\mathrm{rev}\,\alpha_1)\ast ll(x,\alpha_2)\land \alpha=\alpha_1{+}... | from itertools import permutations
def make_heap(order):
heap = {}
for i, node in enumerate(order):
nxt = order[i+1] if i+1 < len(order) else None
heap[node] = nxt
return heap, (order[0] if order else None)
def to_list(heap, head):
out = []
seen = set()
cur = head
while cur... |
MATH-CRYPTO-000203 | math_competition_problem | Combinatorics & Graph Theory | Szemerédi regularity lemma and graph limit theory (graphons) | Research Level | Let $W:[0,1]^2\to[0,1]$ be a symmetric measurable graphon, i.e. $W(x,y)=W(y,x)$ for a.e. $(x,y)$, with Lebesgue measure $\mu$ on $[0,1]$. For a finite measurable partition $P=\{V_1,\dots,V_k\}$ of $[0,1]$ into positive-measure sets, define the step graphon $W_P$ by
$$ W_P(x,y)=\frac{1}{\mu(V_a)\mu(V_b)}\int_{V_a\times ... | Proof. Identify $L^2([0,1]^2)=L^2(\mu\times\mu)$. For a partition $P$, let $\mathcal{B}_P$ be the sigma-algebra generated by the rectangles $V_a\times V_b$. Then $W_P=\mathbb{E}[W\mid\mathcal{B}_P]$ is the orthogonal projection of $W$ onto $L^2(\mathcal{B}_P)$. Put $E_t=\|W-W_{P_t}\|_2^2$. Since $0\le W\le1$ and $0\le ... | For every $\varepsilon\in(0,1)$, the refinement algorithm terminates with a partition $P$ satisfying $\operatorname{disc}_P(W)\le\varepsilon$, using at most $\lfloor\varepsilon^{-2}\rfloor$ refinement steps and producing at most $4^{\lfloor\varepsilon^{-2}\rfloor}$ parts. The finite-graph version with normalized cut di... | import math, random
def make_graph(n, seed=12345, p=0.5):
rng = random.Random(seed)
A = [[0.0] * n for _ in range(n)]
for i in range(n):
for j in range(i + 1, n):
if rng.random() < p:
A[i][j] = A[j][i] = 1.0
return A
def block_average(A, P):
n = len(A)
AP = ... |
MATH-CRYPTO-000008 | math_competition_problem | Algebraic Geometry | Moduli spaces of algebraic curves and Deligne-Mumford compactification | Research Level | Let \(n=6\) and let \(\overline{\mathcal M}_{0,6}\) be the Deligne--Mumford moduli stack of stable genus-zero curves with six ordered marked points. For a subset \(A\subset \{1,\dots,6\}\) with \(2\le |A|\le 4\), let \(D_A=D_{A|A^c}\) denote the boundary divisor in \(\overline{\mathcal M}_{0,6}\) whose generic point ha... | Let \(U=\{1,\dots,6\}\). Since \(\dim\overline{\mathcal M}_{0,6}=6-3=3\), and both \(D_S\) and \(D_T\) are boundary divisors of codimension one, the class \(\psi_3 D_S D_T\) has total codimension three and may be evaluated as an integer.
The partitions satisfy \(S=\{1,2\}\subsetneq T=\{1,2,3,4\}\subsetneq U\). For suc... | I = 1 | from fractions import Fraction
from math import factorial
def psi_integral_0(k, exps):
deg = sum(exps.values())
if k < 3:
return Fraction(1, 1) if deg == 0 else Fraction(0, 1)
if deg != k - 3:
return Fraction(0, 1)
num = factorial(k - 3)
den = 1
for a in exps.values():
... |
MATH-CRYPTO-000128 | math_competition_problem | Algebraic Geometry | Moduli spaces of algebraic curves and Deligne-Mumford compactification | Research Level | Work over $\mathbb{C}$. For $n \geq 3$, let $\overline{M}_{0,n}$ be the Deligne-Mumford-Knudsen moduli space of stable $n$-pointed genus-0 curves. Such a curve is a connected nodal curve $C$ of arithmetic genus $0$. It carries distinct smooth marked points $p_1,\dots,p_n$, and every irreducible component has at least $... | **Step 0: the string equation.** Let $\pi:\overline{M}_{0,n+1}\to\overline{M}_{0,n}$ forget the point $p_{n+1}$ and stabilize. Let $D_{i,n+1}$ be the boundary divisor where $p_i$ and $p_{n+1}$ lie alone on a rational tail. Then $\psi_i=\pi^*\psi_i+D_{i,n+1}$. Moreover $\psi_i\cdot D_{i,n+1}=0$, because $\mathbb{L}_i$ i... | $\int_{\overline{M}_{0,n}}\prod\psi_i^{a_i}=\binom{n-3}{a_1,\dots,a_n}$ and #boundary divisors $=2^{n-1}-n-1$; for $n=7$: $\int\psi_1^2\psi_2^2=6$ and $56$ boundary divisors. | from functools import lru_cache
from math import factorial
from itertools import combinations
@lru_cache(maxsize=None)
def F(a):
n = len(a)
assert sum(a) == n - 3
if n == 3:
return 1
k = a.index(0)
b = a[:k] + a[k+1:]
tot = 0
for j in range(len(b)):
if b[j] >= 1:
... |
MATH-CRYPTO-000194 | math_competition_problem | Complex Analysis | Bieberbach conjecture, de Branges theorem, and Loewner evolution | Research Level | Let $\kappa:[0,\infty)\to\partial\mathbb{D}$ be measurable (the driving function). For $z\in\mathbb{D}$ let $w(z,t)$ solve the radial Loewner ODE
$$\frac{\partial w}{\partial t}=-w\,\frac{1+\kappa(t)w}{1-\kappa(t)w},\qquad w(z,0)=z.$$
It is classical (Loewner, Pommerenke) that $f(z)=\lim_{t\to\infty}e^{t}w(z,t)=z+a_2z^... | Step 1 (coefficient ODEs). Expand $\frac{1+\kappa w}{1-\kappa w}=1+2\kappa w+2\kappa^2w^2+O(w^3)$. Write $w=e^{-t}v$ with $v=z+b_2(t)z^2+b_3(t)z^3+\cdots$ and $b_n(0)=0$. Then $w_t=e^{-t}(v_t-v)$. The ODE becomes
$$v_t=-2\kappa e^{-t}v^2-2\kappa^2e^{-2t}v^3+\cdots.$$
Compare coefficients. For $z^2$: $b_2'=-2\kappa e^{-... | (a) $a_2=-2\int_0^\infty e^{-t}\kappa\,dt$ and $a_3=4\big(\int_0^\infty e^{-t}\kappa\,dt\big)^2-2\int_0^\infty e^{-2t}\kappa^2\,dt$.
(b) $|a_2|\le2$ and $|a_3|\le3$, with $|a_3|=3$ iff $\kappa$ is a.e. a constant $c$ (rotated Koebe function $z/(1+cz)^2$, $a_3=3c^2$). By density, $|a_3|\le3$ on all of $\mathcal{S}$.
(c)... | import numpy as np
def coeffs_ode(kappa, T=40.0, N=200000):
# RK4 on b2' = -2 k e^{-t}, b3' = -4 k e^{-t} b2 - 2 k^2 e^{-2t}
h = T / N
b2 = 0j
b3 = 0j
def F(t, b2):
k = kappa(t)
return -2*k*np.exp(-t), -4*k*np.exp(-t)*b2 - 2*k*k*np.exp(-2*t)
t = 0.0
for _ in range(N):
... |
MATH-CRYPTO-000081 | math_competition_problem | Topology & Dynamics | Thurston geometrization of 3-manifolds and Mostow rigidity | Research Level | Let $M$ be the complement of the figure-eight knot in $S^3$. It is known that $M$ admits a complete hyperbolic structure obtained by gluing two regular ideal tetrahedra. An ideal tetrahedron in $\mathbb{H}^3$ is determined up to isometry by a shape parameter $z \in \mathbb{C} \setminus \{0,1\}$ with $\operatorname{Im} ... | (a) From $z(1-z) = w(1-w)$, we obtain $z - z^2 = w - w^2$, hence $z^2 - w^2 - z + w = 0$, i.e., $(z-w)(z+w-1) = 0$. Thus either $z = w$ or $z + w = 1$.
Case 1: $z = w$. Then the first equation becomes $z^2 (1-z)^2 = 1$, so $z(1-z) = \pm 1$. Since $\operatorname{Im} z > 0$, the equation $z(1-z) = 1$ gives $z^2 - z + 1 ... | The unique solution is $z = w = e^{i\pi/3}$. The volume is $\operatorname{Vol}(M) = 2 \mathrm{Cl}_2(\pi/3) \approx 2.029883212819$ (to 12 decimal places). By Mostow rigidity, this volume is a topological invariant of the figure-eight knot complement. | import mpmath as mp
mp.mp.dps = 50
def clausen2(theta):
return mp.nsum(lambda n: mp.sin(n*theta)/n**2, [1, mp.inf])
cl2_pi3 = clausen2(mp.pi/3)
known_cl2_pi3 = mp.mpf('1.0149416064096536250212025542745202859416893075303')
assert abs(cl2_pi3 - known_cl2_pi3) < mp.mpf('1e-40'), f'Cl2(pi/3) mismatch: {cl2_pi3} vs {... |
MATH-CRYPTO-000159 | math_competition_problem | Threshold Cryptography | FROST Schnorr threshold signatures and distributed key generation (DKG) | Research Level | Let $\mathbb{G}=\langle g\rangle$ be a cyclic group of prime order $q$, written multiplicatively. Let $H_1,H_2$ be hash functions with outputs in $\mathbb{Z}_q$. Fix integers $1\le t\le n<q$. Participants are indexed by $P_1,\dots,P_n$, and participant $P_i$ has public index $i\in\mathbb{Z}_q^{*}$.
**DKG (Pedersen/Fel... | **1. DKG consistency.**
For every pair $(j,i)$ the accepted check reads $g^{s_{j,i}}=\prod_k g^{a_{j,k}i^k}=g^{f_j(i)}$ by definition of the commitments. Since $g$ has order $q$, the exponents agree modulo $q$. (In the honest case $s_{j,i}=f_j(i)$ holds by construction.)
Summing over $j$ gives $s_i=\sum_j f_j(i)=F(i)$.... | 1. $s_i=F(i)$, $Y_i=g^{s_i}$ and $Y=g^{F(0)}$.
2. $\sum_{i\in S}\lambda_i^S i^k=\delta_{k,0}$ for $0\le k<t$, so $\sum_{i\in S}\lambda_i^S s_i=x$; for $t=1$, $\lambda=1$.
3. $g^{z_i}=D_iE_i^{\rho_i}Y_i^{\lambda_ic}$ and $g^z=RY^c$.
4. DKG verification costs $\Theta(n^2t)$ exponentiations, the broadcast is $nt$ group el... | import hashlib, random
p = 2039
q = 1019
g = 4
assert pow(g, q, p) == 1 and g != 1
def H(*a):
return int(hashlib.sha256(repr(a).encode()).hexdigest(), 16) % q
def lag(i, S):
num = den = 1
for j in S:
if j != i:
num = num * j % q
den = den * (j - i) % q
return num * pow... |
MATH-CRYPTO-000111 | math_competition_problem | Formal Verification | Hoare logic, loop invariants, and automated verification with Z3 SMT bitvectors | Research Level | Fix an integer $w\ge 1$ and set $\mathbb B_w=\{0,1,\ldots,2^w-1\}$. Identify each $a\in\mathbb B_w$ with its $w$-bit binary expansion. Let $\operatorname{popcount}_w(a)$ be the number of $1$ bits in that expansion. All program arithmetic is modulo $2^w$; bitwise $\&$ acts on $w$-bit expansions. Consider the imperative ... | Let $x_0$ denote the initial value of $x$. Since $x$ is never modified, the postcondition is equivalently $c=\operatorname{popcount}_w(x_0)$.\n\nClaim 1 (clearing the least significant $1$). For every nonzero $y\in\mathbb B_w$,\n\n$\qquad \operatorname{popcount}_w(y\,\&\,(y-1))=\operatorname{popcount}_w(y)-1.$\n\nProof... | For every $w\ge 1$ and every input $x\in\mathbb B_w$, the program $P_w$ terminates after exactly $\operatorname{popcount}_w(x)$ loop iterations and outputs $c=\operatorname{popcount}_w(x)$. The inductive loop invariant is $\operatorname{popcount}_w(x_0)=c+\operatorname{popcount}_w(y)$, where $x_0$ is the initial value ... | #!/usr/bin/env python3\nfrom z3 import *\n\nW = 8\n\ndef popcount_int(x, w=W):\n return bin(x & ((1 << w) - 1)).count('1')\n\ndef popcount_bv(v, w):\n res = BitVecVal(0, w)\n for i in range(w):\n res = res + ZeroExt(w - 1, Extract(i, i, v))\n return res\n\ndef run_program(x, w=W):\n mask = (1 << w... |
MATH-CRYPTO-000067 | math_competition_problem | Algebraic Geometry | Grothendieck duality and Serre duality on coherent sheaves | Research Level | Let $k$ be a field and let $X \subset \mathbb{P}^3_k$ be a smooth complete intersection of two hypersurfaces of degrees $d_1, d_2 \geq 1$, so that $X$ is a smooth projective curve. Let $i: X \hookrightarrow \mathbb{P}^3$ be the closed immersion.\n\n(a) Using Grothendieck duality for the finite morphism $i$, i.e. $i_*\m... | Step 1 (Koszul resolution). Let $f_1,f_2$ be the defining forms, a regular sequence. Let $E = \mathcal{O}(-d_1)\oplus\mathcal{O}(-d_2)$ and $P=\mathbb{P}^3$. The Koszul complex $0\to \mathcal{O}_P(-d_1-d_2)\to E \to \mathcal{O}_P \to i_*\mathcal{O}_X\to 0$ is exact.\n\nStep 2 (Grothendieck duality for $i$). For finite ... | $\omega_X \cong \mathcal{O}_X(d_1+d_2-4)$, $g = \tfrac12 d_1d_2(d_1+d_2-4)+1$; for $(3,4)$: $g=19$ and $h^1(X,\mathcal{O}_X(1)) = 10$. | from math import comb\n\ndef hP(n):\n return comb(n+3,3) if n>=0 else 0\n\ndef h3P(n):\n # h^3(O_P3(n)) = h^0(O(-n-4))\n return hP(-n-4)\n\ndef chiP(n):\n return comb(n+3,3) if n>=-3 else -comb(-n-1,3)\n\ndef chiX(n,d1,d2):\n return chiP(n)-chiP(n-d1)-chiP(n-d2)+chiP(n-d1-d2)\n\ndef genus(d1,d2):\n re... |
MATH-CRYPTO-000206 | math_competition_problem | Post-Quantum Cryptography | Module-LWE and Ring-LWE error distribution parameter tuning (ML-KEM/Kyber) | Research Level | Let η be a positive integer. Let A_i,B_i (1≤i≤η) be independent Bernoulli(1/2) random variables. Define X=Σ_{i=1}^{η}(A_i-B_i); its law is the centered binomial distribution CBD_η. In ML-KEM/Kyber parameter tuning, the secret/error and secondary-error centered binomial parameters (η1,η2) are certified by tail criteria ... | Step 1: Exact PMF. Write S_+=Σ_{i=1}^{η}A_i and S_-=Σ_{i=1}^{η}B_i. Then S_+ and S_- are independent Binomial(η,1/2) variables, so Pr[S_+=a]=C(η,a)/2^η and similarly for S_-. Since X=S_+-S_-, Pr[X=x]=Σ_{a-b=x} [C(η,a)/2^η][C(η,b)/2^η]=4^{-η}Σ_{b} C(η,b+x)C(η,b). Put j=b. We need the identity Σ_j C(η,j+x)C(η,j)=C(2η,η+x... | m(1/32)=3, with equality Pr[|CBD_3|≥3]=1/32; m(1/4)=2, with Pr[|CBD_2|≥2]=1/8. Hence the ML-KEM/Kyber centered-binomial tuning pair is (η1,η2)=(3,2). | from fractions import Fraction
from math import comb
def pmf(eta, x):
if x < -eta or x > eta:
return Fraction(0, 1)
return Fraction(comb(2 * eta, eta + x), 4 ** eta)
def tail_boundary(eta):
return Fraction(2, 4 ** eta)
for eta in range(1, 10):
total = sum((pmf(eta, x) for x in range(-eta, eta... |
MATH-CRYPTO-000221 | math_competition_problem | Homomorphic Encryption | BGV and BFV leveled homomorphic schemes: noise growth and modulus switching | Research Level | Let $n$ be a power of two and let $R=\mathbb{Z}[x]/(x^n+1)$. For $a=\sum_i a_i x^i\in R$, write $\|a\|_\infty=\max_i|a_i|$. Let $t\ge 2$ be the plaintext modulus. Let $p$ be an odd prime with $p\equiv 1\pmod t$ and $p\nmid t$. Let $q$ be a modulus coprime to $p$, and set $Q=qp$.
The secret key is a ternary polynomial ... | **Existence and uniqueness.** Since $p\nmid t$, $t$ is invertible mod $p$. Because $p$ is odd, the interval $[-(p-1)/2,(p-1)/2]$ contains exactly $p$ consecutive integers. These form a complete residue system mod $p$, so each $u_{k,i}$ exists and is unique.
Consequently $t u_{k,i}\equiv -c_{k,i}\pmod p$, so $\delta_k\... | $M=\dfrac{t(p-1)(1+h)}{2}$; for $t=17$, $p=103$, $h=5$: $M=5202$. | import itertools
def negamul(a,b,n):
r=[0]*n
for i in range(n):
for j in range(n):
k=i+j
if k<n: r[k]+=a[i]*b[j]
else: r[k-n]-=a[i]*b[j]
return r
def bal(x,p):
x%=p
return x-p if x>(p-1)//2 else x
def switch_delta(c,t,p):
tinv=pow(t,-1,p)
return... |
MATH-CRYPTO-000151 | math_competition_problem | Lattice Cryptanalysis | Kannan's embedding technique vs Babai's nearest plane algorithm for CVP | Research Level | Let $q = 10007$ and $N = 1000$. Let $L = q\mathbb{Z}^2 \subset \mathbb{R}^2$, equipped with the ordered (deliberately skewed) basis $\mathbf{b}_1 = (qN, q)$ and $\mathbf{b}_2 = (q, 0)$. This is a basis of $L$, since $\det\begin{pmatrix} N & 1 \\ 1 & 0 \end{pmatrix} = -1$.
For an integer $s$ with $1 \le s \le \lfloor q... | **Step 0 (Gram–Schmidt data).**
- $\mathbf{b}_1^* = \mathbf{b}_1 = q(N, 1)$, so $\|\mathbf{b}_1^*\|^2 = q^2(N^2+1)$.
- $\mathbf{b}_2^* = \mathbf{b}_2 - \mu \mathbf{b}_1$ with $\mu = \langle \mathbf{b}_2, \mathbf{b}_1 \rangle / \|\mathbf{b}_1\|^2 = N/(N^2+1)$. This gives $\mathbf{b}_2^* = \frac{q}{N^2+1}(1, -N)$ and $\|... | (a) Babai's nearest plane succeeds exactly for $s \in \{1, 2, 3, 4, 5\}$. The condition is $Ns \le q/2$, i.e. $s \le \lfloor 10007/2000 \rfloor = 5$; it fails for $6 \le s \le 5003$. (b) Kannan's embedding with $M = 1$ makes $\pm(\mathbf{e}_s, 1)$ the unique shortest vectors of $L'$ for all $1 \le s \le 70$. This follo... | from fractions import Fraction as F
import math
q, N = 10007, 1000
b1 = (q * N, q)
b2 = (q, 0)
def dot(u, v):
return u[0] * v[0] + u[1] * v[1]
# Gram-Schmidt
mu = F(dot(b2, b1), dot(b1, b1))
b1s = (F(b1[0]), F(b1[1]))
b2s = (b2[0] - mu * b1[0], b2[1] - mu * b1[1])
def rnd(x):
# rounding convention: floor(x ... |
MATH-CRYPTO-000216 | math_competition_problem | Zero-Knowledge Proofs | Bulletproofs: inner product arguments without trusted setup and range proofs | Research Level | Let $p$ be a prime and let $n=2^k$ with $k\ge 1$. For $\mathbf{v}\in\mathbb{Z}_p^{m}$ with $m$ even, write $\mathbf{v}_L=(v_0,\dots,v_{m/2-1})$ and $\mathbf{v}_R=(v_{m/2},\dots,v_{m-1})$. Write $\langle\cdot,\cdot\rangle$ for the standard inner product over $\mathbb{Z}_p$.
Let $\mathbf{a}^{(0)}=\mathbf{a}$ and $\mathb... | **(a) Cross-term identity.** Fix $j$ and write $\mathbf{a}=\mathbf{a}^{(j-1)}$, $\mathbf{b}=\mathbf{b}^{(j-1)}$ and $x=x_j$. Expand by bilinearity:
$$\langle x\mathbf{a}_L+x^{-1}\mathbf{a}_R,\;x^{-1}\mathbf{b}_L+x\mathbf{b}_R\rangle=\langle\mathbf{a}_L,\mathbf{b}_L\rangle+x^2\langle\mathbf{a}_L,\mathbf{b}_R\rangle+x^{-... | The scalars satisfy $a^*=\sum_i a_i\prod_{t=1}^k x_t^{(-1)^{\beta_t(i)}}$ and $b^*=\sum_i b_i\prod_{t=1}^k x_t^{-(-1)^{\beta_t(i)}}$. Their product is $a^*b^*=\langle\mathbf{a},\mathbf{b}\rangle+\sum_{j=1}^{k}(x_j^2L_j+x_j^{-2}R_j)$. The proof size is $2\log_2 n$ group elements plus $2$ field elements. | import random
p = 2**61 - 1
inv = lambda x: pow(x, p - 2, p)
ip = lambda u, v: sum(a * b for a, b in zip(u, v)) % p
def run(k):
n = 2**k
a = [random.randrange(p) for _ in range(n)]
b = [random.randrange(p) for _ in range(n)]
xs = [random.randrange(1, p) for _ in range(k)]
A, B = a[:], b[:]
acc... |
MATH-CRYPTO-000119 | math_competition_problem | Differential Privacy | Laplace and Gaussian mechanisms: privacy budget (epsilon, delta) composition theorems | Research Level | Let $\mathcal{D}$ be a data universe and $f:\mathcal{D}\to\mathbb{R}$ a real-valued query. For $\Delta>0$ and $b>0$ the scalar Laplace mechanism is $M^{\mathrm{Lap}}_{f,b}(D)=f(D)+W$ with $W\sim\mathrm{Lap}(b)$; for $\sigma>0$ the scalar Gaussian mechanism is $M^{\mathrm{Gau}}_{f,\sigma}(D)=f(D)+Z$ with $Z\sim N(0,\sig... | Part 1: Laplace composition. For one scalar Laplace mechanism with scale $b$, the density is $p_D(y)=\frac{1}{2b}e^{-|y-f(D)|/b}$. If $|f(D)-f(D')|\le\Delta$, then for all $y$, $p_D(y)/p_{D'}(y)=\exp((|y-f(D')|-|y-f(D)|)/b)\le e^{\Delta/b}$. Hence the mechanism is $(\Delta/b,0)$-DP. For independent composition, densiti... | Laplace: the $k$-fold independent composition of Laplace mechanisms with equal sensitivity $\Delta$ and scale $b$ is exactly $(k\Delta/b,0)$-DP, and the bound is attained by taking the product of lower-tail sets. Gaussian: with $\mu=\Delta^2/(2\sigma^2)$ and $k\mu>0$, the exact composed privacy curve is\n$$\delta_k(\ep... | import math, random
def Phi(x):
return 0.5 * math.erfc(-x / math.sqrt(2.0))
def gaussian_delta(k, eps, Delta, sigma):
if k == 0 or Delta == 0.0 or sigma == math.inf:
return 0.0
mu = Delta * Delta / (2.0 * sigma * sigma)
if mu == 0.0:
return 0.0
s = math.sqrt(2.0 * k * mu)
a = (... |
End of preview. Expand in Data Studio
No dataset card yet
- Downloads last month
- 64