INFO-231:

Introduction to
Mathematical Foundations of
Security
Yan Huang
yh33@indiana.edu
 Yan Huang
Research Interests:
Security
Algorithms
Functional Programming Systems
Cryptography

I am looking for motivated undergraduate researchers.

Course Administrivia
• Web site: http://homes.soic.indiana.edu/yh33/Teaching/I231-2016/syllabus.html
• TA: Ruiyu Zhu (zhu52@indiana.edu)
Office Hours: Tuesday 1-2. GA 1st floor Lobby
• Textbooks: (both from Cambridge University Press)
-[required] Programming in Haskell, Graham Hutton
-[required] A Cryptography Primer: Secrets and Promises,
Philip Klein
-[recommended] An Introduction to Mathematical
Cryptography, J. Hoffstein, J. Pipher, J. H. Silverman
Goals of this course
• Stimulate your interests in
-Mathematics
-Computer programming

• Some useful Math ideas

-Prepare for later courses
-Benefit your future career
Components of this course

Haskell
Algebra Probability
programming

Computational
Applications
Complexity
Grades
Home work 40%
Quiz 20%
Final 40%

ü Every homework assignment counts.

ü No late homework will be accepted.
ü Final grades are curved at the end of the semester.
Homework Policy
• You can discuss the problems with other students in
the class, but everyone should type up the answers
independently.
• On your submitted paper
-Credit who you have obtained help from
-Write down who you have offered help to
• Plagiarism will always be reported and cause a failure
of this course.
More policies
• Quizzes
- Closed book, Closed notes
- Can happen during any lecture
- Zero point on quizzes in lectures of your absence
- Three worst scores automatically dropped (e.g., due to missing attendance)
- Class attendance is required unless you demonstrate to me that you mastered
the lecture contents in advance. Must obtain permission to skip lectures.
• Final
- Open book, take home
- No collaboration
- Must type up and submit electronically
How to get an A+?
• Factorize the following number
189721033099831854220700797842841354892470928484226462861838184732495
886835944169521825942409750174014649148448296440574720913526137987437
473357773230905553892237303084784011168818947451081579379097447822881
667432882904379382192765785334484626092964491724567613895658573635823
440320704164445430154614611228964821896107965926838383389899407160291
009707165203728441693191054364480704346562993029545686786243942022722
547324163598311076715637428198166427036328133401910860218006553001325
991055259400990064904499288444751897045897700726555141998311062645769
93649173200857755181189779752280025089963275809434722408052661993
• Finish your assignments reasonably well and demonstrate your ability of
proactive learning
- Study relevant materials not covered/required in class
- Implement challenging stuff
- Solve optional problems Do talk to me in advance to
settle down your specific plans
Environment Setup
Bring your laptop to class
- Quizzes
- Try out ideas on the fly.
Madoko
• https://www.madoko.net/
- Connects well with Dropbox, Github, Onedrive etc.
• Detailed reference manual:
http://research.microsoft.com/en-
us/um/people/daan/madoko/doc/reference.html
• You are required to type up your assignments using either
Madoko or LaTeX.

Daan Leijen, creator of Madoko.

 Madoko

• Italic • Inline math

*important* => important $ f(x) = x^2 + 1 $

• Boldface • Displayed math

~ Equation { #eqn-label }
**important** => important W = F \cdot s
~
Madoko
• Superscripts (^) and Subscripts (~)
- E.g., Black_pit_, Ball~sky~
• Strike out (~~, two tildes)
- E.g., There is a ~~strike out~~ here.
• Links
- E.g., [Google](http://www.google.com).
• Images
![bfly]
[bfly]: images/butterfly-200.png "A Monarch" { width:
100px }
Madoko Blocks

• Block for Displayed math • Equivalently

~ Equation ~ Begin Equation
W = F \cdot s W = F \cdot s
~ ~
• Nested blocks
~ Equation
F=ma
~~ Equation
An nested equation distinguished by double tildes
~~
~
 Madoko 1
\frac{1}{n}
𝑛

• $...$ marks the region where 𝑥$ x_1

LaTeX math-mode applies Lim \lim

• LaTeX symbol lookup: mod \mod

http://detexify.kirelabs.org/cl → \rightarrow

assify.html ∞ \infty
Madoko
• Embedding program code

``` haskell
main = print “Hello World!”
```
Why Haskell?
•Present math ideas
-Precise
-Succinct
-Easy to experiment
•A bonus skill to your adventurous future
§ Functional programming: the basic method of
computation is application of functions to arguments
Why Haskell? A language that doesn't affect the
way you think about programming
is not worth knowing.

A good programming language is a

conceptual universe for thinking
about programming.

-- Alan Perlis
Professor of Yale
The first Turing Award Laureate
Historical Background
1930s:

Alonzo Church develops the lambda calculus, a

simple but powerful theory of functions.
Historical Background
1950s:

John McCarthy develops Lisp, the first functional

language, with some influences from the lambda
calculus, but retaining variable assignments.
Historical Background
1970s:

John Backus develops FP, a functional

language that emphasizes higher-order
functions and reasoning about programs.
Historical Background
1970s:

Robin Milner and others develop ML, the first

modern functional language, which introduced type
inference and polymorphic types.
Historical Background
1987:

An international committee of researchers

initiates the development of Haskell, a
standard lazy functional language.
Historical Background
1990s:

Phil Wadler and others develop type classes and

monads, two of the main innovations of Haskell.
Historical Background
2003:

The committee publishes the Haskell Report,

defining a stable version of the language; an
updated version was published in 2010.
Historical Background
2010-date:

Standard distribution, library support, new

language features, development tools, use in
industry, influence on other languages, etc.
Example Practical Uses
• Haxl — Facebook's anti-spam program
• Cryptol — A language and toolchain for developing and
verifying cryptography algorithms
• seL4 — The first formally verified microkernel
…
Example Haskell Code
• Summing the integers 1 to 10 in Java:
int total = 0;
for (int i = 1; i <= 10; i++)
total = total + i;

The method of computation is variable assignment.

• In Haskell, this is simply a one-liner

sum [1..10]
Installing Haskell
GLASGOW HASKELL COMPILER (GHC)
• Freely available
https://​www.​haskell.​org/​platform/​
• A leading implementation of Haskell comprising a compiler
ghc and an interpreter ghci
• The interactive nature of the interpreter makes it well-suited
for teaching and prototyping
Starting GHCi

$ ghci

GHCi, version X: http://www.haskell.org/ghc/ :? for help

Prelude λ:

“Prelude λ:” prompts for Haskell expressions to evaluate.

GHCi as a desktop calculator

Prelude λ: 2+3*4
14
Prelude λ: (4+1)*5
25
Prelude λ: 3^2
9
Prelude λ: sqrt (3^2 + 4^2)
5.0
The Standard Prelude
Haskell comes with a large number of standard
library functions. E.g., the library also provides
many useful functions on lists.
z Select the first element of a list:

Prelude λ: head [1,2,3,4,5]

1
z Remove the first element from a list:

Prelude λ: tail [1,2,3,4,5]

[2,3,4,5]

z Select the nth element of a list: (list index starts from 0)

Prelude λ: [1,2,3,4,5] !! 2
3

z Select the first n elements of a list:

Prelude λ: take 3 [1,2,3,4,5]

[1,2,3]
z Remove the first n elements from a list:

Prelude λ: drop 3 [1,2,3,4,5]

[4,5]

z Calculate the length of a list:

Prelude λ: length [1,2,3,4,5]

5

z Calculate the sum of a list of numbers:

Prelude λ: sum [1,2,3,4,5]

15
z Calculate the product of a list of numbers:

Prelude λ: product [1,2,3,4,5]

120

z Append two lists:

Prelude λ: [1,2,3] ++ [4,5]

[1,2,3,4,5]

z Reverse a list:

Prelude λ: reverse [1,2,3,4,5]

[5,4,3,2,1]
Function Application
In mathematics, function application is denoted using
parentheses, and multiplication is often denoted using
juxtaposition or space.

f(a,b) + c d

Apply the function f to a and b, and add the

result to the product of c and d.
In Haskell, function application is denoted using
space, and multiplication is denoted using *.

f a b + c*d

As previously, but in Haskell syntax.

Moreover, function application is assumed to
have higher priority than all other operators.

fa+b

Means (f a) + b, rather than f (a + b).

Examples
Mathematics Haskell
f(x) fx
f(x,y) fxy

f(g(x)) f (g x)

f(x,g(y)) f x (g y)

f(x)g(y) fx*gy

f(-1) f (-1)
Useful GHCi Commands
Command Meaning

:load name load script name

:reload reload current script
:set editor name set editor to name
:edit name edit script name
:edit edit current script
:type expr show type of expr
:? show all commands
:quit quit GHCi
Charge
• Haskell
- Install Haskell Platform on your computer.
- Try out the GHCi evaluations covered in this lecture.

• Madoko
- Read through Madoko’s reference manual
- Try out Madoko tricks as you read the manual.

• Homework 0 announced
- Start early!
- Submit through Canvas