Tid-bit: delicacy, dainty, snack, nibble, appetizer, hors d’oeuvre, goody, dipper, finger food

Adam Engst is the publisher of the site TidBITS. This is a site dedicated to technical insights about all aspects of Apple machines: from nano to servers.

Today I want to talk about mathematical tidbits not Apple devices, but look at the above site for information about Apple stuff of all kinds.

Variations on Montgomery’s trick

Peter Montgomery is a cryptographer at Microsoft. Just recently, Joppe Bos and Arjen Lenstra have edited a book titled Topics in Computational Number Theory Inspired by Peter L. Montgomery. The chapters range to Montgomery’s work on elliptic curves, factoring, evaluating polynomials, computing null-spaces of matrices over finite fields, and FFT extensions for algebraic groups. Bos and Lenstra say in their intro that most of this was “inspired by integer factorization, Peter’s main research interest since high school.” Factoring, always factoring…

Today we discuss one of Montgomery’s simpler but most influential ideas going back to a 1985 paper: how to compute mod ${N}$ when you can only do operations mod ${R}$.

An almost exponential improvement in bounds against ACC

 Source from previous paper

Cody Murray is a PhD student of Ryan Williams at MIT. He and Ryan have a new paper that greatly improves Ryan’s separation of nonuniform ${\mathsf{ACC}}$ circuits from uniform nondeterministic time classes. The previous best separation was from ${\mathsf{NEXP}}$, that is, nondeterministic time ${2^{n^{O(1)}}}$. The new one is from ${\mathsf{NQP}}$, which is nondeterministic time ${2^{(\log n)^{O(1)}}}$. The ‘Q’ here means “quasi-polynomial,” not “quantum.”

Today we discuss the new ideas that led to this breakthrough on a previous breakthrough.

Facing the awful truth that computers are physical machines

 As moderator of RSA 2016 panel

Paul Kocher is the lead author on the second of two papers detailing a longstanding class of security vulnerability that was recognized only recently. He is an author on the first paper. Both papers credit his CRYPTO 1996 paper as originating the broad kind of attack that exploits the vulnerability. That paper was titled, “Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems.” Last week, the world learned that timing attacks can jeopardize entire computing systems, smartphones, the Cloud, everything.

Today we give a high-level view of the Meltdown and Spectre security flaws described in these papers.

With wishes for a memorable New Year 2018

Muhammad Afzal Upal is Chair of the Computing and Information Science Department at Mercyhurst University. He works in machine learning and cognitive science, most specifically making inferences from textual data. In joint papers he has refined a quantitative approach to the idea of postdiction originally suggested by Walter Kintsch in the 1980s.

Today we review some postdictions from 2017 and wish everyone a Happy New Year 2018.

How we might compare AlphaZero against standards of perfection