BEGIN:VCALENDAR VERSION:2.0 PRODID:-//ENSL/CWI/KCL/IRISA Joint Online Cryptography Seminars//https://j cs.trusted-third-party.org/// BEGIN:VEVENT SUMMARY:SVP_p is Deterministically NP-Hard for all p > 2\, Even to Approxi mate Within a Factor of 2^{log^{1 - eps} n} by Isaac Hair DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20260323T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20260323T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202603231300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nWe prove that SVP_p is NP-hard to approximate within a fac tor of 2^{log^{1 - eps} n}\, for all constants eps > 0 and p > 2\, under s tandard deterministic Karp reductions. This result is also the first proof that exact SVP_p is NP-hard in a finite ell_p norm. Hardness for SVP_p wi th p finite was previously only known if NP is not contained in RP\, and u nder that assumption\, hardness of approximation was only known for all co nstant factors. As a corollary to our main theorem\, we show that under th e Sliding Scale Conjecture\, SVP_p is NP-hard to approximate within a smal l polynomial factor\, for all constants p > 2.\n \nOur proof techniques are surprisingly elementary\; we reduce from a regularized PCP instance d irectly to the shortest vector problem by using simple gadgets related to Vandermonde matrices and Hadamard matrices.\n\nIsaac Hair is an undergradu ate at UCSB\, currently conducting research in cryptography with Prof. Ami t Sahai at UCLA. END:VEVENT BEGIN:VEVENT SUMMARY:Introduction to Deniable Authentication: Goals\, Setting and Requi rements by Guilherme Rito DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20260309T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20260309T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202603091300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nDeniable authentication is a highly desirable property for secure communication: it allows a sender Alice to authentically transmit messages to a designated receiver Bob in such a way that only Bob gets con vinced that Alice indeed sent these messages.\nIn particular\, it guarante es that even if Bob tries to convince a (non-designated) party Judy that A lice sent some message\, and even if Bob gives Judy his own secret key\, J udy will not be convinced because as far as she knows Bob could be making it all up!\n\nThis talk will give an introduction to deniable authenticati on and present some current challenges in the area.\n\nWe will introduce t wo main technical instantiations of deniable authentication---Designated V erifier Signatures and Ring Signatures.\nAs we do so\, we will identify a (particularly unique) setup requirement of deniable authentication\, namel y\, that dishonest parties must know their secret keys.\nTo enforce this\, we introduce a Key-Registration procedure that (we show) is sufficient fo r deniable authentication.\nIt guarantees\, roughly\, that if a user’s k ey registration is successful\, then the user can extract by themselves a valid secret key from their interaction with the registration authority.\n We explain why this setup seems inherently necessary by listing a series o f (simple) attacks that void deniability.\nEach of these attacks consists of a user successfully registering a public key for which it can convincin gly claim it does not know a valid (corresponding) secret key.\nFinally\, we will discuss some of the current challenges in bringing deniable authen tication into practice.\n\nGuilherme Rito is a postdoctoral researcher at Ruhr University Bochum\, in the group of Eike Kiltz.\nHe received his Ph.D . from ETH Zurich under the supervision of Ueli Maurer.\n\nHis research in terests lie broadly in cryptography.\nRecently\, he has been focusing on d eniable authentication and consistency guarantees for broadcast encryption schemes.\n END:VEVENT BEGIN:VEVENT SUMMARY:Meet-in-the-Middle Attacks on Full ChiLow by Eran Lambooij DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20260223T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20260223T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202602231300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nChiLow (EC2025) is a low latency cipher designed for in-li ne memory encryption. Low latency ciphers are getting increasingly popular due to a demand from industry. The main caveat is that these ciphers are notoriously hard to design\, due to the tight constraints (sub nanosecond latency).\nChilow uses a novel non-linear layer: ChiChi which is based on the Keccak Chi function and adapted for even-bit state sizes. This propert y\, the aggressive amount of rounds\, and the novelty of the construction have led to a remarkable amount of cryptanalysis in a short amount of time . \n\nIn this talk we first look at memory encryption as a general concept \, why we need it in practice\, and why low-latency ciphers are *fun* to l ook at. We then give a gentle introduction into MitM attacks. Finally we l ook at our attack on ChiLow\, going from a simple yet efficient attack\, t hrough some optimizations\, to a full-round attack on ChiLow breaking the designers' security claims.\n\nEran Lambooij is a PostDoctoral researcher at INRIA Paris in the COSMIQ team working on the analysis of symmetric cip hers focusing on small-domain and low-latency ciphers END:VEVENT BEGIN:VEVENT SUMMARY:On the Security of FHE in the CPA^D Model by Marina Checri DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20260209T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20260209T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202602091300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nFully Homomorphic Encryption (or FHE) is a set of cryptogr aphic techniques that allows computations to be carried out directly over encrypted data\, ensuring the confidentiality of data during calculations without prior decryption. However\, so far\, the security of FHE is not w ell understood beyond the basic CPA (Chosen Plaintext Attack) level. This talk aims to clarify the security of FHE in regimes beyond the CPA model. We focus on a specific security notion called CPA^D\, in which the adversa ry Eve has more power than in the CPA model—specifically\, she can also request the decryption of well-formed ciphertexts. Thus\, in this work\, w e conduct attacks and propose new constructions in order to advance the un derstanding of FHE's security properties in the CPA^D security model.\n\n Marina Checri is a young researcher who has just completed her PhD thesis at CEA List\, Paris Saclay University\, under the supervision of Renaud Si rdey and Jean-Paul Bultel. She is interested in Fully Homomorphic Encrypti on (FHE) and threshold multi-party protocols. Her work focuses mainly on s ecurity notions beyond CPA for FHE schemes. END:VEVENT BEGIN:VEVENT SUMMARY:Module Learning with Errors with Truncated Matrices by Katharina Boudgoust DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20260112T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20260112T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202601121300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nThe Module Learning with Errors (M-LWE) problem is one of the most commonly used hardness assumption in lattice-based cryptography. In its standard version\, a matrix A is sampled uniformly at random over a quotient ring R_q\, as well as noisy linear equations in the form of As+e mod q\, where s is the secret\, sampled uniformly at random over R_q\, an d e is the error\, coming from a Gaussian distribution. Many previous work s have focused on variants of M-LWE\, where the secret and/or the error ar e sampled from different distributions. Only few works have focused on dif ferent distributions for the matrix . One variant proposed in the literatu re is to consider matrix distributions where the low-order bits of a unifo rm are deleted. This seems a natural approach in order to save in bandwidt h. We call it truncated M-LWE.\n\nIn this talk\, we show that the hardness of standard M-LWE implies the hardness of truncated M-LWE\, both for sear ch and decision versions. Prior works only covered the search variant and relied on the (module) assumption\, limitations which we are able to overc ome. Overall\, we provide two approaches\, offering different advantages. The first uses a general Rényi divergence argument\, applicable to a wide range of secret/error distributions\, but which only works for the search variants of (truncated) M-LWE. The second applies to the decision version s\, by going through an intermediate variant of M-LWE\, where additional h ints on the secret are given to the adversary. However\, the reduction mak es use of discrete Gaussian distributions. \n\nKatharina Boudgoust is a te nured researcher at the French public research organization CNRS and affil iated with the ECO team of the LIRMM in Montpellier\, France. She is gener ally interested in lattice-based cryptography\, spanning topics such as un derlying computational hardness assumptions\, to building and analyzing cr yptosystems. END:VEVENT BEGIN:VEVENT SUMMARY:Wagner’s Algorithm Provably Runs in Subexponential Time for SIS^ ∞ by Johanna Loyer DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20251208T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20251208T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202512081300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nWe revisit the Blum-Kalai-Wasserman (BKW) algorithm and it s subexponential variant proposed by Kirchner and Fouque (CRYPTO 2015) for solving Learning with Errors (LWE). Taking a modular view\, we regard BKW as a combination of Wagner's algorithm (CRYPTO 2002)\, run over the corre sponding dual problem\, and the Aharonov-Regev distinguisher (JACM 2005). Hence\, the subexponential Wagner step alone should be of interest for sol ving this dual problem -- namely\, the Short Integer Solution problem (SIS ) -- but this appears to have been undocumented so far. \nWe reinterpret t his Wagner step as walking backward through a chain of projected lattices\ , zigzagging through some auxiliary superlattices. This approach yields an approximate discrete Gaussian sampler for $q$-ary lattices\, running in t ime $\\exp(O(n / \\log \\log n))$.\nApplied to $\\mathrm{SIS}^\\infty$ wit h norm bound $\\beta = q / \\mathrm{polylog}(n)$\, the method provides the first provable subexponential-time algorithm for this setting. We discuss its implications for lattice-based cryptography\, including the NIST stan dard ML-DSA (Dilithium)\, whose security remains unaffected in practice.\n \nThis is a joint work with Léo Ducas and Lynn Engelberts. \n\nJohanna Lo yer is a postdoctoral researcher at Inria Saclay in the GRACE team\, worki ng on the classical and quantum cryptanalysis of post-quantum schemes\, wi th a particular focus on lattice- and code-based cryptography. Before join ing Inria Saclay\, she completed her PhD at Inria Paris in 2023 and held a postdoctoral position at CWI in Amsterdam. END:VEVENT BEGIN:VEVENT SUMMARY:Format-Preserving Compression-Tolerating Authenticated Encryption for Images by Kaishuo Cheng DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20251124T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20251124T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202511241300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nWe study the problem of provably-secure format-preserving authenticated encryption scheme\nfor images\, where decryption is successf ul even when ciphertexts undergo compression. This novel primitive offers users more control and privacy when sharing and storing images on social m edia and other photo-centric\, compressing platforms like Facebook and Goo gle Photos. Since compression is usually lossy\, we cannot expect the decr ypted image to be identical to the original. But we want the decrypted ima ge to be visually as close to the original image as possible. \nThere is a vast number of works on image encryption\, mostly in the signal processin g community\, but they do not provide formal security analyses. We formall y define security\, covering the goals of image confidentiality and integr ity. While we first treat the problem generically\, we are particularly in terested in the construction for the most common compression format\, JPEG . We design a scheme for JPEG compression using the standard symmetric cry ptographic tools and special pre- and post-processing. We formally assess the security guarantees provided by the construction\, discuss how to sel ect the parameters using empirical experiments\, and study performance of our scheme in terms of computational efficiency and decryption quality. We also build a browser plug-in that helps users store and share photos priv ately. \n\nI am a 4th year PhD student in Georgia Tech advised by Joseph J aeger and Sasha Boldyreva. END:VEVENT BEGIN:VEVENT SUMMARY:Somewhat Homomorphic Encryption from Linear Homomorphism and Spars e LPN by Alexandra Henzinger DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20251110T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20251110T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202511101300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nIn this talk\, I will show how to construct somewhat homom orphic encryption from the sparse learning-parities-with-noise problem\, a long with an assumption that implies linearly homomorphic encryption (e.g. \, the DDH or DCR assumptions). The resulting schemes support an a-priori bounded number of homomorphic operations: o(\\log \\lambda) multiplication s followed by poly(\\lambda) additions\, where \\lambda is a security para meter. Unlike prior somewhat-homomorphic-encryption schemes for bounded-de gree polynomials\, our new schemes do not rely on lattice assumptions or b ilinear maps. Moreover\, our schemes are conceptually simple: much as in G entry\, Sahai\, and Waters’ fully-homomorphic-encryption scheme\, cipher texts in our scheme are matrices\, homomorphic addition is matrix addition \, and homomorphic multiplication is matrix multiplication.\n\nJoint work with Henry Corrigan-Gibbs\, Yael Kalai\, and Vinod Vaikuntanathan (EUROCRY PT 2025).\n\nAlexandra Henzinger is a Ph.D. student in the Parallel and Di stributed Operating Systems group at MIT\, advised by Henry Corrigan-Gibbs . Alexandra works on building computer systems that protect their users’ security and privacy. Much of her recent work has focused on private info rmation retrieval\, from designing cryptographic protocols to building a p rivate search engine. She has received an NSF GRFP fellowship and an MIT E ECS Great Educators fellowship\, and she was selected as a 2024 EECS Risin g Star. END:VEVENT BEGIN:VEVENT SUMMARY:Game Changer: A Modular Framework for OPRF Security by Karla Fried richs DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20251027T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20251027T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202510271300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nOblivious pseudorandom functions (OPRFs) allow the blind e valuation of a pseudorandom function\, which makes them a versatile buildi ng block that enjoys usage in numerous applications. So far\, security of OPRFs is predominantly captured in the Universal Composability (UC) framew ork\, where an ideal functionality covers the expected security and privac y properties. While the OPRF functionality appears intuitive at first\, th e ideal-world paradigm also comes with a number of challenges: from imposi ng idealized building blocks when building OPRFs\, to the lack of modulari ty\, and requiring intricate UC knowledge to securely maneuver their usage . Game-based definitions are a simpler way to cover security properties. T hey model each property in a single game\, which grants modularity in form alizing\, proving\, and using OPRFs. Interestingly\, the few game-based wo rks on OPRFs each re-invent the security model\, with considerable variati on. Thus\, the advantages of the game-based approach remain out of reach: definitions are not easily accessible and comparability across works is lo w. In this work\, we therefore systematize all existing notions into a cle ar\, hierarchical framework. We unify or separate properties\, making hidd en relations explicit. This effort reveals the necessity of two novel prop erties: an intermediate privacy notion and a stronger unpredictability not ion. Finally\, we analyze the two most prominent constructions in our fram ework: HashDH and 2HashDH. The former does not achieve UC security\, but h as advantages in applications that require key rotation or updatability\; yet it lacks a security analysis. We show that it achieves most security p roperties in our framework. We also observe that HashDH and 2HashDH do not satisfy our strongest privacy notion\, indicating that the guarantees by the UC functionality are not as well understood as we might expect them to be. Overall\, we hope that our framework facilitates the usage and design of OPRFs.\n\nKarla Friedrichs is a PhD student in the group of Anja Lehma nn at Hasso Plattner Institute. She has a background in cybersecurity and NLP\; in the first year of her PhD\, she explores topics in the realm of a nonymous credentials and provable security of cryptographic primitives. END:VEVENT BEGIN:VEVENT SUMMARY:Threshold Signatures from One-Way Functions by Pedro Branco DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20251013T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20251013T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202510131300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nA threshold signature allows one to delegate its signing r ights to parties\, such that any subset of size can sign a message on thei r behalf. In this work\, we show how to construct threshold signatures for any and from one way functions\, thus establishing the latter as a necess ary and sufficient computational assumption. Our protocol makes non-black box use of one-way functions\, and can be generalized to other access stru ctures\, such as monotone policies.\n\nThis is joint work with Giulio Mala volta.\n\nPedro is a postdoc at Bocconi University. Previously\, he was a postdoc at the Max Planck Institute for Security and Privacy and a postdoc at Johns Hopkins University. He received my PhD from Tecnico Lisbon in 20 22. END:VEVENT BEGIN:VEVENT SUMMARY:Cryptanalysis of an Efficient Signature Based on Isotropic Quadrat ic Forms by Henry Bambury DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20250929T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20250929T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202509291300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nIf lattice reduction is used today as the main cryptanalyt ic tool to attack lattice-based schemes\, it can also apply to other schem es\, for which lattices do not appear explicitly in the construction. \n\n DEFI is an efficient signature scheme proposed by Feussner and Semaev\, ba sed on a structured version of quadratic form equivalence. It borrows idea s from both multivariate and lattice cryptography. \n\nWe present a key-re covery attack on DEFI. Our lattice-based attack is partially heuristic\, b ut works on all proposed parameters: experimentally\, it recovers the secr et key in a few minutes\, using less than ten (message\, signature) pairs. \n\n- joint work with Phong Nguyen.\n\nI am a third year PhD student at EN S in Paris\, under the supervision of Phong Nguyen. My work is mainly rela ted to lattices and their use in cryptanalysis. END:VEVENT BEGIN:VEVENT SUMMARY:Super-Quadratic Quantum Speed-Ups and Guessing Many Likely Keys by Julian Nowakowski DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20250901T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20250901T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202509011300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nIn this talk\, we consider the fundamental problem of gues sing cryptographic keys\, drawn from some distribution $\\mathcal{D}$. The optimal classical algorithm enumerates keys in decreasing order of likeli hood. The optimal quantum algorithm\, due to Montanaro (2011)\, is a sophi sticated Grover search.\n\nWe give the first tight analysis for Montanaro ’s algorithm\, showing that its runtime is $2^{H_{2/3}(\\mathcal{D})/2}$ \, where $H_\\alpha(\\cdot)$ denotes Renyi entropy with parameter $\\alpha $. Interestingly\, this is a direct consequence of an information theoreti c result called Arikan’s Inequality (1996) – which has so far been mis sed in the cryptographic community – that tightly bounds the runtime of classical key guessing by $2^{H_{1/2}(\\mathcal{D})}$.\n\nSince $H_{2/3}(\ \mathcal{D}) < H_{1/2}(\\mathcal{D})$ for every non-uniform distribution $ \\mathcal{D}$\, we thus obtain a super-quadratic quantum speed-up $s>2$ ov er classical key guessing. To give some numerical examples\, for the binom ial distribution used in Kyber\, we obtain quantum speed-up $s>2.04$. For $n$-dimensional small error LPN keys\, we achieve *unbounded* quantum spee dup $s = \\Omega(n^{1/12})$.\n\nAdditionally\, we provide the first thorou gh analysis of guessing in a multi-key setting. Specifically\, we consider the task of attacking many keys sampled independently from some distribut ion $\\mathcal{D}$\, and aim to guess a fraction of them. For product dist ributions $\\mathcal{D} = \\chi^n$\, we show that any constant fraction of keys can be guessed within $2^{H(\\mathcal{D})}$ classically and $2 ^{H(\ \mathcal{D})/2}$ quantumly per key\, where $H(\\chi)$ denotes Shannon entr opy. In contrast\, Arikan's Inequality implies that guessing a single key costs $2^{H_{1/2}(\\mathcal{D})}$ classically and $2^{H_{2/3}(\\mathcal{D} )/2}$ quantumly. Since $H(\\mathcal{D}) < H_{2/3}(\\mathcal{D}) < H_{1/2}( \\mathcal{D})$\, this shows that in a multi-key setting the guessing cost per key is substantially smaller than in a single-key setting\, both class ically and quantumly.\n\nJulian Nowakowski is a fourth-year PhD student at Ruhr University Bochum\, supervised by Alexander May. He is currently a v isiting researcher at CWI in Amsterdam\, hosted by Léo Ducas. His researc h focuses on the cryptanalysis of post-quantum cryptography\, with particu lar interest in lattice-based and code-based constructions. END:VEVENT BEGIN:VEVENT SUMMARY:A Privacy-Preserving Aid Distribution System with Assessment Capab ilities\; Or\, a Case Study on Threat Modeling and System Design by Christ ian Knabenhans DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20250721T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20250721T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202507211300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nToday\, humanitarian aid distribution heavily relies on ma nual processes that can be slow\, error-prone\, and costly. Humanitarian a id organizations therefore have a strong incentive to digitalize the aid d istribution process. This would allow them to scale up their operations\, reduce costs\, and increase the impact of their limited resources. Digital izing the aid distribution process introduces new challenges\, especially in terms of privacy and security. These challenges are particularly acute in the context of humanitarian aid\, where the recipients are often vulner able populations\, and where the aid distribution process is subject to a high degree of scrutiny by the public\, the media\, and the donors. This i s compounded by a very strong threat model\, with adversaries ranging from corrupt officials to armed groups\, and by the fact that the recipients t hemselves may not be able to protect their own privacy. \n\n\nThis talk is split into three main parts: first\, we stress the need for assessments w hen deploying privacy-preserving applications in the real world\, using co ncrete examples. In particular\, we discuss the tension between supporting assessments and the security and privacy of the application's users. \n\n Second\, we reflect on our experience in designing privacy-preserving appl ications for various use cases\, and discuss how we go from an informal\, high-level need expressed by our partners\, to a formal model and a concre te protocol. Here\, we stress common pitfalls\, and outline a methodology that we have synthesized from our experience. \n\nFinally\, we discuss how we tackled the use case of a privacy-preserving aid distribution system w ith statistics\, in collaboration with partners from the International Com mittee of the Red Cross. We present a general framework to collect and eva luate statistics in a privacy-preserving way (including one-time functiona l encryption\, a new primitive that we introduce)\, and we present two con crete instantiations of this framework (based on linear secret sharing\, a nd threshold fully homomorphic encryption\, respectively).\n\n\n\n\nChrist ian Knabenhans is a doctoral student at EPFL\, advised by Carmela Troncoso (with whom he works on applying advanced cryptographic primitive to real- world systems) and Alessandro Chiesa (working on lattice-based succinct an d zero-knowledge arguments). END:VEVENT BEGIN:VEVENT SUMMARY:Why Johnny Can Deny: On Practical Deniable Group Chat Encryption b y Daniel Collins DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20250623T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20250623T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202506231300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nGroup chat encryption in practice generally relies on symm etric cryptography to encrypt messages\, and digital signatures so that us ers can authenticate as having sent a given message. This template forms t he basis of many group chat encryption schemes in practice including MLS\, Signal and Keybase\, and has been abstracted as *symmetric signcryption* and explored in a fruitful line of recent work (Jaeger\, Kumar and Stepano vs\, Eurocrypt'24\; Jaeger and Kumar\, Eurocrypt'25). Although practical m essengers like Signal claim to provide *deniability* for users\, this has not been analysed on the chat encryption level. Therefore\, in this work\, we define and explore the deniability of symmetric signcryption. Deniabil ity is unavoidably lost\, however\, if the adversary learns the group key\ , which is a significant limitation\, especially in large groups.\n\nMotiv ated by this limitation\, we make the following contributions to character ise the practicality of strongly-deniable group chat encryption:\n- We int roduce the *extended symmetric signcryption* primitive that allows public key pairs in its syntax and therefore provides stronger deniability\, and construct it from symmetric encryption and multi-designated verifier signa tures (MDVS) secure under strong security notions stemming from Damgård e t al. (TCC'20).\n- Although signatures must grow linearly in size\, previo us MDVS constructions were impractical even for small groups. Therefore\, we provide two new MDVS constructions. The first is based on DDH and is co ncretely efficient. The second is based on indistinguishability obfuscatio n and is the first construction for which signatures grow in the number of users that are allowed to be corrupted in the deniability game\, which co uld be significantly smaller than the size of the group. The only other kn own construction with this property is from Damgard et al. (TCC'20) which relies on functional encryption and thus requires a master secret key\, wh ich is impractical for group messaging.\n- We revisit the Public Key Encry ption for Broadcast (PKEBC) primitive introduced by Maurer et al. at Euroc rypt'22 used to construct deniable public-key encryption. In PKEBC\, the s et of public keys the sender encrypts to is output during decryption\, and therefore ciphertexts grow linearly in size. We provide an information-th eoretic argument to show that ciphertexts must grow linearly even if we do *not* require public keys to be output upon decryption. This negative res ult further motivates the use of symmetric encryption in group messaging.\ n\nOngoing work with Wonseok Choi\, Joseph Jaeger\, Akshaya Kumar\, Xiangy u Liu and Vassilis Zikas.\n\nDaniel Collins is a postdoctoral researcher w orking with Juan Garay and Vassilis Zikas\, currently at Texas A&M Univers ity and previously at Georgia Tech and Purdue University. His work focuses on cryptography and particularly on secure messaging systems and distribu ted protocol design. In secure messaging\, Daniel has modelled real-world protocols used by billions in practice\, designed new protocols and explor ed the foundations of secure communication. In distributed protocols\, he has worked on reducing the cost of solving tasks like consensus\, broadcas t and multi-party computation\, and on designing protocols that provide gu arantees when parties experience severe network and adversarial behaviour. Daniel completed his PhD in 2024 at EPFL in Switzerland under Serge Vaude nay's supervision and was awarded a Thesis Distinction by the school. Befo re that\, he received a Bachelors in Computer Science and Mathematics from the University of Sydney and was awarded the University Medal for his Hon ours thesis. END:VEVENT BEGIN:VEVENT SUMMARY:The Greyhound and Labrador lattice-based proof systems and their i mplementation by Gregor Seiler DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20250609T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20250609T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202506091300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nI will present the Greyhound polynomial commitment scheme\ , and the underlying Labrador proof system for lattice relations with shor t proofs. I will then place particular emphasis on optimized implementatio n strategies for these systems.\n\nGregor Seiler is a staff research scien tist at IBM Research. He is a co-designer of the NIST post-quantum cryptog raphy standards ML-KEM\, ML-DSA and FN-DSA END:VEVENT BEGIN:VEVENT SUMMARY:Cryptanalysis of rank 2 Module-LIP for certain number fields by Gu ilhem Mureau DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20250428T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20250428T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202504281300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nIn 2022\, Ducas et al. introduced the signature scheme Haw k\, based of the presumed hardness of a new problem in lattice-based crypt ography: the Lattice Isomorphism Problem for the module-lattice O_L^2\, wh ere L is a cyclotomic number field. Last year we presented a polynomial ti me algorithm solving this problem when L is a totally real number field (t hus not affecting the security of Hawk). More recently\, we provided a red uction of the same problem when L is now a CM field (thus containing Hawk' s instance) to the problem of finding a generator of a principal quaternio nic ideal.\nIn this talk we give a framework containing both the totally r eal and the CM case\, and we will discuss the differencies. This is based on a joint work with C. Chevignard\, P-A. Fouque\, A. Pellet-Mary\, H. Pli atsok and A. Wallet.\n\n\nI started my PhD in September 2023 at Inria / Un iversity of Bordeaux (France)\, after a master degree in pure mathematics. My thesis is about isomorphisms of structured lattices\, a subject motiva ted by the recent use of such concepts in cryptography. More generally\, I 'm interested in all fields of number theory and their applications in cry ptography. END:VEVENT BEGIN:VEVENT SUMMARY:An Information Theory for Post-Quantum Cryptography: Learning With Quantization by Cong Ling DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20250331T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20250331T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202503311300@https://jcs.trusted-third-party.org/ DESCRIPTION:Paper: https://eprint.iacr.org/2024/714\n\nInformation Theory and Cryptography share a common foundation in Shannon’s pioneering work. These fields are deeply interconnected and have the potential to mutually enhance one another. The advent of Post-Quantum Cryptography (PQC) offers a unique opportunity to reunite these disciplines. In this work\, we unco ver a novel connection between information theory and the Learning With Er rors (LWE) problem. Specifically\, we introduce Learning With Quantization (LWQ)\, a new problem closely related to LWE and Learning With Rounding ( LWR). LWQ establishes a tight security reduction from LWE while enabling e fficient ciphertext compression. Notably\, we demonstrate that the compres sion rate is ultimately governed by the capacity of the “LWE channel\, ” thereby unifying the concepts of information-theoretic compression and computational security.\n\nCong Ling is a Professor of Information Theory and Cryptography at Imperial College London. His research focuses on the study of lattices and their applications to coding and cryptography\, as w ell as exploring their connections with number theory and quantum informat ion. END:VEVENT BEGIN:VEVENT SUMMARY:Lova: Lattice-Based Folding Scheme from Unstructured Lattices by G iacomo Fenzi DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20250317T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20250317T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202503171300@https://jcs.trusted-third-party.org/ DESCRIPTION:Paper: https://eprint.iacr.org/2024/1964\n\nFolding schemes (K othapalli et al.\, CRYPTO 2022) are a conceptually simple\, yet powerful c ryptographic primitive that can be used as a building block to realise inc rementally verifiable computation (IVC) with low recursive overhead withou t general-purpose non-interactive succinct arguments of knowledge (SNARK). \nMost folding schemes known rely on the hardness of the discrete logarit hm problem\, and thus are both not quantum-resistant and operate over larg e prime fields. Existing post-quantum folding schemes (Boneh\, Chen\, ePri nt 2024/257) based on lattice assumptions instead are secure under structu red lattice assumptions\, such as the Module Short Integer Solution Assump tion (MSIS)\, which also binds them to relatively complex arithmetic. \nIn contrast\, we construct Lova\, the first folding scheme whose security re lies on the (unstructured) SIS assumption. We provide a Rust implementatio n of Lova\, which makes only use of arithmetic in hardware-friendly power- of-two moduli. Crucially\, this avoids the need of implementing and perfor ming any finite field arithmetic. At the core of our results lies a new ex act Euclidean norm proof which might be of independent interest\n\nI am a PhD student at EPFL\, focusing on theoretical and concrete improvements in post-quantum proof systems.\nGenerally\, I focus on construction based on the security of hash functions\, and lattices. I also give terrible names to such constructions. END:VEVENT BEGIN:VEVENT SUMMARY:Practical Post-Quantum Signatures for Privacy by Corentin Jeudy DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20250303T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20250303T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202503031300@https://jcs.trusted-third-party.org/ DESCRIPTION:Paper: https://eprint.iacr.org/2024/131\n\nThe transition to p ost-quantum cryptography has been an enormous challenge and effort for cry ptographers over the last decade\, with impressive results such as the fut ure NIST standards. However\, the latter has so far only considered centra l cryptographic mechanisms (signatures or KEM) and not more advanced ones\ , e.g.\, targeting privacy preserving applications. Of particular interest is the family of solutions called blind signatures\, group signatures and anonymous credentials\, for which standards already exist\, and which are deployed in billions of devices. Such a family does not have\, at this st age\, an efficient post-quantum counterpart although very recent works imp roved this state of affairs by offering two different alternatives: either one gets a system with rather large elements but a security proved under standard assumptions or one gets a more efficient system at the cost of ad -hoc interactive assumptions or weaker security models. Moreover\, all the se works have only considered size complexity without implementing the qui te complex building blocks their systems are composed of. In other words\, the practicality of such systems is still very hard to assess\, which is a problem if one envisions a post-quantum transition for the corresponding systems/standards.\n\nIn this work\, we propose a construction of so-call ed signature with efficient protocols (SEP)\, which is the core of such pr ivacy-preserving solutions. By revisiting the approach by Jeudy et al. (Cr ypto 2023) we manage to get the best of the two alternatives mentioned abo ve\, namely short sizes with no compromise on security. To demonstrate thi s\, we plug our SEP in an anonymous credential system\, achieving credenti als of less than 80 KB. In parallel\, we fully implemented our system\, an d in particular the complex zero-knowledge framework of Lyubashevsky et al . (Crypto’22)\, which has\, to our knowledge\, not be done so far. Our w ork thus not only improves the state-of-the-art on privacy-preserving solu tions\, but also significantly improves the understanding of efficiency an d implications for deployment in real-world systems.\n\nJoint work with Sv en Argo\, Tim Güneysu\, Georg Land\, Adeline Roux-Langlois\, Olivier Sand ers.\n\nI am a cryptography researcher at Orange. I completed my PhD on th e design of advanced post-quantum signature schemes under the supervision of Pierre-Alain Fouque (Rennes University)\, Adeline Roux-Langlois (CNRS) and Olivier Sanders (Orange). My work focuses\n on lattice-based cryptogra phic constructions for privacy-enhanced authentication mechanisms\, and im plementations. I also sometimes work on the theoretical study of lattice s ecurity foundations. END:VEVENT BEGIN:VEVENT SUMMARY:Unbounded ABE for Circuits from LWE\, Revisited by Valerio Cini DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20250217T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20250217T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202502171300@https://jcs.trusted-third-party.org/ DESCRIPTION:Paper: https://eprint.iacr.org/2024/1507\n\nWe introduce new l attice-based techniques for building ABE for circuits with unbounded attri bute length based on the LWE assumption\, improving upon the previous con structions of Brakerski and Vaikuntanathan (CRYPTO 16) and Goyal\, Koppula \, and Waters (TCC 16). Our main result is a simple and more efficient un bounded ABE scheme for circuits where only the circuit depth is fixed at s et-up\; this is the first unbounded ABE scheme for circuits that rely only on black-box access to cryptographic and lattice algorithms. The scheme a chieves semi-adaptive security against unbounded collusions under the LWE assumption. The encryption time and ciphertext size are roughly 3x larger than the prior bounded ABE of Boneh et al. (EUROCRYPT 2014)\, substantiall y improving upon the encryption times in prior works. As a secondary contr ibution\, we present an analogous result for unbounded inner product predi cate encryption that satisfies weak attribute-hiding.\n\nBased on joint wo rk with Hoeteck Wee.\n\nValerio Cini is a postdoctoral researcher at Bocco ni University working with Giulio Malavolta. He has been working on lattic e-based constructions of advanced encryption schemes and proof systems. END:VEVENT BEGIN:VEVENT SUMMARY:Can you break lattice cryptography with a moon-sized computer? by Sam Jaques DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20250203T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20250203T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202502031300@https://jcs.trusted-third-party.org/ DESCRIPTION:Paper: https://cic.iacr.org/p/1/3/6\n\nFor most lattice-based schemes (including Kyber/ML-KEM and Dilithium/ML-DSA)\, the best known att acks are generic lattice attacks\, and the fastest generic lattice attacks are based on lattice sieving. However\, lattice sieving is an extremely m emory-intensive algorithm: how does this change the landscape of attack co mplexity?\n\nIn this talk I will argue that at the scale of hardware neces sary to run these attacks\, we must consider parallelism\, and the most re alistic parallel\, planet-sized architecture is a vast mesh network. I wil l give a straightforward modification of existing lattice sieving algorith ms that will run on this architecture\, and then a more complicated recurs ive version that nearly matches the asymptotic cost obtained by ignoring a ll these real-world constraints. In fact\, if we have a 3-dimensional mesh network (imagine filling the interior of the moon with computers)\, then we can match the unconstrained cost\, but with a 2-dimensional network (im agine covering the surface of the moon with computers) accounting for memo ry and routing does increase the cost estimates. If we make some dubious a ssumptions about the constants\, this adds about 14 bits to the security o f Kyber-512.\n\nSam Jaques is an assistant professor at the University of Waterloo\, where he works on quantum cryptanalysis and generally considers attacks by computers that may never exist. He has a PhD from Oxford Unive rsity and a master’s from the University of Waterloo. END:VEVENT BEGIN:VEVENT SUMMARY:Smoothing Parameter and Shortest Vector Problem on Random Lattices by Amaury Pouly DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20250120T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20250120T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202501201300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nLattice problems have many applications in various domains of computer science. There is currently a gap in the understanding of th ese problems with respect to their worst-case complexity and their average -case behaviour. For instance\, the Shortest Vector problem (SVP) on an n- dimensional lattice has worst-case complexity $2^{n+o(n)}$. However\, in p ractice\, people rely on heuristic (unproven) sieving algorithms of time c omplexity $2^{0.292n+o(n)}$ to assess the security of lattice-based crypto graphy schemes. Those heuristic algorithms are experimentally verified for lattices used in cryptography\, which are usually random in some way.\n\n In this talk\, I will present some recent work that tries to bridge the ga p between worst-case and heuristic algorithms. Using the formalism of rand om real lattices developed by Siegel\, we show a tighter upper bound on an important lattice parameter called the smoothing parameter that applies t o almost all random lattices. This allows us to obtain a $2^{n/2+o(n)}$ ti me algorithm for an approximation version of the SVP on random lattices wi th a small constant approximation factor. We will also see that in this se tting\, the corresponding approximation version of GapSVP is provably easy \, giving a formal version of the "Gaussian Heuristic".\n\n\nI am a CNRS r esearcher\, currently on sabbatical at lowRISC C.I.C. My research interest s include analog models of computation\, numerical analysis\, verification of hybrid systems and cryptography. Recently\, I have become interested i n latticed-based cryptography and mathematical aspects of lattices in part icular. END:VEVENT BEGIN:VEVENT SUMMARY:Two-Round Threshold Signature from Algebraic One-More Learning wit h Errors by Kaoru Takemure DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20241118T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20241118T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202411181300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nThreshold signatures have recently seen a renewed interest due to applications in cryptocurrency while NIST has released a call for multi-party threshold schemes\, with a deadline for submission expected fo r the first half of 2025. So far\, all lattice-based threshold signatures requiring two-rounds or less are based on heavy tools such as (fully) homo morphic encryption (FHE) and homomorphic trapdoor commitments (HTDC). This is not unexpected considering that most efficient two-round signatures fr om classical assumptions either rely on idealized model such as algebraic group models or on one-more type assumptions\, none of which we have a nic e analogue in the lattice world.\n\nIn this work\, we construct the first efficient two-round lattice-based threshold signature without relying on F HE or HTDC. It has an offline-online feature where the first round can be preprocessed without knowing message or the signer sets\, effectively maki ng the signing phase non-interactive. The signature size is small and show s great scalability. For example\, even for a threshold as large as 1024 s igners\, we achieve a signature size roughly 11 KB. At the heart of our co nstruction is a new lattice-based assumption called the algebraic one-more learning with errors (AOMMLWE) assumption. We believe this to be a strong inclusion to our lattice toolkits with an independent interest. We establ ish the selective security of AOMMLWE based on the standard MLWE and MSIS assumptions\, and provide an in depth analysis of its adaptive security\, which our threshold signature is based on.\n\nI'm a postdoctoral researche r at PQShield under the supervision of Shuichi Katsumata. I'm aslo a colla borative researcher at AIST. I hold a PhD degree from the University of El ectro-Communications\, Japan. I have mainly been working on classical and (lattice-based) post-quantum aggregatable signatures\, e.g.\, aggregate si gnature\, multi-signature\, and threshold signature. END:VEVENT BEGIN:VEVENT SUMMARY:Cryptanalysis of Lattice-Based Sequentiality Assumptions and Proof s of Sequential Work by Yi Tang DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20241028T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20241028T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202410281300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nThis work *completely breaks* the sequentiality assumption (and broad generalizations thereof) underlying the candidate lattice-base d proof of sequential work (PoSW) recently proposed by Lai and Malavolta a t CRYPTO 2023.\nIn addition\, it breaks an essentially identical variant o f the PoSW\, which differs from the original in only an arbitrary choice t hat is immaterial to the design and security proof (under the falsified as sumption).\nThis suggests that whatever security the original PoSW may hav e is fragile\, and further motivates the search for a construction based o n a sound lattice-based assumption.\n\nSpecifically\, for sequentiality pa rameter $T$ and SIS parameters $n\,q\,m = n \\log q$\, the attack on the s equentiality assumption finds a solution of quasipolynomial norm $m^{\\lce il \\log T \\rceil}$ (or norm $O(\\sqrt{m})^{\\lceil \\log T \\rceil}$ wit h high probability) in only *logarithmic* ~$O_{n\,q}(\\log T)$ depth\; thi s strongly falsifies the assumption that finding such a solution requires depth *linear* in $T$.\n(The ~${O}$ notation hides polylogarithmic factors in the variables appearing in its subscript.)\nAlternatively\, the attack finds a solution of polynomial norm $m^{1/\\varepsilon}$\nin depth ~$O_{n \,q}(T^{\\varepsilon})$\, for any constant $\\varepsilon > 0$.\nSimilarly\ , the attack on the (slightly modified) PoSW constructs a valid proof in * polylogarithmic* ~${O}_{n\,q}(\\log^2 T)$ depth\, thus strongly falsifying the expectation that doing so requires linear sequential work.\n\nYi is c urrently a PhD student in CSE at University of Michigan.\nYi works on latt ice problems with Chris Peikert\, and applied cryptography with Paul Grubb s.\n\nYi got his Master's degree in CS at Courant Institute of Mathematica l Sciences\, New York University.\nDuring that time Yi worked on lattice p roblems with Oded Regev\, and applied cryptography with Yevgeniy Dodis. END:VEVENT BEGIN:VEVENT SUMMARY:A Systematic Study of Sparse LWE by Sagnik Saha DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20241014T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20241014T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202410141300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nIn this work\, we introduce the sparse LWE assumption\, an assumption that draws inspiration from both Learning with Errors (Regev J ACM 10) and Sparse Learning Parity with Noise (Alekhnovich FOCS 02). Exact ly like LWE\, this assumption posits indistinguishability of ( A\, sA+e mo d p) from (A\, u) for a random u where the secret s\, and the error vector e is generated exactly as in LWE. However\, the coefficient matrix A in s parse LPN is chosen randomly from Z^{n \\times m}_p so that each column ha s Hamming weight exactly k for some small k. We study the problem in the regime where k is a constant or polylogarithmic. The primary motivation fo r proposing this assumption is efficiency. Compared to LWE\, the samples c an be computed and stored with roughly O(n/k) factor improvement in effici ency. Our results can be summarized as:\n\nFoundations: We show several pr operties of sparse LWE samples\, including: 1) The hardness of LWE/LPN wit h dimension k implies the hardness of sparse LWE/LPN with sparsity k and a rbitrary dimension n >= k. 2) When the number of samples m=Omega(n log p) \, length of the shortest vector of a lattice spanned by rows of a random sparse matrix is large\, close to that of a random dense matrix of the sam e dimension (up to a small constant factor). 3) Trapdoors with small polyn omial norm exist for random sparse matrices with m = O(n log p) columns. 4 ) Efficient algorithms for sampling such matrices together with trapdoors exist when the number of columns\, m = Otilde(n^2).\n\nCryptanalysis: We examine the suite of algorithms that have been used to break LWE and spars e LPN. While naively many of the attacks that apply to LWE do not exploit sparsity\, we consider natural extensions that make use of sparsity. We pr opose a model to capture all these attacks. Using this model we suggest he uristics on how to identify concrete parameters. Our initial cryptanalysis suggests that concretely sparse LWE with a modest k and slightly bigger d imension than LWE will satisfy similar level of security as LWE with simil ar parameters.\n\nApplications: We show that the hardness of sparse LWE im plies very efficient homomorphic encryption schemes for low degree computa tions. We obtain the first secret key Linearly Homomorphic Encryption (LH E) schemes with slightly super-constant\, or even constant\, overhead\, wh ich further has applications to private information retrieval\, private se t intersection\, etc. We also obtain secret key homomorphic encryption fo r arbitrary constant-degree polynomials with slightly super-constant\, or constant\, overhead. \n\nWe stress that our results are preliminary. Howev er\, our results make a strong case for further investigation of sparse LW E.\n\nI'm a 2nd-year PhD Student at Carnegie Mellon University advised by Prof. Aayush Jain. Before starting my PhD\, I used to work as a software e ngineer at Google. I completed my Bachelors' and Masters' degrees from Mas sachusetts Institute of Technology in 2018 and 2019 respectively. END:VEVENT BEGIN:VEVENT SUMMARY:Flood and Submerse: Distributed Key Generation and Robust Threshol d Signature from Lattices by Guilhem Niot DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240930T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240930T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202409301300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nThreshold cryptography has recently been a very active fie ld of research\, notably following the NIST call for threshold primitives. Notable works in post-quantum cryptography built threshold signatures by relying on noise flooding [dPKM+23\,EKT24\,BKLM+24]\, and designed short a nd efficient schemes. They however left opened the questions of distributi ng the key generation\, and of making the signing process robust - i.e. gu aranteeing that a valid signature is output even in the present of malicio us parties.\nIn this talk\, I will present our novel techniques for buildi ng Distributed Key Generation and Robust Threshold Signatures. To do so\, we introduced a novel framework for constructing verifiable short secret s haring based on random submersions — that is projection over a random su bspace blinded by a small Gaussian noise. Our techniques apply to all the aforementionned work\, and we also showcased their applications to Plover [EENP+24] to build the first hash-and-sign threshold signature\, additiona lly having a DKG and robust signing procedure.\n\nI am a PhD student at PQ Shield and Univ Rennes 1 under the supervision of Thomas Prest and Pierre- Alain Fouque. I am especially interested in applied cryptography and the c onstruction of efficient primitives and protocols. My works so far include d lattice-based constructions for masking-friendly signatures\, threshold signatures\, and also secure messaging. END:VEVENT BEGIN:VEVENT SUMMARY:Threshold Raccoon: Practical Threshold Signatures from Standard La ttice Assumptions by Mary Maller DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240923T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240923T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202409231300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nThreshold signatures improve both availability and securit y of digital signatures by splitting the signing key into shares handed ou t to different parties. Later on\, any subset of at least parties can coop erate to produce a signature on a given message. While threshold signature s have been extensively studied in the pre-quantum setting\, they remain s parse from quantum-resilient assumptions.\n\nWe present the first efficien t lattice-based threshold signatures with signature size 13~KiB and commun ication cost 40~KiB per user\, supporting a threshold size as large as 102 4~signers. We provide an accompanying high performance implementation. The security of the scheme is based on the same assumptions as Dilithium\, a signature recently selected by NIST for standardisation which\, as far as we know\, cannot easily be made threshold efficiently.\n\nAll operations u sed during signing are due to symmetric primitives and simple lattice oper ations\; in particular our scheme does not need heavy tools such as thresh old fully homomorphic encryption or homomorphic trapdoor commitments as in prior constructions. The key technical idea is to use _one-time additive masks_ to mitigate the leakage of the partial signing keys through partial signatures.\n\nI am a cryptography researcher at the Ethereum Foundation and PQShield. I am generally interested in public key cryptography with a heavy focus on zero-knowledge proofs. I am also interested in threshold c ryptography. I enjoy building and analysing practical cryptographic solut ions to real world problems. END:VEVENT BEGIN:VEVENT SUMMARY:Don’t Use It Twice! Solving Relaxed Linear Code Equivalence Prob lems by Alessandro Budroni DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240624T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240624T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202406241300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nThe Linear Code Equivalence (LCE) Problem has received inc reased attention in recent years due to its applicability in constructing efficient digital signatures. Notably\, the LESS signature scheme based on LCE is under consideration for the NIST post-quantum standardization proc ess\, along with the MEDS signature scheme that relies on an extension of LCE to the rank metric\, namely Matrix Code Equivalence (MCE) Problem. Bui lding upon these developments\, a family of signatures with additional pro perties\, including linkable ring\, group\, and threshold signatures\, has been proposed. These novel constructions introduce relaxed versions of LC E (and MCE)\, wherein multiple samples share the same secret equivalence. Despite their significance\, these variations have often lacked a thorough security analysis\, being assumed to be as challenging as their original counterparts. Addressing this gap\, our work delves into the sample comple xity of LCE and MCE --- precisely\, the sufficient number of samples requi red for efficient recovery of the shared secret equivalence. Our findings reveal\, for instance\, that one shouldn't use the same secret twice in th e LCE setting since this enables a polynomial time (and memory) algorithm to retrieve the secret. Consequently\, our results unveil the insecurity o f two advanced signatures based on variants of the LCE Problem.\n\nAlessan dro Budroni is a researcher at the Technology Innovation Institute of Abu Dhabi. He defended his Ph.D. in 2022 at the University of Bergen under the supervision of Professor Igor Semaev. Before that\, he obtained a master' s degree at the University of Trento and worked as a cryptography engineer at Miracl\, London. His research interests range from cryptography with c odes and lattices to efficient algorithms for secure cryptographic impleme ntations. END:VEVENT BEGIN:VEVENT SUMMARY:Lattice-Based Functional Commitments: Constructions and Cryptanaly sis by David Wu DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240603T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240603T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202406031300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nA functional commitment allows a user to commit to an inpu t x and later open up the commitment to a value f(x) for an arbitrary func tion f. We require that the size of the commitment and the size of the ope ning be sublinear in the length of the input x. In this talk\, I first des cribe how to construct functional commitments from the recently-introduced \\ell-succint SIS assumption (this is a falsifiable q-type generalization of the classic SIS assumption). Then\, I will highlight some challenges i n constructing lattice-based extractable functional commitments (which are equivalent to succinct non-interactive arguments of knowledge) and descri be a (heuristic) attack on recently-proposed lattice-based knowledge assum ptions underlying extractable functional commitments and SNARKs.\n\nBased on joint work with Hoeteck Wee\n\nDavid Wu is an assistant professor in th e Department of Computer Science at the University of Texas at Austin. He is broadly interested in applied and theoretical cryptography as well as c omputer security. Previously\, David received a PhD in computer science fr om Stanford University in 2018 and was an assistant professor at the Unive rsity of Virginia from 2019 to 2021. He has received the NSF CAREER Award\ , the Microsoft Research Faculty Fellowship\, and a Google Research Schola r Award. His work has been recognized with a Best Paper Award at CRYPTO (2 022)\, two Best Young-Researcher Paper Awards at CRYPTO (2017\, 2018) and an Outstanding Paper Award at ESORICS (2016).\n END:VEVENT BEGIN:VEVENT SUMMARY:Abuse-Resistant Location Tracking: Balancing Privacy and Safety in the Offline Finding Ecosystem by Gabrielle Beck DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240422T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240422T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202404221300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nLocation tracking accessories (or ``tracking tags'') such as those sold by Apple\, Samsung\, and Tile\, allow owners to track the lo cation of their property via offline finding networks. The tracking protoc ols were designed to ensure that no entity (including the vendor) can use a tag's broadcasts to surveil its owner. These privacy guarantees\, howeve r\, seem to be at odds with the phenomenon of {\\em tracker-based stalkin g}\, where attackers use these very tags to monitor a target's movements. Numerous such criminal incidents have been reported\, and in response\, ma nufacturers have chosen to substantially weaken privacy guarantees in orde r to allow users to detect stalker tags. This compromise has been adopted in a recent IETF draft jointly proposed by Apple and Google. \n \n\nWe put forth the notion of {\\em abuse-resistant offline finding protocols} that aim to achieve a better balance between user privacy and stalker detectio n. We present an efficient protocol that achieves stalker detection under realistic conditions without sacrificing honest user privacy. At the heart of our result\, and of independent interest\, is a new notion of {\\em mu lti-dealer secret sharing} which strengthens standard secret sharing with novel privacy and correctness guarantees. We show that this primitive can be instantiated efficiently on edge devices using variants of Interleaved Reed-Solomon codes combined with new lattice-based decoding algorithms.\n\ nGabrielle Beck is an independent researcher and consultant who defended h er PhD at Johns Hopkins last semester. Before Hopkins\, she completed her bachelor's degree at the University of Michigan where she studied computer science. Her research interests mainly involve developing new practical c ryptographic constructions to solve the problems of everyday people with a special focus in metadata-hiding and other unconventional problem areas. Separately\, she has recently become very interested in some select topics within coding theory. END:VEVENT BEGIN:VEVENT SUMMARY:Quantum Oblivious LWE Sampling and Insecurity of Standard Model La ttice-Based SNARKs by Pouria Fallahpour DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240325T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240325T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202403251300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nThe Learning With Errors (LWE) problem asks to find s from an input of the form\n(A\, b = As + e) ∈ (Z/qZ)^{m×n} × (Z/qZ)^{m}\, for a vector e that has small-magnitude entries. In\nthis work\, we do not focus on solving LWE but on the task of sampling instances. As these are\ nextremely sparse in their range\, it may seem plausible that the only way to proceed is to first\ncreate s and e and then set b = As + e. In partic ular\, such an instance sampler knows the\nsolution. This raises the quest ion whether it is possible to obliviously sample (A\, As+e)\, namely\,\nwi thout knowing the underlying s. A variant of the assumption that oblivious LWE sampling\nis hard has been used in a series of works constructing Suc cinct Non-interactive Arguments\nof Knowledge (SNARKs) in the standard mod el. As the assumption is related to LWE\, these\nSNARKs have been conjectu red to be secure in the presence of quantum adversaries.\nOur main result is a quantum polynomial-time algorithm that samples well-distributed LWE\n instances while provably not knowing the solution\, under the assumption t hat LWE is hard.\nMoreover\, the approach works for a vast range of LWE pa rametrizations\, including those used\nin the above-mentioned SNARKs.\n\nI am a PhD student at ENS Lyon under the supervision of Prof. Damien Stehl é. I am interested in a wide range of topics in theoretical computer scie nce. I am currently working on qunatum cryptanalysis of lattice-based prim itives. END:VEVENT BEGIN:VEVENT SUMMARY:A New Sieving-Style Information-Set Decoding Algorithm by Vu Nguy en DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240311T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240311T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202403111300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nThe problem of decoding random codes is a fundamental prob lem for code-based cryptography\, including recent code-based candidates i n the NIST post-quantum standardization process.\nIn this paper\, we prese nt a novel sieving-style information-set decoding (ISD) algorithm\, addres sing the task of solving the syndrome decoding problem. Our approach invol ves maintaining a list of weight-$2p$ solution vectors to a partial syndro me decoding problem and then creating new vectors by identifying pairs of vectors that collide in $p$ positions.\nBy gradually increasing the parity -check condition by one and repeating this process iteratively\, we find t he final solution(s). We show that our novel algorithm performs better tha n other ISDs in the memory-restricted scenario when applied to McEliece. Notably\, in the case of problem instances with very low relative weight\, it seems to significantly outperform all previous algorithms. In particul ar\, for code-based candidate BIKE\, the algorithm has lower bit complexit y than the previous best results.\n\nI am Ph.D. student at Lund University . My main research interest is code-based post-quantum cryptography. I als o performed cryptanalysis on a few LPN-based post-quantum schemes (wPRF\, Firekite). END:VEVENT BEGIN:VEVENT SUMMARY:Two-Round Threshold Lattice Signatures from Threshold Homomorphic Encryption by Tjerand Silde DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240212T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240212T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202402121300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nMuch recent work has developed efficient protocols for thr eshold signatures\, where $n$ parties share a signing key and some thresho ld $t$ of those parties must interact to produce a signature. Yet efficien t threshold signatures with post-quantum security have been elusive\, with the state-of-the-art being a two-round scheme by Damgård et al. (PKC'21) based on lattices that supports only the full threshold case (i.e.\, $t=n $).\n\nWe show here a two-round threshold signature scheme based on standa rd lattice assumptions that supports arbitrary thresholds $t\\leq n$. Esti mates of our scheme's performance at the $128$-bit security level show tha t in the 3-out-of-5 case\, we obtain signatures of size $20$ KB and public keys of size $14$ KB. We achieve improved parameters if only a small numb er of signatures are ever issued with the same key.\n\nAs an essential bui lding block and independent contribution\, we construct an actively secure threshold (linearly) homomorphic encryption scheme that supports arbitrar y thresholds $t \\leq n$.\n\nThis is joint work with Kamil Doruk Gur and J onathan Katz at the University of Maryland\, and the paper is available at : https://eprint.iacr.org/2023/1318.\n\nI am an Associate Professor in Cry ptology at the Department of Information Security and Communication Techno logy at the Norwegian University of Science and Technology (NTNU) in Trond heim\, where I am the Research Group Leader of the NTNU Applied Cryptology Lab. My main foci of research are lattice-based cryptography and zero-kno wledge protocols. My interests also span the areas of post-quantum cryptog raphy\, anonymous communication\, multiparty computation\, homomorphic enc ryption\, electronic voting and secure implementation. END:VEVENT BEGIN:VEVENT SUMMARY:Finding short integer solutions when the modulus is small by Eamon n Postlethwaite DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20240129T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20240129T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202401291300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nWe present cryptanalysis of the inhomogenous short integer solution (ISIS) problem for anomalously small moduli by exploiting the ge ometry of BKZ reduced bases of q-ary lattices.\n\nWe apply this cryptanaly sis to examples from the literature where taking such small moduli has bee n suggested. A recent work [Espitau–Tibouchi–Wallet–Yu\, CRYPTO 2022 ] suggests small versions of the lattice signature scheme FALCON and its v ariant MITAKA.\n\nFor one small parametrisation of FALCON we reduce the es timated security against signature forgery by approximately 26 bits. For o ne small parametrisation of MITAKA we successfully forge a signature in se conds.\n\nWe also show that our attack applies to the ``distortion'' techn ique suggested in [Espitau–Tibouchi–Wallet–Yu\, CRYPTO 2022].\n\nI a m currently a postdoctoral researcher at Centrum Wiskunde en Informatica ( CWI) with Léo Ducas focussing on constructions from and cryptanalysis of lattice based cryptography.\nI will start as a junior lecturer at King's C ollege London in January. END:VEVENT BEGIN:VEVENT SUMMARY:On the Hardness of S|LWE> with Gaussian and Other Amplitudes by Yi lei Chen DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20231120T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20231120T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202311201300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nS|LWE> is a quantum variant of LWE where the error term is encoded in the amplitude of a quantum state. The S|LWE> problem was origi nally studied by Chen\, Liu\, Zhandry [Eurocrypt 2022]\, motivated by solv ing a variant of SIS problem. \nIn this talk I will talk about the previou s result by Chen\, Liu\, Zhandry\, as well as a recent paper on the hardne ss and algorithms for S|LWE> with Gaussian and other amplitudes. Our main results in the recent paper are\n1. There exist quantum reductions from st andard LWE or worst-case GapSVP to S|LWE> with Gaussian amplitude with unk nown phase\, and arbitrarily many samples.\n2. There is a subexponential t ime algorithm for with Gaussian amplitude with known phase\, given subexpo nentially many quantum samples. The algorithm is modified from Kuperberg's sieve\, and in fact works for more general amplitudes as long as the ampl itudes and phases are completely known.\nOne way of interpreting our new r esult is: to show a sub-exponential time quantum algorithm for standard LW E\, all we need is to handle phases in amplitudes better\, either in the a lgorithm or the reduction.\nBased on two papers\, one with Qipeng Liu\, Ma rk Zhandry (eprint: https://eprint.iacr.org/2021/1093)\, and another with Zihan Hu\, Qipeng Liu\, Han Luo\, Yaxin Tu (eprint https://eprint.iacr.org /2023/1498).\n\nYilei is an assistant professor at Tsinghua University Ins titute for Interdisciplinary Information Science (IIIS). Yilei's main rese arch interests are lattice-based cryptography and quantum computation. END:VEVENT BEGIN:VEVENT SUMMARY:New Coding-Theoretic Assumptions for Correlated Pseudorandomness G eneration by Lisa Kohl (CWI) & Nicolas Resch (UvA) . DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20231106T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20231106T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202311061300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nA fundamental concept in cryptography is pseudorandomness\ , namely the ability to efficiently generate many bits that look indisting uishable from random. For example\, if two parties can agree on a short ra ndom seed\, a pseudorandom generator allows them to later obtain long rand om strings that look essentially uniform. \n\nMotivated by concerns in sec ure multiparty computation\, a recent generalization of this primitive has been designed and studied. Namely\, from two short correlated seeds\, lon g correlated strings can be generated later\, without requiring any furthe r communication from the parties. Such objects\, termed pseudorandom corre lation generators (PCGs)\, result in some of the most efficient secure com putation protocols.\n\nIn this presentation\, we will first discuss a gene ral recipe for PCGs\, studying the important special case of the oblivious transfer (OT) correlation. We will observe that a crucial ingredient is a pseudorandom generator that has sufficient linear structure\; i.e.\, a ps eudorandom generator derived from a “learning parity with noise”-type assumption. In the second half of the talk\, we will discuss new coding-th eoretic assumptions which have been proposed to design highly-efficient PC Gs. As a particular highlight\, we will discuss a PCG requiring only linea r time to expand short seeds into many OT instances. \n\nBased on joint wo rks with Elette Boyle\, Geoffroy Couteau\, Niv Gilboa\, Yuval Ishai\, and Peter Scholl.\n\nLisa Kohl is a senior researcher with the CWI Cryptology Group in Amsterdam. A special focus of her research work lies in exploring new directions for secure computation\, with the goal of developing pract ical post-quantum secure protocols. Website: lisakohl.me\n\nNicolas Resch is an assistant professor with the Theoretical Computer Science Group from the Informatics Institute of the University of Amsterdam. His research fo cusses on error-correcting codes and cryptography and (naturally) their in tersection. Website: nicolas-resch.caard.co END:VEVENT BEGIN:VEVENT SUMMARY:Applications of relation lattices\, and open questions by Steven G albraith DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20231023T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20231023T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202310231300@https://jcs.trusted-third-party.org/ DESCRIPTION:Also: Bush House (SE) 1.06\n\nLet $G$ be a finite abelian grou p and let $g_1\,...\,g_n \\in G$. Define the relation lattice $L = \\{ (x_ 1\,...\,x_n) \\in Z^n : \\sum_{i=1}^n x_i g_i = 0 \\}$. Ducas and Pierrot (Designs\, Codes and Cryptography\, 2019) showed how relation lattices can provide families of dense lattices with a polynomial-time bounded distanc e decoding algorithm. Li\, Ling\, Xing and Yeo (IEEE Transactions on Infor mation Theory 2020) proposed using a relation lattice for a version of the McEliece code-based post-quantum encryption scheme. I will survey these r esults and discuss some improvements to the cryptosystem of Li\, Ling\, Xi ng and Yeo.\n\nProfessor Galbraith is a researcher in mathematics of publi c key cryptography at the University of Auckland in New Zealand. He has he ld positions at Royal Holloway\, Bristol\, Institute of Experimental Mathe matics (Essen)\, and Waterloo. END:VEVENT BEGIN:VEVENT SUMMARY:Doubly Efficient Private Information Retrieval and Fully Homomorph ic RAM Computation from Ring LWE by Wei-Kai Lin DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20231009T150000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20231009T160000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202310091500@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nCan we design a private variant of "Google search" that wo uld enable users to search the Internet privately without revealing their queries to Google? Fully homomorphic encryption gives a solution to this p roblem\, where users would send their search queries to Google encrypted i n a way that allows Google to compute the encrypted search results\, witho ut learning anything about the query itself. However\, this solution would require Google to run a huge computation that touches the entire content of the Internet to answer each encrypted search query\, making it realisti cally infeasible! Is there a way for Google to preprocess the Internet con tent into a special data structure that would allow it to answer any encry pted query efficiently by only accessing some small number of locations in the data structure? We give a solution to this problem as a special case of our work.\n\nConcretely\, we construct the first schemes for "doubly ef ficient private information retrieval" and "fully homomorphic encryption i n the RAM model" under standard cryptographic hardness assumptions (Ring L earning with Errors). Previously we only had heuristic candidate construct ions that only satisfied relaxed variants of these primitives. Our new sol utions combine tools from cryptography together with data structures for f ast polynomial evaluation (Kedlaya and Umans '08).\n\nJoint work with Etha n Mook and Daniel Wichs.\n\nI am an assistant professor in the Computer Sc ience Department at University of Virginia. Earlier\, I was a postdoctoral researcher at Northeastern University\, advised by Professor Daniel Wichs . I got my Ph.D. in Computer Science at Cornell and then worked as a postd oc at CMU\, both advised by Professor Elaine Shi. Prior to that\, I got my B.S. and M.S. degrees from National Taiwan University\, and then I was a software engineer. END:VEVENT BEGIN:VEVENT SUMMARY:Efficient Laconic Cryptography from Learning With Errors by Russel l W. F. Lai DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20230626T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20230626T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202306261300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nLaconic cryptography is an emerging paradigm that enables cryptographic primitives with sublinear communication complexity in just t wo messages. In particular\, a two-message protocol between Alice and Bob is called laconic if its communication and computation complexity are esse ntially independent of the size of Alice's input. This can be thought of a s a dual notion of fully-homomorphic encryption\, as it enables "Bob-optim ized" protocols. This paradigm has led to tremendous progress in recent ye ars. However\, all existing constructions of laconic primitives are consid ered only of theoretical interest: They all rely on non-black-box cryptogr aphic techniques\, which are highly impractical.\n\nThis work shows that n on-black-box techniques are not necessary for basic laconic cryptography p rimitives. We propose a completely algebraic construction of laconic encry ption\, a notion that we introduce in this work\, which serves as the corn erstone of our framework. We prove that the scheme is secure under the sta ndard Learning With Errors assumption (with polynomial modulus-to-noise ra tio). We provide proof-of-concept implementations for the first time for l aconic primitives\, demonstrating the construction is indeed practical: Fo r a database size of \n\, encryption and decryption are in the order of si ngle digit milliseconds.\n\nLaconic encryption can be used as a black box to construct other laconic primitives. Specifically\, we show how to const ruct:\n\n- Laconic oblivious transfer\n- Registration-based encryption sch eme \n- Laconic private-set intersection protocol\n\nAll of the above have essentially optimal parameters and similar practical efficiency. Furtherm ore\, our laconic encryption can be preprocessed such that the online encr yption step is entirely combinatorial and therefore much more efficient. U sing similar techniques\, we also obtain identity-based encryption with an unbounded identity space and tight security proof (in the standard model) .\n\nRussell W. F. Lai is an Assistant Professor at the Department of Comp uter Science of Aalto University since 2022. He works on a range of topics in cryptography including lattice-based cryptography\, succinct arguments \, and anonymous systems. He obtained his PhD degree from Friedrich-Alexan der University Erlangen-Nuremberg in 2022. END:VEVENT BEGIN:VEVENT SUMMARY:On Structure-Preserving Cryptography and Lattices by Dennis Hofhei nz DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20230612T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20230612T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202306121300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nThe Groth-Sahai proof system is a highly efficient pairing -based proof system for a specific class of group-based languages. Cryptog raphic primitives that are compatible with these languages (such that we c an express\, e.g.\, that a ciphertext contains a valid signature for a giv en message) are called “structure-preserving”. The combination of stru cture-preserving primitives with Groth-Sahai proofs allows to prove comple x statements that involve encryptions and signatures\, and has proved usef ul in a variety of applications. However\, so far\, the concept of structu re-preserving cryptography has been confined to the pairing setting.\n\nIn this talk\, I will outline a strategy for structure-preserving cryptograp hy from lattices. At the heart of this framework lies a lattice-based argu ment system for “noisy” languages (formalized as “structure-preservi ng sets”)\, and the observation that this proof system is compatible wit h a number of existing lattice-based primitives. We demonstrate the useful ness of our framework with a lattice-based construction of verifiably encr ypted signatures. As a secondary contribution\, we present a more efficien t variant of Rückert's signature scheme. I should note that (like in the group-based setting of structure-preserving cryptography)\, all our constr uctions are in the standard model.\n\n\nBefore joining ETH Zurich's CS dep artment in 2020\, I used to work at the Karlsruhe Institute of Technology in Germany\, and before that at the Centrum Wiskunde en Informatica in Ams terdam\, the Netherlands. I work on the foundations of cryptography\, and in particular on the design and analysis of cryptographic building blocks (such as public-key encryption and signatures). END:VEVENT BEGIN:VEVENT SUMMARY:Witness Encryption\, Null IO\, and Evasive LWE by Hoeteck Wee DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20230515T150000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20230515T160000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202305151500@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nI will present our work on witness encryption and null IO\ , as well as some musings on the evasive LWE assumption (in particular\, r elation to prior zeroizing attacks on IO). Based on joint works with Vinod Vaikuntanathan\, Daniel Wichs\, and David Wu.\n\nHoeteck is a senior scie ntist at NTT Research\, currently on leave from CNRS and ENS\, Paris. END:VEVENT BEGIN:VEVENT SUMMARY:Fast Practical Lattice Reduction through Iterated Compression by K eegan Ryan DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20230417T160000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20230417T170000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202304171600@https://jcs.trusted-third-party.org/ DESCRIPTION:Note the changed time.\n\nWe introduce a new lattice basis red uction algorithm with approximation guarantees analogous to the LLL algori thm and practical performance that far exceeds the current state of the ar t. We achieve these results by iteratively applying precision management t echniques within a recursive algorithm structure and show the stability of this approach. We analyze the asymptotic behavior of our algorithm\, and show that the heuristic running time is $O(n^{\\omega}(C+n)^{1+\\varepsilo n})$ for lattices of dimension $n$\, $\\omega\\in (2\,3]$ bounding the cos t of size reduction\, matrix multiplication\, and QR factorization\, and $ C$ bounding the log of the condition number of the input basis $B$. This y ields a running time of $O\\left(n^\\omega (p + n)^{1 + \\varepsilon}\\rig ht)$ for precision $p = O(\\log \\|B\\|_{max})$ in common applications. Ou r algorithm is fully practical\, and we have published our implementation. We experimentally validate our heuristic\, give extensive benchmarks agai nst numerous classes of cryptographic lattices\, and show that our algorit hm significantly outperforms existing implementations.\n\nKeegan Ryan is a 4th year PhD student advised by Prof. Nadia Heninger at the University of California\, San Diego. His research interests include practical cryptana lysis of real-world systems\, particularly problems involving lattice redu ction. END:VEVENT BEGIN:VEVENT SUMMARY:Private Re-Randomization for Module LWE and Applications to Quasi- Optimal ZK-SNARKs by Ron Steinfeld DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20230417T090000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20230417T100000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202304170900@https://jcs.trusted-third-party.org/ DESCRIPTION:Note the changed time.\n\nWe introduce the first candidate lat tice-based Designated Verifier (DV) ZK-SNARK protocol with \\emph{quasi-op timal proof length} (quasi-linear in the security/privacy parameter)\, avo iding the use of the exponential smudging technique. Our ZK-SNARK also ach ieves significant improvements in proof length in practice\, with proofs l ength below 6 KB for 128-bit security/privacy level. \nOur main technical result is a new regularity theorem for `private' re-randomization of Modul e LWE (MLWE) samples using discrete Gaussian randomization vectors\, also known as a lattice-based leftover hash lemma with leakage\, which applies with a discrete Gaussian re-randomization parameter that is polynomial in the statistical privacy parameter. \nTo obtain this result\, we obtain bou nds on the smoothing parameter of an intersection of a random q-ary SIS mo dule lattice\, Gadget SIS module lattice\, and Gaussian orthogonal module lattice over standard power of 2 cyclotomic rings\, and a bound on the min imum of module gadget lattices. We then introduce a new candidate \\emph{l inear-only} homomorphic encryption scheme called Module Half-GSW (HGSW)\, which is a variant of the GSW somewhat homomorphic encryption scheme over modules\, and apply our regularity theorem to provide smudging-free circui t-private homomorphic linear operations for Module HGSW.\n\nRon Steinfeld is an Associate Professor at Monash University. His research focuses on po st-quantum cryptography and its applications. He obtained his Ph.D. degree in cryptography at Monash University in 2003. He was a postdoctoral ARC R esearch Fellow at Macquarie University. He joined Monash University in 201 2. END:VEVENT BEGIN:VEVENT SUMMARY:Circuit Privacy for FHEW/TFHE-Style Fully Homomorphic Encryption i n Practice by Kamil Kluczniak DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20230306T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20230306T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202303061300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nA fully homomorphic encryption (FHE) scheme allows a clien t to encrypt and delegate its data to a server that performs computation o n the encrypted data that the client can then decrypt. While FHE gives con fidentiality to clients' data\, it does not protect the server's input and computation. Nevertheless\, FHE schemes are still helpful in building del egation protocols that reduce communication complexity\, as the ciphertext 's size is independent of the size of the computation performed on them. \ n\nWe can further extend FHE by a property called circuit privacy\, which guarantees that the result of computing on ciphertexts reveals no informat ion on the computed function and the inputs of the server. Thereby\, circu it private FHE gives rise to round optimal and communication efficient sec ure two-party computation protocols. Unfortunately\, despite significant e fforts and much work put into the efficiency and practical implementations of FHE schemes\, very little has been done to provide useful and practica l FHE supporting circuit privacy. In this work\, we address this gap and d esign the first randomized bootstrapping algorithm whose single invocation sanitizes a ciphertext and\, consequently\, serves as a tool to provide c ircuit privacy. We give an extensive analysis\, propose parameters\, and p rovide a C++ implementation of our scheme. Our bootstrapping can sanitize a ciphertext to achieve circuit privacy at an 80-bit statistical security level in 1.2 or 1.4 seconds\, depending on whether the parameter set targe ts a fast Fourier or a number theoretic transform-based implementation. In addition\, we can perform non-sanitized bootstrapping in around 0.27 or 0 .14 seconds on a laptop where the additional sanitization key takes less t han $0.5$ MB of memory. Crucially\, we do not need to increase the paramet ers to perform computation before or after sanitization takes place. For c omparison's sake\, we revisit the Ducas-Stehl\\'e washing machine method. In particular\, we give a tight analysis\, estimate efficiency\, review ol d\, and provide new parameters. \n\nKamil Kluczniak is currently a Researc h Group Leader at CISPA Helmholtz Center for Information Security. His wor k focuses on efficient fully homomorphic encryption schemes. He obtained his Ph.D. degree in cryptography from the Polish Academy of Sciences in 20 16. In 2017 he worked as a postdoctoral researcher at the Hong Kong Polyt echnique University. In 2018 he joined the CISPA-Stanford Center\, and fro m 2019-2021 he was a visiting assistant professor at Stanford University.\ n END:VEVENT BEGIN:VEVENT SUMMARY:Quantum Rewinding for Many-Round Protocols by Nick Spooner DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20230220T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20230220T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202302201300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nWe investigate the security of succinct arguments against quantum adversaries. Our main result is a proof of knowledge-soundness in the post-quantum setting for a class of multi-round interactive protocols\ , including those based on the recursive folding technique of Bulletproofs .\n\nTo prove this result\, we devise a new quantum rewinding strategy\, t he first that allows for rewinding across many rounds. This technique appl ies to any protocol satisfying natural multi-round generalizations of spec ial soundness and collapsing. For our main result\, we show that recent Bu lletproofs-like protocols based on lattices satisfy these properties\, and are hence sound against quantum adversaries.\n\nNick Spooner is an Assist ant Professor of Computer Science at the University of Warwick. His work f ocuses on post-quantum proof systems. His interests include interactive pr oof systems and zero knowledge in general\, post-quantum cryptography\, qu antum information\, coding theory and computational complexity. Previously he was a postdoc at Boston University\, and he received his PhD from UC B erkeley in 2020. END:VEVENT BEGIN:VEVENT SUMMARY:Post-Quantum Insecurity from LWE by Willy Quach DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20230109T150000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20230109T160000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202301091500@https://jcs.trusted-third-party.org/ DESCRIPTION:Note the changed time.\n\nWe show that for many fundamental cr yptographic primitives\, proving classical security under the learning-wit h-errors (LWE) assumption\, does \\emph{not} imply post-quantum security. This is despite the fact that LWE is widely believed to be post-quantum se cure\, and our work does not give any evidence otherwise. Instead\, it sho ws that post-quantum insecurity can arise inside cryptographic constructio ns\, even if the assumptions are post-quantum secure. \n\nConcretely\, our work provides (contrived) constructions of pseudorandom functions\, CPA-s ecure symmetric-key encryption\, message-authentication codes\, signatures \, and CCA-secure public-key encryption schemes\, all of which are proven to be classically secure under LWE via black-box reductions\, but demonstr ably fail to be post-quantum secure. All of these cryptosystems are statel ess and non-interactive\, but their security is defined via an interactive game that allows the attacker to make oracle queries to the cryptosystem. The polynomial-time quantum attacker can break these schemes by only makin g a few \\emph{classical} queries to the cryptosystem\, and in some cases\ , a single query suffices. \n\nPreviously\, we only had examples of post-q uantum insecurity under post-quantum assumptions for stateful/interactive protocols. Moreover\, there appears to be a folklore belief that for state less/non-interactive cryptosystems with black-box proofs of security\, a q uantum attack against the scheme should translate into a quantum attack on the assumption. This work shows otherwise. Our main technique is to caref ully embed interactive protocols inside the interactive security games of the above primitives.\n\nAs a result of independent interest\, we also sho w a 3-round \\emph{quantum disclosure of secrets (QDS)} protocol between a classical sender and a receiver\, where a quantum receiver learns a secre t message in the third round but\, assuming LWE\, a classical receiver doe s not.\n\nJoint work with Alex Lombardi\, Ethan Mook\, and Daniel Wichs. E print: https://eprint.iacr.org/2022/869\n\nWilly Quach is a 6th year PhD s tudent at Northeastern University advised by Daniel Wichs. END:VEVENT BEGIN:VEVENT SUMMARY:How to Sample a Discrete Gaussian (and more) from a Random Oracle by George Lu DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20221128T150000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20221128T160000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202211281500@https://jcs.trusted-third-party.org/ DESCRIPTION:Note the changed time.\n\nThe random oracle methodology is cen tral to the design of many practical\ncryptosystems. A common challenge f aced in several systems is the need to have\na random oracle that outputs from a structured distribution $\\mathcal{D}$\, even though most \nheurist ic implementations such as SHA-3 are best suited for outputting bitstrings . \n\n\nOur work explores the problem of sampling from discrete Gaussian ( and related) distributions \nin a manner that they can be programmed into random oracles. We make the following contributions:\n\n-We provide a defi nitional framework for our results. We say that a sampling algorithm $\\ma thsf{Sample}$ for \na distribution is explainable if there exists an algor ithm $\\mathsf{Explain}$ where\, for a $x$ in the domain\, we have that\n$ \\mathsf{Explain}(x) \\rightarrow r \\in \\{0\,1\\}^n$ such that $\\mathsf {Sample}(r)=x$. Moreover\, if $x$ is sampled from $\\mathcal{D}$ the expla ined \ndistribution is statistically close to choosing $r$ uniformly at ra ndom. We consider a variant of this definition\nthat allows the statistica l closeness to be a "precision parameter'' given to the $\\mathsf{Explain} $ algorithm. We show that sampling algorithms which satisfy our `explainab ility' property can be programmed as a random oracle.\n\n-We provide a sim ple algorithm for explaining \\emph{any} sampling algorithm that works\nov er distributions with polynomial sized ranges.\nThis includes discrete Gau ssians with small standard deviations. \n\n-We show how to transform a (no t necessarily explainable) sampling algorithm $\\mathsf{Sample}$ for a dis tribution\ninto a new $\\mathsf{Sample}'$ that is explainable. The require ments for doing this is that (1) the probability density function\nis effi ciently computable (2) it is possible to efficiently uniformly sample from all elements that have a probability density\nabove a given threshold $p$ \, showing the equivalence of random oracles to these distributions and ra ndom oracles to uniform bitstrings. \nThis includes a large class of distr ibutions\, including all discrete Gaussians.\n\n-A potential drawback of t he previous approach is that the transformation requires an additional\nco mputation of the density function. We provide a more customized approach t hat shows the Miccancio-Walter\ndiscrete Gaussian sampler is explainable a s is. This suggests that other discrete Gaussian samplers\nin a similar ve in might also be explainable as is.\n\nGeorge is a fourth year PhD student at UT Austin advised by Dr. Brent Waters. END:VEVENT BEGIN:VEVENT SUMMARY:Syndrome Decoding in the Head: Shorter Signatures from Zero-Knowle dge Proofs by Thibauld Feneuil DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20221114T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20221114T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202211141300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nIn this talk\, I will present a new zero-knowledge proof o f knowledge for the syndrome decoding (SD) problem on random linear codes. Instead of using permutations like most of the existing protocols\, we re ly on the MPC-in-the-head paradigm in which we reduce the task of proving the low Hamming weight of the SD solution to proving some relations betwee n specific polynomials. Specifically\, we propose a 5-round zero-knowledge protocol that proves the knowledge of a vector x such that $y=Hx$ and $wt (x)\\leq w$ and which achieves a soundness error close to $1/N$ for an arb itrary $N$.\n\nWhile turning this protocol into a signature scheme\, we ac hieve a signature size of 11-12 KB for 128-bit security when relying on th e hardness of the SD problem on binary fields. Using larger fields (like $ \\mathbb{F}_{256}$)\, we can produce fast signatures of around 8 KB. This allows us to outperform Picnic3 and be competitive with $\\text{SPHINCS}^{ +}$. Since the security relies on the hardness of the syndrome decoding pr oblem for random linear codes which is known to be NP-hard and for which t he cryptanalysis state of the art has been stable for many years\, it resu lts in a conservative signature scheme. Moreover\, our scheme outperforms all the former code-based signature schemes for the common “signature si ze + public key size” metric.\n\nJoint work with [Antoine Joux](https:// cispa.de/en/people/c01anjo) and [Matthieu Rivain](https://www.matthieuriva in.com/).\n\nThibauld Feneuil is a PhD student at CryptoExperts & Sorbonne University (France). He is working on zero-knowledge proofs in post-quant um cryptography. END:VEVENT BEGIN:VEVENT SUMMARY:Some Easy Instances of Ideal-SVP and Implications on the Partial V andermonde Knapsack Problem by Katharina Boudgoust DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20221017T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20221017T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202210171300@https://jcs.trusted-third-party.org/ DESCRIPTION:This will be a hybrid seminar. The speaker will be giving the talk from ENS de Lyon. \n\nThis talk focuses on the shortest vector proble m over so-called ideal lattices. Whereas it is believed to be hard in the worst-case\, prior works have shown that there are several specific cases\ , where the problem becomes easy to solve. We continue this line of work a nd provide a simple condition under which an ideal lattice defines an easy instance of the shortest vector problem. Namely\, we show that the more a utomorphisms stabilize the ideal\, the easier it is to find a short vector in it. This observation was already made for prime ideals in Galois field s\, and we extend it to any ideal (whose prime factors are not ramified) o f any number field\, generalizing the works of Pan et al. (Eurocrypt'21) a nd Porter et al. (ArXiv'21). We then provide a cryptographic application o f this result by showing that particular instances of the partial Vandermo nde knapsack problem\, also known as partial Fourier recovery problem\, ca n be solved classically in polynomial time. As a proof of concept\, we imp lemented our attack and managed to solve those particular instances for co ncrete parameter settings proposed in the literature. For random instances \, we can halve the lattice dimension with non-negligible probability. We conclude the presentation by clarifying the impacts of our results to latt ice-based cryptography.\nThis is a joint work with Erell Gachon and Alice Pellet-Mary.\n\n\nKatharina Boudgoust is a postdoctoral researcher in the Cryptography and Security team of the Aarhus University\, Denmark\, under the supervision of Peter Scholl. She is interested in lattice-based crypto graphy\, and more specifically in the computational hardness assumptions u nderlying lattice-based cryptosystems and threshold cryptography. From Sep tember 2018 to November 2021\, Katharina was a PhD student with the EMSEC team at IRISA Laboratory in Rennes\, France\, under the supervision of Ade line Roux-Langlois and Pierre-Alain Fouque. Her PhD thesis focused on the theoretical hardness of algebraically structured Learning With Errors.\n END:VEVENT BEGIN:VEVENT SUMMARY:On Codes and Learning With Errors over Function Fields by Maxime B ombar DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20221003T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20221003T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202210031300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nIt is a long standing open problem in code-based cryptogra phy to find search to decision reductions for _structured_ versions of the decoding problem (_e.g. for quasi-cyclic codes_). Such results in the lat tice-based setting have been carried out using number fields: Polynomial-L WE\, Ring-LWE\, Module-LWE ...\n\nIn this talk\, I will present a function field analogue of the LWE problem. This new framework leads to another po int of view on structured codes\, strengthening the connections between la ttice-based and code-based cryptography.\n\nThis framework can be instanti ated with function field analogues of the cyclotomic number fields\, namel y _Carlitz_ extensions\, leading to the first search to decision reduction s on various structured versions of the decoding problem\, and Ring-LPN\, which have applications to secure multi party computation. and to an authe ntication protocol.\n\nThis is a joint work with Alain Couvreur and Thomas Debris-Alazard.\n\n\nMaxime is a PhD student at LIX (Laboratoire d'Inform atique de l'École Polytechnique) & Inria\, France. He is interested in th e hardness of various problems related to algebraically structured codes ( either in the Hamming or the rank metric). END:VEVENT BEGIN:VEVENT SUMMARY:Lattice-Based Zero-Knowledge Proofs and Applications: Shorter\, Si mpler\, and More General by Ngoc Khanh Nguyen DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220711T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220711T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202207111300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nWe present a much-improved practical protocol\, based on t he hardness of Module-SIS and Module-LWE problems\, for proving knowledge of a short vector s satisfying As = t mod q. The currently most-efficient technique for constructing such a proof works by showing that the L_\\inft y norm of sis small using CRT slots technique (Esgin et al.\, Asiacrypt 20 20). In this work\, we show that there is a more direct and more efficient way to prove that s has a small L_2 norm which does not require an equivo cation with the L_\\infty norm\, nor any conversion to the CRT representat ion. We observe that the inner product between two vectors r and s can be made to appear as a coefficient of a product (or sum of products) between polynomials with coefficient vectors r and s. Thus\, by using a polynomial product proof system and hiding all but one coefficient\, we can prove kn owledge of the inner product of two vectors (or of a vector with itself) m odulo q. Using a cheap\, "approximate range proof"\, one can then lift the proof to be over Z instead of Zq. Our protocols for proving short norms w ork over all (interesting) polynomial rings but are particularly efficient for rings like Z[X]/(X^n+1) in which the function relating the inner prod uct of vectors and polynomial products happens to be a "nice" automorphism .\n\nThe new proof system can be plugged into constructions of various lat tice-based privacy primitives in a black-box manner. As examples\, we ins tantiate a verifiable encryption scheme and a group signature scheme which are more than twice as compact as the previously best solutions.\n\nNgoc Khanh Nguyen is a fourth-year PhD student at IBM Research Europe - Zurich and ETH Zurich\, Switzerland\, supervised by Dr Vadim Lyubashevsky and Pro f. Dennis Hofheinz. Previously\, Khanh obtained his B.Sc. and M.Eng. degre es in Mathematics and Computer Science at the University of Bristol\, UK.\ n END:VEVENT BEGIN:VEVENT SUMMARY:Anonymity of NIST PQC Round-3 KEMs by Keita Xagawa DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220627T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220627T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202206271300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nThis paper investigates __anonymity__ of all NIST PQC Roun d~3 KEMs: Classic McEliece\, Kyber\, NTRU\, Saber\, BIKE\, FrodoKEM\, HQC\ , NTRU Prime (Streamlined NTRU Prime and NTRU LPRime)\, and SIKE. \n\nWe s how the following results: \n\n* NTRU is anonymous in the quantum random o racle model (QROM) if the underlying deterministic PKE is strongly disjoin t-simulatable. NTRU is collision-free in the QROM. A hybrid PKE scheme con structed from NTRU as KEM and appropriate DEM is anonymous and robust. (Si milar results for BIKE\, FrodoKEM\, HQC\, NTRU LPRime\, and SIKE hold exce pt for one of three parameter sets of HQC.)\n* Classic McEliece is anonymo us in the QROM if the underlying PKE is strongly disjoint-simulatable and a hybrid PKE scheme constructed from it as KEM and appropriate DEM is anon ymous.\n* Grubbs\, Maram\, and Paterson pointed out that Kyber and Saber h ave a gap in the current IND-CCA security proof in the QROM (EUROCRYPT 202 2). \n\nWe found that Streamlined NTRU Prime has another technical obstac le for the IND-CCA security proof in the QROM. \n\nThose answer the open p roblem to investigate the anonymity and robustness of NIST PQC Round~3 KEM s posed by Grubbs\, Maram\, and Paterson (EUROCRYPT 2022). \nWe use strong disjoint-simulatability of the underlying PKE of KEM and strong pseudoran domness and smoothness/sparseness of KEM as the main tools\, which will be of independent interest.\n\nThe full paper is available at https://eprint .iacr.org/2021/1323\n\nKeita Xagawa received his B.S. degree from Kyoto Un iversity and M.S. and D.S. degrees from Tokyo Institute of Technology in 2 005\, 2007\, and 2010\, respectively. He joined NTT Corporation in 2010.\n END:VEVENT BEGIN:VEVENT SUMMARY:Rigorous computation of class group and unit group by Alice Pellet -Mary DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220613T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220613T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202206131300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nComputing the class group and the unit group of a number f ield is an important problem of algorithmic number theory. Recently\, it h as also become an important problem in cryptography\, since it is used in multiple algorithms solving the shortest vector problem in ideal lattices. \n\nSubexponential algorithms (in the discriminant of the number field) ar e known to solve this problem in any number fields\, but they heavily rely on heuristics. The only non-heuristic known algorithm\, due to Hafner and McCurley\, is restricted to imaginary quadratic number fields.\n\nIn this talk\, I will present a rigorous subexponential algorithm computing units and class group (and more generally T-units) in any number field\, assumi ng the extended Riemann hypothesis.\n\nThis is a joint work with Koen de B oer and Benjamin Wesolowski.\n\nAlice is a CNRS researcher (chargée de re cherche) at the university of Bordeaux. She is part of the Institut de Mat hématiques de Bordeaux (IMB) and of the Lfant inria team. She is interest ed in lattice based cryptography\, and more specifically in the hardness o f algorithmic problems related to algebraically structured lattices. END:VEVENT BEGIN:VEVENT SUMMARY:Anonymous\, Robust Post-Quantum Public Key Encryption by Varun Mar am DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220516T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220516T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202205161300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nA core goal of the NIST PQC competition is to produce publ ic-key encryption (PKE) schemes which\, even if attacked with a large-scal e quantum computer\, maintain the security guarantees needed by applicatio ns. The main security focus in the NIST PQC context has been IND-CCA secur ity\, but other applications demand that PKE schemes provide *anonymity* ( Bellare et al.\, ASIACRYPT 2001)\, and *robustness* (Abdalla et al.\, TCC 2010). Examples of such applications include anonymous communication syste ms\, cryptocurrencies\, anonymous credentials\, searchable encryption\, an d auction protocols. Almost nothing is known about how to build post-quant um PKE schemes offering these security properties. In particular\, the sta tus of the NIST PQC candidates with respect to anonymity and robustness is unknown. \n\nIn this work\, we initiate a systematic study of anonymity a nd robustness for post-quantum PKE schemes. Firstly\, we identify implicit rejection as a crucial design choice shared by most post-quantum KEMs\, s how that implicit rejection renders prior results on anonymity and robustn ess for KEM-DEM PKEs inapplicable\, and transfer prior results to the impl icit-rejection setting where possible. Secondly\, since they are widely us ed to build post-quantum PKEs\, we examine how the Fujisaki-Okamoto (FO) t ransforms (Fujisaki and Okamoto\, Journal of Cryptology 2013) confer robus tness and enhance weak anonymity of a base PKE. \n\nWe then leverage our t heoretical results to study the anonymity and robustness of three NIST KEM finalists---Saber\, Kyber\, and Classic McEliece---and one alternate\, Fr odoKEM. Overall\, our findings for robustness are definitive: we provide p ositive robustness results for Saber\, Kyber\, and FrodoKEM\, and a negati ve result for Classic McEliece. Our negative result stems from a striking property of KEM-DEM PKE schemes built with the Classic McEliece KEM: for a ny message $m$\, we can construct a single hybrid ciphertext $c$ which dec rypts to the chosen $m$ under *any* Classic McEliece private key.\n\nOur f indings for anonymity are more mixed: we identify barriers to proving anon ymity for Saber\, Kyber\, and Classic McEliece. We also found that in the case of Saber and Kyber\, these barriers lead to issues with their IND-CCA security claims. We have worked with the Saber and Kyber teams to fix the se issues\, but they remain unresolved. On the positive side\, we were abl e to prove anonymity for FrodoKEM and a variant of Saber introduced by D'A nvers et al. (AFRICACRYPT 2018). Our analyses of these two schemes also id entified technical gaps in their IND-CCA security claims\, but we were abl e to fix them.\n\nThis is a joint work with Paul Grubbs (University of Mic higan) and Kenneth G. Paterson (ETH Zurich). \n\n\nVarun Maram is a third- year PhD student in the Applied Cryptography group at ETH Zurich\, supervi sed by Prof. Kenny Paterson. His current research interests lie in the are a of post-quantum cryptography\, both in the asymmetric and symmetric sett ings. Varun is also one of the primary submitters of "Classic McEliece"\, a finalist algorithm for PKE and key-establishment in the NIST PQC standar dization process. END:VEVENT BEGIN:VEVENT SUMMARY:Non-Interactive Zero Knowledge from Sub-exponential DDH by Zhengzh ong Jin DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220502T153000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220502T163000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202205021530@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nWe provide the first constructions of non-interactive zero -knowledge and Zap arguments for NP based on the sub-exponential hardness of Decisional Diffie-Hellman against polynomial time adversaries (without use of groups with pairings).\n\nCentral to our results\, and of independe nt interest\, is a new notion of interactive trapdoor hashing protocols.\n \n\nI have a broad interest in Theoretical Computer Science. Currently\, I am working on Cryptography and Coding Theory. I am a fifth year Ph.D. stu dent at Johns Hopkins University\, fortunately co-advised by Abhishek Jain and Xin Li. \n END:VEVENT BEGIN:VEVENT SUMMARY:Public-Key Encryption from Continuous LWE by Charlotte Hoffmann DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220404T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220404T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202204041300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nThe continuous learning with errors (CLWE) problem was rec ently introduced by Bruna et al. (STOC 2021). They showed that its hardnes s implies infeasibility of learning Gaussian mixture models\, while its tr actability implies efficient Discrete Gaussian Sampling and thus asymptoti c improvements in worst-case lattice algorithms. No reduction between CLWE and LWE is currently known\, in either direction. \n\nWe propose four pub lic-key encryption schemes based on the hardness of CLWE\, with varying tr adeoffs between decryption and security errors\, and different discretizat ion techniques. Some of our schemes are based on hCLWE\, a homogeneous var iant\, which is no easier than CLWE. Our schemes yield a polynomial-time a lgorithm for solving hCLWE\, and hence also CLWE\, using a Statistical Zer o-Knowledge oracle.\n\nThis is joint work with Andrej Bogdanov\, Miguel Cu eto Noval and Alon Rosen. E-print: https://eprint.iacr.org/2022/093\n\n\nC harlotte is a PhD student in the Cryptography group at IST Austria under t he supervision of Krzysztof Pietrzak. END:VEVENT BEGIN:VEVENT SUMMARY:Classical vs Quantum Random Oracles by Takashi Yamakawa DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220307T103000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220307T113000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202203071030@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nIn this paper\, we study relationship between security of cryptographic schemes in the random oracle model (ROM) and quantum random oracle model (QROM). First\, we introduce a notion of a proof of quantum a ccess to a random oracle (PoQRO)\, which is a protocol to prove the capabi lity to quantumly access a random oracle to a classical verifier. We obser ve that a proof of quantumness recently proposed by Brakerski et al. (TQC '20) can be seen as a PoQRO. We also give a construction of a publicly ver ifiable PoQRO relative to a classical oracle. Based on them\, we construct digital signature and public key encryption schemes that are secure in th e ROM but insecure in the QROM. In particular\, we obtain the first exampl es of natural cryptographic schemes that separate the ROM and QROM under a standard cryptographic assumption. \n\nOn the other hand\, we give liftin g theorems from security in the ROM to that in the QROM for certain types of cryptographic schemes and security notions. For example\, our lifting t heorems are applicable to Fiat-Shamir non-interactive arguments\, Fiat-Sha mir signatures\, and Full-Domain-Hash signatures etc. We also discuss appl ications of our lifting theorems to quantum query complexity.\n\n\nTakashi Yamakawa is a researcher at NTT in Japan. He earned his PhD in Science fr om The University of Tokyo in 2017.His research focuses on post-quantum an d quantum cryptography. END:VEVENT BEGIN:VEVENT SUMMARY:On the Lattice Isomorphism Problem\, Quadratic Forms\, Remarkable Lattices\, and Cryptography by Wessel van Woerden DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220207T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220207T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202202071300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nA natural and recurring idea in the knapsack/lattice crypt ography literature is to start from a lattice with remarkable decoding cap ability as your private key\, and hide it somehow to make a public key. Th is is also how the code-based encryption scheme of McEliece (1978) proceed s.\n\nThis idea has never worked out very well for lattices: ad-hoc approa ches have been proposed\, but they have been subject to ad-hoc attacks\, u sing tricks beyond lattice reduction algorithms. On the other hand the fra mework offered by the Short Integer Solution (SIS) and Learning With Error s (LWE) problems\, while convenient and well founded\, remains frustrating from a coding perspective: the underlying decoding algorithms are rather trivial\, with poor decoding performance.\n\nIn this work\, we provide gen eric realisations of this natural idea (independently of the chosen remark able lattice) by basing cryptography on the lattice isomorphism problem (L IP). More specifically\, we provide:\n\n- a worst-case to average-case red uction for search-LIP and distinguish-LIP within an isomorphism class\, by extending techniques of Haviv and Regev (SODA 2014). \n\n- a zero-knowled ge proof of knowledge (ZKPoK) of an isomorphism. This implies an identific ation scheme based on search-LIP. \n\n- a key encapsulation mechanism (KEM ) scheme and a hash-then-sign signature scheme\, both based on distinguish -LIP.\n\nThe purpose of this approach is for remarkable lattices to improv e the security and performance of lattice-based cryptography. For example\ , decoding within poly-logarithmic factor from Minkowski's bound in a rema rkable lattice would lead to a KEM resisting lattice attacks down to a pol y-logarithmic approximation factor\, provided that the dual lattice is als o close to Minkowski's bound. Recent works have indeed reached such decode rs for certain lattices (Chor-Rivest\, Barnes-Sloan)\, but these do not pe rfectly fit our need as their duals have poor minimal distance.\n\nWessel is a PhD student in the Cryptology Group at CWI in Amsterdam under the sup ervision of Léo Ducas. END:VEVENT BEGIN:VEVENT SUMMARY:Log-S-unit lattices using Explicit Stickelberger Generators to sol ve Approx Ideal-SVP by Olivier BERNARD DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220124T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220124T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202201241300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nIn 2020\, Bernard and Roux-Langlois introduced the Twisted -PHS algorithm to solve Approx-SVP for ideal lattices on any number field\ , based on the PHS algorithm by Pellet-Mary\, Hanrot and Stehlé in 2019. They performed experiments for prime conductors cyclotomic fields of degre es at most 70\, reporting approximation factors reached in practice. The m ain obstacle for these experiments is the computation of a log-$\\mathcal{ S}$-unit lattice\, which requires classical subexponential time.\n\nIn thi s paper\, our main contribution is to extend these experiments to 210 cycl otomic fields of any conductor $m$ and of degree up to 210. Building upon new results from Bernard and Ku{\\v{c}}era on the Stickelberger ideal\, we construct a maximal set of independent $\\mathcal{S}$-units lifted from t he maximal real subfield using explicit Stickelberger generators obtained via Jacobi sums. Hence\, we obtain full-rank log-$\\mathcal{S}$-unit subla ttices fulfilling the role of approximating the full Tw-PHS lattice. Notab ly\, our obtained approximation factors match those from Bernard and Roux- Langlois using the original log-$\\mathcal{S}$-unit lattice in small dimen sions.\n\nAs a side result\, we use the knowledge of these explicit Sticke lberger elements to remove almost all quantum steps in the CDW algorithm\, by Cramer\, Ducas and Wesolowski in 2021\, under the mild restriction tha t the plus part of the class number verifies $h^{+}_{m}\\leq O(\\sqrt{m})$ .\n\nThe full paper is available on [ePrint:2021/1384](https://eprint.iacr .org/2021/1384).\nThis is joint work with Andrea Lesavourey\, Tuong-Huy Ng uyen and Adeline Roux-Langlois.\n\nOlivier BERNARD is a research engineer at the cryptology laboratory of Thales\, Gennevilliers\, and is currently in the third year of a part-time PhD under the supervision of Pierre-Alain Fouque and Adeline Roux-Langlois. His research interests mainly focus on number theoretic cryptanalyses and more generally on algorithmic number th eory. END:VEVENT BEGIN:VEVENT SUMMARY:Lattice sieving via quantum random walks by Johanna Loyer DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20220110T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20220110T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202201101300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nLattice-based cryptography is one of the leading proposals for post-quantum cryptography. The Shortest Vector Problem (SVP) is argua bly the most important problem for the cryptanalysis of latticebased crypt ography\, and many lattice-based schemes have security claims based on its hardness. The best quantum algorithm for the SVP is due to Laarhoven [Laa 16 PhD thesis] and runs in (heuristic) time $d^{0.2653d+o(d)}$. \nWe prese nt an improvement over Laarhoven’s result and present an algorithm that has a (heuristic) running time of $d^{0.2570d+o(d)}$ where $d$ is the latt ice dimension. We also present time-memory trade-offs where we quantify th e amount of quantum memory and quantum random access memory of our algorit hm. \nThe core idea is to replace Grover’s algorithm used in [Laa16 PhD thesis] in a key part of the sieving algorithm by a quantum random walk in which we add a layer of local sensitive filtering.\n\n2nd year PhD studen t at Inria Paris advised by André Chailloux. END:VEVENT BEGIN:VEVENT SUMMARY:On the (in)security of ROS by Michele Orrù DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20211213T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20211213T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202112131300@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nWe present an algorithm solving the ROS (Random inh omogeneities in a Overdetermined Solvable system of linear equatio ns) problem in polynomial time for $\\ell > \\log p$ dimensions. Our algorithm can be combined with Wagner’s attack\, and lead s to a sub-exponential solution for any dimension $\\ell$ with b est complexity known so far.\nWhen concurrent executions are allow ed\, our algorithm leads to practical attacks against unforgeabili ty of blind signature schemes such as Schnorr and Okamoto–Schn orr blind signatures\, threshold signatures such as GJKR and the original version of FROST\, multisignatures such as CoSI and t he two-round version of MuSig\, partially blind signatures such a s Abe–Okamoto\, and conditional blind signatures such as ZGP17. \n\nThis is joint work with [Fabrice Benhamouda](https://www.normalesup.or g/~fbenhamo/)\, [Tancrède Lepoint](https://tlepoint.github.io/)\, [Julian Loss](https://www.julianloss.com/)\, [Mariana Raykova](https://marianapr. github.io/).\n\n\nMichele is a postdoc at UC Berkeley under the supervisio n of [Alessandro Chiesa](https://people.eecs.berkeley.edu/~alexch/). \n\nP rior to that\, he was a PhD student at École Normale Supérieure\, under the supervision of [Georg Fuchsbauer](https://www.di.ens.fr/~fuchsbau/). H e is interested in the intersection between authentication and anonymity.\ n\nIn the past\, he contributed to Python\, Debian\, and Tor. END:VEVENT BEGIN:VEVENT SUMMARY:Does Fiat-Shamir Require a Cryptographic Hash Function by Willy Qu ach DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20211129T143000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20211129T153000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202111291430@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nThe Fiat-Shamir transform is a general method for reducing interaction in public-coin protocols by replacing the random verifier mes sages with deterministic hashes of the protocol transcript. The soundness of this transformation is usually heuristic and lacks a formal security pr oof. Instead\, to argue security\, one can rely on the random oracle metho dology\, which informally states that whenever a random oracle soundly ins tantiates Fiat-Shamir\, a hash function that is ``sufficiently unstructure d'' (such as fixed-length SHA-2) should suffice. Finally\, for some specia l interactive protocols\, it is known how to (1) isolate a concrete securi ty property of a hash function that suffices to instantiate Fiat-Shamir an d (2) build a hash function satisfying this property under a cryptographic assumption such as Learning with Errors.\n\nIn this work\, we abandon thi s methodology and ask whether Fiat-Shamir truly requires a cryptographic h ash function. Perhaps surprisingly\, we show that in two of its most commo n applications --- building signature schemes as well as (general-purpose) non-interactive zero-knowledge arguments --- there are sound Fiat-Shamir instantiations using extremely simple and non-cryptographic hash functions such as sum-mod-$p$ or bit decomposition. In some cases\, we make idealiz ed assumptions (i.e.\, we invoke the generic group model)\, while in other s\, we prove soundness in the plain model.\n\nOn the negative side\, we al so identify important cases in which a cryptographic hash function is prov ably necessary to instantiate Fiat-Shamir. We hope this work leads to an i mproved understanding of the precise role of the hash function in the Fiat -Shamir transformation.\n\nJoint work with Yilei Chen\, Alex Lombardi and Fermi Ma.\nEprint: https://eprint.iacr.org/2020/915\n\nWilly Quach is a 5t h year PhD student at Northeastern University advised by Daniel Wichs. END:VEVENT BEGIN:VEVENT SUMMARY:Compressed Σ-Protocol Theory by Thomas Attema DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20211115T120000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20211115T130000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202111151200@https://jcs.trusted-third-party.org/ DESCRIPTION:Note the changed time.\n\nΣ-Protocols provide a well-understo od basis for secure algorithmics. Compressed Σ-protocol theory (CRYPTO 20 20) was introduced as a strengthening yielding protocols with low communic ation complexity. It is built around basic Σ-protocols for proving that a compactly committed (long) vector satisfies a linear constraint. The comm unication complexity of these protocols is first compressed\, from linear down to logarithmic\, using a recursive ``folding-technique'' adapted from Bulletproofs (Bootle et al.\, EUROCRYPT 2016\, and Bünz et al.\, S&P 201 8)\, at the expense of logarithmic rounds. Proving in ZK that the secret v ector satisfies a given constraint -- captured by a (non-linear) circuit - - is then by (blackbox) reduction to the linear case\, via arithmetic secr et-sharing techniques adapted from MPC.\n\nThis abstract modular theory ha s been instantiated from a variety of cryptographic hardness assumptions\, i.e.\, the discrete-logarithm\, strong-RSA\, knowledge-of-exponent assump tion. In two separate works\, it has also been generalized to a bilinear c ircuit model and instantiated from the ring-SIS assumption. Thus for all t hese platforms compressed Σ-protocol theory yields circuit zero-knowledge protocols with (poly)-logarithmic communication.\n\nAll in all\, our theo ry should more generally be useful for modular (``plug-&-play'') design of practical cryptographic protocols\; this is further evidenced by our sepa rate work on proofs of partial knowledge.\n\nJoint work with: Ronald Crame r\, Serge Fehr\, Lisa Kohl and Matthieu Rambaud\n\nThomas Attema is a rese archer at the applied research institute TNO in The Netherlands\, where he works on (applied) multi-party computation\, zero-knowledge proof systems and post-quantum cryptography. Moreover\, he is pursuing a part-time PhD in the Cryptology group of CWI under the supervision of Ronald Cramer. END:VEVENT BEGIN:VEVENT SUMMARY:On the Security of Homomorphic Encryption on Approximate Numbers b y Baiyu Li DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20211004T150000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20211004T160000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202110041500@https://jcs.trusted-third-party.org/ DESCRIPTION:\n\nIn this talk\, we study the passive security model of appr oximate\nhomomorphic encryption schemes. We present new passive security d efinitions\nfor homomorphic encryption in the approximate computation sett ing\, by naturally\nextending the traditional notion of IND-CPA security.\ nWe propose both indistinguishability-based and simulation-based variants\ ,\nas well as restricted versions of the definitions that limit the order and number\nof adversarial queries (as may be enforced by some application s).\nWe prove implications and separations among different definitional va riants\,\nshowing a hierarchy of approximate homomorphic encryption scheme s.\nOur models provide a solid theoretical basis for the security evaluati on of\napproximate homomorphic encryption schemes (against passive attacks ).\n\nAs the main application of our passive security models\, we present passive attacks\nagainst CKKS\, the homomorphic encryption scheme for arit hmetic on approximate numbers\npresented at Asiacrypt 2017. The attack is both theoretically efficient (running in\nexpected polynomial time) and ve ry practical\, leading to complete key recovery with\nhigh probability and very modest running times. \nWe implemented and tested the attack against major open source homomorphic encryption\nlibraries\, including HEAAN\, S EAL\, HElib\, PALISADE and Lattigo\, and when computing\nseveral functions that often arise in applications of the CKKS scheme to\nprivacy-preservin g machine learning.\nOur attack shows that the traditional formulation of IND-CPA security (or\nindistinguishability against chosen plaintext attack s) achieved by CKKS does not\nadequately capture security against passive adversaries when applied to approximate\nencryption schemes\, and that a d ifferent\, stronger definition is required to evaluate\nthe security of su ch schemes.\n\nWe further discuss possible modifications to CKKS that may serve as countermeasures\nto our attacks\, and we also discuss open proble ms of efficiently achieving provable\nsecurity under our new definitions.\ n\nThis talk is based on the joint work with Daniele Micciancio.\n\n\nBaiy u Li graduated with a Ph.D. degree from UCSD in 2021\, advised by Daniele\ nMicciancio. His research interests include formal methods for secure comp utation\nprotocol design and analysis\, as well as lattice-based cryptogra phy.\nPreviously he received his Master's and Bachelor's degrees in CS and Pure Math from\nthe University of Waterloo. END:VEVENT BEGIN:VEVENT SUMMARY:Quantum Reduction of Finding Short Code Vectors to the Decoding Pr oblem by Thomas Debris-Alazard DTSTART;TZID=Europe/London;VALUE=DATE-TIME:20210920T130000 DTEND;TZID=Europe/London;VALUE=DATE-TIME:20210920T140000 DTSTAMP;VALUE=DATE-TIME:20260406T192007Z UID:202109201300@https://jcs.trusted-third-party.org/ DESCRIPTION:The seminar will be at 13:00 UK time\, 14:00 FR time\n\nIn thi s talk we will give a quantum reduction from finding short codewords in a random linear code to decoding for the Hamming metric. This is the first t ime such a reduction (classical or quantum) has been obtained. Our reducti on adapts to linear codes Stehlé-Steinfield-Tanaka-Xagawa’ re-interpret ation of Regev’s quantum reduction from finding short lattice vectors to solving the Closest Vector Problem. The Hamming metric is a much coarser metric than the Euclidean metric and this adaptation has needed several ne w ingredients to make it work. For instance\, in order to have a meaningfu l reduction it is necessary in the Hamming metric to choose a very large d ecoding radius and this needs in many cases to go beyond the radius where decoding is unique. Another crucial step for the analysis of the reduction is the choice of the errors that are being fed to the decoding algorithm. For lattices\, errors are usually sampled according to a Gaussian distrib ution. However\, it turns out that the Bernoulli distribution (the analogu e for codes of the Gaussian) is too much spread out and can not be used fo r the reduction with codes. Instead we choose here the uniform distributio n over errors of a fixed weight and bring in orthogonal polynomials tools to perform the analysis and an additional amplitude amplification step to obtain the aforementioned result.\n\n\n\nThomas Debris-Alazard is a resear ch scientist (chargé de recherche) at Inria in the Grace project-team. He was previously a postdoctoral research assistant in the Information Secur ity Group under the supervision of Martin R. Albrecht. He received his PhD from Inria under the supervision of Jean-Pierre Tillich. END:VEVENT END:VCALENDAR