[HN Gopher] Did Schnorr destroy RSA? Show me the factors
___________________________________________________________________
Did Schnorr destroy RSA? Show me the factors
Author : sweis
Score : 150 points
Date : 2021-03-03 20:38 UTC (2 hours ago)
(HTM) web link (sweis.medium.com)
(TXT) w3m dump (sweis.medium.com)
| chrisco255 wrote:
| For those of us less familiar with cryptography and RSA in
| general: what are the implications if RSA is broken? What are the
| mitigations that would need to occur in its place?
| tgsovlerkhgsel wrote:
| If RSA-2048 is practically broken or breakable:
|
| The public web and code signing PKIs collapse overnight. Most
| certificate authorities use RSA-2048 either for the roots or
| intermediates. The HN site not only uses a RSA-2048 key in its
| own certificate, the CA issuing that certificate and the root
| CA issuing the intermediate also do.
|
| All data transmitted without forward secrecy on most web sites
| is compromised. Most websites nowadays use forward secrecy
| and/or ECDSA, but data sent years ago may still be of value
| (e.g. passwords) and become decryptable now.
|
| Any data (e.g. backups, past e-mails) encrypted using RSA keys
| is at risk.
|
| Any authentication system relying on RSA keys has a problem.
| This can include systems like smartcards or HSMs that are hard
| to update, software or firmware updates, etc. Banking too.
|
| Edit to add - if RSA-1024 is practically breakable but RSA-2048
| is not: some systems that relied on RSA-1024 have a problem.
| These should be rare, but sometimes legacy doesn't get updated
| until it becomes an absolute emergency. Everyone realizes that
| RSA-2048 is only a matter of time, that time is running out
| quicker than expected, and starts upgrading to ECDSA with more
| urgency. This will likely take a long time due to legacy
| hardware.
| aaomidi wrote:
| 1. We kinda knew RSA has an expiration date due to quantum
| computers. Assuming the paper is true, this just brought the
| expiration date far closer to us.
|
| 2. Major issue is going to be webpki and replaying govt
| captured encrypted communications.
|
| 3. There are a lot of abandoned servers out there that use RSA.
| There is a lot of code signing that uses RSA. There is just a
| lot of identity proven on the web that uses RSA to prove the
| identity. It's going to be a clusterfuck of identity. Again,
| assuming the paper means RSA is just completely broken.
| chrisco255 wrote:
| Does this technique for factorization by Schnorr have any
| implications for any other cryptographic methods as well (if
| confirmed)?
| dataflow wrote:
| > 1. We kinda knew RSA has an expiration date due to quantum
| computers.
|
| Only if you somehow "know" quantum computing is ever going to
| be practically realized. It may never be.
| [deleted]
| freeone3000 wrote:
| There's no real big theoretical problems in the quantum
| computer building space. There's problems of scale, and
| funding, and usual growing pains of a new industry, but
| scale went from 7 to 24 fairly quickly and all it took was
| more money. If I gave IBM $10T dollars, they could build me
| a 1024-qbit computer. Once it gets cheaper, which is the
| current problem, I don't see any reason why Azure Quantum
| (ex) wouldn't simply decrease in price to where it can be
| used practically.
| [deleted]
| [deleted]
| Laakeri wrote:
| >There's no real big theoretical problems in the quantum
| computer building space
|
| The current quantum computers are just on the edge of
| what we can simulate classically, so we can't yet rule
| out the possibility that realizing a quantum computation
| requires an exponential amount of energy in the number of
| qubits. (Though it should be noted that quantum mechanics
| predicts that this will not happen.)
| coliveira wrote:
| > it should be noted that quantum mechanics predicts that
| this will not happen
|
| There is a possibility that QM will break somewhere, but
| I wouldn't consider this very probable...
| rurban wrote:
| He didn't claim it is broken. Only that it can be broken 2x
| faster than before. RSA 4096 as recommended by the FSF is still
| secure. RSA 2048 might be breakable by the NSA. But so far we
| are at 800-1000 at risk.
| TacticalCoder wrote:
| > He didn't claim it is broken.
|
| But then there's that line: "This destroys the RSA
| cryptosystem" in the abstract of the paper.
| anonisko wrote:
| "Broken" generally isn't a binary event in cryptography.
|
| It's a continuum from "impossible to do with all the time and
| energy of the universe and the most advanced computers we have"
| to "my commodity hardware can crack it in a few minutes".
|
| The same goes for fears of quantum computing breaking current
| cryptography. It goes from effectively impossible to "yeah, we
| could break it with a few years of constant computation, which
| is plenty of time to switch to quantum resistant schemes".
| jMyles wrote:
| > "Broken" generally isn't a binary event in cryptography.
|
| If there were, for example, a way to glean a private key
| without factoring the modulus, I think we'd all agree that
| this amounts to "breaking" the system insofar as that it
| changes the applicability of the hardness assumption.
|
| On the other hand, simply achieving a faster way to factor
| the modulus is, at best, part of a continuum as you say.
| bawolff wrote:
| Well that's generally true, sometimes breakthroughs do happen
| overnight. Its not impossible.
| anonisko wrote:
| Yup. That's why I say generally.
|
| Even if the paper is correct it seems to fall into the
| 'moving down the continuum' category.
| bawolff wrote:
| This would massively break basically all traditional public key
| crypto i think (depends a bit on if it extends to eliptic-curve
| or just integer based RSA [edit: meant to say whether the
| algorithm can be adapted to solving discrete logrithms over
| eliptic curves]). It would be the biggest crypto thing to
| happen in the last 30 years at least.
|
| The mitigation would be to move to experimental post-quantum
| crypto systems immediately (quantum computers have all the fuss
| because they can break rsa).
|
| This is basically an unbelievable result. Without actually
| providing some factored numbers i am very doubtful.
|
| [I have not read paper]
|
| Edit: as pointed out below, i may have gotten overexcited.
| Still an incredible result if true.
| teraflop wrote:
| There is no such thing as "elliptic-curve RSA".
| jMyles wrote:
| > This would massively break basically all traditional public
| key crypto i think (depends a bit on if it extends to
| eliptic-curve or just integer based RSA).
|
| "A bit"? A lot more than a bit. A world.
|
| And on the surface, since it appears to be a factoring
| system, rather than a general purpose discrete log solver,
| the consequences, while incredible, are far more limited than
| the picture you paint. If this is even true; a matter over
| which I'm skeptical.
| sillysaurusx wrote:
| There are lots of alternative constructions. ECC, for example.
|
| 1024-bit and higher RSA is still unfactorable, so I don't think
| anyone will be attacking RSA directly any time soon.
| anonisko wrote:
| Reminiscent of Craig Wright's claim to be Satoshi.
|
| It doesn't matter what you claim with words if you can't back it
| up with cryptographic evidence.
|
| Shut up and prove you've done (or can do) the work.
| [deleted]
| biolurker1 wrote:
| Are you really comparing a con artist with one of the most
| famous cryptographers?
| anonisko wrote:
| Dear lord no. I can see how it might come across like that.
|
| More drawing attention to the wider theme that we generally
| should not take people at their word when we have the option
| to demand proof of work that can't be faked or mistaken.
|
| Don't trust. Verify.
| Ar-Curunir wrote:
| These are not trivial algorithms to implement, and the
| other factorization records require months of work from
| implementation experts. It's not an easy task, and theory
| work stands independently of implementation effort.
| tandr wrote:
| What does "36 bits of work" mean, sorry?
| bawolff wrote:
| My naive assumption would be, takes 2^36 cpu operations
| ISL wrote:
| If so, 2^36 ~ 7 x 10^10, so a few seconds on GHz processors.
| wtallis wrote:
| 2^36 arithmetic operations is what is claimed. That's not
| quite the same as CPU operations, because we only have 64-bit
| CPUs with up to 512-bit vector instructions, but we're
| talking about factoring 800-bit numbers. So we need to allow
| for several CPU instructions to implement each of the
| required arithmetic operations.
| jtsiskin wrote:
| Yeah I would be great if they could translate that into core-
| years to match the references they listed
| aDfbrtVt wrote:
| I'm guessing it's a shorthand for the order of units of work.
| log2(8.4E10) = 36.3 bits of operations
| tgsovlerkhgsel wrote:
| Devil's advocate: Posting the factors requires implementation
| work, then optimization, then a manageable but possibly still not
| trivial amount of resources and time - and likely a lot of trial
| and error. It is perfectly conceivable that a paper would be
| published before the implementation is actually better than a
| slower but heavily optimized approach. (I don't even try to
| understand the paper, but I've seen a mention that it's a storage
| tradeoff, which may make it a very different kind of optimization
| problem.)
|
| Do we know that the paper is definitely from Schnorr? (Edit: The
| article claims its provenance is confirmed). The "destroys the
| RSA cryptosystem" claim is now part of the paper. While anyone
| can make mistakes, I would expect such claims to be at least
| somewhat carefully checked before releasing them.
|
| Either way, I expect that we'll see either a
| retraction/correction or factors within weeks.
| TacticalCoder wrote:
| I am no cryptographer. I did implement, from the paper, Yao's
| "socialist millionaire" cryptographic protocol but... It was only
| a few lines of code and a very simple (to understand, not to come
| up with) paper.
|
| Now I just looked at that Schnorr paper and, well, I can tell you
| that I'm not going to be the one implementing it : (
| jMyles wrote:
| I'm skeptical. The paper is too tough for me to digest without
| spending days/weeks/lifetimes focusing on it (and there are many
| who can do it much faster obviously). But I think that if RSA is
| materially broken, we'll know it from movements in the ground
| (eg, sudden mysterious forged signatures) by the time a paper is
| published.
|
| I don't think that such a secret can be kept for more than a few
| minutes with immediately proceeding to runtime weaponization.
| gojomo wrote:
| I can imagine a certain pure-theorist mindset being confident
| enough in their reasoning, but not yet their coding, to report
| this first. Or, strategically holding definitive proof back as a
| hammer to deploy once the doubters reveal themselves.
|
| Why not let others do the rote reduction-to-practice?
|
| Why not create an example where your theory was correct, & your
| reputation was on the line, that took a little while to resolve -
| but when it does, it does so definitively in your favor, so you
| are more trusted in future pre-definitive-verification
| pronouncements?
|
| (I don't know enough about Schnorr-the-person to know if this
| fits his personality, but I can imagine such personalities.)
| jagger27 wrote:
| That's really all there is to it. Pudding, proof, etc.
| natch wrote:
| > the provenance of the paper has been confirmed: it is indeed
| Schnorr.
|
| What I read is that someone contacted Schnorr _over email_ to get
| this confirmation.
|
| I'm not saying the confirmation is wrong. And I'm not saying
| email cannot convey information.
| ornxka wrote:
| Well, it's definitely suspect now that RSA is broken.
| AnimalMuppet wrote:
| "Email cannot convey information"? Baloney. It does all the
| time.
|
| You seem to mean something different from what your words
| say...
| sodality2 wrote:
| Factors or gtfo
| NoKnowledge wrote:
| This take is rather naive. Those RSA factoring records were done
| by a large international team of researchers, using well
| established algorithms and decades of work on implementing those
| methods as fast as possible.
|
| The blog post says the paper mentions 8.4e10 operations for
| factoring, but I can't find that number in the paper anywhere.
| The post then states: "The 800-bit claims would be 36 bits of
| work." I don't know what that means.
|
| [edit]: the numbers are in the new version
| (https://eprint.iacr.org/2021/232). I was looking at the old
| version uploaded yesterday.
| titanomachy wrote:
| > The post states that 800-bit claims would be 36 bits of work.
| I don't know what that means.
|
| From the article: "Schnorr's paper claims to factor ... 800-bit
| moduli in 8.4*1010 operations"
|
| 2^36 ~= 8.4*1010, so I guess "36 bits of work" means 2^36
| operations. Analogous to how a password with 36 bits of entropy
| would require 2^36 guesses. My first time encountering the
| phrase "bits of work" as well, though.
| tgsovlerkhgsel wrote:
| 2^36 "operations" can still take a lot of time if each
| operation is multiplying two giant numbers, unless the meaning
| of "operation" is somehow normalized to mean e.g. 64 bit
| integer operations.
| UncleOxidant wrote:
| It didn't take long for custom ASICs for mining bitcoin to
| emerge. It wouldn't take long for custom ASICs to do these
| kinds of operations a lot faster than on a general purpose
| CPU to emerge.
| TacticalCoder wrote:
| > 2^36 "operations" can still take a lot of time if each
| operation is multiplying two giant number
|
| It took me 3.3 years of actual computation time to do about
| 2^46 multiplication+modulo of two 2048 bit numbers on a Core
| i7. 2^36 of 2048 bit numbers should be doable in a day on an
| eight years old CPU.
|
| P.S: that was on a single core, for the problem I solved was
| explicitly created as to not be parallelizable.
| libeclipse wrote:
| Supposing the paper does describe a more efficient
| factorisation algorithm, that does not imply that factoring a
| 800 bit prime (like the author of this article suggests) would
| be cheap.
| contravariant wrote:
| It's in the abstract:
|
| >Our accelerated strongprimal-dual reduction of [GN08] factors
| integers N[?]2^400 and N[?]2^800 by 4.2*10^9 and 8.4*10^10
| arithmetic operations.
| AnimalMuppet wrote:
| Increasing the length by a factor of 2^400 only increased the
| amount of work by a factor of 20? Staggering, if true in
| general.
| vitus wrote:
| Actually, you're only increasing the length of the number
| by a factor of 2, since 2^400 is a 400-bit number.
|
| If true, it's still leaps and bounds ahead of anything we
| have today, though.
| abetusk wrote:
| OK, here is a brief overview for people:
|
| To factor a number N (assumed to essentially be the product of
| two very large primes), find a 'short' lattice vector [0] using
| LLL [1] (and BKZ reduction? [2]) that finds many relations of the
| form: (u_i) = p_i,0 * p_{i,1} * ... * p_{i,n-1}
| (u_i - v_i * N) = q_{i,0} * q_{i,1} * ... * q_{i,n-1}
|
| where p,q are small primes.
|
| Numbers that have all their factors less than some prime, B, are
| said to be "B-smooth". In the above, both (u_i) and (u_i - v_i *
| N) are p_{i,n-1}-smooth and q_{i,n-1}-smooth, respectively.
|
| Construct many u_i and (u_i - v_i * N), so much so that you can
| create a product of primes, r_i, of the form:
| r_0^{2 b_0} * r_1^{2 b_1} * ... * r_{n-1}^{2 b_{n-1}} = 1 mod N
|
| where each b_i are integers.
|
| Since all exponents (2 _b_i) are even, we have the potential to
| find the square root of 1 which has the potential to resolve to
| two different numbers since N is composite. One of those is the
| product of r_i^{b_i} and the other is -1. Since y^2 = 1 mod N, we
| get (y-1)_ (y+1) = 0 mod N. If (y-1) or (y+1) are not 0, then
| then must share a factor of N and we've successfully factored.
|
| The trick is, of course, finding the smooth numbers. To do this,
| a lattice basis is made such that you find a short integer
| relation of the form a_0 ln(p_0) + a_1 ln(p_1)
| + ... + a_{n-1} ln(p_{n-1}) ~= ln(N)
|
| where ~= means "approximately equal to".
|
| u is chosen as the product of primes of all a_i > 0 and v is
| chosen to be the product of all primes where a_i < 0. The hope is
| that (u - v*N) is also p_{n-1}-smooth, which, as far as I
| understand, most of the math in the paper is trying to justify.
|
| The main innovation here, as far as I can tell, is that Schnorr
| is fiddling with the 'weighting' of the main diagonal when
| constructing the lattice basis. I interpret this as basically
| trying to randomize the initial lattice basis so that the chances
| of getting a different integer relation (for eventual
| construction of u,v) is more probable.
|
| I've been confused about this for over a decade as variants of
| this algorithm, and Schnorr's work in general, have been well
| published. For example, there's a paper from 2010 on "A Note on
| Integer Factorization Using Lattices" by Antonio Vera which
| discusses Schnorr's [3] construction.
|
| Is Schnorr trying to shout louder so people will listen or is
| there something else fundamentally flawed with this type of
| algorithm?
|
| Just a word of warning, LLL solves polynomial factorization in
| polynomial time (given a polynomial with integer coefficients,
| find it's factor polynomials also with integer coefficients) [4]
| and has been used to break other (now very old) cryptosystems
| [5]. If there's a candidate algorithm to solve integer factoring,
| lattice reduction (LLL, PSLQ, etc.) are it.
|
| I know of fplll that's a stand alone (FOSS) implementation of LLL
| and some extensions (BKZ, etc.) [6].
|
| [0] https://en.wikipedia.org/wiki/Lattice_reduction
|
| [1]
| https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%...
|
| [2]
| https://www.newton.ac.uk/files/seminar/20140509093009501-202...
|
| [3] https://arxiv.org/pdf/1003.5461.pdf
|
| [4]
| https://en.wikipedia.org/wiki/Factorization_of_polynomials#F...
|
| [5] https://web.eecs.umich.edu/~cpeikert/lic13/lec05.pdf
|
| [6] https://github.com/fplll/fplll
| titanomachy wrote:
| Thanks for summarizing, and talking about what's novel here.
|
| In the paper Schnorr suggests that this algorithm factors
| 800-bit integers in ~10^11 operations [36 bits], whereas the
| Number Field Sieve uses ~10^23 [76 bits]. Does that 76-bit
| figure represent the current state of the art, more or less?
|
| Also, since the paper talks only in terms of specific sizes of
| integers, I assume there's no claimed asymptotic speedup over
| existing methods?
| dang wrote:
| This was heavily discussed yesterday. (Edit: this next bit was
| out of date:) It seems the provenance of the paper and the
| 'destroy' claim are unclear.
|
| _"This destroys the RSA cryptosystem"_ -
| https://news.ycombinator.com/item?id=26321962 - March 2021 (140
| comments)
| john_alan wrote:
| Nah it's confirmed as from Schnorr.
|
| He even reiterated his belief it leaves RSA rekt.
|
| All that's left is the veracity of the attack.
| dang wrote:
| Ok thanks! I was out of date.
| tyingq wrote:
| Isn't it typical to release the paper first, for peer vetting,
| ahead of any actual working proof?
|
| It seems like the only reason for the _" put up or shut up"_
| reactions is that _" destroys RSA"_ comment in the submitted
| abstract...which isn't in the actual paper.
| chrisseaton wrote:
| > is that "destroys RSA" comment in the submitted
| abstract...which isn't in the actual paper
|
| I think it is - https://eprint.iacr.org/2021/232.pdf
| tyingq wrote:
| Ah, I see. It's been removed in a newer revision of the
| paper. https://www.math.uni-
| frankfurt.de/~dmst/teaching/WS2019/SVP9...
| chrisseaton wrote:
| Is that a retraction? What changed to cause that removal?
| dTP90pN wrote:
| The newer 12-page version on the preprint server has a PDF
| creation date of 3/3/2021, 11:32:56 AM, created with
| pdfeTeX-1.30.4.
|
| https://eprint.iacr.org/eprint-
| bin/getfile.pl?entry=2021/232...
|
| The previous (reportedly wrongly uploaded) version is from
| 12/5/2019, 9:10:13 AM created with pdfeTeX-1.30.4.
|
| https://eprint.iacr.org/eprint-
| bin/getfile.pl?entry=2021/232...
|
| The university website version is from 3/5/2020, 12:00:19
| PM created with pdfTeX-1.40.15.
|
| These dates & times are MM/DD/YYYY & CET.
|
| A co-editor of the Cryptology ePrint Archive confirmed the
| submission on twitter:
|
| https://twitter.com/Leptan/status/1367103240228261894
| m4lvin wrote:
| That times out for me, I guess www.math.uni-frankfurt.de is
| now getting more attention than usual ;-)
|
| Here is a version in the Google cache, it has the date of
| tomorrow on it "work in progress 04.03.2020" and no longer
| contains the "destroys RSA" sentence: https://webcache.goog
| leusercontent.com/search?q=cache:E0L-S3...
| bhaney wrote:
| Other way around I think. Your link is an old version of
| the paper. The one on eprint was just updated today with a
| version of the paper that adds the "destroys RSA" line and
| removes the "work in progress" line (put it in the wayback
| machine to see the version that was there yesterday without
| the claim of destroying RSA)
| [deleted]
| itcrowd wrote:
| The factors could be included in the manuscript as an example..
| dragontamer wrote:
| The sum-of-three cubes announcement was tweeted pretty easily.
|
| https://twitter.com/robinhouston/status/1169877007045296128
|
| Its easier to drum up support for your paper when you have a
| quick way to prove to the community of mathematicians that your
| results are golden.
|
| EDIT: The original webpage:
| http://math.mit.edu/~drew/sumsofcubes.html
|
| As you can see, the sum-of-cubes announcements are very terse.
| Ultimately pointing to the following link:
| https://share.cocalc.com/share/900eec7e-0710-4e2f-a03a-dba01...
|
| That kind of website / tweet is a "drop the mic" moment. It
| really makes people pay attention.
| coliveira wrote:
| That's not how science works. Yes, if your algorithm is
| simple enough and you can create an implementation, then it
| is good that you produce a working version. But it may be
| more complicated to implement the algorithm than writing a
| paper. This doesn't mean that the implementation is
| impossible.
| anonisko wrote:
| The whole paper is linked, https://eprint.iacr.org/2021/232.pdf
| jasonmp85 wrote:
| This is math. The working proof _is_ the paper. It just takes a
| long time to refute if there's a subtle error. "Putting up"
| ISN'T proof but it will sure get a lot of important people to
| drop what they're doing and check the paper faster.
| croddin wrote:
| How broken does this claim RSA is? SHA-1 was known to be broken
| for a long time before actually pulling off a collision was
| performed for example.[1]
|
| [1]https://en.wikipedia.org/wiki/SHA-1#Attacks
| Klwohu wrote:
| You probably understand how serious this is, so many people are
| going to become very emotional as this strikes at the very
| foundations of the Internet and digital security as we know it.
| The reactions I've seen so far do seem very emotional and this
| will only become much, much worse if there's a PoC which is
| produced.
| andrewla wrote:
| For something of this magnitude, I think the expected behavior
| would be to delay the release of the paper until the ecosystem
| had time to adapt. To prove the paper is valid (and to assert
| precedence) you would offer to factor several "nothing up my
| sleeve" numbers -- like sha512("schnorr1") +
| sha512("schnorr2").
|
| As it is, if the algorithm presented is valid then this
| potentially compromises currently operating systems.
| toast0 wrote:
| I haven't read the paper or anything, but if the expected
| adaptation is to drop support for RSA; no reasonable amount
| of time will make it a seamless transition.
|
| There are so many devices and pieces of software that are
| stuck on RSA, a headsup of say 5 years would still result in
| a clossal mess; may as well have the mess now.
| [deleted]
| dcow wrote:
| I do not agree that so-called "responsible disclosure" would
| or should be the expected behavior. I do understand how
| someone accustomed to corporate bug bounties and private
| security mailing lists may think so, though. Full disclosure
| is a perfectly reasonable strategy especially when we're
| operating in the academic realm. Industry always takes years
| to catch up to academia anyway.
| nine_k wrote:
| If this paper allows to produce a working RSA cracker in a
| month, much of high-value IT infrastructure is under
| imminent threat.
|
| Yes, you can replace your SSH keys with elliptic ones, and
| maybe adjust your TLS accepted algorithms. Even this is not
| always easy or cheap.
|
| But other things that may rely on RSA (or triple RSA) may
| have trouble upgrading fast, and upgrading them at all is
| going to cost a lot.
| coliveira wrote:
| If you find something that can break all cryptography in the
| world, then I think your best option (even for your personal
| security) is to release everything publicly.
| kybernetikos wrote:
| From a personal safety point of view?
| bhouston wrote:
| The first thing this will be used for is stealing Bitcoin and
| other cryptocurrency I predict. So watch out for your wallets.
| kinghajj wrote:
| Bitcoin wallets don't use RSA, but ECDSA.
| hn_throwaway_99 wrote:
| This was my exact argument:
| https://news.ycombinator.com/item?id=26323951
|
| Should be trivial to show a working proof on a smaller-than-usual
| RSA number if "this _really_ destroys RSA ".
| racecar789 wrote:
| I know a lot of programming languages, but I have never wrapped
| my head around math notation.
|
| Question for someone who is familiar math notation...was the
| abstract of this article easy to understand?
|
| For me, the abstract seems like code but no commentary explaining
| what each bloc does. But I could be mistaken.
| chmod775 wrote:
| > For me, the abstract seems like code but no commentary
| explaining what each bloc does. But I could be mistaken.
|
| You are mistaken. (Pretty much) all of mathematics is written
| as natural language, and those symbols are just abbreviations
| for stuff that could also be written as words. If I read those
| sentences out loud, another could write them back down and
| arrive at something that looks the same.
|
| That's why all of mathematical notation is embedded in
| sentences - they are _part_ of the sentence and can be read as
| such.
|
| Further that is really basic notation a first semester student
| of any STEM discipline should be able to read, though I
| wouldn't expect them to know what a lattice and some of the
| other terminology is.
| kfrzcode wrote:
| I'd love a "cheat sheet" or dictionary for mathematical
| notation. I don't know how to pronounce half of the embedded
| symbology, let alone what rules apply. It seems so esoteric
| and arbitrary sometimes, though I recognize it's most
| certainly not.
| woah wrote:
| You will not be able to understand the notation if you do not
| understand the math
| nightcracker wrote:
| For context: I'm a computer science MSc student.
|
| The notation is easy to understand (and as far as mathematical
| notation goes, really quite tame). I don't know what a nearly
| shortest vector of a lattice is in this context, but I do
| understand everything else. Note that means I have no idea how
| the actual method works, but I can understand what's being
| claimed.
| sterlind wrote:
| Not an expert at all, but you can think of lattices as
| evenly-spaced grid points in a vector space. Given a set of
| basis vectors b0..bn, and arbitrary integers a0..an, a0b0 +
| ... + anbn are points on the lattice b.
|
| You can have a "good basis" where the norms for b are low, or
| an equivalent "bad basis" with the same lattice points but
| with high norms. That's one hard problem (lattice reduction),
| but there are polynomial-time approximations.
|
| The shortest vector problem, iirc, is to find the vector with
| the smallest norm in the best possible basis of that lattice.
| wtallis wrote:
| The first half of the abstract is more akin to declaring the
| data types and structures used, and the second half is mostly a
| very high level summary of the overall method and results. It's
| not supposed to be interpreted like code. It's just setting up
| the context you need to start interpreting the meat of the
| paper, and giving you a heads-up about what background topics
| to Google if anything in the abstract sounds unfamiliar.
| dutchmartin wrote:
| For someone who took a matrix calculation (linear algebra)
| course like me, it was kinda understandable.
___________________________________________________________________
(page generated 2021-03-03 23:00 UTC)