May 2018 - mathfun@mailman.xmission.com

[math-fun] number arithmetic: power side-channels?
by Henry Baker 20 May '18

20 May '18

I've been thinking about the *power* side-channel: the ability to watch instantaneous power consumption to guess what a computer is computing. Closely related: the chip temperature side-channel: the ability to watch instantaneous temperature distributions across a chip to guess what a computer is computing. Note that simple power supply filtering doesn't work well enough, as one might be able to watch enough computation to still be able to discern some amount of information. Since many computers would like to keep confidential what they are computing, the question is raised: **Are there computer arithmetic circuits which draw the same sequence of instantaneous power draws *regardless* of the numbers being computed or moved?** For example, some computer circuit may draw slightly more power when a "1" appears on a bus instead of a "0". Under these conditions, it might make sense to drive the bus with both the number and its binary complement, in order to keep the power draw the same, no matter what bit pattern is being operated on. Are there particular number representations and arithmetic circuits (or even *boolean circuits*) whose power consumption is indifferent ("oblivious") to the input bit patterns? Note that CMOS typically utilizes both PNP and NPN transistors in a complementary fashion. However, due to semiconductor physics, these transistors are not 100% complementary -- especially at high clock rates -- and therefore they don't provide as much obliviousness as one would like, so assume for this conversation that we might still have to mirror even CMOS gates.

8 10

[math-fun] Unsolved number theory problem
by Dan Asimov 19 May '18

19 May '18

Which integers S are the sum of three cubes: S = J^3 + K^3 + L^3 ??? (None of the form S == ±4 (mod 9), for instance.) Some low numbers are hard to find the J, K, L for, like: 30 = (−662037799708799)3 + 1908092688412843 + 6567116892545653 . The first S for which a solution is unknown is 33. The complete list of S < 1000 with no known solution (as far as I can tell) is as follows: 33 42 114 165 390 579 627 633 732 795 906 921 975 . —Dan

2 1

Re: [math-fun] number arithmetic: power side-channels?
by Henry Baker 19 May '18

19 May '18

Thanks, Mike. This is indeed the type of attack that computers processing private information can be subjected to. Paul Kocher has done some terrific work, and I've watched a number of his talks on YouTube. Much of his earlier work had to do with watching crypto algorithms on smart cards and computers. More recently he's been active on Spectre (cache timing side-channel) vulnerability. However, it has become clear (!) that nearly *all* computing has some privacy aspects, so nearly all computers & computations will have to start incorporating resistance to side-channel attacks such as timing (which may be "visible" from thousands of miles away) to power and electromagnetic side-channels, which may be visible for tens of meters -- e.g., it might even be possible to hack a Wifi router's radio receiver to detect certain electromagnetic emissions from a nearby laptop. There may be severe performance consequences as a result of such side-channel resistance: greatly increased compute times, greatly increased compute energies, much more expensive shielding, etc. Nevertheless, just as our automobiles have had to incorporate crash-resistance, fail-safe and ABS brakes, and other safety measures, computers will have to have analogous improvements. At 02:45 PM 5/16/2018, Mike Stay wrote: >Paul Kocher did lots of research along these lines. >https://www.rambus.com/introduction-to-differential-power-analysis-and-rela… > >On Wed, May 16, 2018 at 3:39 PM, Henry Baker <hbaker1(a)pipeline.com> wrote: >> Constant power might not be too cool, but may be >> unavoidable for certain calculations -- e.g., AES >> encryption/decryption. It would be an interesting >> theorem if constant power were the *only* solution. >> >> Some sort of "tri-stating with memory" might allow >> lower power consumption for the vast majority of >> wires that won't be changing on every clock cycle. >> Having a wire stay at either "0" or "1" for long >> periods of time doesn't cost anything, but changing >> the state of a wire does cost the charging/discharging >> of the capacitance of the wire. >> >> In this type of logic, the problem won't be "1's" or >> "0's", but transitions: "+1", "-1". So the game may >> be to have a double-width bus where half the bus gets >> XOR'd with <secret> and the other half gets XOR'd >> with not-<secret>, so that exactly length-<secret> >> bits change. >> >> I think it may be possible to build systems having >> both "secret" and "non-secret" bits; the only >> constraint is that the instantaneous power is >> independent of the secret bits -- i.e., the >> power computation function is a *tautology* of >> the secret bits. >> >> This leads us to consider a circuit design system >> which outputs circuits both for the value to be >> computed, as well as another circuit which computes >> the power/energy consumed by the computation. It >> is up to the circuit design system to make sure that >> the two sets of circuits are in sync. >> >> While we're at it, we can also output a circuit >> that computes the *timing* for the value-computing >> circuit. For many situations, this circuit may be >> trivial, but for others -- e.g., carry-propagation -- >> this circuit may not be trivial. >> >> At 01:47 PM 5/16/2018, Tom Knight wrote: >>>There are circuit topologies (as opposed to semiconductor technologies) that compute both the true and complement of every signal. To a very good first approximation, the power dissipated is constant in these circuits independent of the data flowing through them. The downside is that power dissipation is constant, but high. ECL logic is an early bipolar version, but similar topologies can be built with NMOS or CMOS technologies. It might be appropriate to use these topologies in security-sensitive applications. >>> >>>> On May 16, 2018, at 1:46 PM, Henry Baker <hbaker1(a)pipeline.com> wrote: >>>> I've been thinking about the *power* side-channel: >>>> the ability to watch instantaneous power consumption >>>> to guess what a computer is computing. >>>> >>>> Closely related: the chip temperature side-channel: >>>> the ability to watch instantaneous temperature >>>> distributions across a chip to guess what a computer >>>> is computing. >>>> >>>> Note that simple power supply filtering doesn't >>>> work well enough, as one might be able to watch >>>> enough computation to still be able to discern >>>> some amount of information. >>>> >>>> Since many computers would like to keep confidential >>>> what they are computing, the question is raised: >>>> >>>> **Are there computer arithmetic circuits which draw >>>> the same sequence of instantaneous power draws >>>> *regardless* of the numbers being computed or moved?** >>>> >>>> For example, some computer circuit may draw slightly >>>> more power when a "1" appears on a bus instead of a >>>> "0". Under these conditions, it might make sense to >>>> drive the bus with both the number and its binary >>>> complement, in order to keep the power draw the same, >>>> no matter what bit pattern is being operated on. >>>> >>>> Are there particular number representations and >>>> arithmetic circuits (or even *boolean circuits*) >>>> whose power consumption is indifferent ("oblivious") >>>> to the input bit patterns? >>>> >>>> Note that CMOS typically utilizes both PNP and NPN >>>> transistors in a complementary fashion. However, >>>> due to semiconductor physics, these transistors are >>>> not 100% complementary -- especially at high clock >>>> rates -- and therefore they don't provide as much >>>> obliviousness as one would like, so assume for >>>> this conversation that we might still have to mirror >>>> even CMOS gates. > >-- >Mike Stay - metaweta(a)gmail.com >http://www.math.ucr.edu/~mike >http://reperiendi.wordpress.com

2 2

[math-fun] D. Wilson
by James Propp 18 May '18

18 May '18

Does anyone have updated contact information for* wilson(a)ctron.com*? Thanks, Jim Propp

3 3

[math-fun] Who wrote this paper?
by Henry Baker 17 May '18

17 May '18

Well, I'm not 100% certain, but *someone* must have written a paper *sometime* about positional number systems using an *algebraic* and/or *algebraic integer* radix and integer numerals. Knuth? Knuth? Anyone? Anyone? Several interesting things: If p(r) is the minimal polynomial for r, and deg(p)=n, then we can express r^n in terms of lower powers of r, and thus there is some possible redundancy in the representations. Also, if n>1, then there are multiple r's satisfying p(r)=0, so we have to relate representations using r and r', s.t. p(r)=p(r')=0. Clearly, complex number systems of the 1+i type qualify, but I don't recall any such systems with n>2. Also, cyclotomic polynomials have the same unfortunate property that base-(e^i) numbers have -- namely, it is a lot more difficult to represent large numbers.

8 15

[math-fun] The Muffin Problem -- my gang solved one of your conjectures
by William Gasarch 17 May '18

17 May '18

In Jan 2009 this email list discussed the Muffin Problem which was due to Alan Frank: You have m muffins to give out to s students. You want to give everyone m/s muffins. How to divide-and-distribute and maxmize the min piece. We let f(m,s) be the size of the smallest piece in the opt procedure. I saw the problem at Gathering for Gardner 2016 and worked on it for two years (unaware of the discussions on this list). I read over all the discussion done here (thanks to Jim Propp's arxiv of it) and there was not much overlap: 1) Erich Friedman prove f(m,s) = (m/s)f(s,m) 2) Veit Elser proved that f(m,s) can be computed by a Mixed Int Program 3) Someone conjectured that for m>s f(m,s) \ge 1/3. That last conjecture we proved! Here are pointers to where to look for our work 1) Conference proceeding for FUN with Algorihtms: https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/ffmuff.pdf The appendix has the proof of f(m,s) \ge 1/3 2) slides on a talk I give on the problem: https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/muffintalk.pdf 3) the long long papers on it on arxiv (not recommended- but one day it will be better) https://arxiv.org/abs/1709.02452

1 0

[math-fun] Draft of May 2018 blog post
by James Propp 15 May '18

15 May '18

I started writing a new draft titled "Time and Tesseracts" and would love to get your comments, whether I receive them before or after I publish the essay on my blog (late on the 16th or early on the 17th). Sorry for the many rough spots near the end, which I plan to work on over the next couple of days. Even after the 17th I'm likely to continue to tinker with the piece, and feedback will be gratefully acknowledged. (I'm aware that the footnote-links don't work, but there are probably lots of other glitches I'm unaware of.) Please leave your feedback here: https://mathenchant.wordpress.com?p=2303&shareadraft=5afa4b14f3cc0 but be aware that the feedback-link is a "party line"; if I receive an unsigned comment there, all I'll know is that it's from some math-fun subscriber. (Which may be your intention. But if you have a comment I want to act upon, I may have some follow-up questions for you, such as "Is the following rewrite less terrible?", which I won't be able to ask you if I don't know who you are!) Title: Time and Tesseracts Beginning: "The fourth dimension became a thing you talked about, without knowing what it meant." --- Marcel Duchamp 16th-century scholar Gerolamo Cardano1 thought the fourth dimension was contrary to Nature. 17th-century thinker John Wallis2 thought the very idea of it was monstrous. And now 21st century virt... Read more: https://mathenchant.wordpress.com?p=2303&shareadraft= 5afa4b14f3cc0 Thanks, jamespropp

1 0

[math-fun] Tetrahedral hypercube projection
by James Propp 14 May '18

14 May '18

Let u, v, w, and x be the vectors from the center of a tetrahedron to the four vertices. Does the zonohedron formed by the fifteen vectors u, v, w, x, u+v, u+w, u+x, v+w, v+x, w+x, u+v+w, u+v+x, u+w+x, v+w+x, and u+v+w+x=0 have a name? Better, are there images of it on the web? Better still, are there gifs or videos that show it rotating in a way that brings its three-dimensionality to the fore? I ask because this seems like a nice way of looking at a hypercube (leaving aside the defect that two of the vertices of the hypercube coincide). Jim Propp

6 10

[math-fun] (no subject)
by Bob Mayans 14 May '18

14 May '18

http://general.myglenwoodhomes.com Bob Mayans

1 0

[math-fun] What is this function? puzzle
by Bill Gosper 13 May '18

13 May '18

Wow. Experimentally, it's also x+1 for -1≤x≤0, -x-1 for -2≤x≤-1, and √(1-2x-x²) for -3≤x≤-2, wherein it goes imaginary. gosper.org/puzfn.png It can probably be guessed anywhere. Where has it been proven? Note the tiny flat spot in the imaginary part near x = -3.5. --rwg On 2018-05-12 03:54, James Propp wrote: > Could f be a polynomial? Assuming deg f is at least 1, Joerg’s equation > implies 2 deg f = 1 + def f, so we’ll need def f = 1. Putting f(x) = ax+b > in Joerg’s equation, we get (ax+b)^2 - 1 = x (ax+a+b), or > > (a^2) x^2 + (2ab) x + (b^2 - 1) = (a) x^2 + (a+b) x, > > with unique solution a=b=1. > > So I’m guessing f(x) = x+1. > > Jim Propp > > On Saturday, May 12, 2018, Joerg Arndt <arndt(a)jjj.de> wrote: > >> f(x)^2 - 1 = x * f(x+1) >> No idea how to proceed from there, though. >> >> Best regards, jj >> >> >> * Dan Asimov <dasimov(a)earthlink.net> [May 05. 2018 08:20]: >> > Define a function f : [0,oo) —> R via >> > >> > f(x) = sqrt(1 + x*sqrt(1 + (x+1)*sqrt(1 + (x+2)*sqrt(1+... >> > >> > Evaluate f(x) in closed form. >> > >> > —Dan

1 0