text:
# PLZZZ help i beg look at picture firsttt

###### Question:

PLZZZ help i beg look at picture firsttt

### In the play The Diary of Anne Frank, which event interrupts the Hanukkah celebration in the Secret Annex? 1. a fight between Mr. Dussel and Peter 2. a noise from the warehouse downstairs 3. Mrs. Frank becoming ill from eating rotten potatoes 4. Mr. Frank telling everyone to be quiet or they'll be discovered please help! I think it is the last one but I am not sure?

In the play The Diary of Anne Frank, which event interrupts the Hanukkah celebration in the Secret Annex? 1. a fight between Mr. Dussel and Peter 2. a noise from the warehouse downstairs 3. Mrs. Frank becoming ill from eating rotten potatoes 4. Mr. Frank telling everyone to be quiet or they'll be di...

### A yearbook printer charges based on the number of pages printed. Here is a table that shows the cost of some recent yearbooks. Numbers of pages: 50, 100, 150, 200 Cost:-------------------> 1.55, 2.25, 2.95, 3.65 which equation gives the cost, y, in terms of the number of pages, x? y=0.014x+49.15 y=0.014x+1.55 y=0.014x+0.85 y=58.8x+0.85

A yearbook printer charges based on the number of pages printed. Here is a table that shows the cost of some recent yearbooks. Numbers of pages: 50, 100, 150, 200 Cost:-------------------> 1.55, 2.25, 2.95, 3.65 which equation gives the cost, y, in terms of the number of pages, x? y=0.014x+49.15 ...

### Solve for x: |2x + 12| = 18 x = 3, x = –3 x = 3, x = –15 x = 15, x = –15 x = –3, x = 15

Solve for x: |2x + 12| = 18 x = 3, x = –3 x = 3, x = –15 x = 15, x = –15 x = –3, x = 15...

### Which of the following is a radical equation X + square root of 5 =12 X^2 =16 3 + X square root of 7 =13 7 square root of x =14

Which of the following is a radical equation X + square root of 5 =12 X^2 =16 3 + X square root of 7 =13 7 square root of x =14...

### Is the GCF of two numbers is equal to the lesser of the numbers?

Is the GCF of two numbers is equal to the lesser of the numbers?...

### What should health-care professionals refrain from doing to ensure quality health care for all patients? A. Stereotyping and having prejudices against certain people B. Using nonverbal communication such as hand gestures C. Referring patients to other health care professionals D. Sharing patient charts with the patients families E. Hiring an interpreter to communicate with patients

What should health-care professionals refrain from doing to ensure quality health care for all patients? A. Stereotyping and having prejudices against certain people B. Using nonverbal communication such as hand gestures C. Referring patients to other health care professionals D. Sharing patient ch...

### Identify the design of the following study. A researcher classifies students according to three parental income groups and also according to three possible score ranges on the SAT examination. He randomly selects two students from each of the nine (Income, SAT) combinations. The researcher records the grade point averages (GPA) of those sample members at the end of the sophomore year. a. Randomized block design b. Two-Factor ANOVA with replication c. One-way ANOVA

Identify the design of the following study. A researcher classifies students according to three parental income groups and also according to three possible score ranges on the SAT examination. He randomly selects two students from each of the nine (Income, SAT) combinations. The researcher records t...

### Who the richest man ever?

Who the richest man ever?...

### If the Earth is tilted on it's axis, does that mean the world is always turning up??

If the Earth is tilted on it's axis, does that mean the world is always turning up??...

### 19. In each of the following ligures, find the values of x and y

19. In each of the following ligures, find the values of x and y...

### Select the correct verb form to complete this statement. Yo _____ muy contenta. vuelvo veilvo velvo volvo

Select the correct verb form to complete this statement. Yo _____ muy contenta. vuelvo veilvo velvo volvo...

### In 3 to 5 sentences, analyze potential impacts of oceans on human populations as the result of climate change in the current century.

In 3 to 5 sentences, analyze potential impacts of oceans on human populations as the result of climate change in the current century....

### Round to 2 decimal places * 1 point An architect is designing a building topped with a hemispherical dome. She creates a scale model of the building using a scale of 0.25 inch : 1 foot. In the scale model, the diameter of the dome is 23.75 inches. What will be the circumference, in feet, of the actual dome?

Round to 2 decimal places * 1 point An architect is designing a building topped with a hemispherical dome. She creates a scale model of the building using a scale of 0.25 inch : 1 foot. In the scale model, the diameter of the dome is 23.75 inches. What will be the circumference, in feet, of the actu...

### What are nights like in Vietnam, and how does it affect Rat Kiley?

What are nights like in Vietnam, and how does it affect Rat Kiley?...

### Find the value of x in the figure A. 40* B. 50* C. 140* D. 180 Please help me

Find the value of x in the figure A. 40* B. 50* C. 140* D. 180 Please help me...

### Factor the GCF: −6x4y5 − 15x3y2 + 9x2y3

Factor the GCF: −6x4y5 − 15x3y2 + 9x2y3...

### Max fischer is a bookkeeper his annual trip insurance cost 11700 his employer

max fischer is a bookkeeper his annual trip insurance cost 11700 his employer...


text:
# Does continuity in one variable and locally Lipschitz in another imply uniformity in the first?

I understand the definition of Lipschitz functions when talking of functions of single variables. However, I have trouble understanding it when it is a multivariable function.

Suppose $f(t,x):D \times \mathbb{R} \to \mathbb{R}$ is continous in $t$ and locally Lipschitz in $x$ for each fixed $t \in D$ where $D= [t_0,t_1] \subset \mathbb{R}$. Here $D$ is a closed finite interval. In other words, for every fixed $t$ there exists some local Lipschitz constant $L$ such that $|f(t,x_1) -f(t,x_2)| \leq L|x_1 - x_2|$. Local is understood to mean that for some $x_0 \in \mathbb{R}$ we have $x_1,x_2$ belong to a neighborhood of $x_0$.

Does this imply that $f$ is locally Lipschitz in $x$ uniformly in $t \in D$?

Here uniformly means that for all $t \in D$ the Lipschitz constant is independent of $t$ i.e given $x_0$ and some neighborhood of $x_0$ there exists some maximal Lipschitz constant $L_*$ that works for all $t \in D$.

Intuitively I don't think the implication holds. However, I have not been able to come up with a counter example with D defined to be a closed finite interval. With D defined as an open set, various counter examples exist.

Also, if you impose conditions that $D$ is compact and that $f(t,x)$ can be written as $f(t,x)=g(t)h(x)$ or $f(t,x)=g(t)+h(x)$ it can be shown than $g(t)$ achieves its maximum in $D$ and that $L$ defined as a function of this maximum works for all $t$.

However I am looking for proof that the implication holds in the general case (D is closed and finite, f(t,x) has no special form) OR for a valid general counter example.

## migrated from mathoverflow.netFeb 12 '16 at 5:54

This question came from our site for professional mathematicians.

Taking $D = [0,1]$, I think $f(t,x) = t \sin(x/t^2)$ is a counterexample.
(Here of course $f(0,x)=0$.)
• I am not so sure. The function is bounded above by 2 in $D$. For example, $$\left| {f\left( {t,x} \right) - f\left( {t,y} \right)} \right| = \left| {t\sin \left( {x/{t^2}} \right) - t\sin \left( {y/{t^2}} \right)} \right|$$ $$\left| {f\left( {t,x} \right) - f\left( {t,y} \right)} \right| \leq \left| t \right|\left| {\sin \left( {x/{t^2}} \right) - \sin \left( {y/{t^2}} \right)} \right|$$ $$\left| {f\left( {t,x} \right) - f\left( {t,y} \right)} \right| \leq 2\left| t \right| \leq 2\left| t \right|\left| {x - y} \right|$$ Then we can chose $L=2|t|$ which in $D$ is 2. – ITA Feb 11 '16 at 22:24
• @IvanAbraham: Your last inequality $2|t| \le 2 |t| |x-y|$ isn't right - this inequality is supposed to hold for any $x$ and $y$, even when $|x-y|$ is very small. In fact, since $f(t, \cdot)$ is $C^1$ its best Lipschitz constant on a neighborhood is the supremum of its derivative (with respect to $x$) on that neighborhood - and you can directly compute that this goes to infinity as $t \to 0$. – Nate Eldredge Feb 11 '16 at 23:01
• @IvanAbraham: Explicitly, take $t = 0.01$, $x=0$ and $y = 0.0001 \pi/2$. Then $|f(t,x)-f(t,y)| = 0.01$ while $2 |t| |x-y| \approx 0.0000031415$. – Nate Eldredge Feb 11 '16 at 23:16
• Yes you are right, the inequality would have needed to be multiplied by $|x-y|$ on both sides and not just on the right to hold. My bad. I am accepting your answer, because after looking at some plots I get the intuition. As $x,y$ get arbitrarily close to each other $f(.,.)$ doesn't. Is there any way to formally show that $L=L(t)$ along the lines I was proceeding? Or does one have to do an $\epsilon - \delta$ type of construction? – ITA Feb 12 '16 at 0:09
• I think this works: $$\left| {f\left( {t,x} \right) - f\left( {t,y} \right)} \right| = \left| {t\sin \left( {x/{t^2}} \right) - t\sin \left( {y/{t^2}} \right)} \right|$$ $$\leq \left| t \right|\left| {\sin \left( {x/{t^2}} \right) - \sin \left( {y/{t^2}} \right)} \right|$$ $$\left| {f\left( {t,x} \right) - f\left( {t,y} \right)} \right| \leq 2\left| t \right| \Rightarrow \left| {x - y} \right|\frac{{\left| {f\left( {t,x} \right) - f\left( {t,y} \right)} \right|}}{{\left| {x - y} \right|} }$$ $$\leq \frac{{2\left| t \right|}}{{\left| {x - y} \right|}}\left| {x - y} \right| = L|x-y|$$ – ITA Feb 12 '16 at 0:54

format: plain


text:
I will give an online talk on Wednesday 12pm New York time (EDT) as part of the “Symbolic Computations and Post-Quantum Cryptography” seminar series. My talk is titled “Polly Cracker Revisited” and I’ll present classical and noisy problems in multivariate polynomial rings and how they relate to homomorphic encryption. I will post my slides here afterwards.

Edit: Slides with typos and all that.

# Algorithms for LWE and the Approximate GCD Problem over the Integers

Let $n$ be the number of variables in some polynomial ring $\mathbb{R}[x_1,\dots,x_n]$ (with $\mathbb{R}$ a ring) and let $d$ be the degree of a bunch of polynomials $F = [f_1,\dots,f_m]$ in $\mathbb{R}$, i.e., $\deg(f_i) = d$. Of course, we can “solve” $F$ by computing a Gröbner basis on $F$. Furthermore, it is well-known that if $n=1$ computing a GB is equivalent to computing the GCD of $F$ and that if $d=1$ computing a GB is equivalent to Gaussian elimination, i.e., finding a triangular basis for a module. In a nutshell, Gröbner bases generalise GCDs and Gaussian elimination. So far, so classical.

It is no secret that I spent some time looking into a problem which we call Gröbner Bases with Noise (GBN), which again can be seen — with the appropriate choice of parameters — as a generalisation of the LWE problem (cf. these slides for some details. Sorry, the paper is still not done). Similarly, we may consider GBN as a generalisation of an approximate GCD problem over $\mathbb{R}[x]$.

In our work (you know, the one which isn’t done yet), we define GBN over $\mathbb{F}_q$ to keep things simple but the notion can easily be extended to for example $\mathbb{Z}$. Hence, one could say GBN over $\mathbb{Z}$ is a generalisation of GCDs over $\mathbb{Z}[x]$ and in particular over $\mathbb{Z}$ (cf. this paper which constructs a homomorphic encryption scheme based on the approximate GCD problem over the integers) which is just $\mathbb{Z}[x]$ restricted to constant polynomials. So, we have a connection between GBN, LWE and the approximate GCD problem.

Now, as my tag cloud gives away, I like linear algebra and have the tendency to think about problems in terms of linear algebra and triangular bases. Hence, the above connection made me think about the applicability of algorithms for solving LWE to the approximate GCD problem over the integers. It turns out, they are applicable (kinda).

# Cryptanalysis of “Fully Homomorphic Encryption over the Binary Polynomials”

Turns out, I’m not he only one who was inspired to adapt the Fully Homomorphic Encryption over the Integers scheme by van Dijk, Gentry, Halevi and Vaikuntanathan to polynomials.  Gu Chunsheng posted a pre-print on the IACR eprint server this week which essentially instantiates the integer scheme over univariate polynomials over $\mathbb{F}_2$.  Below is my implementation (in Sage) of his somewhat homomorphic scheme:

class BinPolySHE:
def __init__(self, n):
n = n
tau = n # choice here
P = PolynomialRing(GF(2),'x')

x = P.gen()

s = P.random_element(degree=2*n+1)
while not (s.is_irreducible() and s.degree()==2*n+1):
s = P.random_element(degree=2*n+1)

b = []

a0 = P.random_element(2*n+1)
if a0.degree() < 2*n+1:
a0 += x**(2*n+1)
e0 = P.random_element(degree=n-1)
b0 = a0*s + x*e0 # deg: 4*n+2

b.append(b0)

for i in range(1,tau):
ai = P.random_element(degree=n) # choice here
ei = P.random_element(degree=n-1)
bi = ai*s + x*ei # deg 3*n+1
bi = bi % b0
b.append(bi)

self.n = n
self.pk = b
self.sk = s
self.P = P

def encrypt(self, m):
T = []

for i in range(1, len(self.pk)):
if random() <= 0.5: # choice here
T.append(i)

c = self.P(m%2)

x = self.P.gen()

for i in T:
e = self.P.random_element(degree=self.n-1)
c += self.pk[i] + x*e

return c % self.pk[0]

def decrypt(self, c):
x = self.P.gen()
return (c % self.sk) % x

Regular readers of this blog might have noticed that the scheme looks like a bit like a univariate specialisation of this PollyCracker scheme. Indeed, just like this first PollyCracker scheme, Gu’s scheme is badly broken. Below, the source code of my attack:

    def attack(self, c):

A = Matrix(GF(2),len(self.pk),4*self.n+2)

x = self.P.gen()

for i,b in enumerate(self.pk):
for j in b.exponents():
A[i,A.ncols()-j-1] = 1
E = A.echelon_form(reduced=False)

pk2 = []
for i,r in enumerate(A.rows()):
b = 0
for j in range(A.ncols()):
b += E[i,A.ncols()-j-1]*x**j
pk2.append(b)

for b in pk2:
if c[b.degree()]:
c -= b
return c % x

The attack proceeds pretty much as discussed here: we can compute a triangular basis for the span of the public key and use that to perform all eliminations. Since the noise does not grow with each addition and does not affect the constant coefficient (which holds the message), we can essentially ignore it.

# Polly Cracker Revisited – Slides

I just gave a talk in the ISG seminar at Royal Holloway, University of London about this Polly Cracker business I’ve been thinking about lately. I’ve also decided to publish the slides. However, I’d like to stress that everything in there is preliminary, i.e. this is yet another of those presentations presenting work in progress (which I personally think is a good thing to do). Anyway, here’s the abstract:

“Since Gentry’s seminal work on homomorphic encryption, this area has received considerable attention from the cryptographic community. Perhaps one of the most natural homomorphic schemes conceivable is Polly Cracker which is naturally homomorphic. However, almost all Polly Cracker inspired schemes that have been proposed so far have been badly broken. In fact, it was conjectured about 15 years ago in “Why you cannot even hope to use Gröbner Bases in Public Key Cryptography: an open letter to a scientist who failed and a challenge to those who have not yet failed.”that it was impossible to construct a secure Polly Cracker-style scheme.

In this work we initiate a formal treatment of cryptosystems based on the hardness of Gröbner basis computations for random systems of equations, discuss their limitations, why standard techniques from homomorphic encryption research fail in this area, and propose a Polly Cracker variant based on polynomial system solving with noise which is a first step towards a provably secure Polly Cracker public-key scheme.”

# Cryptanalysis of my Somewhat Homomorphic PollyCracker Scheme

About 5 months ago I wrote about a homomorphic scheme based on integers and an adaptation of this schemes to use multivariate polynomials. At the very end I wrote:

“Of course, I assume that my adaptation above can still be broken somehow since that’s what tends to happen with multivariate crypto schemes. Also, I’m really really not an expert on public-key cryptography. Hey, this is a blog post, not a research paper … so break it in the comments

Well, with some delay, here is how to break it. Recall, that the secret is some Gröbner basis $g_0,\dots,g_{n-1}$ in $\mathbb{F}[x_0,\dots,x_{n-1}]$ (assume $\mathbb{F}_2$ for simplicity) and that a ciphertext is constructed as

$c = \sum_{i=0}^{n-1} f_ig_i + m' + m$

where $m'$ has constant coefficient 0 and $f_i$ are random polynomials. Now, let $\deg(f_i) = Q, \deg(g_i) = P, \deg(m') = N$ with $N < P$ to ensure correct decryption (i.e. no interference of the noise with the normal form computation).

To break the scheme simply request $n^(P+Q)$ encryptions of zero and compute the row echelon form on the linearisation of those polynomials of degree $P+Q$ without elimination above the pivot (i.e. don’t compute the reduced row echelon form). Throw away any element of degree $\leq N$ and call the resulting list $S$. This list $S$ allows to decrypt any ciphertext $c$ by reducing $c$ modulo $S$.

Below, the attack in Sage:

class PolynomialHomomorphic:
def __init__(self, l):
self.l = l
K = GF(2) # pick some field
# we choose a ring with l unknowns, which
# should make any GB computation at least
# as hard as 2^l if we pick the ideal sufficiently
# random.
R = PolynomialRing(K, l, 'x', order='degrevlex')
self.K = K
self.R = R
# our small ideal, defines the message space.
self.b = Ideal([x for x in R.gens()])

# these parameters are pretty arbitrary from a
# security perspective!
self.N = 1
self.P = 2
self.Q = 1
self.key_gen()

def key_gen(self):
b,l = self.b, self.l
K, R = self.K, self.R
# we pick a random ideal with l element of degree P
p = [R.gen(i)**self.P + R.random_element(degree=self.P-1)
for i in range(l)]
self.p = Ideal(p)

def encrypt(self, m):
# we pick some m' which encodes the
# same plaintext but is bigger
m = self.R(m)
mprime = self.R.random_element(degree=self.N)
mprime -= mprime.constant_coefficient()
mprime += m.constant_coefficient()

# adding a random ideal element
for f in self.p.gens():
mprime += self.R.random_element(degree=self.Q)*f
return mprime

def decrypt(self, c):
# decryption is just as in the integer case.
return c.reduce(self.p).reduce(self.b)

def break_cpa(pc, challenge):
ciphertexts = [pc.encrypt(0) for _ in xrange(2*pc.l**(pc.Q+pc.P))]
F = Sequence(ciphertexts)
A,v = F.coefficient_matrix(sparse=False)
E = A.echelon_form(full=False)
s = dict([(f.lm(),f) for f in (E*v).list() if f.degree() >= pc.P])

while True:
print challenge
if challenge.lm() in s:
challenge = challenge - s[challenge.lm()]
else:
if challenge.degree() > pc.P:
raise ValueError("Ah, snap! It didn't work.")
else:
return challenge.constant_coefficient()

This works because the noise is constructed in such a way as to never interfere with elimination: it does not affect any leading monomial of the ideal ever. Thus, we don’t need to consider it during the elimination and simply ignore the lower terms once we are done.

Note that this attack does not work against the integer homomorphic scheme by van Dijk et al. because there additions are not free: When we perform elimination of the higher order bits in the integer scheme also the noise accumulates; eventually it surpasses the size of the prime $p$ leaving us with no information. Put differently, we can attack schemes that are inspired by the integer-based scheme if additions are free. Thus, while it might seem tempting to replace integers by, say, univariate polynomials which are often considered essentially computationally equivalent to integers and which would provide free additions  it would break the security of the scheme.

# Somewhat Homomorphic Encryption

Today I read the paper “Computing Arbitrary Functions of Encrypted Data” by Craig Gentry in which he explains the basic ideas behind his work on fully homomorphic encryption. If you don’t know what homomorphic encryption is: it means that one can evaluate a function on ciphertexts which has the same result as evaluating that function on the plaintexts. Thus, one can compute with data without getting to see it. The canonical example Gentry uses in his papers is a search engine that searches through sensitive data without seeing the actual content. It is similar to secure multi-party computation except that it is not interactive at all, i.e. you send your query and get the result back without any interaction in between. In the above mentioned paper Gentry gives a simplified version of a recent integer based fully homomorphic scheme. This simplified version is symmetric and only somewhat homomorphic (more on this below). Since the basic idea of the scheme is so simple, it is quickly implemented. The code below is actually some slight generalisation such that b isn’t always forced to be two.

class IntegerHomomorphic:
def __init__(self, l, b=2):
self.b = b
self.l = l  # lambda is out security parameter
# these parameters determine the size
# of various numbers and are chosen such that
# the approximate GCD is assumed to be hard.
self.N = 2**(l)
self.P = 2**(l**2)
self.Q = 2**(l**5)
self.key_gen()

def key_gen(self):
# the secret key is simply an odd number of P bits.
p = ZZ.random_element(0, self.P-1)
if p%self.b == 0:
p += ZZ.random_element(1, self.b)
self.p = p

def encrypt(self, m):
# we want to encrypt 0 <= m < b, thus we pick some m'
# for which m' % b == m % b holds to avoid having
# known bits (== 0) in the computation below.
mprime = ZZ.random_element(0,self.N-1)
mprime = mprime - mprime%self.b + m%self.b
# the ciphertext is this m' with some multiple of p
q = ZZ.random_element(0,self.Q-1)
return mprime + self.p*q

def decrypt(self, c):
# if we now p decryption is easy since we can simply
# mod out p and then recover the value mod b
return ZZ((c % self.p) % self.b)

To see that this scheme is somewhat homomorphic observe that as long as the noise is small enough such that things don’t wrap around we have and for some number .

Here is a toy example:

sage: IH = IntegerHomomorphic(3,)
sage: IH.encrypt(0)
1269419566719153208598601566220616500605965999\
730518673686683244436179224382
sage: IH.encrypt(0) + IH.encrypt(1)
61002356472659294938919367702545237501719846898\
35782651710838758570047089506
sage: IH.decrypt(IH.encrypt(0) + IH.encrypt(1))
1
sage: IH.decrypt(IH.encrypt(0) + IH.encrypt(1)*IH.encrypt(1))
1

However, there is only a limited number of operations we can perform before we overflow, hence the “somewhat homomorphic” in the title:

sage: IH.decrypt(prod(IH.encrypt(1) for _ in range(1000)))
0
sage: IH.decrypt(prod(IH.encrypt(1) for _ in range(1000)))
1

The security of this construction can be reduced (according to the paper, I didn’t check it) to the approximate GCD problem, that is: given and , compute or in and . The problem hasn’t received much attention so far. Currently it is assumed to be hard if and have bits, has bits and has bits.

Thus, the size of the scheme is both bounded by the gap between and which dictates how much computations one can fit before wrapping around and the sizes required for the approximate GCD to be hard. Of course, if you spent more than three years starring at multivariate polynomial ideals you will have noticed by now that this whole scheme can be instantiated using multivariate polynomial ideals as well:

class PolynomialHomomorphic:
def __init__(self, l, b=2):
self.l = l
K = GF(127)  # pick some field
# we choose a ring with l unknowns, which
# should make any GB computation at least
# as hard as 2\^l if we pick the ideal sufficiently
# random.
R = PolynomialRing(K, l, 'x', order='degrevlex')
self.K = K
self.R = R
# our small ideal, defines the message space.
self.b = Ideal([x for x in R.gens()])

# these parameters are pretty arbitrary from a
# security perspective!
self.N = 1
self.P = 2
self.Q = 5
self.key_gen()

def key_gen(self):
b, l = self.b, self.l
K, R = self.K, self.R
# we pick a random ideal with l element of degree P
p = [R.random_element(degree=self.P) for _ in range(l)]
self.p = Ideal(p)

def encrypt(self, m):
# we pick some m' which encodes the
# same plaintext but is bigger
m = self.R(m)
mprime = self.R.random_element(degree=self.N)
mprime -= mprime - mprime.reduce(self.b)
mprime += m.reduce(self.b)

# adding a random ideal element
for f in self.p.gens():
mprime += self.R.random_element(degree=self.Q)*f
return mprime

def decrypt(self, c):
# decryption is just as in the integer case.
return c.reduce(self.p).reduce(self.b)

This scheme looks a bit similar to PolyCracker where the security was also related to normal form computations. PolyCracker was broken because normal forms are simpler than Gröbner bases, that is you don’t necessarily need a Gröbner basis to compute them. However, in this scheme you must find the ideal first, before you can start thinking about whether you need a Gröbner basis of it or not. Of course, I assume that my adaptation above can still be broken somehow since that’s what tends to happen with multivariate crypto schemes. Also, I’m really really not an expert on public-key cryptography. Hey, this is a blog post, not a research paper … so break it in the comments 🙂

Anyway, here’s a toy example:

sage: PH = PolynomialHomomorphic(2)
sage: f = PH.encrypt(3) * PH.encrypt(2) * PH.encrypt(1) + PH.encrypt(2)
sage: PH.decrypt(f)
8

Of course, this is just the first step. The really cool stuff happens after this simple step. Gentry constructs a fully homomorphic scheme from such a somewhat homomorphic scheme … if you want to know how, go read the paper 🙂

Update: See this post for a break of this scheme and corrected Sage code.


text:
# Challenge

This is a simple one: Given a positive integer up to 1,000,000, return the closest prime number.

If the number itself is prime, then you should return that number; if there are two primes equally close to the provided number, return the lower of the two.

Input is in the form of a single integer, and output should be in the form of an integer as well.

I don't care how you take in the input (function, STDIN, etc.) or display the output (function, STDOUT, etc.), as long as it works.

This is code golf, so standard rules apply—the program with the least bytes wins!

# Test Cases

Input  =>  Output
------    -------
80     =>      79
100    =>     101
5      =>       5
9      =>       7
532    =>     523
1      =>       2
• Hi and welcome to PPCG!. To avoid down voting due to lack of quality I suggest you to post it to the sandbox first and after a couple of days post it here Mar 27 '19 at 15:17
• This is one of the outputs requested in this challenge. Mar 27 '19 at 15:24
• Very closely related but not quite identical. Mar 27 '19 at 15:35
• @Arnauld I saw that one, but I thought that they were different enough to warrant a new question. Mar 27 '19 at 15:37
• See also OEIS A051697. Mar 28 '19 at 8:52

Swift, 186 bytes

func p(a:Int){let b=q(a:a,b:-1),c=q(a:a,b:1);print(a-b<=c-a ? b:c)}
func q(a:Int,b:Int)->Int{var k=max(a,2),c=2;while k>c && c != a/2{if k%c==0{k+=b;c=2}else{c=c==2 ? c+1:c+2}};return k}

Try it online!

ÆpæRÆnạÞƲ2>?2Ḣ

Try it online!

# Python 2, 93 bytes

lambda n:sorted(range(1,3*n),key=lambda x:abs(x-n)if all(x%k for k in range(2,x))else 2*n)[0]
• You don't need the f= in the start Mar 27 '19 at 20:46
• @EmbodimentofIgnorance Thanks, fixed that along with the range and non-prime penalty criteria that was causing n=1 to fail Mar 27 '19 at 21:00
• The primality check doesn't work for Fermat pseudoprimes such as 341=31*11 which it calls prime.
– xnor
Mar 27 '19 at 21:16

# Ruby, 67 bytes

def p n;n.prime?;end;def a b,c=0;p(b-c)?b-c:p(b+c)?b+c:a(b,c+1);end

Try it online!

# TSQL query, 155 bytes

USE master
DECLARE @ INT=1000000;

WITH C as(SELECT abs(number-500+@)r,abs(number)+2s
FROM spt_values)SELECT top 1r FROM c
WHERE 0not in(SELECT c.r%s FROM c d
WHERE c.r>s)ORDER BY abs(r-@),r

Try it online

• @TobySpeight thanks for improving my answer. Can you please explain what this <!-- language-all: lang-sql --> does? Is it something I should include in all my answers ? Mar 28 '19 at 19:24
• That's a prettify hint; you can find out about it near the end of Editing Help. Mar 28 '19 at 22:18

# C# (Visual C# Interactive Compiler), 87 bytes

n=>{int i=0;for(;n<2||Enumerable.Range(2,n-2).Any(x=>n%x<1);n+=++i%2<1?-i:i);return n;}

Try it online!

# Ruby-rprime, 39 bytes

Relies on the idea that for any positive integer $$\n\$$, the $$\n\$$th prime is always larger than $$\n\$$.

->n{Prime.take(n).min_by{|i|(i-n).abs}}

Try it online!

# Zsh, 101 92 91 90 bytes

-9 by collapsing the body into the head of p's loop, -1 from using i=j instead of i=$1 in main loop, -1 by replacing a && with a ,. p(){for ((n=2;n<$1&&$1%n++;)): (($1==n))&&<<<$1} j=$1
for ((i=j;;++j,--i))p $i||p$j&&exit

57 48 bytes to the prime testing function, 43 41 bytes to the main loop (1 byte to the newline between them):

p(){  # prime function: takes one input, outputs via return code
for (( n = 2; n < $1 &&$1 % n++; ))   # divisibility check in loop header
:                 # no-op loop body
(( $1 == n )) && # if we looped up to$1:
<<< $1 # echo out$1. Otherwise, this will return false
}

For the last condition, we can't use the shorter (($1-n))||, because we need to return false to the main loop if we didn't find a prime. We print in the function to avoid complexity in the main loop. j=$1                          # set i = j = $1. Doing one in and one out is smallest for (( i = j; ; ++j , --i )) # loop indefinitely, increment and decrement p$i || p $j && exit # if either$i or \$j was a prime, exit

Conditionals are left-associative, which we take advantage of here. We do test the starting number twice to make the decrement logic simpler.

# Wolfram Language (Mathematica), 22 bytes

RiemannR/*Round/*Prime

Try it online!

This is an approximate solution that by chance works for all of the given test cases, but gives a slightly wrong result for other inputs. The Riemann R function is an approximation of the prime-counting function, which we round to the nearest integer and then request the prime number of that index.

# C (gcc), 78 65 bytes

f(n,i,j){for(i=j=0;j-1;i++)for(j=n+=i%2?-i:i;--j,n-1&&n%j;);i=n;}

Try it online!

f(n,i,j){
for(i=j=0;j-1;i++)      //while j!=1
for(j=n+=i%2?-i:i;  // step to next closest value to original input n
--j,n-1&&n%j;); // find greatest factor which is less than j
i=n;                    //return
}
• @ceilingcat division by 0 when n=1
– att
Aug 26 '19 at 22:32

# TI-BASIC (TI-84+), 74 Bytes

Ans→A:{2,3→A:For(P,5,2A,2:If min(remainder(P,seq(X,X,3,1+√(P),2:P→∟A(1+dim(∟A:End:abs(A-∟A:∟A(1+sum(not(cumSum(Ans=min(Ans

Hexdump:
(Token hex-values found here.)

72 04 41 3E 08 32 2B 33 04 41 3E D3 50 2B 35 2B | Ans→A:{2,3→A:For(P,5,
32 41 2B 32 3E CE 1A EF 32 50 2B 23 58 2B 58 2B | 2A,2:If min(remainder(P,seq(X,X,
33 2B 31 70 BC 50 11 2B 32 3E 50 04 EB 41 10 31 | 3,1+√(P),2:P→∟A(1
70 B5 EB 41 3E D4 EE B2 41 71 EB 41 3E EB 41 10 | +dim(∟A:End:abs(A-∟A:∟A(
31 70 B6 B8 BB 29 72 6A 1A 72                   | 1+sum(not(cumSum(Ans=min(Ans

Input is an integer in Ans. Output is printed implicitly.
Note: due to limitations on how large lists can be, $$\A\$$ is limited to $$\0 \le A \le 3953\$$

Explanation:

Ans→A                                  ;store the input in a variable called "A"
{2,3→A                                 ;store the list {2 3} into a list called "A"
For(P,5,2A,2                           ;loop from 5 to two times the input using a step
; of 2
seq(X,X,3,1+√(P),2  ;generate a list of integers from 3 to 1 + the
; square root of the loop counter using a step of 2
; (e.g. P=21, list={3 5})
remainder(P,                    ;then take the loop counter modulo each element
; (e.g. P=21, list={0 1})
If min(                                ;if all of the resulting elements are non-zero,
; then
P→∟A(1+dim(∟A                          ;add the loop counter's value to the list "A", the
; list of primes
End
abs(A-∟A                               ;subtract the input from the primes list and take
; the absolute value of each element (distance to
; each prime)
1+sum(not(cumSum(Ans=min(Ans        ;find the first index of the minimum value
∟A(                                    ;then use that index to get the value in the primes
; list at that index
;implicit output

Examples:

100:prgmCDGF1F
101
5:prgmCDGF1F
5
80:prgmCDGF1F
79


text:
Because Sonnets Aren't Enough

Computer Science Level 5

Sonnet 18

Shakespearean Sonnets take up the rhyme scheme

$AB\,AB \quad CD\,CD \quad EF\,EF \quad GG$

Each letter describe each similar line ending. If two lines rhyme, they are assigned the same letter.

What is the number of possible rhyme schemes a poetry with 14 lines can have?

×


text:
03-476 Ira Herbst, Erik Skibsted
Absence of quantum states corresponding to unstable classical channels: homogeneous potentials of degree zero (621K, Postscript) Oct 28, 03
Abstract , Paper (src), View paper (auto. generated ps), Index of related papers

Abstract. We develop a general theory of absence of quantum states corresponding to unstable classical channels. A principal example treated in detail is the following: Consider a real-valued potential $V$ on $\mathbf{R}^{n}$, $n\geq2$, which is smooth outside zero and homogeneous of degree zero. Suppose that the restriction of $V$ to the unit sphere $S^{n-1}$ is a Morse function. We prove that there are no $L^{2}$--solutions to the Schr\"odinger equation $i\partial_t \phi=(-2^{-1}\Delta +V)\phi$ which asymptotically in time are concentrated near local maxima or saddle points of $V_{|S^{n-1}}$. Consequently all states concentrate asymptotically in time near the local minima. Short-range perturbations are included.

Files: 03-476.src( 03-476.keywords , HS_271003.ps )


text:
### Cosmology III

The horizon problem: the universe has a finite age, so even light can only have travelled a finite distance by any given time. The CMB from all parts of the sky is at the same temperature (to one part in 105), but points more than 2 degrees apart are not causally connected (calculation to come later), so there seems to be no reason for the whole CMB to be at the same temperature. This is the horizon problem.

The structure problem: Anisotropies in the CMB are the progenitors of the large scale structures we see today. In order to observe such structures, perturbations (amplitude of fluctuations) must have existed in the density spectrum on scales that would have been outside the horizon until recently. Causal processes could not have generated such perturbations.

How can we solve these problems? The proposed solution is-

Inflationary expansion: a period in the evolution of the universe when the scale factor was accelerating, i.e. $\ddot{a}>0$.

Back to the Friedmann equation:

$(\frac{\dot{a}}{a})^2=\frac{8\pi G}{3}\rho-\frac{kc^2}{a^2}$

${\dot{a}}^2=\frac{8\pi G}{3}\rho a^2-kc^2$

Differentiate w.r.t. time-

$2\ddot{a}\dot{a}=\frac{8\pi G}{3}\dot{\rho}a^2+=\frac{16\pi G}{3}\rho a \dot{a}$

Fluid equation: $\dot{\rho}=-\frac{3\dot{a}}{a}(\rho+\frac{p}{c^2})$

Substitute-

$2\ddot{a}=-8\pi Ga(\rho+\frac{p}{c^2})+\frac{16\pi G}{3}\rho a$

$\frac{\ddot{a}}{a}=-4\pi G\rho -\frac{4\pi Gp}{c^2}+\frac{8\pi G\rho}{3}$

$\frac{\ddot{a}}{a}=\frac{4\pi G}{3}(\rho+\frac{3p}{c^2})$

This is the acceleration equation.

Given a positive density, to satisfy $\ddot{a}>0$, we need

$\rho+\frac{3p}{c^2}<0$

$p<\frac{-\rho c^2}{3}$

We can achieve this by including a cosmological constant with an equation of state $p=\frac{-\rho}{c^2}$

Put cosmological constant into Friedmann equation.

$H^2=\frac{8\pi G}{3}\rho-\frac{kc^2}{a^2}+\frac{\Lambda}{3}$

Now suppose the last term dominates

$\Rightarrow (\frac{\dot{a}}{a})^2=\frac{\Lambda}{3}$

$a(t)=e^{\sqrt{\frac{\Lambda}{3}}t}$

an exponential increase in the scale factor.

After some time, inflation must come to an end (end of a phase transition)- then the universe continues to expand in the way we thought it was before.

Inflation is believed to have lasted for 10-35 seconds, but during this time, all cosmic dimensions would be amplified by a factor of 1050.

Note: at the time of inflation, the time required for expansion by a factor of 2 was 10-35 seconds, but today the time required would be 1017 seconds.

Solution to the flatness problem: remember, for $|\Omega-1|=\frac{|k|}{a^2H^2}$ we saw that the LHS is an increasing function of time, driving Ω away from 1. Inflation drives it away-

$\ddot{a}>0 \Rightarrow \frac{d}{dt}(\dot{a})>0 \Rightarrow \frac{d}{dt}(aH)>0$

So inflation makes Ω so close to 1 that all subsequent expansion between the end of inflation and the present is insufficient to move it away again.

Solution to the horizon problem: a region which is the same order of size as the horizon before inflation could encompass the entire observable horizon today. The particle horizon expands superluminally during inflation.

How much expansion do we need from inflation? Inflation ends at 10-34 seconds. The expansion is perfectly exponential and Ω is now near to 1. We’ll assume that the universe is radiation dominated at this point, and that now $|\Omega_0-1|\leq 0.01$.

Age of Universe ~1017 sec

Radiation dominated $\Omega-1 \propto t$

$|\Omega(t_0)-1|\leq 0.01 \Rightarrow |\Omega(10^{-34}s)-1\leq 10^{-54}$

For constant H during inflation, $|\Omega(t_0)-1|\propto \frac{1}{a^2}$

This basic calculation gives us that a is increased by a factor of 1027 during inflation.

The principle of equivalence: Einstein tells us that “all local freely falling, non-rotating laboratories are fully equivalent for the performance of all physical experiments”. In other words, it is always possible to choose a local co-ordinate system such that all the laws of physics have the same form as they do in an unaccelerated gravity-free Cartesian system (in easy to understand terms, basically we don’t need to keep learning new laws of physics every time we go somewhere). When it comes to space-time, this simplifies things greatly- acceleration=gravitation=curvature.

Event: a location in space-time at (x,y,z,t).

World line: the trajectory of a body moving through space-time. A body at a fixed location in space follows a world-line parallel to the time axis, in the direction of increasing time. A body moving in space follows a world line making a slope with respect to the time axis. Since a body or signal cannot exceed the speed of light, there is a maximum slope to such world lines.

For a given point in time, we have a light cone (see the diagram on the Cosmology II page). Light cones act as cosmological horizons, separating the knowable from the unknowable.

Proper time: if we choose a frame in which A and B occur at the same spatial location (xA=xB), then the time measured between the two events is the proper time Δτ.

$\Delta\tau=\frac{\Delta S}{c}$

Proper distance is measured between A and B in a frame in which they occur simultaneously.

Geodesics: when space-time is curved by the presence of mass, the straightest possible world-lines are called geodesics. In curved space, a geodesic has a maximum or minimum interval; a massless particle like a photon follows a null-geodesic with $\int\sqrt{(ds)^2}=0$

Effect of mass on space-time: three fundamentals-

1. Mass acts on space-time, telling it how to curve.
2. Space-time acts on mass, telling it how to move.

The metric explains how to calculate distance intervals.

$ds^2=\sum_{a,b}g_{ab}dx^adx^b$

ds=line element of proper time

dxa, dxb=co-ordinate intervals

gab is the metric; it is a symmetric second-rank tensor (NxN matrix).

Euclidean 2-space

$ds^2=1.dx^2+0.dxdy+0.dydx+1.dy^2$

i.e. Pythagoras’ theorem.

$g_{ab}= \left[ \begin{array}{ cc} 1&0 \\ 0&1 \end{array} \right] = diag(1,1)$

Minkowski space-time

$ds^2=-c^2dt^2+dx^2+dy^2+dz^2$

$ds^2=-c^2dt^2+dr^2+r^2(d\theta^2+\sin^2\theta d\phi^2)$

A light pulse will expand spherically at speed c-

$dx^2+dy^2+dz^2=dr^2=c^2dt^2$

But the motion is purely radial, so dθ=dФ=0 and ds2=0.

No proper time elapses- characteristic of a light ray (so everything works as we thought it did).

Homogeneous and isotropic metrics: a special class of metrics are those which describe isotropic space-time. For these, the purely spatial part of the metric dl2 may be written-

$dl^2=f(r,t)(dx^2+dy^2+dz^2)$

$dl^2=f(r,t)(dr^2+r^2d\theta^2+r^2\sin^2\theta d\phi^2)$

An example of a homogeneous and isotropic metric is-

$g_{00}=g_{00}(t); g_{0i}=0$

$f(r,t)=a^2(t)(1+\frac{kr^2}{4})^{-2}$

Friedmann-Robertson-Walker metric (FRW metric) for homogeneous and isotropic space-time.

$ds^2=-c^2dt^2+(a(t))^2(1+\frac{kr^2}{4})^{-2}[dr^2+r^2d\theta^2+r^2\sin^2\theta d\phi^2]$

or equivalently

$ds^2=-c^2dt^2+(a(t))^2[d\chi^2+\chi^2(d\theta^2+\sin^2\theta d\phi^2)]$

(this is the called the ‘co-moving form’ of the metric).

χ=sin r for k>0

χ=r for k=0

χ=sinh r for k<0

Another alternative-

$ds^2=-c^2dt^2+(a(t))^2[\frac{dr^2}{1-kr^2}+r^2d\theta^2+r^2\sin^2\theta d\phi^2]$

Here, k can be identified with the Gaussian curvature of space, 1/radius2

Deriving cosmological redshift from the FRW metric (go on, you know you want to): For a light ray, ds=0; also, dθ=dФ=0 for a radial path travelled from the point of the light’s emission at χe to its arrival at the Earth at χ=0.

The FRW metric looks like:

$ds^2=-c^2dt^2+(a(t))^2[\frac{dr^2}{1-kr^2}+r^2d\theta^2+r^2\sin^2\theta d\phi^2]$

For a light ray

$ds^2=-c^2dt^2+(a(t))^2[\frac{dr^2}{1-kr^2}$

Suppose that one crest of the light wave was emitted at time te and received at to and the next crest was emitted at tete and received at toto.

$\frac{dt}{a(t)}=\frac{1}{c}\frac{d\chi}{\sqrt{1-k\chi^2}}$

First crest $\int_{t_e}^{t_o} \frac{dt}{a(t)}= \frac{1}{c} \int_0^{\chi_e} \frac{d\chi}{\sqrt{1-k\chi^2}}$

Next crest $\int_{t_e+\Delta t_e}^{t_o+\Delta t_o} \frac{dt}{a(t)}= \frac{1}{c} \int_0^{\chi_e} \frac{d\chi}{\sqrt{1-k\chi^2}}$

Subtracting these equations ->

$\int_{t_e+\Delta t_e}^{t_o+\Delta t_o} \frac{dt}{a(t)}- \int_{t_e}^{t_o} \frac{dt}{a(t)}=0$

But

$\int_{t_e+\Delta t_e}^{t_o+\Delta t_o} \frac{dt}{a(t)}= \int_{t_e}^{t_o} \frac{dt}{a(t)}+ \int_{t_o}^{t_o+\Delta t_o} \frac{dt}{a(t)}-\int_{t_e}^{t_e+\Delta t_e} \frac{dt}{a(t)}$

So

$\int_{t_o}^{t_o+\Delta t_o} \frac{dt}{a(t)} -\int_{t_e}^{t_e+\Delta t_e}\frac{dt}{a(t)} =0$

Neglect any change in a(t) during Δte and Δto, so regard a(t) as constant in the above integrals.

$\frac{1}{a(t_o)} \int_{t_o}^{t_o+\Delta t_o}dt =\frac{1}{a(t_e)} \int_{t_e}^{t_e+\Delta t_e}dt$

$\frac{\Delta t_o}{a(t_o)}= \frac{\Delta t_e}{a(t_e)}$

$\frac{\Delta t_e}{\Delta t_o}= \frac{a(t_e)}{a(t_o)}$

Set $a(t_o)=1$

$\Delta t_e=\frac{\lambda_e}{c}$ and $\Delta t_o=\frac{\lambda_o}{c}$

Redshift

$1+z=\frac{\lambda_o}{\lambda_e}=\frac{\Delta t_o}{\Delta t_e}=\frac{a(t_o)}{a(t_e)}$ regardless of the form of a.

Active galaxies and quasars are the most spectacular objects in the sky, with high luminosities (~1013 L¤) produced from relatively tiny volumes (<1pc). They form luminous, compact nuclei at the centres of some galaxies; sometimes jets of relativistic material emanate from the active nuclei and propagate over hundreds of thousands of kpc. Active galaxies and quasars were more numerous in the past, and are useful as beacons to the distant universe.

Properties of active galactic nuclei (AGN)

1. Angular size. Most have very small angular size, but this property is also wavelength dependent.
2. Most have >galactic luminosity; but of course, objects with low luminosity are hard to find in the first place (possibly skewing results)- dust, obscuration and beaming can mislead.
3. Most have a broad band continuum; often spectral shape from IR to x-rays is constant.
4. Most have strong emissions, sometimes very broad.
5. Most are variable- short wavelengths are stronger and faster than long.
6. Most are weakly polarised; a small minority are strongly variable and polarised (these are correlated with radio and gamma rays- in some cases emission lines are absent).
7. Many show compact radio emission. A minority show spectacular extended radio emission.

Naïve estimate of size-scale of emitting region from time variability: if an emitting region varies more rapidly than the light-crossing time, then the variability will be washed out. Hence, if a source varies on a timescale of δt, then the size L of the emitting region satisfies

$L

(Actually, relativistic corrections are needed but this will do as the aforementioned naïve estimate).

At radio wavelengths, Very Long Baseline Interferometry is used to measure milli-arcsecond scales.

Hydrogen lines

1. Lyman series- transitions to n=1 (UV)
2. Balmer series- transitions to n=2 (visible); 656.3nm (red), 486.1nm (blue-green), 434.1nm (violet) and 410.2nm (violet)- Hα, Hβ, Hγ and Hδ
3. Paschen series- transitions to n=3 (IR)

Why are some emission lines so broad? Our first thought might be that it is due to thermal broadening. Put $mv^2 \simeq kT$, where v=2000kms-1 – for hydrogen, this gives T~5×108K. But at this temperature, the atoms will most likely be ionised, in which case we won’t be seeing any emission lines anyway.

Also, this would predict that the line widths depend on the mass of the atomic species (for a given T, $v \propto \frac{1}{\sqrt{m}}$), but measurements show that carbon and hydrogen lines are comparable (C should be $\frac{1}{\sqrt{12}}$ H).

So thermal broadening cannot make the dominant contribution- bulk motions of the gas are likely to be responsible instead.

Apparent superluminal motion

To an observer on Earth-

Object travelling at speed v is at A at t=0.

Light from A reaches Earth at $t=\frac{vt_1\cos{\theta}+d}{c}$

Object is at B at t=t1.

Light from B reaches Earth at $t=t_1+\frac{d}{c}$

It looks like the object has travelled distance vt1sinθ in time $t_1+\frac{d}{c}-\frac{vt_1\cos{\theta}}{c}-\frac{d}{c}$

Apparent transverse velocity of object measured on Earth

$v_{app}=\frac{vt_1\sin{\theta}}{t_1-\frac{vt_1\cos{\theta}}{c}}$

$v_{app}=\frac{v\sin{\theta}}{1-\beta \cos{\theta}}$

which can appear to be greater than c.

At B, time=t1

At C, time=β t1cosθ

$\Delta t=t_1(1-\beta \cos\theta)$

$\Delta x=vt_1\sin\theta$

$\Delta s^2=c^2\Delta t^2-\Delta x^2$

$\Delta s^2=c^2t_1^2(1-\beta \cos\theta)^2- v^2t_1^2\sin^2\theta$

If vapp>c, then B and C have spacelike separation.

Active galaxies- models: Any model must explain the high luminosity- a small but efficient energy source is needed. Possibilities are-

1. Star cluster- luminosity due to supernova. But observed variability is too coherent for a supernova, the lifetime is too short and there is no explanation for the radio jets.
2. Supermassive stars- again unlikely, because these are unstable to collapse.
3. Supermassive black hole (fuelled by accretion) provides the best possibility- it is small and efficient with a stable potential well and a stable direction for radio jets. There is evidence for such enormous masses in nearby galaxies.


text:
# Tag Info

2

This answer has 2 parts, the 1st on "quantifying" the security of unbroken ciphers, the 2nd on the choice of ciphers for different usage scenarios. If (on a scale of 1 to 10) AES is 5 and Serpent is 10, what would ChaCha be? First, you have to quantify their security in order for the scores to be meaningful. The quantification must have a basis, ...

3

Theory aside, there's basically no way to have security on the CAN bus. The Controller Area Network, or CAN bus, is a differential bus that is robust enough for critical communications but simple enough to be used with micro-controllers. CAN bus employs a message-based protocol over four wires, power, ground, CAN-, and CAN+, where the message from a device ...

6

Yes, there is an important one; The Non-Reputation; Non-repudiation refers to a situation where a statement's author cannot successfully dispute its authorship or the validity of an associated contract The HMAC key is a symmetric key therefore there is no non-repudiation. Both sides can not claim that the other side sends them the message $m$. I.e. They ...

0

You have and oracle call of $$O(\texttt{your-string}) = (\operatorname{AES-128-ECB}(\texttt{your-string} || \texttt{unknown-string})$$ Since you know that the AES has 16-byte block cipher and it uses CBC, request; $$C = O(\texttt{AAAAAAAAAAAAAAAx})$$ from oracle, where $\texttt{x}$ is the first byte of the random key. Now ask to oracle these encryptions C ...

10

All AES candidates due to specification were Pseudo-Random Permutation (PRP), however, today we don't need a PRP. We can live with a Pseudo-Random Function (PRF) since the CTR mode is designed for PRFs. CTR modes don't need the reverse operation as CBC. This can reduce the area/time cost of implementations. As an example; the ChaCha is a PRF and turned into ...

15

A serious issues with AES is its sensitivity to timing and cache side-channel attacks in many portable pure-software implementations, due to the hard-to-avoid table lookups (exceptions: bitsliced implementation, CPUs without a data cache, CPUs with AES-NI, some slow code). An ARX cipher (in the sense of using only additions, rotations/shifts, and XOR; e.g ...

34

Nobody seems to need a 192 bit version, we can do fine with just AES-128 and AES-256. Having a key that's 1.5 times the block size is a nuisance (or 0.75 times the block size if the block size is doubled). The key schedules of AES-192 and AES-256 are vulnerable to attack; we could do with a better key schedule where even these attacks are avoided. They don't ...

20

I don't think that saving rounds to increase speed is necessary. On machines with AES-NI (which is most today), it takes less time to encrypt in AES than it does to read from memory. There are rare cases where the time to encrypt is too slow. One change that I think should have been made is to also standardize a larger block size. Although 128 bits seems ...

11

The others had a fixed number of rounds (32 for Serpent, 16 for Twofish, etc.) regardless of the key size. Why was this? Is there some cryptographic attack which is unique to Rijndael which would warrant this? During the second AES conference, the Rijndael team was asked about this design decision. They turned it around, and pointed out that smaller keys ...

4

I'd argue for (3) for these reasons: the algorithms are used within their operating assumptions; related: AES may be insecure if the keys have a specific format; no entropy is lost when performing the conversion to 32 bytes as compared to (1). AES-128 is also considered secure at the moment, but it may not be if quantum computers are created that enable ...

1

You can assign each device its own unique certificate with a signature issued by the CA (for example, could be the manufacturer) on the certificate. So each device stores the following: its own unique certificate (its public key), its corresponding secret key, and the signature on its certificate issued by the CA. During key exchange, 2 devices would send ...

0

Lastly, a 32-byte HMAC value of the ciphertext is created using the HMAC key and SHA-256 and written as the last two blocks of the ciphertext (32 bytes). You really should include the IV in the calculation. Otherwise the authentication tag validates, and with a wrong IV it will still result in invalid plaintext. This is less of an issue with the salt, as a ...

0

If the key is derived from the password there is no reason to store it anywhere. The main problem in your outline is not the cryptography. You are explicitly writing the passwords to disk. This is a really bad idea. The deletion may not happen at all, e.g powe failure. Even if it does on a modern hard drive it is really hard to overwrite data it won't ...

0

That is right, but is it possible that the victim send me his encrypted symmetric key and I will send the decrypted key back? I have not personally written any ransonware, nor have I examined how they operation; however if I were to, that is what I would do - once the victim has paid up, they would send a copy of the encrypted symmetric key, decrypt it, and ...

1

I am assuming you meant to use a=2, so that if it sends an error message, we know that MCB was 1. Anyway RSA in practice is never used in raw form like this precisely because this malleability allows attacks like you just mentioned. Such malleability also allows an attacker to create fake signatures from an oracle and with good padding, we cannot trick any ...

0

I don't think you need RSA either. Where will you store the private key and how will you protect it from being stolen anyway? Use a good and hard to guess password, and a long enough salt and use a good KDF to derive an AES key to encrypt your data, I think it will work better? And 256 bits is huge, it will take many times longer than the age of current ...

0

As @mentallurg answered: use AES-256. Today, any cipher at or above 128-bit security level is very strong and as John Kelsey says: "Thare is no meaningful difference between 192-bit and 256-bit keys in terms of practical bruteforce attacks; impossible is impossible." But, just to bear with you: you can use Threefish-1024. Threefish is a fast and ...

2

Based on your comments I have a feeling that may be you don't really understand what a huge number of combinations a 256-bit key means. At the first glance 256 bit is "just" 16 bytes. But look at it closer. With 256 bits we can encode $2^{256} = 10^{77}$ numbers. It is 100 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 ...

0

In this case, this answer also should be a comment (I'm sorry!). @Hunter, the NIST SP 800-108 define the use of hmac as PRF. For example, in python, you can use: hash_algo = hashes.SHA512() kdf = KBKDFHMAC(algorithm=hash_algo, mode=Mode.CounterMode, length=32, rlen=4, llen=4, location=CounterLocation.BeforeFixed, label=label, context=context, fixed=None, ...

0

I recommend HKDF - it's a key-based key derivation function (as opposed to password-based). It accepts an already-high entropy input (your AES key), a salt (you could use your "plain text"), and optional info, for contextualizing the key. It would be better to use your main key to derive two separate keys, one for encryption, and one for HMAC... ...

2

In general, we always assume that the mode of operation is known ahead of time. In practice, this should be bound to the key - if the key is only used for a single mode of operation then the above shouldn't happen. However, if the same key is used for multiple modes of operation, then the mode ID should be made part of the ciphertext and therefore included ...

4

Actually, your numbers seem shockingly high at 2724 cycles for one block - even with the key schedule. Crypto++ uses standard AES-NI for the encryption of blocks and for the key generation they use AESKEYGENASSIST for the SBox (unfortunately). Ideally the expected performance would be (for their implementation, not for one with an optimized on-the-fly key ...

2

AES has highly optimized implementations, including additions of special instructions to intel CPUs specifically for AES. but even without it is amazing how much optimization can go into the implementation og an algorithm it's quite an art. I also have doubts in your measurements, the maximum may be only noise from context switches etc. AES can be ...

1

Honestly, it would be more secure, but not by much, and that is assuming you are using finite field inversion s-boxes. A better use of multiple 8-bit s-boxes would be to make them key dependent, however in software that can have the unfortunate side effect of creating another side channel to leak information about the key. If you want something based on the ...

0

Let us decrypt the CBC encrypted ciphertext.(IV and Key each of 16 bytes=128 bits) key = 140b41b22a29beb4061bda66b6747e14 IV = 4ca00ff4c898d61e1edbf1800618fb28 Cipher Text = 28a226d160dad07883d04e008a7897ee2e4b7465d5290d0c0e6c6822236e1daafb94ffe0c5da05d9476be028ad7c1d81 Now if you put them in any CBC decryption function you will get plaintext as Basic ...

1

For the CBC mode the encryption and decryption equations are as follows; CBC encryption; \begin{align} C_1 &= E_k(P_1 \oplus IV)\\ C_i &= E_k(P_i \oplus C_{i-1}),\;\; 1 < i < nb, \end{align} CBC decryption; \begin{align} P_1 =& D_k(C_1) \oplus IV\\ P_i =& D_k(C_i) \oplus C_{i-1},\;\; 1 < i < nb, \end{align} But I'm not 100% ...

Top 50 recent answers are included


text:
learn-physics-0.6.4: Haskell code for learning physics

Physics.Learn.BeamStack

Description

Splitters, recombiners, and detectors for Stern-Gerlach experiments.

Synopsis

# Core laboratory components

data BeamStack Source #

Instances
 Source # Instance detailsDefined in Physics.Learn.BeamStack MethodsshowList :: [BeamStack] -> ShowS #

A beam of randomly oriented spin-1/2 particles.

Given angles describing the orientation of the splitter, removes an incoming beam from the stack and replaces it with two beams, a spin-up and a spin-down beam. The spin-down beam is the most recent beam on the stack.

Given angles describing the orientation of the recombiner, returns a single beam from an incoming pair of beams.

Given angles describing the direction of a uniform magnetic field, and given an angle describing the product of the Larmor frequency and the time, return an output beam from an input beam.

Remove the most recent beam from the stack.

Interchange the two most recent beams on the stack.

Return the number of beams in a BeamStack.

detect :: BeamStack -> [Double] Source #

Return the intensities of a stack of beams.

# Standard splitters

A Stern-Gerlach splitter in the x direction.

A Stern-Gerlach splitter in the y direction.

A Stern-Gerlach splitter in the z direction.

# Standard magnetic fields

Given an angle in radians describing the product of the Larmor frequency and the time, apply a magnetic in the x direction to the most recent beam on the stack.

Given an angle in radians describing the product of the Larmor frequency and the time, apply a magnetic in the y direction to the most recent beam on the stack.

Given an angle in radians describing the product of the Larmor frequency and the time, apply a magnetic in the z direction to the most recent beam on the stack.

# Standard combiners

A Stern-Gerlach recombiner in the x direction.

A Stern-Gerlach recombiner in the y direction.

A Stern-Gerlach recombiner in the z direction.

# Filters

Filter for spin-up particles in the x direction.

Filter for spin-down particles in the x direction.

Filter for spin-up particles in the z direction.

Filter for spin-down particles in the z direction.


text:
# Integrate Noto Serif KR into a Flutter app

I wanted to try out google_fonts and use it to display beautiful text in Korean. It was harder than the doc said.

I started according to the instructions at https://pub.dev/packages/google_fonts, adding the dependency to my pubspec.yaml, then using one of its predefined methods:

Text(
'음악',
),

It worked with latin letters but not with Korean hangul. So I tried with a Locale

Text(
'음악',
),

Didn't work either. Looking at the Google Fonts page for the font, the title is "Noto Serif KR", so I tried passing that String instead:

Text(
'음악',

Since I had downloaded the KR family, the font filename was NotoSerifKR-[font weight].otf. I tried running it again. No luck. So my guess is that it won't look for localized fonts even if it's hosted. So I renamed my file to NotoSerif-[font weight].otf. And finally, it worked!


text:
## Euclidean vector

• In mathematics, physics, and engineering, a Euclidean vector (sometimes called a geometric or spatial vector, or—as here—simply a vector) is a geometric object that has magnitude (or length) and direction. Vectors can be added to other vectors according to vector algebra. A Euclidean vector is frequently represented by a line segment with a definite direction, or graphically as an arrow, connecting an initial point A with a terminal point B, and denoted by ${\displaystyle {\overrightarrow {AB}}.}$

A vector is what is needed to "carry" the point A to the point B; the Latin word vector means "carrier". It was first used by 18th century astronomers investigating planet rotation around the Sun. The magnitude of the vector is the distance between the two points and the direction refers to the direction of displacement from A to B. Many algebraic operations on real numbers such as addition, subtraction, multiplication, and negation have close analogues for vectors, operations which obey the familiar algebraic laws of commutativity, associativity, and distributivity. These operations and associated laws qualify Euclidean vectors as an example of the more generalized concept of vectors defined simply as elements of a vector space.

The algebraically imaginary part, being geometrically constructed by a straight line, or radius vector, which has, in general, for each determined quaternion, a determined length and determined direction in space, may be called the vector part, or simply the vector of the quaternion.
(1, 2, 3) + (−2, 0, 4) = (1 − 2, 2 + 0, 3 + 4) = (−1, 2, 7).
${\displaystyle \mathbf {a} =(2,3).}$
${\displaystyle \mathbf {a} =(a_{1},a_{2},a_{3}).}$
also written
${\displaystyle \mathbf {a} =(a_{\text{x}},a_{\text{y}},a_{\text{z}}).}$
${\displaystyle \mathbf {a} =(a_{1},a_{2},a_{3},\cdots ,a_{n-1},a_{n}).}$
${\displaystyle \mathbf {a} ={\begin{bmatrix}a_{1}\\a_{2}\\a_{3}\\\end{bmatrix}}=[a_{1}\ a_{2}\ a_{3}].}$
${\displaystyle {\mathbf {e} }_{1}=(1,0,0),\ {\mathbf {e} }_{2}=(0,1,0),\ {\mathbf {e} }_{3}=(0,0,1).}$
${\displaystyle \mathbf {a} =(a_{1},a_{2},a_{3})=a_{1}(1,0,0)+a_{2}(0,1,0)+a_{3}(0,0,1),\ }$
${\displaystyle \mathbf {a} =\mathbf {a} _{1}+\mathbf {a} _{2}+\mathbf {a} _{3}=a_{1}{\mathbf {e} }_{1}+a_{2}{\mathbf {e} }_{2}+a_{3}{\mathbf {e} }_{3},}$
${\displaystyle \mathbf {a} =\mathbf {a} _{\text{x}}+\mathbf {a} _{\text{y}}+\mathbf {a} _{\text{z}}=a_{\text{x}}{\mathbf {i} }+a_{\text{y}}{\mathbf {j} }+a_{\text{z}}{\mathbf {k} }.}$
${\displaystyle {\mathbf {e} }_{1}=(1,0,0),\ {\mathbf {e} }_{2}=(0,1,0),\ {\mathbf {e} }_{3}=(0,0,1)}$
${\displaystyle {\mathbf {a} }=a_{1}{\mathbf {e} }_{1}+a_{2}{\mathbf {e} }_{2}+a_{3}{\mathbf {e} }_{3}.}$
${\displaystyle {\mathbf {a} }=a_{1}{\mathbf {e} }_{1}+a_{2}{\mathbf {e} }_{2}+a_{3}{\mathbf {e} }_{3}}$
${\displaystyle {\mathbf {b} }=b_{1}{\mathbf {e} }_{1}+b_{2}{\mathbf {e} }_{2}+b_{3}{\mathbf {e} }_{3}}$
${\displaystyle a_{1}=b_{1},\quad a_{2}=b_{2},\quad a_{3}=b_{3}.\,}$
${\displaystyle {\mathbf {a} }=a_{1}{\mathbf {e} }_{1}+a_{2}{\mathbf {e} }_{2}+a_{3}{\mathbf {e} }_{3}}$
${\displaystyle {\mathbf {b} }=b_{1}{\mathbf {e} }_{1}+b_{2}{\mathbf {e} }_{2}+b_{3}{\mathbf {e} }_{3}}$
${\displaystyle a_{1}=-b_{1},\quad a_{2}=-b_{2},\quad a_{3}=-b_{3}.\,}$
${\displaystyle \left\|\mathbf {a} \right\|={\sqrt {{a_{1}}^{2}+{a_{2}}^{2}+{a_{3}}^{2}}}}$
${\displaystyle \left\|\mathbf {a} \right\|={\sqrt {\mathbf {a} \cdot \mathbf {a} }}.}$
Unit vector
${\displaystyle \mathbf {\hat {a}} ={\frac {\mathbf {a} }{\left\|\mathbf {a} \right\|}}={\frac {a_{1}}{\left\|\mathbf {a} \right\|}}\mathbf {e} _{1}+{\frac {a_{2}}{\left\|\mathbf {a} \right\|}}\mathbf {e} _{2}+{\frac {a_{3}}{\left\|\mathbf {a} \right\|}}\mathbf {e} _{3}}$
Zero vector
${\displaystyle \mathbf {a} +\mathbf {b} =(a_{1}+b_{1})\mathbf {e} _{1}+(a_{2}+b_{2})\mathbf {e} _{2}+(a_{3}+b_{3})\mathbf {e} _{3}.}$
${\displaystyle \mathbf {a} -\mathbf {b} =(a_{1}-b_{1})\mathbf {e} _{1}+(a_{2}-b_{2})\mathbf {e} _{2}+(a_{3}-b_{3})\mathbf {e} _{3}.}$
${\displaystyle r\mathbf {a} =(ra_{1})\mathbf {e} _{1}+(ra_{2})\mathbf {e} _{2}+(ra_{3})\mathbf {e} _{3}.}$
${\displaystyle \mathbf {a} \cdot \mathbf {b} =\left\|\mathbf {a} \right\|\left\|\mathbf {b} \right\|\cos \theta }$
${\displaystyle \mathbf {a} \cdot \mathbf {b} =a_{1}b_{1}+a_{2}b_{2}+a_{3}b_{3}.}$
${\displaystyle \mathbf {a} \times \mathbf {b} =\left\|\mathbf {a} \right\|\left\|\mathbf {b} \right\|\sin(\theta )\,\mathbf {n} }$
${\displaystyle {\mathbf {a} }\times {\mathbf {b} }=(a_{2}b_{3}-a_{3}b_{2}){\mathbf {e} }_{1}+(a_{3}b_{1}-a_{1}b_{3}){\mathbf {e} }_{2}+(a_{1}b_{2}-a_{2}b_{1}){\mathbf {e} }_{3}.}$
${\displaystyle \mathbf {a} =p\mathbf {e} _{1}+q\mathbf {e} _{2}+r\mathbf {e} _{3}}$.
${\displaystyle p=\mathbf {a} \cdot \mathbf {e} _{1}}$,
${\displaystyle q=\mathbf {a} \cdot \mathbf {e} _{2}}$,
${\displaystyle r=\mathbf {a} \cdot \mathbf {e} _{3}}$.
${\displaystyle \mathbf {a} =u\mathbf {n} _{1}+v\mathbf {n} _{2}+w\mathbf {n} _{3}}$
${\displaystyle u=\mathbf {a} \cdot \mathbf {n} _{1}}$,
${\displaystyle v=\mathbf {a} \cdot \mathbf {n} _{2}}$,
${\displaystyle w=\mathbf {a} \cdot \mathbf {n} _{3}}$.
${\displaystyle u=(p\mathbf {e} _{1}+q\mathbf {e} _{2}+r\mathbf {e} _{3})\cdot \mathbf {n} _{1}}$,
${\displaystyle v=(p\mathbf {e} _{1}+q\mathbf {e} _{2}+r\mathbf {e} _{3})\cdot \mathbf {n} _{2}}$,
${\displaystyle w=(p\mathbf {e} _{1}+q\mathbf {e} _{2}+r\mathbf {e} _{3})\cdot \mathbf {n} _{3}}$.
${\displaystyle u=p\mathbf {e} _{1}\cdot \mathbf {n} _{1}+q\mathbf {e} _{2}\cdot \mathbf {n} _{1}+r\mathbf {e} _{3}\cdot \mathbf {n} _{1}}$,
${\displaystyle v=p\mathbf {e} _{1}\cdot \mathbf {n} _{2}+q\mathbf {e} _{2}\cdot \mathbf {n} _{2}+r\mathbf {e} _{3}\cdot \mathbf {n} _{2}}$,
${\displaystyle w=p\mathbf {e} _{1}\cdot \mathbf {n} _{3}+q\mathbf {e} _{2}\cdot \mathbf {n} _{3}+r\mathbf {e} _{3}\cdot \mathbf {n} _{3}}$.
${\displaystyle u=c_{11}p+c_{12}q+c_{13}r}$,
${\displaystyle v=c_{21}p+c_{22}q+c_{23}r}$,
${\displaystyle w=c_{31}p+c_{32}q+c_{33}r}$,
${\displaystyle {\begin{bmatrix}u\\v\\w\\\end{bmatrix}}={\begin{bmatrix}c_{11}&c_{12}&c_{13}\\c_{21}&c_{22}&c_{23}\\c_{31}&c_{32}&c_{33}\end{bmatrix}}{\begin{bmatrix}p\\q\\r\end{bmatrix}}}$.
${\displaystyle c_{11}=\mathbf {n} _{1}\cdot \mathbf {e} _{1}}$
${\displaystyle c_{12}=\mathbf {n} _{1}\cdot \mathbf {e} _{2}}$
${\displaystyle c_{13}=\mathbf {n} _{1}\cdot \mathbf {e} _{3}}$
${\displaystyle c_{21}=\mathbf {n} _{2}\cdot \mathbf {e} _{1}}$
${\displaystyle c_{22}=\mathbf {n} _{2}\cdot \mathbf {e} _{2}}$
${\displaystyle c_{23}=\mathbf {n} _{2}\cdot \mathbf {e} _{3}}$
${\displaystyle c_{31}=\mathbf {n} _{3}\cdot \mathbf {e} _{1}}$
${\displaystyle c_{32}=\mathbf {n} _{3}\cdot \mathbf {e} _{2}}$
${\displaystyle c_{33}=\mathbf {n} _{3}\cdot \mathbf {e} _{3}}$
${\displaystyle {\mathbf {x} }=x_{1}{\mathbf {e} }_{1}+x_{2}{\mathbf {e} }_{2}+x_{3}{\mathbf {e} }_{3}.}$
${\displaystyle {\mathbf {y} }-{\mathbf {x} }=(y_{1}-x_{1}){\mathbf {e} }_{1}+(y_{2}-x_{2}){\mathbf {e} }_{2}+(y_{3}-x_{3}){\mathbf {e} }_{3}.}$
${\displaystyle {\mathbf {x} }_{t}=t{\mathbf {v} }+{\mathbf {x} }_{0},}$
${\displaystyle {\mathbf {F} }=m{\mathbf {a} }}$
${\displaystyle E={\mathbf {F} }\cdot ({\mathbf {x} }_{2}-{\mathbf {x} }_{1}).}$
${\displaystyle {\frac {df}{d\tau }}=\sum _{\alpha =1}^{n}{\frac {dx^{\alpha }}{d\tau }}{\frac {\partial f}{\partial x^{\alpha }}}.}$
${\displaystyle t^{\alpha }={\frac {dx^{\alpha }}{d\tau }}.}$
${\displaystyle {\frac {d}{d\tau }}=\sum _{\alpha }t^{\alpha }{\frac {\partial }{\partial x^{\alpha }}}.}$
${\displaystyle \mathbf {a} \equiv a^{\alpha }{\frac {\partial }{\partial x^{\alpha }}}.}$
Wikipedia


text:
# Give feedback

Thanks for taking the time to share your feedback about the DML-CZ system. Your comments are appreciated!

1. Article:
Choquet-like integrals with respect to level-dependent capacities and $\varphi$-ordinal sums of aggregation function
2. Author:
Mesiar, Radko
3. Source:
Kybernetika / 3
4. Your name:
Please enter your name
5. Your Email:
This address will be used to follow up on your feedback.
6. Comments:
7.

Partner of


text:
# How can I prevent my bullet from influencing other players when colliding with them?

So when my bullet which is a Rigidbody is hitting another player which is also a Rigidbody, the bullet is getting destroyed immediately. But it seems that this isn't enough to prevent the physics to be applied. I guess that's why my player is getting pushed backward all the time when he is getting hit. I don't want this behaviour, so I tried to fix it :

I tried to lower the mass of the bullet which didn't help. I also tried to change the bullet behavior to a trigger, but the collision detection failed very often.

• I don't know the scale of your project but have a look at this: answers.unity3d.com/questions/327412/… (in short, using rigidbodies for every single bullet is ineffective, using a raycast method is more of what you want to do, usually) Unless you're Battlefield or something :P Dec 8, 2016 at 16:45
• Yeah the bullets have physics, so they are dropping and so on (It's 2D so I don't have to worry too much about performance of these bullets) Dec 9, 2016 at 6:46
• If it's 2D, why not pre-calculate the bullet's trajectory? Instead of using actualy physics, because that way, you can get rid of the unnecessary interactions of bullets with physics objects (usually you want physics interactions between bigger objects). If you absolutely want to use physics to simulate the bullet, then consider using a collider that will be bigger than the rigidbody (say, if the rigidbody is 1cm by 1cm, make the collider that will destroy the body of the bullet into a 1.1cm by 1.1cm collider instead.) that should do what you're trying to do. Dec 9, 2016 at 7:17
• Mhm I will look into that, some questions for better understanding : Would you implement rockets with the same methods? And do you know about teeworlds, would you implement the projectiles of teeworlds with that technique or rather use phsysics? Dec 9, 2016 at 20:35
• If the bullet is supposed to push the character back, then use physics, if not, try to exclude it altogether. So, I would use physics with a rocket (because if I'm doing the collision and the pushback with it, then why not) also, there won't be a ton of rockets going around. For a minigun type of weapon though, I would rather not apply physics. Math is much less expensive in terms of CPU usage than physics is, so try to avoid using physics as much as you can. Dec 9, 2016 at 20:40

If you wish to use physics on an object but not have it push other stuff back, it's a good idea to encase the rigidbody inside a collider, so if you have a 1cm square (or cube if you're in 3D) rigidbody on a bullet, then make its collider into a 1.1cm square. This will mean that before the physics calculations of the hit can take place, the collider will do the calculations it's supposed to and then get rid of the bullet. Of course, colliders can still do a push-back like effect, but it should be infinitesimal compared to a rigidbody. Besides, you still don't want the physics calculations kicking off for a minigun that's dishing out 6000 bullets per minute.


text:
# Anthropics is pretty normal

post by Stuart_Armstrong · 2019-01-17T13:26:22.929Z · score: 28 (11 votes) · LW · GW · 9 comments

## Contents

  Common understanding of anthropics
Updating and conditional probability
The anthropic principle
Conditional probabilities
The power of Bayes compels you!
Survivorship bias and special Earths
Anthropic reasoning in medium sized universes
Defining medium sized universes
Anthropic probability in medium sized universes
Anthropics for beginners

In this post, I'll defend these claims:

1. The common understanding of anthropic reasoning is wrong.
2. There are interesting reasons for that error.
3. Anthropic updating is the same as normal updating. For example, our survival is evidence that the world is safer than we thought.
4. Full anthropic reasoning is actually pretty normal and easy in most cases.
5. We don't need to define some special class of "observers" to do anthropic reasoning.

# Common understanding of anthropics

By the "common understanding", I mean something like:

• : "If we had died in an existential catastrophe, we wouldn't be around to observe it. Hence we can't conclude anything from our survival about the odds of existential risk."

Sometimes "can't conclude anything" is weakened to allow some weak updating.

Now sounds reasonable. But consider instead:

• : "If we had won the lottery, a lottery-losing us wouldn't be around to observe it. Hence we can't conclude anything from our loss about the odds of winning the lottery."

Formally the two arguments have the same structure. Now, people might start objecting that the difference between an observer or no observers is not the same thing as the difference between an observer seeing a loss and one not seeing it. And then I might respond by slicing into the definition of observer, creating "half-observers", and moving smoothly between observer and non-observer...

But that's the wrong response, on both of our parts (shame on you, hypothetical strawman, for reasoning like that!). The key question is not "can we justify that and might be different?" Because we can always justify something like that if we work on it hard enough.

Instead we should be asking "1) Why do we find convincing?", and "2) Do we have reasons to believe is wrong?"

My answer to 2) is "yes, of course; is clearly wrong, and is formally structured the same way, so there must be a paradox lurking there" (spoiler: there is a paradox lurking there).

For 1), I introspected on why I had been lead astray for so long, and here are some of the reasons why we might believe (or at least think that anthropic reasoning is hard):

• A desire to not go overboard.
• Conditional probabilities being confusing if not written out in full.
• An awareness of survivorship bias.
• Anthropic probability theories seem confusing and full of paradoxes.

The desire not to go overboard is the easiest to understand: to those who might say "so, it turns out we were safe after all!", we can answer, correctly "not necessarily; we might just have got lucky". And that is correct; we might have got lucky. But it's also some evidence, at least, that maybe we were safer than we thought.

# Updating and conditional probability

## The anthropic principle

Let's go back to the idea that started this all: the anthropic principle. Looking at the Wikipedia article on it, there seems to be a bunch of different principles; here's my attempt at putting them in a table:

The Barrow and Tipler Strong AP is in my view wrong (I think they're mixing frequentist and Bayesian probability, if they have to posit an actual multiverse). But the other ones seem trivially true, just as matter of conditional probability. And the differences between them are unimportant: whether it's looking at the whole universe, or our space-time location, and at observers in general, carbon based life, or just ourselves. All of these are equally true, and it seems to me that people arguing about different versions of the AP just haven't seen them written down as they are here, where it's clear that they are all of a similar format:

• Conditional on some form of life (which includes us) existing, it is almost certain that anything necessary for that life, has actually happened.

## Conditional probabilities

Now look back at . It looks similar, but it isn't; the conditionals are used a bit differently. What says is "conditional on us surviving, the probability of an existential catastrophe having happened is zero. And this probability is independent of whether the world is safe or not. Hence we can't deduce whether the world is safe or not".

All the mischief is in that word "hence". Conditional probabilities are tricky and counterintuitive; to pick an example from logical uncertainty, ''0=1''"0=0" while "0=0""0=1". And, in general, you can't move "is independent of" from one side of the conditional to the other.

So these probabilities have to be computed explicitly - though you can get a hint of the potential mistake by considering "conditional on us seeing ourselves lose the lottery, the probability of us winning the lottery is zero. And this probability is independent of the odds of the lottery. Hence we can't say anything about the odds of the lottery".

## The power of Bayes compels you!

I have actually computed the odds explicitly [LW · GW], using Bayesian reasoning, to show that statements like are wrong. But let's invert the problem: if we assumed was true, what would that imply?

Imagine that the world is either (low risk of existential catastrophe) or (high risk of existential catastrophe). Then would argue that is the same as : our survival provides no evidence of the world being safe. Then applying almighty Bayes:

The same reasoning shows . Therefore would force us to conclude that the safe and the dangerous worlds have exactly the same level of risk!

Similar problems arise if we try and use weaker versions of - maybe our survival is some evidence, just not strong evidence. But Bayes will still hit us, and force us to change our values of terms like . There are simply not enough degrees of freedom in the system for anthropic updating to be done any way other than in the normal way.

# Survivorship bias and special Earths

There are clearly issues of selection bias and survivorship bias in anthropic reasoning. We can't conclude from seeing all the life around us, that the universe is full of life.

But that doesn't stop us from updating normally, it just means we have to update on exactly what we know: not on the information that we observe, but on the fact that we observe it.

Take a classical example of survivorship bias: hedge funds success. We see a lot of successful hedge funds, and we therefore conclude that hedge funds are generally successful. But that conclusion is mistaken, because the least successful hedge funds tend to go bankrupt, leaving us with a skewed sample. So if we noticed "most hedge funds I can see are successful", concluded "most hedge funds are successful", and updated on that... then we'd be wrong.

Similarly, if we noticed a lot of life around us, concluded "life is common", and updated on that, we'd be wrong. If, however, we instead concluded "life is common on at least one planet" and updated on that, then we would be correct.

Notice how specific the update requirements can be. Suppose we had three theories. Theory gives a probability to life existing on any given planet. Theory gives a probability for life existing on any Earth-like planet, and for other planets. While theory gives a probability to life existing on Earth, specifically, and to life existing anywhere else.

Now, the different might have different priors. But updating them on the fact of our existence will increase the probability of twice as much as , which itself is twice as much as . Even though posits a universe filled with life and a universe almost empty of life, our existence is evidence for over .

So, when updating on anthropic evidence, we have to update on what we see (and the fact that we see it), and not assume we are drawing from a random sample of possible observations about the universe. But, with those caveats, anthropic updating works just as normal updating.

# Anthropic reasoning in medium sized universes

There's a final reason that anthropic reasoning can seem daunting. I've shown above that the update process of anthropic probability is the normal update process. But what about the initial probabilities? There are a plethora of anthropic probability theories - SIA, SSA, FNC - and some people (ie me) arguing that probabilities don't even exist, and that you have to use decision theory instead.

But in this section I'll show that, if you make some reasonable assumptions about the size of the universe (or at least the size of the part of the universe you're willing to consider), then all those probabilities collapse into the same thing, which is pretty much just normal probability for the universe in which you exist. If we make those assumptions, we can then do anthropic probabilities in an easy way, at least for problems without explicit duplication.

## Defining medium sized universes

Let's talk about how unique you are. From human to human, there is typically 20 million base pairs of variation. Our brain processes 50 bits per second, or 2.2 billion bits in a lifetime. A lot of this information will be highly redundant, but not all of it.

The Hubble volume roughly cubic light years, or roughly in volume. In bits, this is . So if we packed our Hubble volume with humans, and those humans were initially identical but had had about ten seconds to diverge, then we would not expect to find two copies of the same human anywhere.

Of course, humans are not packed anywhere near that density, and humans diverge a lot more than that. So we expect to go a great great great ... great great great distance before finding identical copies of ourselves.

So I define a medium sized universe as universes larger than our own, but where we'd expect to find but a single copy of ourselves. These universes can, of course, be very big - a universe that is times bigger than the Hubble volume would count as a very small example of a medium-sized universe.

• I suggest that, in general, we restrict anthropic reasoning to medium-sized universes.

This might seem controversial; after all, doesn't the universe appear to be infinite? Well, probability theories have problems with infinity, anthropic probability theories even more so [LW · GW]. In most areas, we are fine with ignoring the infinity and just soldiering on in our local area; I'm suggesting that we do that for most anthropic reasoning as well. By "most" I mean "reasoning about situations that don't involve infinities, deliberate duplication, or simulations". Though you can't shove that many simulations into a medium sized universe, so avoiding simulations may be unnecessary (it does tend to make the rest of the reasoning much easier, though).

## Anthropic probability in medium sized universes

Different theories of anthropic probability are trying to answer subtly different questions about the universe and ourselves [LW · GW]. But they only really differ if there are multiple copies of the same person.

Take SIA. We know that SIA is independent of reference class [LW · GW], so we may as well take the reference class consisting of a the agents subjectively indistinguishable from a given human (eg ourselves). Because there are almost certainly no duplicates in this universe, this reduces to a single copy, at most. So if is the probability function for SIA with this reference class, then it is almost exactly equal to for the non-anthropic probability distribution over universes.

And is just the Full Non-indexical conditioning version of anthropic probability. Now, I know that FNC is inconsistent [LW · GW]; still, in medium sized universes, it's very close to being consistent (and very close to being SIA).

If we use SSA with the reference class or the consistent class [LW · GW] , we get a similar almost equality:

• .

And understates how nearly identical these probabilities are.

Now, there is one anthropic probability theory that is different: SSA with significantly larger reference class (say the class of all humans, all sentient beings, or all "observers"). But this post [LW · GW] argues against those larger reference classes, claiming they belong more to decision theory and morality, not probability. And remember, the definition of the reference class for SSA is contained in the question we are asking. Only for questions where "we could have been person X", in a specific sense, does SSA with larger reference classes make sense.

Another reason to restrict to is that in medium sized universes, the anthropic probabilities are essentially free from all the usual paradoxes [LW · GW].

Notice that in using , we haven't had to formally define what an "observer" is, or what would qualify an agent to get that rank. Instead we're just looking at agents that are subjectively indistinguishable from each other, a narrow and reasonably well-defined class.

# Anthropics for beginners

So, here's how to proceed with anthropics in most situations:

1. Assume the universe is medium sized.
2. Check (or assume) that there is no actual duplication or simulations going on.
3. Use a prior over universes, and update it based on the fact that you exist.
4. Proceed to update using any other information you find, remembering selection bias: the update is the fact that you saw this information, not that the information exists.

And that should suffice for most non-specialised work in the area.

comment by shminux · 2019-01-18T02:46:22.047Z · score: 10 (2 votes) · LW · GW

Again, anthropics is basically generalizing from one example [LW · GW]. Yes, humans have dodged an x-risk bullet a few times so far. There was no nuclear war. The atmosphere didn't explode when the first nuclear bomb was detonated (something that happens to white dwarfs in binary systems, leading to some supernovae explosion). The black plague pandemic did not wipe out nearly everyone, etc. If we have a reference class of x-risks and assign the probability of a close call p to each member of the class, then all we know is that after observing n close calls the probability of no extinction would be p^n. If the number is vanishingly small, we might want to reconsider our estimate of p ("the world is safer than we thought"). Or maybe the reference class is not constructed correctly. Or maybe we truly got luckier than other hypothetical observable civilizations who didn't make it. Or maybe quantum immortality is a thing. Or maybe something else. After all, there is only one example, and until we observe some other civilizations actually not making it through, anthropics is groundless theorizing. Maybe we can gain more insights into the reference classes and the probabilities of a close call, and of surviving an even from studying near extinction events roughly fitting into the same reference class (past asteroid strikes, plagues, climate changes, ...). However, none of the useful information comes from guessing the size of the universe, of whether we are in a simulation, of "updating based on the fact that we exist" beyond accounting for the close calls and x-risk events.

That said, I certainly agree with your point 4. That only the observed data need to be accounted for.

comment by Stuart_Armstrong · 2019-01-18T08:21:28.589Z · score: 2 (1 votes) · LW · GW

none of the useful information comes from guessing the size of the universe, of whether we are in a simulation,

The reason I assume those is so that only the "standard" updating remain - I'm deliberately removing the anthropically weird cases.

comment by Chris_Leong · 2019-01-19T14:03:36.370Z · score: 3 (2 votes) · LW · GW

1) Subjectively distinguishable needs to be clarified. It can either a) that a human receives enough information/experience to distinguish themselves b) that a human will remember information/experience in enough detail to distinguish themselves from another person. The later is more important for real-world anthropics problems and results in significantly more copies.

2) "In most areas, we are fine with ignoring the infinity and just soldiering on in our local area" - sure, but SSA is inherently non-local. It applies over the whole universe, not just the Hubble Volume. If we're going to use an approximation to handle our inability to model infinities, we should be using a large universe, large enough to break your model, rather than a medium sized one.

comment by Stuart_Armstrong · 2019-01-21T13:06:02.071Z · score: 2 (1 votes) · LW · GW

The correct way to handle SSA is to deal with the exact question that it poses. But for most purposes, this approximation suffices.

comment by Dr. Jamchie · 2019-01-20T12:06:35.912Z · score: 1 (1 votes) · LW · GW
And then I might respond by slicing into the definition of observer, creating "half-observers", and moving smoothly between observer and non-observer...

Do you have this written down somewhere in more detail? It seems that for this to work one needs to assume the gradual appearance of consciousness, something like rock<beetle<mouse<ape<human. Will this work if one assumes consciousness to be binary, that it either is or it isn't?

comment by Stuart_Armstrong · 2019-01-21T13:08:12.303Z · score: 2 (1 votes) · LW · GW

Will this work if one assumes consciousness to be binary, that it either is or it isn't?

If it's binary, I point out the binariness is arbitrary, start looking at states of uncertainty about whether there was consciousness or not (or observers or not), talk about video feeds that may or may not be observed, or start looking at disasters that kill the population gradually yet inevitably. It's... not a very fruitful avenue to explore, in my view.

comment by ofer · 2019-01-17T17:31:06.705Z · score: 1 (1 votes) · LW · GW
Therefore A1 would force us to conclude that the safe and the dangerous worlds have exactly the same level of risk!
Similar problems arise if we try and use weaker versions of A1 - maybe our survival is some evidence, just not strong evidence. But Bayes will still hit us, and force us to change our values of terms like P( we survived | dangerous ).

I'm confused by this. The event "we survived" here is actually the event "at least one observer similar to us survived", right? (for some definition of "similar").
If the number of planets on which creatures similar-to-us evolve is sufficiently large, we get:
at least one observer similar to us survivedat least one observer similar to us survived dangerous

comment by Stuart_Armstrong · 2019-01-17T18:23:39.356Z · score: 5 (2 votes) · LW · GW

No, the event "we survived" is "we (the actual people now considering the anthropic argument and past xrisks) survived".

Over enough draws, you have .

So we update the lottery odds based on whether we win or not; we update the danger odds based on whether we live. If we die, we alas don't get to do much updating (though note that we can consider hypothetical with bets that pay out to surviving relatives, or have a chance of reviving the human race, or whatever, to get the updates we think would be correct in the worlds where we don't exist).

comment by ofer · 2019-01-17T21:22:48.426Z · score: 2 (2 votes) · LW · GW

Thank you, I understand this now (I found it useful to imagine code that is being invoked many times and is terminated after a random duration; and reflect on how the agent implemented by the code should update as time goes by).

I guess I should be overall more optimistic now :)


text:
# Fourth Annual Large Hadron Collider Physics Conference 2016

12-18 June 2016
Lund University
Europe/Zurich timezone
REGISTRATION FOR LHCP2016 IS NOW CLOSED

## Heavy flavour production and spectroscopy at the LHC

Not scheduled
20m
Lund University

#### Lund University

Sandgatan 2, Lund, Sweden
Talk Heavy Flavour physics

### Speaker

Michal Kreps (University of Warwick (GB))

### Description

With large data samples collected by LHC experiments at several energies, Quantum Chromodynamics can be tested in detail with heavy flavour production. Moreover huge samples of data allow to challenge our understanding of hadrons in detailed studies of systems not being available before. In this talk we will review recent results on heavy quark hadron production at LHC. Besides production we will also discuss recent spectroscopy results with check for the existence of tetraquark state decaying to $B_s \pi^+$ claimed by the D0 collaboration or model independent confirmation of pentaquark states.

### Primary author

Michal Kreps (University of Warwick (GB))

### Presentation Materials

There are no materials yet.