11 CISPA Papers at Eurocrypt 2024. Eurocrypt is the International Conference on the Theory and Applications of Cryptographic Techniques.

<!DOCTYPE html> <html lang="en" class="no-js"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"/> <title>11 CISPA Papers at Eurocrypt 2024. Eurocrypt is the International Conference on the Theory and Applications of Cryptographic Techniques.</title> <meta property="og:title" content="11 CISPA Papers at Eurocrypt 2024. Eurocrypt is the International Conference on the Theory and Applications of Cryptographic Techniques." /> <meta property="og:type" content="website" /> <meta property="og:url" content="https://cispa.de/en/research/conferences/2024/eurocrypt-2024" /> <link href="/cache-buster-1739788623/css/main.css" media="screen" rel="stylesheet" type="text/css" /> <link href="/cache-buster-1739788623/images/icons/favicon.ico" rel="icon" /> <script src="/js/common.bundle.js?bust=4" nonce="c62f259f6037830056b58504959c4b4f"></script> </head> <body class="darkmode " id="page-top" itemscope itemtype="http://schema.org/WebPage"> <meta itemprop="name" content="11 CISPA Papers at Eurocrypt 2024. Eurocrypt is the International Conference on the Theory and Applications of Cryptographic Techniques."/> <span class="d-none" data-label-send-email>Send email</span> <span class="d-none" data-label-copy-email>Copy Email Address</span> <nav class="topnav container-fluid d-flex" id="mainNav" itemscope="" itemtype="http://schema.org/SiteNavigationElement"> <div class="topnav-logos" itemscope="" itemtype="https://schema.org/Organization"> <a href="/en" itemprop="url"> <div class="topnav-logo-image"> <img itemprop="logo" class="show-on-bright rounded-circle" alt="Light Logo of Helmholtz Center for Information Security (CISPA)" title="CISPA" src="/images/cispa-logo-on-bright.svg"> <img itemprop="logo" class="show-on-dark rounded-circle" alt="Dark Logo of Helmholtz Center for Information Security (CISPA)" title="CISPA" src="/images/cispa-logo-on-dark.svg"> </div> <div class="topnav-logo-text"> <img itemprop="logo" class="show-on-bright" alt="Text Light Logo of Helmholtz Center for Information Security (CISPA)" title="CISPA" src="/images/cispa-txt-black.svg"> <img itemprop="logo" class="show-on-dark" alt="Text Dark Logo of Helmholtz Center for Information Security (CISPA)" title="CISPA" src="/images/cispa-txt-white.svg"> </div> </a> </div> <div class="topnav-switch"> <a href="?darkmode-toggle" id="darkmodeSwitch" class="darkmode-switch" title="Toggle darkmode"> <span>⬤</span> </a> </div> <div class="topnav-backdrop"></div> <div class="topnav-menu"> <div id="menu" data-text-open="Close" data-text-closed="Menu" class="topnav-menu-burger"> <a href="#menu" class="topnav-burger" role="button" title="To navigation menu"> <span class="icon-bar"></span> <span class="icon-bar"></span> </a> </div> <div id="menu-close" data-text-open="Close" data-text-closed="Menu" class="topnav-menu-burger"> <a href="#" class="topnav-burger topnav-burger-close" role="button" title="Close navigation menu"> <span class="icon-bar"></span> <span class="icon-bar"></span> </a> </div> <div class="topnav-menu-flyout"> <div class="flyout-meta"> <form role="search" action="/en/search"> <div class="input-group"> <input class="form-control" name="q" type="search" placeholder="What are you looking for?" value="" aria-label="Search"> <div class="input-group-append"> <button type="submit" class="btn search" aria-label="Submit Search"> <i class="mdi mdi-magnify"></i> </button> </div> </div> </form> <div class="switch-language"> <ul class="pagination"> <li class="page-item active"> <span class="page-link"> EN <span class="sr-only">(current)</span> </span> </li> <li class="page-item"> <a class="page-link" href="https://cispa.de/de"> DE </a> </li> </ul> </div> </div> <div class="flyout-menu"> <div class="h2 label flyout-breadcrumb"> <a href="#" class="mdi mdi-chevron-left" title="Back to previous menu level"><span class="d-none">Back to previous menu level</span></a> <span class="flyout-breadcrumb-root">Menu</span> <span class="flyout-breadcrumb-sublevel"></span> </div> <ul class="navbar-nav level-one"> <li class="nav-item"> <a class="nav-link" target="_self" href="/en" title="Home" itemprop="url"> <span itemprop="name">Home</span> </a> </li> <li class="nav-item"> <div class="nav-link" title="Research"> <span>Research</span> </div> <ul class="navbar-nav level-two" data-title="Research"> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/research" title="Overview" itemprop="url"> <span itemprop="name">Overview</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/research/algorithmic-foundations-and-cryptography" title="Algorithmic Foundations and Cryptography " itemprop="url"> <span itemprop="name">Algorithmic Foundations and Cryptography </span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/research/trustworthy-information-processing" title="Trustworthy Information Processing" itemprop="url"> <span itemprop="name">Trustworthy Information Processing</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/research/reliable-security-guarantees" title="Reliable Security Guarantees" itemprop="url"> <span itemprop="name">Reliable Security Guarantees</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/research/threat-detection-and-defenses" title="Threat Detection and Defenses" itemprop="url"> <span itemprop="name">Threat Detection and Defenses</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/research/secure-connected-and-mobile-systems" title="Secure Connected and Mobile Systems" itemprop="url"> <span itemprop="name">Secure Connected and Mobile Systems</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/research/empiricial-and-behavioral-security" title="Empirical and Behavioral Security" itemprop="url"> <span itemprop="name">Empirical and Behavioral Security</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/research/publications" title="Publications" itemprop="url"> <span itemprop="name">Publications</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/research/funded-projects-and-collaborations" title="Funded Projects & Collaborations" itemprop="url"> <span itemprop="name">Funded Projects & Collaborations</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/research/awards" title="Awards" itemprop="url"> <span itemprop="name">Awards</span> </a> </li> </ul> </li> <li class="nav-item"> <div class="nav-link" title="About CISPA"> <span>About CISPA</span> </div> <ul class="navbar-nav level-two" data-title="About CISPA"> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/about" title="Overview" itemprop="url"> <span itemprop="name">Overview</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/about/organization" title="Organization" itemprop="url"> <span itemprop="name">Organization</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/about/director-page" title="Director's Page" itemprop="url"> <span itemprop="name">Director's Page</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/about/procurement" title="Procurement" itemprop="url"> <span itemprop="name">Procurement</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/invoicing-e-invoice" title="invoicing-e-invoice" itemprop="url"> <span itemprop="name">invoicing-e-invoice</span> </a> </li> </ul> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/people" title="People" itemprop="url"> <span itemprop="name">People</span> </a> </li> <li class="nav-item"> <div class="nav-link" title="Career"> <span>Career</span> </div> <ul class="navbar-nav level-two" data-title="Career"> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/career" title="Overview" itemprop="url"> <span itemprop="name">Overview</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/career/faq" title="FAQ" itemprop="url"> <span itemprop="name">FAQ</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="https://jobs.cispa.saarland/" title="Job Openings" itemprop="url"> <span itemprop="name">Job Openings</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/career/excellence-program" title="Excellence Program" itemprop="url"> <span itemprop="name">Excellence Program</span> </a> </li> </ul> </li> <li class="nav-item"> <div class="nav-link" title="News & Events"> <span>News & Events</span> </div> <ul class="navbar-nav level-two" data-title="News & Events"> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/news-and-events" title="Overview" itemprop="url"> <span itemprop="name">Overview</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/news-and-events/podcast" title="Podcast" itemprop="url"> <span itemprop="name">Podcast</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/news-and-events/distinguished-lecture-series" title="CISPA DLS" itemprop="url"> <span itemprop="name">CISPA DLS</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/zine" title="zine" itemprop="url"> <span itemprop="name">zine</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/news-and-events/movies" title="Videos" itemprop="url"> <span itemprop="name">Videos</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/glossary" title="Glossary" itemprop="url"> <span itemprop="name">Glossary</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/news-and-events/press" title="Media Relations" itemprop="url"> <span itemprop="name">Media Relations</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/display" title="Display" itemprop="url"> <span itemprop="name">Display</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/no-coffee-no-research" title="No Coffee, No Research" itemprop="url"> <span itemprop="name">No Coffee, No Research</span> </a> </li> </ul> </li> <li class="nav-item"> <div class="nav-link" title="Technology Transfer"> <span>Technology Transfer</span> </div> <ul class="navbar-nav level-two" data-title="Technology Transfer"> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/technology-transfer" title="Overview" itemprop="url"> <span itemprop="name">Overview</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/startups-and-entrepreneurship" title="Startups & Entrepreneurship" itemprop="url"> <span itemprop="name">Startups & Entrepreneurship</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/product-labs" title="Product Labs" itemprop="url"> <span itemprop="name">Product Labs</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/contact-technology-transfer" title="Contact" itemprop="url"> <span itemprop="name">Contact</span> </a> </li> </ul> </li> <li class="nav-item"> <div class="nav-link" title="Knowledge Transfer"> <span>Knowledge Transfer</span> </div> <ul class="navbar-nav level-two" data-title="Knowledge Transfer"> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/knowledge-transfer" title="Overview" itemprop="url"> <span itemprop="name">Overview</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/cysec-lab" title="Cysec Lab" itemprop="url"> <span itemprop="name">Cysec Lab</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/cysec-lab-news" title="Cysec Lab News" itemprop="url"> <span itemprop="name">Cysec Lab News</span> </a> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/citizen-science" title="Citizen Science" itemprop="url"> <span itemprop="name">Citizen Science</span> </a> </li> </ul> </li> <li class="nav-item"> <a class="nav-link" target="_self" href="/en/contact" title="Contact" itemprop="url"> <span itemprop="name">Contact</span> </a> </li> </ul> </div> </div> </div> </nav>   <nav class="container-fluid" aria-label="breadcrumb"> <div class="row"> <div class="col-10 offset-lg-3 col-lg-7"> <ol class="breadcrumb"> <li class="breadcrumb-item"> <a href="/en">Home</a> </li> <li class="breadcrumb-item"> Research </li> </ol> </div> </div> </nav>  <header class="py-5 container-fluid header-text-trail "> <div class="row"> <div class="offset-1 col-10 offset-lg-2 col-lg-9"> <h1 class="headline-multiline-animation headline-multiline-lines-3"> <em class="headline-multiline-animation-top-animation1" data-text="11 CISPA"></em> <em class="headline-multiline-animation-top-animation2" data-text="11 CISPA"></em> <em class="headline-multiline-animation-top">11 CISPA</em> <em class="headline-multiline-animation-center">PAPERS AT</em> <em class="headline-multiline-animation-bottom">eurocript 2024</em> <em class="headline-multiline-animation-bottom-animation1" data-text="eurocript 2024"></em> <em class="headline-multiline-animation-bottom-animation2" data-text="eurocript 2024"></em> </h1> </div> <div class="wysiwyg lead header-text-trail-leadin offset-1 col-10 offset-md-2 col-md-8 offset-lg-3 col-lg-5" > <p>Eurocrypt 2024, the 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, took place at Kongresshaus in Zurich, Switzerland on May 26-30, 2024. Eurocrypt 2024 was organized by the International Association for Cryptologic Research (IACR).</p> </div> </div> </header> <section class="outer-spacing container-fluid" > <div class="row"> <div class="offset-1 col-10 offset-lg-2 col-lg-8">  <div class="accordion" id="accordion-414554"> <div class="accordion-panel"> <div class="accordion-header" id="accordion-heading-414554-4"> <h3> <button class="btn collapsed" type="button" data-toggle="collapse" data-target="#accordion-collapse-414554-4" aria-expanded="false" aria-controls="accordion-collapse-414554-4"> A Holistic Security Analysis of Monero Transactions <i class="mdi mdi-chevron-down"></i> </button> </h3> </div> <div id="accordion-collapse-414554-4" class="collapse" aria-labelledby="accordion-heading-414554-4"> <div class="accordion-body"> <p>Monero is a popular cryptocurrency with strong privacy guarantees for users’ transactions. At the heart of Monero’s privacy claims lies a complex transaction system called RingCT, which combines several building blocks such as linkable ring signatures, homomorphic commitments, and range proofs, in a unique fashion. In this work, we provide the first rigorous security analysis for RingCT (as given in Zero to Monero, v2.0.0, 2020) in its entirety. This is in contrast to prior works that only provided security arguments for parts of RingCT. To analyze Monero’s transaction system, we introduce the first holistic security model for RingCT. We then prove the security of RingCT in our model. Our framework is modular: it allows to view RingCT as a combination of various different sub-protocols. Our modular approach has the benefit that these components can be easily updated in future versions of RingCT, with only minor modifications to our analysis. At a technical level, we split our analysis in two parts. First, we identify which security notions for building blocks are needed to imply security for the whole system. Interestingly, we observe that existing and well-established notions (e.g., for the linkable ring signature) are insufficient. Second, we analyze all building blocks as implemented in Monero and prove that they satisfy our new notions. Here, we leverage the algebraic group model to overcome subtle problems in the analysis of the linkable ring signature component. As another technical highlight, we show that our security goals can be mapped to a suitable graph problem, which allows us to take advantage of the theory of network flows in our analysis. This new approach is also useful for proving security of other cryptocurrencies.</p>  <div class=" "> <a href="https://cispa.de/de/research/publications/79211-a-holistic-security-analysis-of-monero-transactions" role="button" class="btn btn-primary btn-md btn-external " > read full paper <i class="mdi mdi-arrow-top-right"></i> </a> </div> </div> </div> </div><div class="accordion-panel"> <div class="accordion-header" id="accordion-heading-414554-3"> <h3> <button class="btn collapsed" type="button" data-toggle="collapse" data-target="#accordion-collapse-414554-3" aria-expanded="false" aria-controls="accordion-collapse-414554-3"> Early Stopping for Any Number of Corruptions <i class="mdi mdi-chevron-down"></i> </button> </h3> </div> <div id="accordion-collapse-414554-3" class="collapse" aria-labelledby="accordion-heading-414554-3"> <div class="accordion-body"> <p>Minimizing the round complexity of byzantine broadcast is a fundamental question in distributed computing and cryptography. In this work, we present the first early stopping byzantine broadcast protocol that tolerates up to t = n−1 malicious corruptions and terminates in O(min{f 2 , t+ 1}) rounds for any execution with f ≤ t actual corruptions. Our protocol is deterministic, adaptively secure, and works assuming a plain public key infrastructure. Prior early-stopping protocols all either require honest majority or tolerate only up to t = (1 − ϵ)n malicious corruptions while requiring either trusted setup or strong number theoretic hardness assumptions. As our key contribution, we show a novel tool called a polariser that allows us to transfer certificate-based strategies from the honest majority setting to settings with a dishonest majority.</p>  <div class=" "> <a href="https://cispa.de/en/research/publications/79224-early-stopping-for-any-number-of-corruptions" role="button" class="btn btn-primary btn-md btn-external " > read full paper <i class="mdi mdi-arrow-top-right"></i> </a> </div> </div> </div> </div><div class="accordion-panel"> <div class="accordion-header" id="accordion-heading-414554-2"> <h3> <button class="btn collapsed" type="button" data-toggle="collapse" data-target="#accordion-collapse-414554-2" aria-expanded="false" aria-controls="accordion-collapse-414554-2"> Fuzzy Private Set Intersection with Large Hyperballs <i class="mdi mdi-chevron-down"></i> </button> </h3> </div> <div id="accordion-collapse-414554-2" class="collapse" aria-labelledby="accordion-heading-414554-2"> <div class="accordion-body"> <p>Traditional private set intersection (PSI) involves a receiver and a sender holding sets X and Y , respectively, with the receiver learning only the intersection X ∩Y . We turn ourattention to its fuzzy variant, where the receiver holds |X| hyperballs of radius δ in a metric space and the sender has |Y | points. Representing the hyperballs by their center, the receiver learns the points x ∈ X for which there exists y ∈ Y such that dist(x, y) ≤ δ with respect to some distance metric. Previous approaches either require general-purpose multi-party computation (MPC) techniques like garbled circuits or fully homomorphic encryption (FHE), leak details about the sender’s precise inputs, support limited distance metrics, or scale poorly with the hyperballs’ volume. This work presents the first black-box construction for fuzzy PSI (including other variants such as PSI cardinality, labeled PSI, and circuit PSI), which can handle polynomially large radius and dimension (i.e., a potentially exponentially large volume) in two interaction messages, supporting general Lp∈[1,∞] distance, without relying on garbled circuits or FHE. The protocol excels in both asymptotic and concrete efficiency compared to existing works. For security, we solely rely on the assumption that the Decisional Diffie-Hellman (DDH) holds in the random oracle model.</p>  <div class=" "> <a href="https://cispa.de/en/research/publications/79207-fuzzy-private-set-intersection-with-large-hyperballs" role="button" class="btn btn-primary btn-md btn-external " > read full paper <i class="mdi mdi-arrow-top-right"></i> </a> </div> </div> </div> </div><div class="accordion-panel"> <div class="accordion-header" id="accordion-heading-414554-1"> <h3> <button class="btn" type="button" data-toggle="collapse" data-target="#accordion-collapse-414554-1" aria-expanded="true" aria-controls="accordion-collapse-414554-1"> Key Recovery Attack on the Partial Vandermonde Knapsack Problem <i class="mdi mdi-chevron-down"></i> </button> </h3> </div> <div id="accordion-collapse-414554-1" class="collapse show" aria-labelledby="accordion-heading-414554-1"> <div class="accordion-body"> <p>The Partial Vandermonde (PV) Knapsack problem is an algebraic variant of the low-density inhomogeneous SIS problem. The problem has been used as a building block for various lattice-based constructions, including signatures (ACNS’14, ACISP’18), encryptions (DCC’15,DCC’20), and signature aggregation (Eprint’20). At Crypto’22, Boudgoust, Gachon, and Pellet-Mary proposed a key distinguishing attack on the PV Knapsack exploiting algebraic properties of the problem. Unfortunately, their attack doesn’t offer key recovery, except for worstcase keys. In this paper, we propose an alternative attack on the PV Knapsack problem which provides key recovery for a much larger set of keys. Like the Crypto’22 attack, it is based on lattice reduction and uses a dimension reduction technique to speed-up the underlying lattice reduction algorithm and enhance its performance. As a side bonus, our attack transforms the PV Knapsack problem into uSVP instances instead of SVP instances in the Crypto’22 attack. This also helps the lattice reduction algorithm, both from a theoretical and practical point of view. We use our attack to re-assess the hardness of the concrete parameters used in the literature. It appears that many contain a non-negligible fraction of weak keys, which are easily identified and extremely susceptible to our attack. For example, a fraction of 2−19 of the public keys of a parameter set from ACISP’18 can be solved in about 30 hours on a moderate server using off-the-shelf lattice reduction. This parameter set was initially claimed to have a 129-bit security against key recovery attack. Its security was reduced to 87-bit security using the distinguishing attack from Crypto’22. Similarly, the ACNS’14 proposal also includes a parameter set containing a fraction of 2−19 of weak keys; those can be solved in about 17 hours.</p>  <div class=" "> <a href="https://cispa.de/en/research/publications/79239-key-recovery-attack-on-the-partial-vandermonde-knapsack-problem" role="button" class="btn btn-primary btn-md btn-external " > Read full paper <i class="mdi mdi-arrow-top-right"></i> </a> </div> </div> </div> </div><div class="accordion-panel"> <div class="accordion-header" id="accordion-heading-414554-5"> <h3> <button class="btn collapsed" type="button" data-toggle="collapse" data-target="#accordion-collapse-414554-5" aria-expanded="false" aria-controls="accordion-collapse-414554-5"> Lower-Bounds on Public-Key Operations in PIR <i class="mdi mdi-chevron-down"></i> </button> </h3> </div> <div id="accordion-collapse-414554-5" class="collapse" aria-labelledby="accordion-heading-414554-5"> <div class="accordion-body"> <p>Private information retrieval (PIR) is a fundamental cryptographic primitive that allows a user to fetch a database entry without revealing to the server which database entry it learns. PIR becomes non-trivial if the server communication is less than the database size. We show that building (even) very weak forms of PIR protocols requires that the amount of public-key operations scale linearly in the database size. We then use this bound to examine the related problem of communication efficient oblivious transfer (OT) extension. Oblivious transfer is a crucial building block in secure multi-party computation (MPC). In most MPC protocols, OT invocations are the main bottleneck in terms of computation and communication. OT extension techniques allow one to minimize the number of public-key operations in MPC protocols. One drawback of all existing OT extension protocols is their communication overhead. In particular, the sender’s communication is roughly double what is information-theoretically optimal. We show that OT extension with close to optimal sender communication is impossible, illustrating that the communication overhead is inherent. Our techniques go much further; we can show many lower bounds on communication-efficient MPC. E.g. we prove that to build high-rate string OT with generic groups, the sender needs to do linearly many group operations.</p>  <div class=" "> <a href="https://cispa.de/en/research/publications/79210-lower-bounds-on-public-key-operations-in-pir" role="button" class="btn btn-primary btn-md btn-external " > read full paper <i class="mdi mdi-arrow-top-right"></i> </a> </div> </div> </div> </div><div class="accordion-panel"> <div class="accordion-header" id="accordion-heading-414554-6"> <h3> <button class="btn collapsed" type="button" data-toggle="collapse" data-target="#accordion-collapse-414554-6" aria-expanded="false" aria-controls="accordion-collapse-414554-6"> M&M’S: Mix and Match Attacks on Schnorr-Type Blind Signatures with Repetition <i class="mdi mdi-chevron-down"></i> </button> </h3> </div> <div id="accordion-collapse-414554-6" class="collapse" aria-labelledby="accordion-heading-414554-6"> <div class="accordion-body"> <p>Blind signatures allow the issuing of signatures on messages chosen by the user so that they ensure blindness of the message against the signer. Moreover, a malicious user cannot output `+1 signatures while only finishing ` signing sessions. This notion, called one-more unforgeability, comes in two flavors supporting either sequential or concurrent sessions. In this paper, we investigate the security of a class of blind signatures constructed from Sigma-protocols with small challenge space CΣ (i.e., polynomial in the security parameter), using k repetitions of the protocol to decrease the chances of a cheating prover. This class of schemes includes, among others, the Schnorr blind signature scheme with bit challenges and the recently proposed isogeny-based scheme CSI-Otter (Crypto’23), as well as potential blind signatures designed from assumptions with the well-known Sigma-protocol for the graph-isomorphism problem (e.g., Lattice Isomorphism Problem). For this class of blind signatures, we show a polynomial-time attack that breaks one-more unforgeability for any ` ≥ k concurrent sessions in time O(k · |CΣ|). Contrary to the ROS attack, ours is generic and does not require any particular algebraic structure. We also propose a computational trade-off, where, for any t ≤ k, our attack works for ` = k t in time O( k t · |CΣ| t ). The consequences of our attack are as follows. Schemes in the investigated class of blind signatures should not be used concurrently without applying specific transformations to boost the security to support more signing sessions. Moreover, for the parameters proposed for CSI-Otter (k = 128 and |CΣ| = 2), the scheme becomes forgeable after 128 concurrent signing sessions for the basic attack and with only eight sessions in our optimized attack. We also show that for those parameters, it is even possible to compute two signatures in around 10 minutes with just one signing session using the computation power of the Bitcoin network. Thus, we show that, for sequential security, the parameter k must be at least doubled in the security parameter for any of the investigated schemes.</p>  <div class=" "> <a href="https://cispa.de/en/research/publications/79222-m-amp-m-s-mix-and-match-attacks-on-schnorr-type-blind-signatures-with-repetition" role="button" class="btn btn-primary btn-md btn-external " > read full paper <i class="mdi mdi-arrow-top-right"></i> </a> </div> </div> </div> </div><div class="accordion-panel"> <div class="accordion-header" id="accordion-heading-414554-7"> <h3> <button class="btn collapsed" type="button" data-toggle="collapse" data-target="#accordion-collapse-414554-7" aria-expanded="false" aria-controls="accordion-collapse-414554-7"> Tight Security of TNT and Beyond: Attacks, Proofs and Possibilities for the Cascaded LRW Paradigm <i class="mdi mdi-chevron-down"></i> </button> </h3> </div> <div id="accordion-collapse-414554-7" class="collapse" aria-labelledby="accordion-heading-414554-7"> <div class="accordion-body"> <p>Liskov, Rivest and Wagner laid the theoretical foundations for tweakable block ciphers (TBC). In a seminal paper, they proposed two (up to) birthday-bound secure design strategies — LRW1 and LRW2 — to convert any block cipher into a TBC. Several of the follow-up works consider cascading of LRW-type TBCs to construct beyond-the-birthday bound (BBB) secure TBCs. Landecker et al. demonstrated that just tworound cascading of LRW2 can already give a BBB security. Bao et al. undertook a similar exercise in context of LRW1 with TNT — a threeround cascading of LRW1 — that has been shown to achieve BBB security as well. In this paper, we present a CCA distinguisher on TNT that achieves a non-negligible advantage with O(2n/2 ) queries, directly contradicting the security claims made by the designers. We provide a rigorous and complete advantage calculation coupled with experimental verification that further support our claim. Next, we provide new and simple proofs of birthday-bound CCA security for both TNT and its single-key variant, which confirm the tightness of our attack. Furthering on to a more positive note, we show that adding just one more block cipher call, referred as 4-LRW1, does not just re-establish the BBB security, but also amplifies it up to 23n/4 queries. As a side-effect of this endeavour, we propose a new abstraction of the cascaded LRW-design philosophy, referred to as the LRW+ paradigm, comprising two block cipher calls sandwiched between a pair of tweakable universal hashes. This helps us to provide a modular proof covering all cascaded LRW constructions with at least 2 rounds, including 4-LRW1, and its more established relative, the well-known CLRW2, or more aptly, 2-LRW2</p>  <div class=" "> <a href="https://publications.cispa.de/articles/preprint/Tight_Security_of_TNT_and_Beyond_Attacks_Proofs_and_Possibilities_for_the_Cascaded_LRW_Paradigm_/25866685?file=46451572" role="button" class="btn btn-primary btn-md btn-external " > read full paper <i class="mdi mdi-arrow-top-right"></i> </a> </div> </div> </div> </div><div class="accordion-panel"> <div class="accordion-header" id="accordion-heading-414554-8"> <h3> <button class="btn collapsed" type="button" data-toggle="collapse" data-target="#accordion-collapse-414554-8" aria-expanded="false" aria-controls="accordion-collapse-414554-8"> Time-Lock Puzzles with Efficient Batch Solving <i class="mdi mdi-chevron-down"></i> </button> </h3> </div> <div id="accordion-collapse-414554-8" class="collapse" aria-labelledby="accordion-heading-414554-8"> <div class="accordion-body"> <p>Time-Lock Puzzles (TLPs) are a powerful tool for concealing messages until a predetermined point in time. When solving multiple puzzles, in many cases, it becomes crucial to have the ability to batch-solve puzzles, i.e., simultaneously open multiple puzzles while working to solve a single one. Unfortunately, all previously known TLP constructions that support batch solving rely on super-polynomially secure indistinguishability obfuscation, making them impractical. In light of this challenge, we present novel TLP constructions that offer batch-solving capabilities without using heavy cryptographic hammers. Our proposed schemes are simple and concretely efficient, and they can be constructed based on well-established cryptographic assumptions based on pairings or learning with errors (LWE). Along the way, we introduce new constructions of puncturable key-homomorphic PRFs both in the lattice and in the pairing setting, which may be of independent interest. Our analysis leverages an interesting connection to Hall’s marriage theorem and incorporates an optimized combinatorial approach, enhancing the practicality and feasibility of our TLP schemes. Furthermore, we introduce the concept of “rogue-puzzle attacks”, where maliciously crafted puzzle instances may disrupt the batch-solving process of honest puzzles. We then propose constructions of concrete and efficient TLPs designed to prevent such attacks.</p>  <div class=" "> <a href="https://cispa.de/en/research/publications/79286-time-lock-puzzles-with-efficient-batch-solving" role="button" class="btn btn-primary btn-md btn-external " > read full paper <i class="mdi mdi-arrow-top-right"></i> </a> </div> </div> </div> </div><div class="accordion-panel"> <div class="accordion-header" id="accordion-heading-414554-11"> <h3> <button class="btn collapsed" type="button" data-toggle="collapse" data-target="#accordion-collapse-414554-11" aria-expanded="false" aria-controls="accordion-collapse-414554-11"> Toothpicks: More Efficient Fork-Free Two-Round Multi-signatures <i class="mdi mdi-chevron-down"></i> </button> </h3> </div> <div id="accordion-collapse-414554-11" class="collapse" aria-labelledby="accordion-heading-414554-11"> <div class="accordion-body"> <p>Tightly secure cryptographic schemes can be implemented with standardized parameters, while still having a sufficiently high security level backed up by their analysis. In a recent work, Pan and Wagner (Eurocrypt 2023) presented the first tightly secure two-round multi-signature scheme without pairings, called Chopsticks. While this is an interesting first theoretical step, Chopsticks is much less efficient than its non-tight counterparts. In this work, we close this gap by proposing a new tightly secure two-round multi-signature scheme that is as efficient as non-tight schemes. Our scheme is based on the DDH assumption without pairings. Compared to Chopsticks, we reduce the signature size by more than a factor of 3 and the communication complexity by more than a factor of 2. Technically, we achieve this as follows: (1) We develop a new pseudorandom path technique, as opposed to the pseudorandom matching technique in Chopsticks. (2) We construct a more efficient commitment scheme with suitable properties, which is an important primitive in both our scheme and Chopsticks. Surprisingly, we observe that the commitment scheme does not have to be binding, enabling our efficient construction.</p>  <div class=" "> <a href="/en/research/publications/79212-toothpicks-more-efficient-fork-free-two-round-multi-signatures" role="button" class="btn btn-primary btn-md " > read full paper <i class="svg-icon"></i> </a> </div> </div> </div> </div><div class="accordion-panel"> <div class="accordion-header" id="accordion-heading-414554-9"> <h3> <button class="btn collapsed" type="button" data-toggle="collapse" data-target="#accordion-collapse-414554-9" aria-expanded="false" aria-controls="accordion-collapse-414554-9"> Twinkle: Threshold Signatures from DDH with Full Adaptive Security <i class="mdi mdi-chevron-down"></i> </button> </h3> </div> <div id="accordion-collapse-414554-9" class="collapse" aria-labelledby="accordion-heading-414554-9"> <div class="accordion-body"> <p>Sparkle is the first threshold signature scheme in the pairing-free discrete logarithm setting (Crites, Komlo, Maller, Crypto 2023) to be proven secure under adaptive corruptions. However, without using the algebraic group model, Sparkle’s proof imposes an undesirable restriction on the adversary. Namely, for a signing threshold t &lt; n, the adversary is restricted to corrupt at most t/2 parties. In addition, Sparkle’s proof relies on a strong one-more assumption. In this work, we propose Twinkle, a new threshold signature scheme in the pairing-free setting which overcomes these limitations. Twinkle is the first pairing-free scheme to have a security proof under up to t adaptive corruptions without relying on the algebraic group model. It is also the first such scheme with a security proof under adaptive corruptions from a well-studied non-interactive assumption, namely, the Decisional Diffie-Hellman (DDH) assumption. We achieve our result in two steps. First, we design a generic scheme based on a linear function that satisfies several abstract properties and prove its adaptive security under a suitable one-more assumption related to this function. In the context of this proof, we also identify a gap in the security roof of Sparkle and develop new techniques to overcome this issue. Second, we give a suitable instantiation of the function for which the corresponding one-more assumption follows from DDH.</p>  <div class=" "> <a href="https://cispa.de/en/research/publications/79205-twinkle-threshold-signatures-from-ddh-with-full-adaptive-security" role="button" class="btn btn-primary btn-md btn-external " > read full paper <i class="mdi mdi-arrow-top-right"></i> </a> </div> </div> </div> </div><div class="accordion-panel"> <div class="accordion-header" id="accordion-heading-414554-10"> <h3> <button class="btn collapsed" type="button" data-toggle="collapse" data-target="#accordion-collapse-414554-10" aria-expanded="false" aria-controls="accordion-collapse-414554-10"> Two-Round Maliciously-Secure Oblivious Transfer with Optimal Rate <i class="mdi mdi-chevron-down"></i> </button> </h3> </div> <div id="accordion-collapse-414554-10" class="collapse" aria-labelledby="accordion-heading-414554-10"> <div class="accordion-body"> <p>We give a construction of a two-round batch oblivious transfer (OT) protocol in the CRS model that is UC-secure against malicious adversaries and has (near) optimal communication cost. Specifically, to perform a batch of k oblivious transfers where the sender’s inputs are bits, the sender and the receiver need to communicate a total of 3k+o(k)·poly(λ) bits. We argue that 3k bits are required by any protocol with a black-box and straight-line simulator. The security of our construction is proven assuming the hardness of Quadratic Residuosity (QR) and the Learning Parity with Noise (LPN).</p>  <div class=" "> <a href="https://cispa.de/en/research/publications/79223-two-round-maliciously-secure-oblivious-transfer-with-optimal-rate" role="button" class="btn btn-primary btn-md btn-external " > read full paper <i class="mdi mdi-arrow-top-right"></i> </a> </div> </div> </div> </div> </div>  </div> </div> </section>   <footer class="footer bg-theme-white-black"> <div class="container-fluid"> <div class="row justify-content-center"> <div class="col-10 col-lg-6 d-flex flex-column justify-content-between"> <div> <nav> <ul class="nav-footer"> <li class="nav-item"><a href="/en/research" class="nav-link">Research</a></li> <li class="nav-item"><a href="/en/about" class="nav-link">About us</a></li> <li class="nav-item"><a href="/en/career" class="nav-link">Career</a></li> <li class="nav-item"><a href="/en/news-and-events" class="nav-link">News & Events</a></li> <li class="nav-item"></li> </ul> </nav> <p> The CISPA Helmholtz Center for Information Security is a national Big Science institution within the Helmholtz Association. It explores information security in all its facets in order to comprehensively and holistically address the pressing major challenges of cybersecurity and trustworthy artificial intelligence that our society faces in the digital age. CISPA holds a global leadership position in the field of cybersecurity, combining cutting-edge and often disruptive foundational research with innovative applied research, technology transfer, and societal discourse. Thematically, it aims to cover the entire spectrum from theory to empirical research. It is internationally recognized as a training ground for the next generation of cybersecurity experts and scientific leaders in the field. </p> </div> <div class="icon-links"> <a class="icon-link" href="https://www.instagram.com/c_i_s_p_a/" target="" title="CISPA on Instagram"> <i class="mdi mdi-instagram"></i> </a> <a class="icon-link" href="https://www.facebook.com/CispaSaarland/" target="_blank" title="CISPA on Facebook"> <i class="mdi mdi-facebook"></i> </a> <a class="icon-link" href="https://www.linkedin.com/company/cispa/mycompany/" target="_blank" title="CISPA on LinkedIn"> <i class="mdi mdi-linkedin"></i> </a> <a class="icon-link" href="https://open.spotify.com/show/2qC95LSZPmKUmNrgirhpfc" target="_blank" title="CISPA on Spotify"> <i class="mdi mdi-spotify"></i> </a> </div> </div> <div class="col-10 offset-lg-1 col-lg-3 d-flex flex-column justify-content-between"> <div> <div class="brand brand-cispa"> <img class="img-fluid show-on-bright" alt="Logo of Helmholtz Center for Information Security (CISPA)" title="CISPA" src="/images/cispa-logo-txt-rgb.svg"> <img class="img-fluid show-on-dark" alt="Logo of Helmholtz Center for Information Security (CISPA)" title="CISPA" src="/images/cispa-logo-txt-light.svg"> </div> <p>CISPA Helmholtz Center for Information Security<br> Stuhlsatzenhaus 5<br> 66123 Saarbrücken</p> <ul class="list-unstyled linklist"> <li> <a href="tel:+49 681 / 87083 1001" class="link link-phone" title="CISPA Phone Number"> <i class="mdi mdi-phone"></i> +49 681 / 87083 1001 </a> </li> <li> <a href="fax:+49 681 / 87083 8801" class="link link-fax" title="CISPA Fax Number"> <i class="mdi mdi-fax"></i> +49 681 / 87083 8801 </a> </li> <li> <a href="" class="link link-mail" target="_blank" data-dummy="cispa" data-nummy="info" data-tummy="de" title="CISPA Email Address"> <i class="mdi mdi-email-outline"></i> </a> </li> </ul> </div> <div class="brand brand-helmholtz"> <img class="ing-fluid show-on-bright" alt="Logo of the Helmholtz-Gemeinschaft Deutscher Forschungszentren" title="Helmholtz Gemeinschaft" src="/images/helmholtz-brand-dark.svg"> <img class="ing-fluid show-on-dark" alt="Logo of the Helmholtz-Gemeinschaft Deutscher Forschungszentren" title="Helmholtz Gemeinschaft" src="/images/helmholtz-brand-white.svg"> </div> </div> </div> <div class="row justify-content-center"> <div class="col-10"> <hr> </div> </div> <div class="row justify-content-center"> <div class="col-10"> <nav> <ul class="nav-footer nav-meta"> <li class="nav-item"><a href="/en/impressum" class="nav-link">Imprint</a></li> <li class="nav-item"><a href="/en/data-privacy-policy" class="nav-link">Data Privacy Policy</a></li> <li class="nav-item"><a href="/en/news-and-events/press" class="nav-link">Media Relations</a></li> <li class="nav-item"><a class="nav-link" href="/sitemap.xml">Sitemap</a></li> </ul> </nav> </div> <div class="col-10"> <div class="mb-5">Copyright CISPA 2025</div> </div> </div> </div> </footer> </body> </html>

CINXE.COM

11 CISPA Papers at Eurocrypt 2024. Eurocrypt is the International Conference on the Theory and Applications of Cryptographic Techniques.