Negligible and non-negligible

The Stanford online course, Cryptography I, describes:



What does mean "lambda >= lambda d"?

Because the epsilon is a function, we can write the lambda as x and the epsilon as f(x) for easy understanding. We specify f(x) as below, that is an example,

f(x) = 1 / (2^x)

The f(x) is negligible because,

f(x) = 1 / (2^x) <= 1 / (x^d), 
for all d and large enough x. (statement 1)

Why do we consider the statement 1 is true? I am not a mathematician. I prefer to use enough examples and tools to observe and understand problem. The tool, the iPad App Quick Graph+, is used to draw curves of the below functions.

f(x) = 1 / (2^x)
f(x) = 1 / x
f(x) = 1 / (x^2)
f(x) = 1 / (x^3)
f(x) = 1 / (x^4)



It is hard to verify the statement 1 with the picture because the curves are close to each other when x is large. Therefore we transfer the statement 1 as below.

g(x) = 2^x - x^d >= 0, 
for all d and an enough large x. (statement 2)

We give examples, d = 1, 2, 3, 4. The below picture contains the curves.


If we zoom in the picture, we can find an interesting thing.

The statement 2 is true for an enough large x.



For d = 1, g(x) = 2^x - x >= 0, 
           if x >= x1. x1 is any real number.

For d = 2, g(x) = 2^x - x^2 >= 0, 
           if x >= x2. x2 is 4

For d = 3, g(x) = 2^x - x^3 >= 0, 
           if x >= x3. x3 is about 9.94

For d = 4, g(x) = 2^x - x^4 >= 0, 
           if x >= x4. x4 is 16

Because x is also called lambda, that is what means "lambda >= lambda d".

-Count

XOR encryption is a randomized algorithm

We exactly describe that One Time Pad (OTP) encryption, that uses XOR operation, is a randomized algorithm.

Below is the definition of Randomized Algorithms:

A cipher (E, D) over (K, M, C) is OTP, so that

c = E (k, m) = k xor m

K = M = C = {0, 1}^n

For the definition of Randomized Algorithms, if k and c are uniform random variables, the OTP encryption, E, is a randomized algorithm. 

The k, selected in K, must be a uniform random variable for the reason,

Why must the key of the encryption be random?

Why is the c, calculated by the OTP encryption, also a uniform random variables? The question is same to proof the below formula that is the definition of uniform random variable.

Pr [c = c0] = 1 / |C|

Please remember that a random variable is really a function. So transform the formula to display the function E (k, m0),

Pr [c = c0] = 

Pr [E (k, m0) = c0] =

OTP encryption uses XOR operation.

Pr [k xor m0 = c0] = 

Pr [k = c0 xor m0] =

Pr [k = k0] = 1 / |K|

because there is only one k0  that encrypts m0 to generate c0. 

Pr [c = c0] = 1 / |K| = 1 / |C|  

because |K| = |C| = 2^n

We proof that the OTP encryption is a randomized algorithm.

-Count

My Proof for Shannon Theorem

In this topic, I use my informal way to proof Shannon Theorem. Yes, it is informal but easy to understand the theorem. I also proof that the substitute cipher is not perfect secrecy.

Shannon Theorem:

A cipher (E, D) over (K, M, C) has perfect secrecy
=>
|K| >= |M|

The theorem is identical the below statement.

|K| <= |M|
=>
A cipher doesn't have perfect secrecy

My proof of the theorem is to give an example.

Lets

K = {0, 1}, M = C = {0, 1}^2

We define the encryption algorithm E as below.

if k = 0,

 m  c
-----
00 00
01 01
10 10
11 11

if k = 1,

 m  c
-----
00 01
01 10
10 11
11 10

We use the below formula to verify if the cipher is perfect secrecy. It it is perfect secrecy,

Pr [E (k, m) = c] = constant

I use the both pairs

(m, c) = (00, 00) or (00, 10)

to verify it.

Pr [E (k, 00) = 00] = (# of keys) / |K| = 1/2, 

Only one key, k=0, exists.

Pr [E (k, 00) = 10] = (# of keys) / |K| = 0/2 = 0,

We cannot find a key to make the equation.

Pr [E (k, m) = c] = 1/2 or 0

Obviously, it is not constant. Therefore the cipher is not perfect secrecy. We proof it. Actually, the cipher is called substitute cipher.

-Count

Why must the key of the encryption be random?

When I learn the Stanford online course, Cryptography I, I ask my self the question: "Why must the key of the encryption be random?"

The encryption algorithm is written below.

C = E (M, K) 

where
C is ciphertext,
M is plaintext message,
K is a key,
E is an encryption algorithm.

We use XOR algorithm as encryption algorithm.

C = M XOR K.

The purpose is to make C an uniform random variable even though M is not, and specify:

Pr [M=0] = m0

Pr [M=1] = m1
m0 + m1 = 1 and 
m1 <> m2

Pr [K=0] = k0

Pr [K=1] = k1

k0 + k1 = 1

If K is not an uniform random variable, then

k0 <> k1

Below is the table of the equation, C = M XOR K.

M	K	C	Probability
0	0	0	m0 * k0
0	1	1	m0 * k1
1	0	1	m1 * k0
1	1	0	m1 * k1

We can calculate that:

Pr [C=0] = m0 * k0 + m1 * k1 <> 1/2
Pr [C=1] = m0 * k1 + m1 * k0 <> 1/2

Thus C is not a uniform random variable.

I draw the below picture to explain why the two inequalities are right.

m0 * k0 + m1 * k1 <> 1/2
m0 * k1 + m1 * k0 <> 1/2



When I see the two areas m0 * k0 and m1 * k1, I FEEL that m0 * k0 + m1 * k1 <> 1/2.

In conclusion, if we want to build a ciphertext randomly, the key must be random.

We also make sure that XOR encryption is a randomized algorithm because if the key is a uniform random variable, the output ciphertext  is also a uniform random variable.

The next page explain why XOR encryption is a randomized algorithm.

-Count

Private Keys in Blockchain Transactions

If we can answer the question "Where is private keys?" for a secure feature, we almost understand the security framework. How about the private keys in blockchain transactions?

A private key is used to derive a public key and to make a signature in a transaction. A wallet program can use the same private key for each transaction but it is not secure because it is easy to trace a user's behavior of transaction and it has a risk of being compromised.

Bitcoin Developer Guide states: "For both privacy and security, we encourage you to build your applications to avoid public key reuse and, when possible, to discourage users from reusing address."

Please image that there are 1000 different private keys generated if we have 1000 transactions. Do we need to store the all private keys? I consider the answer is No because the private key is useless after the transaction is finished. Therefore a wallet program can clean the unused private keys if it can generate a unique private key for each transaction.

-Count

The padding problem between Java Security and Windows CryptoAPI

If we use Windows CryptoAPI to encrypt plaintext with RSA to get ciphertext, the Java BadPaddingException exception happens when we use Java Security to decrypt the ciphertext with RSA.

We suppose that it is padding problem between Java Security and Windows CryptoAPI, but Windows CryptoAPI default uses PKCS1Padding in RSA, and our Java program uses Cipher.getInstance("RSA/ECB/PKCS1Padding"). Therefore both padding algorithms are same. Where is the problem?

The problem is, ciphertext encrypted by Windows CryptoAPI is little-endian, but Java Security consider ciphertext is big-endian. We can reverse ciphertext before calling RSA decrypt of Java Security.

-Count

Apple Watch Wrist Detection

If we enable password in Apple Watch, it will be locked when we take it off at 15th second in default. There are two cases of the lock scenario as the below picture.

Case A: The watch is initially worn and locked.

• 0 sec: A user inputs password to unlock the watch.
• 0 - 15 sec: The unlocked period is 15 seconds in default. The period can be specified on the watch. If the user clicks the watch in the period, the period will be reset.
• 15+ sec: If the watch is worn, it is keep being unlocked (Case A), otherwise it locks itself (Case A.1).

Case B: The watch is not initially worn and locked.

• 0 sec: A user inputs password to unlock the watch.
• 15 sec: The watch locks itself at the time.

How does Apple Watch detects wrist? I suppose the mechanism is run by photodiode sensors not by G-sensor. There are two rules of wrist detection.

1. Primary rule: Sensors detect distance between watch and wrist via infrared LEDs.
2. Secondary rule: Sensors detect lighting change to determine locking.

The primary rule is easy to be proved. How about the secondary rule? I uses the 3 methods to cheat Apple Watch to keep wearing (unlocking) status.

1. Shake a paper below the watch.
2. Put watch on an iPad that is playing video.
3. Put watch on a glass and shake a paper below the glass. 

Photo 1

Photo 2

Photo 3

-Count