Meta tags:
description=The Elliptic Curve Cryptography blog;

Headings (most frequently used words):

cryptography, on, elliptic, sidh, curve, oct, 30, nov, 2024, taipei, of, isogeny, comments, recent, ellipticnews, 28, celebrating, 40, years, curves, in, ecc, august, 11, 2025, 25th, workshop, taiwan, new, cryptanalysis, siam, conference, applied, algebraic, geometry, ag23, some, the, csidh, group, action, equivalence, between, cdh, and, dlp, eddsa, standardized, attacks, sike, breaking, supersingular, diffie, hellman, hertzbleed, attack, posts, archives, categories, meta,

Text of the page (most frequently used words):
the (433), and (184), that (98), this (82), attack (71), for (68), sidh (57), are (52), not (46), one (42), #isogeny (41), some (40), paper (40), with (39), curve (38), but (37), can (37), compute (35), group (31), #elliptic (30), have (29), there (28), cdh (27), curves (27), posted (27), time (27), may (25), csidh (25), attacks (25), from (25), about (24), was (22), more (22), cryptography (20), how (20), does (20), points (20), key (19), which (19), isogenies (19), all (19), work (18), problem (18), ellipticnews (17), blog (17), also (17), what (16), these (16), they (16), security (16), endomorphism (16), august (15), will (15), degree (15), then (15), oracle (15), dlp (15), ecc (14), sike (14), given (14), post (14), abelian (14), you (14), only (13), such (13), point (13), using (13), known (13), auxiliary (13), other (12), april (12), july (12), new (12), supersingular (12), let (12), been (12), case (12), quantum (12), uncategorized (11), june (11), crypto (11), recent (11), action (11), way (11), has (11), kani (11), any (11), like (11), break (11), than (11), map (11), polynomial (11), class (11), comment (10), december (10), 2013 (10), 2023 (10), general (10), information (10), where (10), two (10), hence (10), small (10), idea (10), algorithms (10), 2012 (9), 2014 (9), 2020 (9), 2022 (9), galbraith (9), torsion (9), nist (9), presented (9), sqisign (9), castryck (9), note (9), when (9), would (9), nice (9), festa (9), now (8), 2011 (8), february (8), october (8), 2016 (8), 2018 (8), leave (8), know (8), get (8), see (8), practical (8), over (8), bit (8), based (8), secret (8), attacker (8), seems (8), ring (8), applications (8), set (8), since (8), had (8), first (8), talk (8), comments (7), november (7), 2015 (7), 2019 (7), between (7), siam (7), workshop (7), steven (7), allows (7), shows (7), lead (7), scheme (7), decru (7), efficient (7), hellman (7), want (7), need (7), both (7), much (7), give (7), signatures (7), talks (7), free (6), website (6), january (6), march (6), 2017 (6), equivalence (6), conference (6), power (6), learn (6), above (6), protocol (6), petit (6), panny (6), wouter (6), hope (6), broken (6), explain (6), order (6), here (6), diffie (6), due (6), varieties (6), damien (6), robert (6), cases (6), real (6), world (6), them (6), don (6), vercauteren (6), system (6), level (6), moral (6), algorithm (6), hard (6), size (6), however (6), ega (6), signature (6), structure (6), audience (6), create (5), your (5), wordpress (5), com (5), sign (5), september (5), 2024 (5), 2025 (5), applied (5), algebraic (5), geometry (5), cryptanalysis (5), oct (5), channel (5), because (5), show (5), into (5), high (5), operations (5), enough (5), timing (5), use (5), form (5), his (5), kutas (5), martindale (5), certain (5), exchange (5), even (5), against (5), result (5), should (5), out (5), sense (5), ingredient (5), efficiently (5), unknown (5), essentially (5), works (5), means (5), prime (5), previous (5), wesolowski (5), special (5), many (5), just (5), secure (5), suppose (5), truth (5), back (5), equivalent (5), solve (5), make (5), papers (5), lattice (5), gave (5), defined (5), day (5), guido (5), knowledge (5), write (4), nov (4), better (4), interesting (4), used (4), systems (4), side (4), yet (4), cryptographic (4), single (4), constant (4), david (4), field (4), impact (4), thomas (4), surfaces (4), specifically (4), provided (4), cryptosystems (4), primes (4), able (4), magic (4), already (4), were (4), peter (4), possible (4), complexity (4), details (4), feo (4), breaking (4), computing (4), dimensional (4), knowing (4), acts (4), dual (4), squares (4), modulo (4), most (4), too (4), eprint (4), benjamin (4), main (4), understanding (4), same (4), starting (4), version (4), giving (4), second (4), provide (4), discrete (4), nothing (4), facts (4), problems (4), pairing (4), solving (4), still (4), believe (4), oracles (4), change (4), generate (4), purpose (4), call (4), parameter (4), csi (4), fish (4), kuperberg (4), psidh (4), subgroup (4), proposed (4), frobenius (4), images (4), start (3), required (3), log (3), view (3), 2021 (3), taipei (3), years (3), posts (3), important (3), approach (3), current (3), despite (3), its (3), theoretical (3), exploits (3), through (3), frequency (3), program (3), seem (3), says (3), specific (3), hertzbleed (3), authors (3), explained (3), doesn (3), traditional (3), code (3), symposium (3), university (3), doubt (3), beullens (3), our (3), without (3), reason (3), very (3), variants (3), base (3), might (3), example (3), fouotsa (3), submission (3), simple (3), theorem (3), composition (3), aspects (3), run (3), having (3), quick (3), research (3), full (3), implementation (3), topic (3), basis (3), identity (3), take (3), simpler (3), subexponential (3), apply (3), original (3), https (3), instances (3), under (3), maino (3), below (3), easily (3), chloe (3), arbitrary (3), eddsa (3), uses (3), instance (3), solves (3), wrote (3), consider (3), people (3), done (3), good (3), theory (3), each (3), needs (3), multiplications (3), whole (3), further (3), short (3), computational (3), scallop (3), 512 (3), cannot (3), formal (3), cost (3), adfmp (3), resist (3), generally (3), schemes (3), effective (3), unfortunately (3), expect (3), different (3), algebra (3), found (3), graphs (3), technique (3), overstretched (3), well (3), personal (3), took (3), maps (3), cyclic (3), kernel (3), type (3), lollipop (3), exact (3), ways (3), own (2), report (2), content (2), account (2), feed (2), 2010 (2), aurore (2), guillevic (2), ag23 (2), 25th (2), taiwan (2), celebrating (2), search (2), older (2), obvious (2), construct (2), updates (2), grained (2), low (2), difference (2), mean (2), moment (2), involves (2), choosing (2), patrick (2), longa (2), exploited (2), triple (2), aspect (2), adaptive (2), quehen (2), leonardi (2), stange (2), prevented (2), help (2), context (2), interestingly (2), target (2), standard (2), montgomery (2), scaling (2), mount (2), zero (2), value (2), news (2), reduce (2), appearance (2), relatively (2), ward (2), similar (2), multivariate (2), correct (2), response (2), subject (2), instead (2), implications (2), useful (2), could (2), richelot (2), products (2), necessary (2), find (2), studying (2), subjects (2), extending (2), why (2), exactly (2), think (2), things (2), must (2), clear (2), close (2), complex (2), kind (2), several (2), possibly (2), boris (2), fixed (2), specified (2), round (2), gpst (2), determines (2), brute (2), directly (2), fact (2), always (2), potential (2), etc (2), analysis (2), results (2), though (2), myself (2), understand (2), true (2), questions (2), recovery (2), emphasise (2), variety (2), look (2), methods (2), check (2), matrix (2), square (2), part (2), factor (2), computers (2), classically (2), defines (2), natural (2), determine (2), improvement (2), rémy (2), oudompheng (2), mentioned (2), recall (2), gives (2), fix (2), org (2), notes (2), elementary (2), completely (2), luciano (2), become (2), page (2), includes (2), related (2), ecdsa (2), opinion (2), edwards (2), logarithm (2), domain (2), parameters (2), digital (2), bad (2), implementations (2), either (2), inversion (2), provides (2), refer (2), 2004 (2), section (2), book (2), stress (2), exponential (2), static (2), types (2), usually (2), implement (2), developer (2), accidently (2), somehow (2), computes (2), unlikely (2), fundamentally (2), muzereau (2), smart (2), bentahar (2), groups (2), those (2), said (2), access (2), polynomially (2), conjectured (2), exist (2), exponent (2), computations (2), additions (2), easy (2), adds (2), maurer (2), comput (2), math (2), coding (2), while (2), overview (2), best (2), nearly (2), large (2), precisely (2), total (2), verify (2), seasign (2), issues (2), currently (2), keygen (2), leroux (2), classical (2), arises (2), discussed (2), allow (2), considered (2), doing (2), actions (2), state (2), art (2), mention (2), ideas (2), rega (2), detail (2), analogue (2), alice (2), chooses (2), sends (2), bob (2), recently (2), presentation (2), readers (2), proofs (2), lorenz (2), hand (2), asked (2), bruhat (2), tits (2), although (2), terminology (2), appear (2), deuring (2), correspondence (2), making (2), orientations (2), quite (2), rather (2), reported (2), progress (2), fundamental (2), forms (2), dimension (2), vanishingly (2), impressed (2), past (2), coauthors (2), hidden (2), borel (2), non (2), antonin (2), week (2), closed (2), attended (2), along (2), last (2), eurocrypt (2), calls (2), structures (2), multi (2), variate (2), cryptology (2), mini (2), history (2), giulio (2), ramanujan (2), coming (2), random (2), eigenspaces (2), lemma (2), scalar (2), evaluate (2), blinding (2), lollipops (2), another (2), applying (2), sinica (2), index (2), celebrate (2), victor (2), neal (2), name, email, loading, collapse, bar, manage, subscriptions, site, reader, privacy, join, 118, subscribers, subscribed, subscribe, entries, meta, categories, archives, michele, orru, stefano, tessaro, alg, practice, dvfs, depend, aggregate, consumption, millions, cpu, cycles, reflect, coarse, behavior, primitives, admit, amplification, guesses, thousands, induce, measurable, fine, maliciously, dependent, countermeasure, property, message, troublesome, cause, shani, contexts, fujisaki, okamoto, transform, implemented, countermeasures, ladder, feature, supposedly, pqc, mailing, list, woke, dynamic, modern, x86, processors, usenix, boston, yingchen, wang, hovav, shacham, texas, austin, riccardo, paccagnella, elizabeth, tang, christopher, fletcher, illinois, urbana, champaign, kohlbrenner, washington, confidence, sudden, powerful, mature, rainbow, attempt, minimise, nor, reflexively, declare, dead, keep, minds, open, mathematicians, wherever, personally, wait, isogenists, come, next, foundations, described, 1997, tools, howe, leprévost, poonen, 2000, noticed, going, discover, thinking, deeply, expressed, meaningfully, language, generalisation, extension, community, scholars, esoteric, discovered, assumes, particular, relies, suggests, attackable, changing, prevent, number, degrees, various, discriminant, multiplication, saved, require, public, setup, twitter, suggestions, avoid, follow, threads, fouotsab, kutasp, candidate, nope, ernst, reducible, subgroups, simplified, intermediate, eventually, private, step, force, gadget, words, sequence, connected, exists, annoyance, weakness, fault, heuristic, normal, acceptable, experimental, haven, team, confirmed, solved, microsoft, ikep217, challenge, eligible, claim, 000, usd, prize, technical, answers, burning, major, breakthrough, relates, jao, finalist, earlier, decades, primarily, motivated, drive, generalization, pure, mathematics, aware, forward, seeing, simply, forcing, extra, fancy, leading, expert, define, matrices, extend, commutes, homomorphism, sum, four, factors, congruent, integers, added, thanks, daniel, bernstein, corresponds, transpose, itself, goal, others, together, assume, sketch, consistency, notation, tomoki, moriya, less, iacr, 1019, sage, updated, techniques, allowing, minute, christophe, improving, implementing, direct, determination, put, diamonds, intuition, beginners, summarise, few, parallel, independent, meaning, laptop, influenced, extends, breaks, preliminary, three, preprints, feel, trouble, keeping, instantly, obsolete, advances, opportunity, advertise, lists, ed25519, least, notable, features, closely, schnorr, avoids, clunky, elegant, document, states, recommendation, newly, increased, performance, resistance, compared, include, widely, edwards25519, recommendations, published, federal, processing, fips, standardized, cryptosystem, contradict, stated, sorts, diffie, love, tell, verheul, evidence, xtr, crypt, hess, ieee, trans, 2008, improved, brown, gallant, cheon, pollard, rho, providing, meets, input, big, created, did, written, talking, unwittingly, logarithms, someone, understatement, started, sure, task, bunch, interest, criticise, didn, say, depends, smooth, asymptotic, awkward, common, concrete, estimates, calculations, suitable, established, multiply, again, chosen, inputs, core, perform, necessarily, chapter, gory, references, wonderfully, formalised, basic, den, boer, 1988, working, developed, 1994, who, replaced, refinements, wolf, 1996, 1999, lms, ima, 2005, obviously, logs, play, around, convince, yourself, assumption, underlies, especially, encryption, briefly, alexander, carl, richard, theodor, schneider, caused, excitement, anxiety, thought, explainer, dlog, practically, dlogs, via, standards, apologies, quickly, typos, course, thing, actual, observed, rank, tends, letting, optimal, negligible, largest, propose, distinct, exponents, repeated, times, lost, suffer, running, scales, namely, getting, merz, fklmpw, issue, requires, vector, within, asymptotics, argue, pre, computation, computed, argues, realistic, precomputation, exceed, asymptotically, choices, excessively, conservative, choice, levels, larger, protocols, uniform, elements, proof, couveignes, stolbunov, kleinjung, bkv, approx, choose, space, smaller, chi, domínguez, esser, kunzweiler, analyses, subset, decoding, relevant, memory, notions, restricted, ideally, uniformly, sampled, perfect, alamati, patranabis, denote, follows, behind, enjoy, constructive, primitive, affected, believed, ideal, quadratic, invariant, finite, title, discussion, really, isn, detailed, luca, overall, intense, fun, remaining, favorite, conferences, video, recordings, sessions, ask, speakers, politely, authorization, publish, ever, available, youtube, recasting, framework, trees, objects, her, push, generation, signing, blazing, fast, she, ross, bowden, stuck, describe, tree, folds, sent, cry, talked, spirit, leonardo, colò, pioneering, orienting, trying, attaching, looks, far, unique, concluded, disconsolate, arguing, extremely, probably, familiar, surprise, kohel, left, feeling, beautiful, missing, scenery, alternating, trilinear, connection, volcano, among, sets, explanation, appears, surface, acting, bilinear, obscure, totally, impractical, looked, risky, underlying, invariants, distance, wasn, express, ambient, sheer, coincidence, hsp, turns, solvable, contained, contains, amount, invented, strong, indication, michael, meyer, generating, friendly, searches, presentations, optimistic, standardization, pretty, pessimistic, answer, came, rescue, sqisignhd, variant, promises, faster, slightly, shorter, considerably, verification, gustavo, banegas, maybe, continuing, giacomo, pope, pke, named, summary, stuff, certainly, workshops, italian, remade, layman, presenting, unpublished, federico, pintore, followed, numbers, unbroken, worthy, cleanup, annamaria, iezzi, wise, heuristics, removed, missed, valerie, gilchrist, supsersingularity, testing, counter, measures, appeared, improvements, artificial, end, everyone, understood, being, else, cartan, disguised, veronese, tempted, classify, bucket, lie, method, puts, linear, advanced, promised, attend, outside, ended, attending, mostly, yin, yang, insights, uov, tuov, submissions, ramp, rest, something, palatable, highlight, lido, codogni, spot, delivered, spectacular, double, spectral, properties, shown, statistically, generalize, showing, obstruction, weil, somewhat, barely, mistook, sga, seminar, journey, modular, hecke, operators, pairings, symposia, included, place, eindhoven, conclude, fixes, tweaks, await, continues, withstand, scrutiny, cryptanalysts, sounds, isogenous, pull, endomorphisms, every, arthur, herlédan, merdy, aurel, studies, insecure, remarks, leaked, corresponding, orientation, covers, discusses, strategies, defenses, malicious, party, installing, backdoor, matter, attacking, finish, runs, finally, desire, equal, present, handled, pushforward, conjugate, denotes, try, clever, blinded, sort, multiple, strategy, proposals, builds, introduced, formed, taking, picture, linked, warned, sweet, sound, needed, explicit, terms, wrong, desired, indeed, polarized, plausible, sections, explains, hiding, whatever, hide, blind, won, quanta, article, frederik, troll, iis, edu, ecc24, shtml, webpage, annual, series, dedicated, study, areas, editions, please, year, autumn, school, location, campus, academia, eccworkshop, html, online, event, 11th, commemorate, founding, ago, miller, koblitz, reflections, their, legacy, broad, expected, 1985, dan, boneh, kristin, lauter, brief, lectures, impacts, textbook, blue, skies, outcomes, unexpected, home, skip,

Text of the page (random words):
ction the total sign verify time for seasign is bit operations since the protocol has to be repeated times of course polynomial time and practical are not the same thing it is an interesting problem to work out what is best for actual practical implementations at high security level at the moment the approach in the scallop paper may be the best way to go as observed in that paper the lattice rank tends to be relatively small letting us compute a nearly optimal basis in negligible time but i note that the largest example in the scallop paper is only a 512 bit class group and 75 dimensional lattice which may not be large enough for high security applications steven galbraith posted in uncategorized leave a comment equivalence between cdh and dlp posted on april 19 2023 by ellipticnews apologies i wrote this quickly and there may be typos the paper dlog is practically as hard or easy as dh solving dlogs via dh oracles on ec standards by alexander may and carl richard theodor schneider seems to have caused some excitement and anxiety so i thought i would write a quick explainer about what it means this is a nice paper but it is important to point out two facts it does not fundamentally change our understanding of cdh and dlp it does not lead to a new attack on any real world system let me briefly explain overview of the moral equivalence of cdh and dlp let be a point on an elliptic curve of prime order the computational diffie hellman cdh problem is given points to compute this computational assumption underlies many elliptic curve cryptosystems especially those based on key exchange or encryption obviously if you can compute discrete logs ie solve dlp then you can compute if you play around with cdh for a while you start to convince yourself of the moral truth that the only way to solve cdh is to compute dlp in short one may start to believe that the computational problems cdh and dlp may be equivalent wonderfully this equivalence has been formalised there are algorithms to solve dlp if given access to an oracle that solves cdh the basic idea is due to den boer crypto 1988 for cdh in a group of order by working in an auxiliary group the idea was further developed by maurer crypto 1994 who replaced the auxiliary group with an elliptic curve over further refinements were done by maurer and wolf crypto 1996 siam j comput 1999 and muzereau smart vercauteren lms j comput math 2004 bentahar ima cryptography and coding 2005 the core of these methods is to perform computations with the auxiliary group in the exponent so one needs to do additions and multiplications modulo additions are easy given and one adds the points to compute multiplications are hard given and we need to compute and this is provided by the cdh oracle the whole point is to be able to do these operations without necessarily knowing what and are i refer you to chapter 21 of my book for all the gory details and references to the papers mentioned i want to stress that the algorithms do things like square and multiply in the exponent suppose i want to compute from then i can call the cdh oracle on to get then i can call the cdh oracle again on to get etc i need the cdh oracle to work on any chosen inputs i just said there are algorithms to solve dlp if given access to an oracle that solves cdh but i didn t say if they are efficient algorithms or not this depends on the auxiliary curve in theory to get a polynomial time algorithm it is necessary to have an auxiliary curve of polynomially smooth order but asymptotic security is a bit awkward for such questions so it is more common to make concrete estimates calculations for specific instances it is conjectured that suitable auxiliary curves exist for each prime one just needs a single nice auxiliary curve hence for theoretical people like me the moral truth that cdh is equivalent to dlp is established for practical people the problem is how to generate such nice curves some work on this problem was done by muzereau smart vercauteren and bentahar the recent eprint paper is on this part of the task they generate a bunch of nice auxiliary curves it means that even practical people can believe the moral truth that cdh and dlp are equivalent for certain elliptic curve groups of interest i like the paper it is good work the purpose of this blog post is not to criticise those authors the purpose is to explain the impact of the work back to the two facts i started with the new paper does not fundamentally change our understanding of cdh and dlp because the moral truth that cdh and dlp are equivalent was already clear but how can i be sure the new paper does not lead to an attack on any real world system how can i be certain the paper does not lead to an attack on any real world system suppose a developer accidently created a system that provides a cdh oracle to an attacker how did they do that they must have somehow written a program that solves cdh in general this means because of the moral truth we have been talking about that this developer accidently and unwittingly wrote a program that computes discrete logarithms on elliptic curves i consider it unlikely that someone could do that this is an understatement what types of oracles are provided by real world systems i believe there are real world systems that provide certain types of cdh oracle i have not had time to look into this but usually these are some kind of static diffie hellman oracle such oracles have a secret and on input a point they compute one big difference between such oracles and a general cdh oracle is that i know how to implement such an oracle without solving dlp first there are improved algorithms for dlp given such an oracle due to brown gallant and cheon they are explained in section 21 5 of my book it is important to stress that these may be better than solving the dlp using pollard rho but they are still exponential time algorithms if your system is providing an attacker with a static diffie hellman oracle then you should check your instance meets the required security level there are also all sorts of variants of cdh like one more diffie hellman problems but i don t have time to talk about them if i had time i d also love to tell you about how pairing inversion provides a cdh oracle but i ll just refer you to verheul evidence that xtr is more secure than supersingular elliptic curve cryptosystems j crypt 2004 and galbraith hess vercauteren aspects of pairing inversion ieee trans it 2008 steven galbraith ps there might be bad implementations or bad cryptosystems in the real world that provide an attacker with an oracle that allows them to break the cryptosystem but that s nothing to do with the recent eprint paper either so this would not contradict the two facts i stated above posted in uncategorized 3 comments eddsa standardized posted on february 6 2023 by ellipticnews a new version of the nist federal information processing standard fips for digital signatures has been published also see here this version includes eddsa there are at least two notable features of eddsa first it is more closely related to schnorr signatures than ecdsa this means it avoids in my opinion many of the clunky aspects of ecdsa and allows a much more elegant security analysis second it uses curves in edwards form specifically the document recommendations for discrete logarithm based cryptography elliptic curve domain parameters states this recommendation includes two newly specified edwards curves which provide increased performance side channel resistance and simpler implementation when compared to traditional curves the curves include the widely used edwards25519 curve i also take the opportunity to advertise this page which lists applications that use ed25519 steven galbraith posted in uncategorized leave a comment attacks on sidh sike posted on august 12 2022 by ellipticnews you may feel like you are having trouble keeping up with the news on sidh sike so am i i hope this blog post doesn t instantly become obsolete due to new advances to recall there are now three preprints giving attacks on sidh an efficient key recovery attack on sidh preliminary version by wouter castryck and thomas decru posted july 30 an attack on sidh with arbitrary starting curve by luciano maino and chloe martindale posted august 8 breaking sidh in polynomial time by damien robert posted august 10 the first two are parallel independent works that apply a theorem due to kani to break sidh in some special cases one of the special cases was the nist submission sike meaning that sike was able to be broken easily on a laptop the most recent paper by damien robert is influenced by the previous two works and extends the attack to work in a much more general case this now breaks sidh completely in all cases i will summarise damien robert s work below but first a few other updates i put up a note kani for beginners to explain in an elementary way that kani s isogeny diamonds are the same as sidh squares and to give some intuition for what kani s theorem says rémy oudompheng posted a note on implementing direct isogeny determination in the castryck decru sike attack and benjamin wesolowski posted understanding and improving the castryck decru attack on sidh both notes explain an improvement to the attack the main idea seems also to have been had by christophe petit and maino martindale the sage code has been updated with these techniques allowing it to break some instances in under a minute tomoki moriya has posted https eprint iacr org 2022 1019 which gives a possible fix for sidh much less efficient and practical though now to sketch the idea by damien robert for consistency with my previous blog post i use some of the castryck decru notation recall that in sidh we have a base curve and isogenies of degree and of degree together with some auxiliary points assume the most natural way to break sidh is to compute on points of order from which one can then determine and sidh is broken this is the goal of the torsion point attacks by petit et al it is also the idea for the improvement to the original attack by rémy oudompheng and others that i mentioned above this is what damien robert s attack does too let then we can write as a sum of four squares in this post i will take the simpler case when all prime factors of the square free part of are congruent to 1 modulo 4 in which case we can write where are integers note added 15 8 2022 thanks to daniel bernstein to do this we need to factor which is polynomial time for quantum computers or subexponential time classically the 4 squares case is polynomial time classically let then where is the identity matrix hence defines an isogeny for any elliptic curve specifically the dual isogeny corresponds to the transpose we have as a map from to itself we will apply this map to both and the secret isogeny is and we can extend this to a map from as note that commutes with since is a group homomorphism we can define an isogeny on the 4 dimensional abelian variety by the dual isogeny is and one can check where is the identity map or identity matrix if you want to view these as matrices now from the auxiliary points in sidh we know how acts on since we can also compute how acts on hence we can compute how acts on since it means we compute now knowing we can use fancy methods to compute isogenies on high dimensional abelian varieties and damien robert is a leading expert on this topic and hence compute on any point so we compute on a basis for and hence compute on and break sidh the full attack works with an 8 dimensional abelian variety i am not aware of any implementation of the attack as yet but i look forward to seeing one the attack can also be set up to compute the isogeny instead simply by brute forcing an extra small 3 power isogeny so that as with my earlier blog post i want to emphasise that this attack is only possible due to decades of research on computing isogenies of general abelian varieties this work was not primarily motivated by cryptographic applications but by the drive to generalization in pure mathematics steven galbraith posted in uncategorized leave a comment breaking supersingular isogeny diffie hellman sidh posted on july 31 2022 by ellipticnews the paper an efficient key recovery attack on sidh by wouter castryck and thomas decru is a major breakthrough in isogeny cryptanalysis this relates to the sidh protocol by jao and de feo and the nist round 4 finalist sike i do not have time to explain all the technical details but here are some quick answers to your burning questions is the result true there is no reason to doubt this code is provided though i haven t run it myself and i understand the sike team has confirmed the attack having solved the microsoft ikep217 challenge castryck and decru are eligible to claim the 50 000 usd prize some aspects of the attack and its complexity analysis are heuristic but that is normal and acceptable for cryptanalysis the experimental results show that the attack is very practical how does the attack work the attack exploits the fact that sidh has auxiliary points and that the degree of the secret isogeny is known the auxiliary points in sidh have always been an annoyance and a potential weakness and they have been exploited for fault attacks the gpst adaptive attack torsion point attacks etc let be the base curve and let have order let be given such that there exists an isogeny of degree with and a key aspect of sidh is that one does not compute directly but as a composition of isogenies of degree 3 in other words there is a sequence of curves connected by 3 isogenies essentially like in gpst the attack determines the intermediate curves and hence eventually determines the private key at step the attack does a brute force search of all possible and the magic ingredient is a gadget that shows which one is correct the above is over simplified the isogenies in the attack are not of degree 3 but of degree a small power of 3 what is this magic ingredient it is a theorem by ernst kani about reducible subgroups of abelian surfaces is there a simple way to explain the magic ingredient nope go learn about richelot isogenies and abelian surfaces what does this mean for the nist round 4 candidate sike the scheme specified in the sike nist submission is broken can sidh be fixed already on twitter there were several suggestions on how to possibly avoid the attack for example follow peter kutas kutasp and boris fouotsa fouotsab for some threads to be able to use the magic ingredient the attacker must efficiently compute a number of isogenies with degrees of the form for various and it is not clear how to do this if we are not close to a curve with small discriminant complex multiplication so one hope is that sidh can be saved by choosing a base curve with unknown endomorphism ring this might require some kind of public setup the paper suggests that variants of sidh such as b sidh using primes other than 2 and 3 ...