Helger Lipmaa
@helger.bsky.social
490 followers
250 following
160 posts
Cryptography professor at the University of Tartu, Estonia. Zero-Knowledge. SNARKs.
Posts
Media
Videos
Starter Packs
Reposted by Helger Lipmaa
COSIC
@cosic.bsky.social
· 21d
Europa test leeftijdscontroles op het internet: is dit het einde van online anonimiteit?
Europa test een app waarmee we ons in de toekomst moeten aanmelden op het internet, om te bewijzen dat we meerderjarig zijn. Critici waarschuwen dat het systeem makkelijk te omzeilen is en ongewenste neveneffecten zal hebben, onder meer voor onze privacy.
www.standaard.be
Reposted by Helger Lipmaa
![Abstract. We resolve the Correlated Agreement (CA) problem for Reed-Solomon codes up to the information-theoretic capacity limit by introducing a fundamental change of basis: from the traditional evaluation domain to the syndrome space. Viewed through this “Syndrome-Space Lens,” the problem of proximity testing transforms into a transparent question of linear-algebraic geometry: a single affine line of syndromes traversing a family of low-dimensional subspaces. This new perspective makes a sharp phase transition at the capacity boundary visible, allowing for a complete characterization of the problem’s behavior across all parameter regimes, yielding short, self-contained proofs.
Classification. We establish a precise trichotomy organized by the rank margin Δ := t − d. At the capacity boundary (Δ = 0), the CA premise is information-theoretically vacuous, and we prove that no rigidity can be concluded without imposing additional structure. One step beyond capacity (Δ = 1), the problem enters a “knife-edge” regime where unconditional rigidity does not hold; soundness is recovered either through a combinatorial witness (such as a repeated error support or a small union of supports) or by adding protocol-level structure (such as independent two-fold MCA checks, DEEP/STIR out-of-domain sampling, or a global error locator). For stricter gaps (Δ ≥ 2), unconditional rigidity holds under a simple algebraic condition ((r + 1)k < m + 1), with explicit quantitative bounds.
MCA and Practical Implications. Below capacity (δ < 1 − ρ), the strengthened mutual correlated agreement (MCA) problem reduces to ordinary correlated agreement. MCA holds under the same hypotheses as CA. When folds are generated with independent challenges (e.g., via domain-separated Fiat-Shamir), the per-round security margins add. The model-scoped soundness law is Pr [FA] ≤ q^(−(∑Δ_(i))s), providing a clear and complete rulebook for selecting safe and efficient parameters in FRI/STARK systems. This work bypasses the complex machinery of list-decoding algorithms entirely and resolves the long-standing open problem concerning the gap between the Johnson bound and capacity.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fwa55bujvdrwlwlwgqmmxmuf/bafkreiaayrmiiifnmnoz3wcuadq7bvpsx5eqo3o2zdw5jtjsbe6weofg2e@jpeg)
Reposted by Helger Lipmaa
Reposted by Helger Lipmaa
![Abstract. Succinct non-interactive arguments of knowledge (SNARKs) based on lattice assumptions offer a promising post-quantum alternative to pairing-based systems, but have until now suffered from inherently quadratic proof sizes in the security parameter. We introduce RoK and Roll, the first lattice-based SNARK that breaks the quadratic barrier, achieving communication complexity of Õ(λ) together with a succinct verification time. The protocol significantly improves upon the state of the art of fully-succinct argument systems established by “RoK, Paper, SISsors” (RPS) [ASIACRYPT’24] and hinges on two key innovations, presented as reductions of knowledge (RoKs): - Structured random projections: We introduce a new technique for structured random projections that allows us to reduce the witness dimensions while approximately preserving its ℓ₂ norm and maintaining the desired tensor structure. In order to maintain succinct communication and verification, the projected image is further committed and adjoined to the original relation. This procedure is recursively repeated until dimension of the intermediate witness becomes poly(λ), i.e. independent of the original witness length. - Unstructured random projection: When the witness is sufficiently small, we let the unstructured projection (over coefficients ℤ_(q)) be sent in plain, as in LaBRADOR [CRYPTO’23]. We observe, however, that the strategy from prior works to immediately lift the projection claim to ℛ_(q), and into our relation, would impose a quadratic communication cost. Instead, we gradually batch-and-lift the projection a the tower of intermediate ring extensions. This reduces the communication cost to Õ(λ) while maintaining a succinct verification time. These two techniques, combined with existing RoKs from RPS, yield a succinct argument system with communication complexity Õ(λ) and succinct verification for structured linear relations.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fwa55bujvdrwlwlwgqmmxmuf/bafkreid4bm7u5l7gd3vcqxjis2acapv2mghcmlnouodjivp5bh3s6iynd4@jpeg)
Reposted by Helger Lipmaa
Reposted by Helger Lipmaa
Jon Ullman
@thejonullman.bsky.social
· Sep 15
Reposted by Helger Lipmaa
Reposted by Helger Lipmaa
Reposted by Helger Lipmaa
Helger Lipmaa
@helger.bsky.social
· Aug 20
Helger Lipmaa
@helger.bsky.social
· Aug 17
Reposted by Helger Lipmaa
Reposted by Helger Lipmaa
Helger Lipmaa
@helger.bsky.social
· Aug 13
Reposted by Helger Lipmaa
Reposted by Helger Lipmaa
