1. We've been a little overwhelmed with the rate of moderator activity lately, and @rigel drew the short straw. Congratudolences are appreciated, or you could give generously to the memorial fund for his sanity.
    Dismiss Notice

Math(s)! Currently: The Long Line

Discussion in 'General Chatter' started by Exohedron, Mar 14, 2015.

  1. Exohedron

    Exohedron Doesn't like words

    I really like Wikipedia's proof of why the determinant is multiplicative: first you show that any n-linear, alternating function F from kn to k is determined by the value it takes on the identity matrix In (viewed as n vectors), and thus that the determinant is the unique such function that takes the value 1 at In, and that for any other n-linear alternating functions F, F applied to M is just F(In)det(M) by linearity in the space of multilinear functions.
    Then you note that the function dA that takes a matrix M to det(AM) is such a function, and takes the value det(A) at M = In, and so in general is just det(A)det(M).

    Step one takes a little effort, though, mostly to convince the reader that the bookkeeping works out.
     
    Last edited: Dec 30, 2018
  2. Exohedron

    Exohedron Doesn't like words

    A slight divergence from pure math stuff, because I attempted to explain some of this to my parents recently:

    Digital Signatures

    You want to send someone a letter, and you want them to be certain that you sent the letter. Conversely, you don't want people sending things under your name.
    If we have a physical letter, the traditional method is to append a signature or a seal, some symbol or sign that your intended recipient can recognize as yours and that can't be produced by anyone else.
    But forgery is a thing, duplicating someone's handwriting or copying a seal. Most of us don't have to worry about that on the physical plane, because that takes effort that aren't worth it for most people.
    But there are types of forgery that do pay well. For instance, art forgery; learning someone's painting style, techniques, materials well enough to claim that you've "found" a lost piece.

    In the digital realm, we send a lot of messages, important ones, and it's very easy to copy bits. So we need a good way of signing things that is more than just appending a bunch of bits containing your name.

    Fortunately, we have some decent public key encryption systems.
    For a recap: in a public key system, you have some algorithm E that takes a key KE and a message p and produces an encrypted string c, and a different algorithm D that takes a different key KD and the encrypted string c and produces the message p. This is different from more traditional, symmetric key cryptography, wherein the two keys are the same. In public key cryptography, because the encryption key is distinct from the decryption key, you can tell people the encryption key, and they can send you encrypted messages using the algorithm E and the key KE, but as long as you keep the decryption key secret, nobody can read those encrypted messages except for you, even if they know the algorithm D.

    So how does that help with signing things?
    A digital signature works similarly to public key encryption. You, the signer, have a key KS and a key KV, and you release KV to the public. There is an algorithm S which takes a message m and your key KS, and produces a signature h, and an algorithm V that takes a message m, a supposed signature h, and a key KV, and verifies whether the signature would be produced by S given the message and the key KS.
    Note that m also gets transmitted. The reason for this is that we want the signature to depend on the message in some fashion. Otherwise a forger could take a valid signature from one message and paste it onto a fake message, like ripping a wax seal from one letter and gluing it onto a fake letter. At the very least, the verifier wants to know that not only did they get a message from the correct person, they got the correct message from that person. This is called authentication, and is slightly different from identifying. But it's still important, because someone might intercept a legitimate message from you, mess with the contents of the message without touching the signature, and then send it onward, and you find yourself promising money to people you didn't mean to.
    Also, for the verifier's benefit, a message with a valid signature can't be repudiated by the sender, because nobody else could have produced a valid signature for that message; hence you can't deny having signed and therefore presumably having sent that message. But this is usually considered a less important aspect compared to identification and authentication.

    Having a public key encryption system actually directly helps with making a digital signature scheme. Your standard public key setup promises that
    p = D(KD, E(KE, p)))
    so that decrypting with the proper decryption key undoes an encryption with the proper encryption key. But a lot of them also have the property that
    c = E(KE, D(KD, c))
    i.e. that encrypting with the proper encryption key undoes a decryption with the proper decryption key. This is not always the case, but it is true for a lot of public key encryption systems, in particular RSA.
    So, to sign a message, you take the message m, you decrypt it using KD to get some "decrypted" h, and you use h as your signature. The verifier, knowing the corresponding key KE, encrypts h and sees if it matches m.
    Voila, a signature. If a would-be forger doesn't know your decryption key KD, they won't be able to "decrypt" m to get h, and so won't be able to produce a valid signature. Moreover, if they don't have the correct m, then the encrypted signature won't match. So we get identification and authentication.

    Okay, so I'm leaving a step out. We don't want to decrypt the entire message, because messages can be long but your signature should be short. So we cheat a little. Instead of decrypting the message, we hash the message, using a complicated function that takes in messages and produces short strings of nonsense. Then we decrypt the hashed message to get a short signature. Then the verifier compares the encrypted signature with the hash of the message.
    The danger here is if two messages generate the same hash in a predictable manner. Fortunately, we also have decent hash functions.

    So that's what your computer is doing under the hood every time it tries to send a message that needs to be trustworthy. It hashes the message, turns the hash into a signature, and then sends the message and the signature; conversely, every time it receives a signed message, it processes the signature, hashes the message, and checks if it got matching results. If the signature corresponds to the message, great. If not, someone is trying to pull a fast one. Or something got garbled during transmission; either way, don't trust the message.

    Now, I'm sure some of you are thinking "wait, isn't RSA going to be insecure when we have quantum computers? Aren't all of our public key systems currently in use going to be insecure against quantum computation? Doesn't that mean that our digital signature algorithms will be insecure?" And the answer is yes.

    So in the future, possibly the near future, we are going to need both encryption algorithms that will stand up against a quantum computer, and digital signature schemes that will stand up against a quantum computer. It seems, from what I can tell, that signature schemes are slightly easier to come up with than encryption algorithms, due to how they handle what each person needs to know, but it's still a hard problem.
     
  3. Exohedron

    Exohedron Doesn't like words

    For reasons, I am currently liveblogging a math paper in my bijou blogette here. The paper, Homological Tools for the Quantum Mechanic, by Tom Mainiero, is about detecting factorizability of tensors via cohomology, available on the arXiv here.
    If you want to see someone reacting in uninformative ways to what is really a small book (126 pages) then you can follow the tag #MathPaperLiveBlog.*

    * I don't know if you can actually follow in a meaningful fashion other than watching the thread and/or searching for "#MathPaperLiveBlog" in the search bar.
     
    Last edited: Jan 26, 2019
  4. Exohedron

    Exohedron Doesn't like words

    Today I learned that a map between Poisson manifolds that preserves the Poisson structure is called an ichthyomorphism.
     
    • Winner x 4
    • Informative x 2
  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice