# HG changeset patch # User Christian Urban # Date 1419031477 0 # Node ID 5b91f5ad27727ec3145cf43fda3a4b432d77c8c7 # Parent e1e0f78baa705362c1b901cd4338b0222cb12605 updated diff -r e1e0f78baa70 -r 5b91f5ad2772 handouts/ho02.pdf Binary file handouts/ho02.pdf has changed diff -r e1e0f78baa70 -r 5b91f5ad2772 handouts/ho02.tex --- a/handouts/ho02.tex Thu Dec 18 15:51:19 2014 +0000 +++ b/handouts/ho02.tex Fri Dec 19 23:24:37 2014 +0000 @@ -54,12 +54,14 @@ polls, but to my knowledge does not use any e-voting in elections. -\item The US used mechanical machines since the 1930s, later - punch cards, now DREs and optical scan voting machines. - But there is a lot of evidence that DREs and optical - scan voting machines are not as secure as they should - be. Some states experiment with Internet voting, but - all experiments have been security failures. +\item The US used mechanical machines since the 1930s, later punch + cards, now DREs and optical scan voting machines. But there is a + lot of evidence that DREs and optical scan voting machines are not + as secure as they should be. Some states experimented with Internet + voting, but all experiments have been security failures. One + exceptional election happened just after hurrican Sandy in 2012 when + some states allowed emergency electronic voting. Voters downloaded + paper ballots and emailed them back to election officials. \item Estonia used since 2007 the Internet for national elections. There were earlier pilot studies for voting @@ -485,6 +487,14 @@ \end{center} \noindent +Another passionate plea to not use electronic voting is the youtube +video + +\begin{center} +\url{https://www.youtube.com/watch?v=w3_0x6oaDmI} +\end{center} + +\noindent Two researchers from Galois, Inc., present an interesting attack against home routers which silently alters pdf-based voting ballots. This shows that the vote submission via diff -r e1e0f78baa70 -r 5b91f5ad2772 handouts/ho06.tex --- a/handouts/ho06.tex Thu Dec 18 15:51:19 2014 +0000 +++ b/handouts/ho06.tex Fri Dec 19 23:24:37 2014 +0000 @@ -394,6 +394,11 @@ \ldots still to be completed (for example can be attacked by MITM attacks) +\subsubsection*{Further Reading} + +Make sure you understand what NP problems +are.\footnote{\url{http://en.wikipedia.org/wiki/NP_(complexity)}} They +are the building blocks for zero-knowledge proofs. \end{document} diff -r e1e0f78baa70 -r 5b91f5ad2772 handouts/ho09.pdf Binary file handouts/ho09.pdf has changed diff -r e1e0f78baa70 -r 5b91f5ad2772 handouts/ho09.tex --- a/handouts/ho09.tex Thu Dec 18 15:51:19 2014 +0000 +++ b/handouts/ho09.tex Fri Dec 19 23:24:37 2014 +0000 @@ -75,14 +75,14 @@ yes---if a compiler can find out that for example a variable will never be negative and this variable is used as an index for an array, then the compiler does not need to generate code -for an underflow-test. Remember some languages are immune to +for an underflow-check. Remember some languages are immune to buffer-overflow attacks, but they need to add underflow and -overflow checks everywhere. If the compiler can omit the -underflow test, for example, then this can potentially -drastically speed up the generated code. According to the John -Regehr, an expert in the field of compilers, overflow checks -can cause 5-10\% slowdown, and in some languages even 100\% -for tight loops.\footnote{\url{http://blog.regehr.org/archives/1154}} +overflow checks everywhere. According to Regehr, an expert in +the field of compilers, overflow checks can cause 5-10\% +slowdown, and in some languages even 100\% for tight +loops.\footnote{\url{http://blog.regehr.org/archives/1154}} If +the compiler can omit the underflow check, for example, then +this can potentially drastically speed up the generated code. What do programs in our simple programming language look like? The following grammar gives a first specification: @@ -264,12 +264,13 @@ snippets for the rest of the program. If yes, then we do the same, but also update the map so that $label$ now points to the rest of the statements. There is one small problem we need -to overcome: our two programs have no label as \emph{entry -point}---that is where the execution starts. We usually assume -that the first statement will be run first. To make this the -default, it is convenient if we add to all our programs a -default label, say \pcode{""} (the empty string). With this we -can define our pre-processing of programs as follows +to overcome: our two programs shown so far have no label as +\emph{entry point}---that is where the execution is supposed +to start. We usually assume that the first statement will be +run first. To make this the default, it is convenient if we +add to all our programs a default label, say \pcode{""} (the +empty string). With this we can define our pre-processing of +programs as follows \begin{center} $\textit{preproc}(prog) \dn \textit{snippets}(\pcode{"":}\;\; prog)$ @@ -368,7 +369,7 @@ whenever we have a number in our program, we just return this number---this is defined in the first clause above. Whenever we encounter an addition, well then we first evaluate the -left-hand side, $\texttt{e}_\texttt{1}$ of the addition (this +left-hand side $\texttt{e}_\texttt{1}$ of the addition (this will give a number), then evaluate the right-hand side $\texttt{e}_\texttt{2}$ (this gives another number), and finally add both numbers together. Here is the subtlety: on @@ -394,15 +395,15 @@ At the moment however, we are a poor fallible god. Look again at the grammar of our programming language and our definition. -Clearly, an expression can contain variables. So far we we +Clearly, an expression can contain variables. So far we have ignored them. What should our interpreter do with variables? They might change during the evaluation of a program. For example the variable \pcode{n} in the factorial program counts down from 5 up to 0. How can we improve our definition above to give also an answer whenever our interpreter encounters a variable in an expression? The solution is to add an -\emph{environment}, $env$ as an additional input argument to -our \textit{eval\_exp} function. +\emph{environment}, written $env$, as an additional input +argument to our \textit{eval\_exp} function. \begin{center} \begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l} @@ -430,17 +431,27 @@ \end{center} \noindent This environment $env$ also acts like a map: it -associates variable names with the current value. In the -clause for variables, we therefore consult this environment -and return whatever value is currently stored for this -variable. This is written $env(x)$ indicating that the -environment acts like a function. If we call the function with -$x$ we obtain the corresponding number. What happens if an -environment does not contain any value for, say, the variable -$x$. Well, then our interpreter just crashes, or will raise an -exception. In this case we had a ``bad'' program that tried to -use a variable before it was initialised. With the second -version of \textit{eval\_exp} we completed our definition for +associates variable with their current values. For example +such an environment might look as follows + +\begin{center} +\begin{tabular}{ll} +$\fbox{\texttt{a}} \mapsto \texttt{1}$ & +$\fbox{\texttt{n}} \mapsto \texttt{5}$ +\end{tabular} +\end{center} + +\noindent Again I hilighted the keys. In the clause for +variables, we can therefore consult this environment and +return whatever value is currently stored for this variable. +This is written $env(x)$. If we query this map with $x$ we +obtain the corresponding number. You might ask what happens if +an environment does not contain any value for, say, the +variable $x$? Well, then our interpreter just crashes, or will +raise an exception. In this case we have a ``bad'' program +that tried to use a variable before it was initialised. The +programmer should not have don this. With the second version +of \textit{eval\_exp} we completed our definition for evaluating expressions. Next comes the evaluation function for statements. We define