text:
# Pursued By Stacks 7: Appendix

19 May 2022

This post is, strictly speaking, a follow up to part three of my series on stacks, on the 2-Yoneda lemma. The classical Yoneda lemma has built into it a naturality statement, while our 2-Yoneda lemma proved essentially only the fact of the isomorphism. Let’s fix that.

Theorem. (The 2-Yoneda Lemma) The functor $$\operatorname{よ}\colon \operatorname{Hom}(\underline{X},\mathsf{D}) \to \mathsf{D}(X)$$ defined on objects as $$(F\colon \underline{X} \to \mathsf{D}) \mapsto F(1_X)$$ and on arrows as $$(\alpha\colon F \Rightarrow G) \mapsto \alpha(1_X)$$ is an equivalence of categories which is pseudonatural in both arguments.

We have proved all but the (pseudo)-naturality statement, which is a little convoluted for the following reason. You see, typically you think of the Yoneda lemma as being about, for instance, natural transformations from the hom-set functor $$\mathsf{C}(\underline{X},\cdot)$$ to a functor $$F$$. Now, $$\underline{X}$$ is not the functor $$\mathbf{Top}(X,\cdot)$$, but rather the functor $$\mathbf{Top}(\cdot,X)$$ which we think of as being valued not in sets, but in categories (groupoids, actually), where the category is the rather uninteresting discrete category comprising an object for each map $$Y \to X$$ and only the identity arrows. Given a map $$h \colon Y \to Z$$, we get a functor $$h^*\colon \underline{X}(Z) \to \underline{X}(Y)$$ given by $$h^*(g\colon Z \to X) = gh \colon Y \to X$$. This is actually a functor (I say, just because I can anticipate that I’m about to write down a not-quite-a-functor). The only natural transformation between functors is the identity.

Anyway, the point is, we should be expecting to suddenly start thinking of an arbitrary category fibered in groupoids $$\mathsf{D}$$ as a contravariant functor from $$\mathsf{Top}$$ to the category of categories (groupoids, actually), where the category is $$\mathsf{D}(Y)$$. Given a map $$h \colon Y \to Z$$, we should get a functor $$h^*\colon \mathsf{D}(Z) \to \mathsf{D}(Y)$$ given by $$h^*(\xi) = h^*\xi$$ and we do, actually. The problem, which we mumbled something about earlier, is that given $$g \colon X \to Y$$, we don’t necessarily have $$g^*h^*\xi = (hg)^*\xi$$, merely that they’re canonically isomorphic. In other words, the operation $$(\cdot)^*$$ is not a contravariant functor, just one up to canonical isomorphism. I super don’t actually want to learn what a pseudofunctor is, but I guess that’s what this is.

## A digression: pseudofunctors

Let’s go slowly: for each object $$X$$ in $$\mathbf{Top}$$ we have an object in the category of groupoids, namely the groupoid $$\mathsf{D}(X)$$. If we think of the hom-set $$\mathbf{Top}(X,Y)$$ as a discrete groupoid, we get a covariant functor defined contravariantly on objects (which are maps!) as $$(f\colon X\to Y) \mapsto f^*\colon \mathsf{D}(Y) \to \mathsf{D}(X)$$. We saw that this is in fact a functor, since given $$\alpha \colon \xi \to \xi'$$, there is a unique arrow $$f^*\alpha \colon f^*\xi \to f^*\xi'$$. The arrows of the category $$\mathbf{Top}(X,Y)$$ are the identity natural isomorphism, which must go to the identity natural transformation of $$f^*$$. Now, I think we’ve insisted that $$1_X^*\xi = \xi$$, and indeed if you pull back a bundle along the identity map, I think it’s fair to say that you get the same bundle. This is secretly good, because it lets us ignore isomorphisms involving the identity, since they are equalities. Now for the hard part. Given $$f\colon X \to Y$$ and $$g \colon Y \to Z$$, by the defining property of a category fibered in groupoids, for each $$\xi \in \mathsf{D}(Z)$$, there is a unique isomorphism $$\eta{f,g}(\xi)$$ making the following diagram commute

$\require{AMScd}\begin{CD} f^*g^*\xi @>g_{\xi}f_{g^*\xi}>> \xi \\ @VV\eta{f,g}(\xi)V @| \\ (gf)^*\xi @>(gf)_{\xi}>> \xi. \end{CD}$

Notice that given an arrow $$\alpha\colon \xi \to \xi'$$, the following diagram commutes

$\begin{CD} f^*g^*\xi @>\eta_{f,g}(\xi)>> (gf)^*\xi \\ @VVf^*g^*\alpha V @VV(gf)^*\alpha V \\ f^*g^*\xi' @>\eta_{f,g}(\xi')>> (gf)^*\xi'. \end{CD}$

This is because of the defining property of categories fibered in groupoids: both paths around the square make the following diagram commute

$\begin{CD} f^*g^*\xi @>\alpha g_\xi f_{g^*\xi}>> \xi' \\ @VVV @| \\ (gf)^*\xi' @>(gf)_{\xi'}>> \xi'; \end{CD}$

indeed we calculate

$\alpha g_\xi f_{g^*\xi} = g_{\xi'} g^*\alpha f_{g^*\xi} = g_{\xi'} f_{g^*\xi'} f^*g^*\alpha = (gf)_{\xi'} \eta_{f,g}(\xi') f^*g^*\alpha$

and

$\alpha g_\xi f_{g^*\xi} = \alpha (gf)_\xi \eta_{f,g}(\xi) = (gf)_{\xi'} (gf)^*\alpha \eta_{f,g}(\xi).$

My source (nLab, gulp) suggests that the isomorphism $$\eta_{f,g}$$ should be natural in $$f$$ and $$g$$. Notice that if $$f \ne f'$$, then there are no natural transformations (isomorphisms) $$f^* \Rightarrow f'^*$$. On the other hand, a family of arrows $$\alpha(\xi) \colon f^*\xi \to f^*\xi$$, define a natural isomorphism $$\alpha \colon f^*\Rightarrow f^*$$ if for each $$\beta \colon \xi \to \xi'$$ in the fiber over $$\mathsf{Y}$$, we have $$\alpha(\xi')f^*\beta = f^*\beta\alpha(\xi)$$. Naturality in $$f$$, then, is the statement that given $$\alpha\colon f^* \Rightarrow f^*$$, the following diagram commutes

$\begin{CD} f^*g^*\xi @>\eta_{f,g}(\xi)>> (gf)^*\xi \\ @VV\alpha(g^*\xi)V @VVV \\ f^*g^*\xi @>\eta_{f,g}(\xi)>> (gf)^*\xi \end{CD}$

which can only hold if the righthand arrow is $$\eta_{f,g}(\xi)\alpha(g^*\xi)\eta_{f,g}(\xi)^{-1}$$, and indeed, I see no other sensible way to define an arrow $$(gf)^*\xi \to (gf)^*\xi$$ out of one from $$f^*\xi \to f^*\xi$$. Naturality in $$g$$ should be similarly silly; I’ll leave it to you.

Since function composition is strictly associative (phew) we just need to check that the following diagram commutes for each $$\xi \in \mathsf{D}(W)$$ and each triple of maps $$f\colon X \to Y$$, $$g\colon Y \to Z$$ and $$h\colon Z \to W$$

$\begin{CD} f^*g^*h^*\xi @>f^*(\eta_{g,h}(\xi))>> f^*(hg)^* \xi \\ @VV\eta_{f,g}(h^*\xi)V @VV\eta_{f,gh}(\xi)V \\ (gf)^*h^*\xi @>\eta_{gf,h}(\xi)>> (hgf)^*\xi. \end{CD}$

This will use our only trick: consider the diagram

$\begin{CD} f^*g^*h^*\xi @>h_{\xi}g_{h^*\xi}f_{g^*h^*\xi}>> \xi \\ @VVV @| \\ (hgf)^*\xi @>(hgf)_\xi>> \xi. \end{CD}$

We calculate:

$h_\xi g_{h^*\xi} f_{g^*h^*\xi} = (hg)_\xi \eta_{g,h}(\xi) f_{g^*h^*\xi} = (hg)_\xi f_{(hg)^*\xi} f^*(\eta_{g,h}(\xi)) = (hgf)_\xi \eta_{f,gh}(\xi) f^*(\eta_{g,h}(\xi))$

and

$h_\xi g_{h^*\xi} f_{g^*h^*\xi} = h_\xi (gf)_{h^*\xi} \eta_{f,g}(h^*\xi) = (hgf)_\xi \eta_{gf,h}(\xi) \eta_{f,g}(h^*\xi).$

Therefore by the defining property of categories fibered in groupoids, we have the coherence of the associating isomorphism. The argument above is summarized in the commuting cube below, where the unlabeled arrows are the “obvious” ones, for instance $$h_\xi \colon h^*\xi \to \xi$$.

## Pseudonaturality in $$\underline{X}$$

Okay enough about pseudofunctors. We already saw in a previous post that functors $$\underline{Y} \to \underline{X}$$ are maps $$f\colon Y \to X$$. (Indeed, the proof uses the first part of the 2-Yoneda lemma.) Such a functor gives us a functor $$f^*\colon \operatorname{Hom}(\underline{X},\mathsf{D}) \to \operatorname{Hom}(\underline{Y},\mathsf{D})$$ defined on objects (functors) as $$f^*F = Ff$$ and on arrows (natural transformations) as $$f^*(\alpha \colon F \Rightarrow G) = \alpha f \colon Ff \Rightarrow Gf$$. On the other side of the equation, we have the functor $$f^*\colon \mathsf{D}(X) \to \mathsf{D}(Y)$$ defined extensively above. Pseudonaturality in $$X$$ then is the claim that the following diagram commutes

$\begin{CD} \operatorname{Hom}(\underline{X},\mathsf{D}) @>\operatorname{よ}_X>> \mathsf{D}(X) \\ @VVf^*V @VVf^*V \\ \operatorname{Hom}(\underline{Y},\mathsf{D}) @>\operatorname{よ}_Y>> \mathsf{D}(Y). \end{CD}$

up to a natural transformation. And indeed, if $$F(1_X) = \xi \in \mathsf{D}(X)$$, we have $$f^*\operatorname{よ}_X(F) = f^*\xi$$ and $$\operatorname{よ}_Y(f^*F) = (f^*F)(1_Y) = F(f\colon Y \to X)$$. Now, recall from part three that we write $$F(Y)$$, since $$f\colon Y \to X$$ is understood and we’d like to consider the arrow $$F(f) \colon F(Y) \to \xi$$. By the definition of categories fibered in groupoids, there is a unique isomorphism $$\sigma_{F,f}\colon F(Y) \to f^*\xi$$ satisfying $$f_\xi \sigma_{F,f} = F(f)$$. We claim that $$\sigma_{F,f}$$ defines a natural transformation making the diagram above commute. This is the claim that for every natural transformation $$\alpha\colon F\Rightarrow G$$ in $$\operatorname{Hom}(\underline{X},\mathsf{D})$$, the following diagram commutes in $$\mathsf{D}(Y)$$:

$\begin{CD} \operatorname{よ}_Y(f^*F) @>\sigma_{F,f}>> f^*\operatorname{よ}_X(F) \\ @VV\operatorname{よ}_Y(f^*\alpha)V @VVf^*\operatorname{よ}_X(\alpha)V \\ \operatorname{よ}_Y(f^*G) @>\sigma_{G,f}>> f^*\operatorname{よ}_X(G). \end{CD}$

Unwound slightly, if we write $$G(X) = \xi'$$ and $$\alpha \colon \xi \to \xi'$$, this is the same diagram as

$\begin{CD} F(Y) @>\sigma_{F,f}>> f^*\xi \\ @VV\alpha(Y)V @VVf^*\alpha V \\ G(Y) @>\sigma_{F,f}>> f^*\xi'. \end{CD}$

The commutativity of this diagram uses our only trick, namely the unique way of filling this diagram:

$\begin{CD} F(Y) @>\alpha F(f)>> \xi' \\ @VVV @| \\ f^*\xi' @>f_{\xi'}>> \xi'. \end{CD}$

We check

$\alpha F(f) = \alpha f_\xi \sigma_{F,f} = f_{\xi'} f^*\alpha \sigma_{F,f}$

and

$\alpha F(f) = G(f)\alpha(Y) = f_{\xi'} \sigma_{G,f} \alpha(Y).$

## A loose end from part six

I think this proves a claim from part six. Let’s test it out. An object $$\xi \in \mathsf{D}(Y)$$ is a map $$f\colon \underline{Y} \to \mathsf{D}$$. Similarly $$\xi' \in \mathsf{D}(X)$$ is a map $$g\colon \underline{X} \to \mathsf{D}$$. An arrow $$\tilde h \colon \xi \to \xi'$$ over a map $$h\colon Y \to X$$ should be the map $$h \colon Y \to X$$ together with a natural transformation $$\alpha\colon f \Rightarrow gh$$.

Let me write things a little more like the above. So we have $$\xi \in \mathsf{D}(Y)$$ equal under $$\operatorname{よ}_Y$$ to $$F\colon \underline{Y} \to \mathsf{D}$$, and similarly $$\xi' = \operatorname{よ}_X(G)$$. We have the functor $$\mathsf{D}(h) = h^*\colon \mathsf{D}(X) \to \mathsf{D}(Y)$$ which corresponds up to natural transformation to precomposition by $$h\colon Y \to X$$. There is a unique isomorphism $$\beta$$ making the following diagram commute

$\begin{CD} \xi @>\tilde h>> \xi' \\ @VV\beta V @| \\ h^*\xi' @>h_{\xi'}>> \xi' \\ @AA\sigma_{G,h}A @| \\ Gh(1_Y) @>G(h)>> \xi' \end{CD}$

We claim that $$\sigma_{G,h}^{-1}\beta$$ comes from (or defines) a unique natural transformation $$\alpha \colon F \Rightarrow Gh$$ (we write $$Gh$$ to avoid confusion with the functor $$h^*$$). At an object $$k \colon Z \to Y$$ of $$\underline{Y}$$, define $$\alpha(Z) = \sigma_{G,hk}^{-1} \eta_{k,h}(\xi') k^*\beta \sigma_{F,k}$$, where $$\eta_{k,h}(\xi') \colon k^*h^*\xi' \to (hk)^*\xi'$$ is the isomorphism defined in the previous section. Given another object $$\ell \colon W \to Y$$ and an arrow $$m \colon Z \to W$$, we need the following diagram to commute

$\begin{CD} F(Z) @>\alpha(Z)>> Gh(Z) \\ @VVF(m)V @VVGh(m)V \\ F(W) @>\alpha(W)>> Gh(W). \end{CD}$

Let’s try putting both paths around the square into the diagram

$\begin{CD} F(Z) @>\tilde h F(k)>> \xi' \\ @VVV @| \\ Gh(W) @>G(h)Gh(\ell)>> \xi'. \end{CD}$

We calculate

$\begin{gather*} G(h)Gh(\ell)Gh(m) \alpha(Z) = G(h)Gh(k)\alpha(Z) = G(hk)\alpha(Z) \\ = (hk)_{\xi'} \sigma_{G,hk} \alpha(Z) = (hk)_{\xi'} \eta_{k,h}(\xi') k^*\beta \sigma_{F,k} \\ = h_{\xi'}k_{h^*\xi'} k^*\beta \sigma_{F,k} = h_{\xi'} \beta k_\xi \sigma_{F,k} = h_{\xi'}\beta F(k) = \tilde h F(k) \end{gather*}$

and

$\begin{gather*} G(h)Gh(\ell)\alpha(W)F(m) = G(h\ell)\alpha(W)F(m) = (h\ell)_{\xi'}\sigma_{G,h\ell}\alpha(W)F(m) \\ = (h\ell)_{\xi'} \eta_{\ell,h}(\xi') \ell^*\beta \sigma_{F,\ell} F(m) = h_{\xi'}\ell_{h^*\xi'} \ell^*\beta \sigma_{F,\ell} F(m) \\ = h_{\xi'}\beta \ell_\xi \sigma_{F,\ell} F(m) = h_{\xi'} \beta F(\ell)F(m) = h_{\xi'}\beta F(k) = \tilde h F(k). \end{gather*}$

The argument is summarized in the following interesting commutative diagram.

Conversely it is clear that given such an $$\alpha \colon F \Rightarrow Gh$$, we get a map $$\tilde h \colon \xi \to \xi'$$ defined by $$G(h)\alpha(Y)$$.

## Pseudonaturality in $$\mathsf{D}$$

Now suppose we have a map of categories fibered in groupoids $$f\colon \mathsf{C} \to \mathsf{D}$$. This is by definition a functor $$f\colon \mathsf{C} \to \mathsf{D}$$ such that $$\pi f = \pi$$. For each $$\xi \in \mathsf{C}(X)$$, we get an object $$f(\xi) \in \mathsf{D}(X)$$, and for each arrow $$\alpha \colon \xi \to \xi'$$ in the fiber, we get an arrow $$f(\alpha)\colon f(\xi) \to f(\xi')$$ in the fiber. In other words, we get a functor $$f|_X \colon \mathsf{C}(X) \to \mathsf{D}(X)$$. Given a functor $$F\colon \underline{X} \to \mathsf{C}$$, postcomposition with $$f$$ yields a functor $$f_*F = fF \colon \underline{X} \to \mathsf{D}$$. Similarly given a natural transformation $$\alpha\colon F\Rightarrow G$$, we get $$f_*\alpha \colon f_*F\Rightarrow f_*G$$. Pseudonaturality in $$\mathsf{D}$$ is the claim that the following diagram commutes

$\begin{CD} \operatorname{Hom}(\underline{X},\mathsf{C}) @>\operatorname{よ}_{\mathsf{C}}>> \mathsf{C}(X) \\ @VVf_*V @VVf|_XV \\ \operatorname{Hom}(\underline{X},\mathsf{D}) @>\operatorname{よ}_{\mathsf{D}}>> \mathsf{D}(X) \end{CD}$

up to a natural transformation. And indeed, if we write $$F(1_X) = \xi$$, $$G(1_X) = \xi'$$ and $$\alpha(1_X) = \alpha \colon \xi \to \xi'$$, we actually have

$f|_X\operatorname{よ}_{\mathsf{C}}(F) = f|_X(\xi) = f(\xi) = f_*F(1_X) = \operatorname{よ}_{\mathsf{D}}(f_*F)$

and

$f|_X\operatorname{よ}_{\mathsf{C}}(\alpha) = f|_X(\alpha) = f(\alpha) = f_*\alpha(1_X) = \operatorname{よ}_{\mathsf{D}}(f_*\alpha),$

so the diagram actually commutes on the nose.


text:
# Difference between revisions of "022 Sample Final A, Problem 7"

Find the present value of the income stream ${\displaystyle Y=20+30x}$ from now until 5 years from now, given an interest rate ${\displaystyle r=10\%.}$
(Note: Once you plug in the limits of integration, you are finished; you do not need to simplify our answer beyond that step.)

Foundations:
The idea of an income stream is bit more complicated to set up than basic interest problems. We have two forces adjusting the balance of the account: the income stream, usually represented as ${\displaystyle I(t)}$, which represents the desired income to be withdrawn from the account, and the interest rate paid to the account. In order to evaluate this result, we use the formula
present value = ${\displaystyle \int _{0}^{T}I(t)e^{-rt}\,dt,}$
where ${\displaystyle T}$ is the time when our stream will run out, ${\displaystyle r}$ is the rate (compounded continuously) paid by the bank and ${\displaystyle I(t)}$ is the desired continuous income stream.
Solution:
There isn't much to do here, except identify that ${\displaystyle T\,=\,5}$, ${\displaystyle I(t)\,=\,20+30x}$ and the rate should be written as ${\displaystyle r\,=\,10\%\,=\,0.10}$.

Click to the final answer to see them in the formula!

Present value = ${\displaystyle \int _{0}^{T}I(t)e^{-rt}\,dt\,=\,\int _{0}^{5}(20+30x)e^{-0.10t}\,dt.}$

format: plain


text:
# Accessing the elements in a table is slower than calculating each time?

This is a follow-up of How to accelerate combinations and sum calculations here?

I have tried all tricks but when N reaches 35 the time is still intimidating in a 16-core server, which is far better than my Mac 2.7 GHz Intel Core i5.

I was thinking that perhaps I could store all the binomials in a table like:

N = 80;
BinomialTable = ParallelTable[Binomial[i, j], {i, 1, N}, {j, 1, N}];

Then I changed all the Binomial[x,y] into BinomialTable[[x]][[y]] in the hope that instead of calculating the combinations each time, getting them from the table would be a better idea.

The new H is named HTable with all Binomial[x,y] replaced by BinomialTable[[x]][[y]].

However, what I got is:

NmaxCompare = 6;
A1 =
ParallelTable[
H[i, j, k, l], {i, 1, NmaxCompare}, { j, 1,
NmaxCompare}, {k, 1, NmaxCompare}, {l, 1, NmaxCompare}] //
AbsoluteTiming;

AA1 = Table[
H[i, j, k, l], {i, 1, NmaxCompare}, { j, 1,
NmaxCompare}, {k, 1, NmaxCompare}, {l, 1, NmaxCompare}] //
AbsoluteTiming;

B1 = ParallelTable[
HTable[i, j, k, l], {i, 1, NmaxCompare}, { j, 1,
NmaxCompare}, {k, 1, NmaxCompare}, {l, 1, NmaxCompare}] //
AbsoluteTiming;

BB1 = Table[
HTable[i, j, k, l], {i, 1, NmaxCompare}, { j, 1,
NmaxCompare}, {k, 1, NmaxCompare}, {l, 1, NmaxCompare}] //
AbsoluteTiming;

It seems there is too much overhead for getting the elements from the table?

Also, ParallelTable of getting elements directly (B1) cannot even beat Table of calculating the combinations each time(AA1).

Does anyone has any idea to save the time on combinations by avoiding calculating them each time? Thanks!

All the code needed here:

N = 80;
BinomialTable = ParallelTable[Binomial[i, j], {i, 1, N}, {j, 1, N}];

H[n1_, n2_, n3_, n4_] :=
(1/(4*Sqrt[n1*(n1 + 1)*n2*(n2 + 1)*n3*(n3 + 1)*n4*(n4 + 1)]))*
Sum[(-1)^(m1 + m2 + m3 + m4)*Binomial[n1 + 1, m1 + 2]*Binomial[n2 + 1, m2 + 2]*Binomial[n3 + 1, m3 + 2]*Binomial[n4 + 1, m4 + 2]*
Binomial[m1 + m3, m1]*Binomial[m2 + m4, m2]*(m1 + m3 + 1)*(m2 + m4 + 1)*
(((m1 + m3 + 2)/2^(m1 + m3))*Sum[Binomial[m1 + m3 + k + 2, k]/2^k, {k, 0, m2 + m4 + 1}] +
((m2 + m4 + 2)/2^(m2 + m4))*Sum[Binomial[m2 + m4 + l + 2, l]/2^l, {l, 0, m1 + m3 + 1}]), {m1, 0, n1 - 1}, {m2, 0, n2 - 1}, {m3, 0, n3 - 1},
{m4, 0, n4 - 1}]

HTable[n1_, n2_, n3_, n4_] :=
(1/(4*Sqrt[n1*(n1 + 1)*n2*(n2 + 1)*n3*(n3 + 1)*n4*(n4 + 1)]))*
Sum[(-1)^(m1 + m2 + m3 + m4)*BinomialTable[n1 + 1, m1 + 2]*BinomialTable[n2 + 1, m2 + 2]*BinomialTable[n3 + 1, m3 + 2]*BinomialTable[n4 + 1, m4 + 2]*
BinomialTable[m1 + m3, m1]*BinomialTable[m2 + m4, m2]*(m1 + m3 + 1)*(m2 + m4 + 1)*
(((m1 + m3 + 2)/2^(m1 + m3))*Sum[BinomialTable[m1 + m3 + k + 2, k]/2^k, {k, 0, m2 + m4 + 1}] +
((m2 + m4 + 2)/2^(m2 + m4))*Sum[BinomialTable[m2 + m4 + l + 2, l]/2^l, {l, 0, m1 + m3 + 1}]), {m1, 0, n1 - 1}, {m2, 0, n2 - 1}, {m3, 0, n3 - 1},
{m4, 0, n4 - 1}]

• You expect readers to bounce to other questions to get code for a working example? No, just.... no. Please provide a complete minimal working example with all needed code. – ciao May 17 '16 at 4:15
• "perhaps I could store all the binomials in a table" - Mathematica already caches internally. – J. M.'s technical difficulties May 17 '16 at 4:18
• @ciao done edited – James LT May 17 '16 at 4:23
• @J.M. but it seems from input[359] and [360] getting from the table is quicker? – James LT May 17 '16 at 4:24
• AIn't much of a difference, AFAICT. Try using RepeatedTiming[] as a check. – J. M.'s technical difficulties May 17 '16 at 4:44

## 1 Answer

This is a very quick-and-dirty, but gives 4X speed-up (7X with tweak for symmetry) on my crappy netbook for the n=8 case, don't have time or patience to test bigger cases to see scaling differences.

Perhaps a description of what you're trying to calculate? It appears to be some combinatorial problem, there may well be a much more efficient scheme to do what you want.

In any case, give this a whirl (and if you're going to iterate cases through various n, don't clear the helper functions between runs):

Clear[s1, s2, bc, mx, sq]
Hx[i_, j_, k_, l_] /; (i > j || k > l) = Missing[];
Hx[n1_, n2_, n3_, n4_] := Hx[n3, n4, n1, n2] =
mx[n1, n2, n3, n4]*
Sum[(-1)^(m1 + m2 + m3 + m4)*bc[n1 + 1, m1 + 2]*bc[n2 + 1, m2 + 2]*
bc[n3 + 1, m3 + 2]*bc[n4 + 1, m4 + 2]*bc[m1 + m3, m1]*
bc[m2 + m4, m2]*(m1 + m3 + 1)*(m2 + m4 + 1)*
(sq[m1, m3]*s1[m1, m2, m3, m4] + (sq[m2, m4])*
s2[m1, m2, m3, m4]),
{m1, 0, n1 - 1}, {m2, 0, n2 - 1}, {m3, 0,n3 - 1}, {m4, 0, n4 - 1}];

s1[m1_, m2_, m3_, m4_] := s1[m1, m2, m3, m4] =
Sum[bc[m1 + m3 + k + 2, k]/2^k, {k, 0, m2 + m4 + 1}];

s2[m1_, m2_, m3_, m4_] := s2[m1, m2, m3, m4] =
Sum[bc[m2 + m4 + l + 2, l]/2^l, {l, 0, m1 + m3 + 1}];

bc[a_, b_] := bc[a, b] = Binomial[a, b];

sq[a_, b_] := sq[a, b] = ((a + b + 2)/2^(a + b));

SetAttributes[mx, Orderless];
mx[n1_, n2_, n3_, n4_] := mx[n1, n2, n3, n4] =
(1/(4*Sqrt[n1*(n1 + 1)*n2*(n2 + 1)*n3*(n3 + 1)*n4*(n4 + 1)]));

(* to make a table, e.g.: *)
nn = 8
res2 = Table[Hx[a, b, c, d], {a, nn}, {b, nn}, {c, nn}, {d, nn}];

• Cool! I also find this Define a function recursively. I was wondering could we do the same tweak for symmetry like s2[m1_, m2_, m3_, m4_] := s2[m3, m2, m1, m4]  like Hx? – James LT May 17 '16 at 15:41


text:
Copied to
clipboard

## G = D4×F7order 336 = 24·3·7

### Direct product of D4 and F7

Series: Derived Chief Lower central Upper central

 Derived series C1 — C14 — D4×F7
 Chief series C1 — C7 — C14 — C2×C7⋊C3 — C2×F7 — C22×F7 — D4×F7
 Lower central C7 — C14 — D4×F7
 Upper central C1 — C2 — D4

Generators and relations for D4×F7
G = < a,b,c,d | a4=b2=c7=d6=1, bab=a-1, ac=ca, ad=da, bc=cb, bd=db, dcd-1=c5 >

Subgroups: 500 in 108 conjugacy classes, 44 normal (22 characteristic)
C1, C2, C2, C3, C4, C4, C22, C22, C6, C7, C2×C4, D4, D4, C23, C12, C2×C6, D7, D7, C14, C14, C2×D4, C7⋊C3, C2×C12, C3×D4, C22×C6, Dic7, C28, D14, D14, D14, C2×C14, F7, F7, C2×C7⋊C3, C2×C7⋊C3, C6×D4, C4×D7, D28, C7⋊D4, C7×D4, C22×D7, C7⋊C12, C4×C7⋊C3, C2×F7, C2×F7, C2×F7, C22×C7⋊C3, D4×D7, C4×F7, C4⋊F7, Dic7⋊C6, D4×C7⋊C3, C22×F7, D4×F7
Quotients: C1, C2, C3, C22, C6, D4, C23, C2×C6, C2×D4, C3×D4, C22×C6, F7, C6×D4, C2×F7, C22×F7, D4×F7

Permutation representations of D4×F7
On 28 points - transitive group 28T41
Generators in S28
(1 15 8 22)(2 16 9 23)(3 17 10 24)(4 18 11 25)(5 19 12 26)(6 20 13 27)(7 21 14 28)
(15 22)(16 23)(17 24)(18 25)(19 26)(20 27)(21 28)
(1 2 3 4 5 6 7)(8 9 10 11 12 13 14)(15 16 17 18 19 20 21)(22 23 24 25 26 27 28)
(1 8)(2 11 3 14 5 13)(4 10 7 12 6 9)(15 22)(16 25 17 28 19 27)(18 24 21 26 20 23)

G:=sub<Sym(28)| (1,15,8,22)(2,16,9,23)(3,17,10,24)(4,18,11,25)(5,19,12,26)(6,20,13,27)(7,21,14,28), (15,22)(16,23)(17,24)(18,25)(19,26)(20,27)(21,28), (1,2,3,4,5,6,7)(8,9,10,11,12,13,14)(15,16,17,18,19,20,21)(22,23,24,25,26,27,28), (1,8)(2,11,3,14,5,13)(4,10,7,12,6,9)(15,22)(16,25,17,28,19,27)(18,24,21,26,20,23)>;

G:=Group( (1,15,8,22)(2,16,9,23)(3,17,10,24)(4,18,11,25)(5,19,12,26)(6,20,13,27)(7,21,14,28), (15,22)(16,23)(17,24)(18,25)(19,26)(20,27)(21,28), (1,2,3,4,5,6,7)(8,9,10,11,12,13,14)(15,16,17,18,19,20,21)(22,23,24,25,26,27,28), (1,8)(2,11,3,14,5,13)(4,10,7,12,6,9)(15,22)(16,25,17,28,19,27)(18,24,21,26,20,23) );

G=PermutationGroup([[(1,15,8,22),(2,16,9,23),(3,17,10,24),(4,18,11,25),(5,19,12,26),(6,20,13,27),(7,21,14,28)], [(15,22),(16,23),(17,24),(18,25),(19,26),(20,27),(21,28)], [(1,2,3,4,5,6,7),(8,9,10,11,12,13,14),(15,16,17,18,19,20,21),(22,23,24,25,26,27,28)], [(1,8),(2,11,3,14,5,13),(4,10,7,12,6,9),(15,22),(16,25,17,28,19,27),(18,24,21,26,20,23)]])

G:=TransitiveGroup(28,41);

35 conjugacy classes

 class 1 2A 2B 2C 2D 2E 2F 2G 3A 3B 4A 4B 6A ··· 6F 6G ··· 6N 7 12A 12B 12C 12D 14A 14B 14C 28 order 1 2 2 2 2 2 2 2 3 3 4 4 6 ··· 6 6 ··· 6 7 12 12 12 12 14 14 14 28 size 1 1 2 2 7 7 14 14 7 7 2 14 7 ··· 7 14 ··· 14 6 14 14 14 14 6 12 12 12

35 irreducible representations

 dim 1 1 1 1 1 1 1 1 1 1 1 1 12 2 2 6 6 6 type + + + + + + + + + + + image C1 C2 C2 C2 C2 C2 C3 C6 C6 C6 C6 C6 D4×F7 D4 C3×D4 F7 C2×F7 C2×F7 kernel D4×F7 C4×F7 C4⋊F7 Dic7⋊C6 D4×C7⋊C3 C22×F7 D4×D7 C4×D7 D28 C7⋊D4 C7×D4 C22×D7 C1 F7 D7 D4 C4 C22 # reps 1 1 1 2 1 2 2 2 2 4 2 4 1 2 4 1 1 2

Matrix representation of D4×F7 in GL8(𝔽337)

 1 330 0 0 0 0 0 0 241 336 0 0 0 0 0 0 0 0 336 0 0 0 0 0 0 0 0 336 0 0 0 0 0 0 0 0 336 0 0 0 0 0 0 0 0 336 0 0 0 0 0 0 0 0 336 0 0 0 0 0 0 0 0 336
,
 336 7 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
,
 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 336 336 336 336 336 336 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0
,
 128 0 0 0 0 0 0 0 0 128 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 336 336 336 336 336 336 0 0 0 0 0 0 1 0

G:=sub<GL(8,GF(337))| [1,241,0,0,0,0,0,0,330,336,0,0,0,0,0,0,0,0,336,0,0,0,0,0,0,0,0,336,0,0,0,0,0,0,0,0,336,0,0,0,0,0,0,0,0,336,0,0,0,0,0,0,0,0,336,0,0,0,0,0,0,0,0,336],[336,0,0,0,0,0,0,0,7,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1],[1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,336,1,0,0,0,0,0,0,336,0,1,0,0,0,0,0,336,0,0,1,0,0,0,0,336,0,0,0,1,0,0,0,336,0,0,0,0,1,0,0,336,0,0,0,0,0],[128,0,0,0,0,0,0,0,0,128,0,0,0,0,0,0,0,0,1,0,0,0,336,0,0,0,0,0,0,1,336,0,0,0,0,0,0,0,336,0,0,0,0,0,1,0,336,0,0,0,0,0,0,0,336,1,0,0,0,1,0,0,336,0] >;

D4×F7 in GAP, Magma, Sage, TeX

D_4\times F_7
% in TeX

G:=Group("D4xF7");
// GroupNames label

G:=SmallGroup(336,125);
// by ID

G=gap.SmallGroup(336,125);
# by ID

G:=PCGroup([6,-2,-2,-2,-3,-2,-7,260,10373,887]);
// Polycyclic

G:=Group<a,b,c,d|a^4=b^2=c^7=d^6=1,b*a*b=a^-1,a*c=c*a,a*d=d*a,b*c=c*b,b*d=d*b,d*c*d^-1=c^5>;
// generators/relations

׿
×
𝔽


text:
Can't Run Module Acceptance Test

I am trying to write tests for puppetlabs-apache (so that my pull request can be accepted). When I run bundle exec rspec spec/acceptance as the documentation says, I get an error facter: command not found. I think I followed all the setup instructions, but I can't run the tests.

This is the error (repeated multiple times):

Failure/Error: install_bolt_on(hosts) unless pe_install?
Beaker::Host::CommandFailure:
Host 'ubuntu-1404-x64' exited with 127 running:
facter --json "osfamily"
Last 10 lines of output were:


text:
## IACR News

Here you can see all recent updates to the IACR webpage. These updates are also available:

There is currently a problem with the jobs channel, and new jobs listings are not appearing here. Please see the jobs page.

#### 05 October 2019

###### Videos on YouTube for Crypto 2019 program and rump session
CRYPTO
Videos from the Crypto 2019 conference are online on YouTube. The videos from the Rump Session are in a separate playlist.

#### 03 October 2019

###### Samuel Jaques, Michael Naehrig, Martin Roetteler, Fernando Virdia
ePrint Report
Grover's search algorithm gives a quantum attack against block ciphers by searching for a key that matches a small number of plaintext-ciphertext pairs. This attack uses $O(\sqrt{N})$ calls to the cipher to search a key space of size $N$. Previous work in the specific case of AES derived the full gate cost by analyzing quantum circuits for the cipher, but focused on minimizing the number of qubits.

In contrast, we study the cost of quantum key search attacks under a depth restriction and introduce techniques that reduce the oracle depth, even if it requires more qubits. As cases in point, we design quantum circuits for the block ciphers AES and LowMC. Our circuits give a lower overall attack cost in both the gate count and depth-times-width cost models. In NIST's post-quantum cryptography standardization process, security categories are defined based on the concrete cost of quantum key search against AES. We present new, lower cost estimates for each category, so our work has immediate implications for the security assessment of post-quantum cryptography.

As part of this work, we release Q# implementations of the full Grover oracle for AES-128, -192, -256 and for the three LowMC instantiations used in Picnic, including unit tests and code to reproduce our quantum resource estimates. To the best of our knowledge, these are the first two such full implementations and automatic resource estimations.
###### Craig Costello
ePrint Report
This paper introduces a new way of instantiating supersingular isogeny-based cryptography in which parties can work in both the ($p+1$)-torsion of a set of supersingular curves and in the ($p-1$)-torsion corresponding to the set of their quadratic twists. Although the isomorphism between a given supersingular curve and its quadratic twist is not defined over GF($p^2$) in general, restricting operations to the x-lines of both sets of twists allows all arithmetic to be carried out over GF($p^2$) as usual. Furthermore, since supersingular twists always have the same GF($p^2$)-rational j-invariant, the SIDH protocol remains unchanged when Alice and Bob are free to work in both sets of twists.

This framework lifts the restrictions on the shapes of the underlying prime fields originally imposed by Jao and De Feo, and allows a range of new options for instantiating isogeny- based public key cryptography. This includes alternatives that exploit Mersenne, Solinas, and Montgomery-friendly primes, the possibility of halving the size of the primes of the Jao-De Feo construction at no known loss of asymptotic security, and more.
###### Sanjit Chatterjee, R. Kabaleeshwaran
ePrint Report
The Camenisch-Lysyanskaya rerandomizable signature (CL-RRS) scheme is an important tool in the construction of privacy preserving protocols. One of the limitations of CL-RRS is that the signature size is linear in the number of messages to be signed. In 2016, Pointcheval-Sanders introduced a variant of rerandomizable signature (PS-RRS) scheme which removes the above limitation. However, the security of PS-RRS scheme was proved under an interactive assumption. In 2018, Pointcheval-Sanders improved this to give a reduction under a parameterized assumption.

In 2012, Gerbush et al.\ introduced the dual-form signature technique to remove the dependency on interactive/parameterized assumption. They applied this technique on the CL-RRS scheme (for single message) and proved its unforgeability under static assumptions instead of the interactive assumption used in the original work but in the symmetric composite-order pairing setting.

In this work, we realize a fully rerandomizable signature scheme in the prime order setting without random oracle based on the SXDH assumption. The signature structure is derived from Ghadafi's structure-preserving signature. We first apply the dual-form signature technique to obtain a composite-order variant, called \texttt{RRSc}. A signature in \texttt{RRSc} consists of only two group elements and is thus independent of the message block length. The security of the proposed scheme is based on subgroup hiding assumptions. Then we use the dual pairing vector space framework to obtain a prime-order variant called \texttt{RRS} and prove its security under the SXDH assumption.
ePrint Report
Outsourcing data to the cloud for personal use is becoming an everyday trend rather than an extreme scenario. The frequent out- sourcing of data increases the possible attack window because users do not fully control their personal files. Typically, once there are established secure channels between two endpoints, communication is considered se- cure. However, in the cloud model the receiver–the cloud–cannot be fully trusted, either because it has been under adversarial control, or because it acts maliciously to increase its revenue by deleting infrequent accessed file blocks. One approach used by current literature to address the aforemen- tioned security concerns is via Remote Data Integrity Checking (RDIC) protocols, whereby a data owner can challenge an untrusted cloud service provider (CSP) to prove faithful storage of its data. Current RDIC protocols assume that the original data format remains unchanged. However, users may wish to compress their data in order to enjoy less charges. In that case, current RDIC protocols become impracti- cal because, each time compression happens on a file, the user has to run a new RDIC protocol. In this work we initiate the study for Auditable Compressed Storage (ACS). After defining the new model we instanti- ate two protocols for different widely used compression techniques: run length encoding and Huffman encoding. In contrast with conventional RDIC, our protocols allow a user to delegate the compression to the cloud in a provably secure way: The client can verify correctness of com- pression without having to download the entire uncompressed file and check it against the compressed one.
###### Tamalika Mukherjee, Noah Stephens-Davidowitz
ePrint Report
We show how to generalize lattice reduction algorithms to module lattices in order to reduce $\gamma$-approximate ModuleSVP over module lattices with rank $k \geq2$ to $\gamma'$-approximate ModuleSVP over module lattices with rank $2 \leq \beta \leq k$. To do so, we modify the celebrated slide-reduction algorithm of Gama and Nguyen to work with module filtrations, a higher-dimensional analogue of the ($\mathbb{Z}$-)basis of a lattice. The particular value of $\gamma$ that we achieve depends on the underlying number field $K$, the ring $R \subset K$, and the embedding (as well as, of course, $k$ and $\beta$). However, for reasonable choices of these parameters, the approximation factor that we achieve is surprisingly close to the one achieved by plain'' lattice reduction algorithms, which require an arbitrary SVP oracle in the same dimension. In other words, we show that ModuleSVP oracles are nearly as useful as SVP oracles for solving approximate ModuleSVP in higher dimensions. Our result generalizes the recent independent result of Lee, Pellet-Mary, Stehl\'e, and Wallet, which works in the important special case when $\beta = 2$ and $R = \mathcal{O}_K$ is the ring of integers of $K$ under the canonical embedding. Indeed, at a high level our reduction can be thought of as a generalization of theirs in roughly the same way that slide reduction generalizes LLL reduction.
###### Murat Yasin Kubilay, Mehmet Sabir Kiraz, Haci Ali Mantar, Ramazan Girgin
ePrint Report
During the last decade, several misbehaving Certificate Authorities (CA) have issued fraudulent TLS certificates allowing MITM kinds of attacks which result in serious security incidents. In order to avoid such incidents, Yakubov et al. recently proposed a new PKI architecture where CAs issue, revoke, and validate X.509 certificates on a public blockchain. In their proposal, each CA has a smart contract on the blockchain for publishing the hash values of its issued certificates and managing their revocation status. However, their proposal has several security and privacy issues. First, TLS clients can only validate certificates through either full nodes or web services, but cannot verify the correctness of the incoming responses. Second, certificate transparency is not fully provided because CAs do not store the certificates themselves but only their hash values in the blockchain which makes to detect fake ones impossible. In this paper, we eliminate the issues of the Yakubov et al.’s scheme and propose a new PKI architecture based on permissioned blockchain with a modified PBFT consensus mechanism. In our modified PBFT, the validators (i.e., the consensus nodes) utilize a dynamic threshold signature scheme to generate signed blocks. In this way, the trust to external entities can be completely eliminated during certificate validation. More concretely, TLS clients can easily verify the genuinity of the final state of the TLS certificates using signed block headers and the Merkle proofs. Also, the privacy of the TLS clients is fully preserved during validation process by avoiding additional communication with the external entities. Our scheme enjoys the dynamic property of the threshold signature because TLS clients do not have to change the verification key even if the validator set is dynamic. Furthermore, TLS clients are also not required to be a peer of the blockchain network and avoid communication overhead. We implement our proposal on private Ethereum network to demonstrate the experimental results. The results show that our proposal has negligible overhead during TLS handshake. The certificate validation duration is less than the duration in the conventional PKI and Yakubov et al.’s scheme.
###### Utsav Banerjee, Tenzin S. Ukyab, Anantha P. Chandrakasan
ePrint Report
Public key cryptography protocols, such as RSA and elliptic curve cryptography, will be rendered insecure by Shor’s algorithm when large-scale quantum computers are built. Cryptographers are working on quantum-resistant algorithms, and lattice-based cryptography has emerged as a prime candidate. However, high computational complexity of these algorithms makes it challenging to implement lattice-based protocols on low-power embedded devices. To address this challenge, we present Sapphire – a lattice cryptography processor with configurable parameters. Efficient sampling, with a SHA-3-based PRNG, provides two orders of magnitude energy savings; a single-port RAM-based number theoretic transform memory architecture is proposed, which provides 124k-gate area savings; while a low-power modular arithmetic unit accelerates polynomial computations. Our test chip was fabricated in TSMC 40nm low-power CMOS process, with the Sapphire cryptographic core occupying 0.28 mm2 area consisting of 106k logic gates and 40.25 KB SRAM. Sapphire can be programmed with custom instructions for polynomial arithmetic and sampling, and it is coupled with a low-power RISC-V micro-processor to demonstrate NIST Round 2 lattice-based CCA-secure key encapsulation and signature protocols Frodo, NewHope, qTESLA, CRYSTALS-Kyber and CRYSTALS-Dilithium, achieving up to an order of magnitude improvement in performance and energy-efficiency compared to state-of-the-art hardware implementations. All key building blocks of Sapphire are constant-time and secure against timing and simple power analysis side-channel attacks. We also discuss how masking-based DPA countermeasures can be implemented on the Sapphire core without any changes to the hardware.
###### Mingchao Yu, Saeid Sahraei, Songze Li, Salman Avestimehr, Sreeram Kannan, Pramod Viswanath
ePrint Report
In this paper, we propose coded Merkle tree (CMT), a novel hash accumulator that offers a constant-cost protection against data availability attacks in blockchains, even if the majority of the network nodes are malicious. A CMT is constructed using a family of sparse erasure codes on each layer, and is recovered by iteratively applying a peeling-decoding technique that enables a compact proof for data availability attack on any layer. Our algorithm enables any node to verify the full availability of any data block generated by the system by just downloading a $\Theta(1)$ byte block hash commitment and randomly sampling $\Theta(\log b)$ bytes, where $b$ is the size of the data block. With the help of only one honest node in the system, our method also allows any node to verify any tampering of the coded Merkle tree by just downloading $\Theta(\log b)$ bytes. We provide a modular library for CMT in {\sf Rust} and {\sf Python} and demonstrate its efficacy inside the {\sf Parity Bitcoin} client.
###### Gang Wang, Zhijie Jerry Shi, Mark Nixon, Song Han
ePrint Report
The fast developing Industrial Internet of Things (IIoT) technologies provide a promising opportunity to build large-scale systems to connect numerous heterogeneous devices into the Internet. Most existing IIoT infrastructures are based on a centralized architecture, which is easier for management but cannot effectively support immutable and verifiable services among multiple parties. Blockchain technology provides many desired features for large-scale IIoT infrastructures, such as decentralization, trustworthiness, trackability, and immutability. This paper presents a blockchain-based IIoT architecture to support immutable and verifiable services. However, when applying blockchain technology to the IIoT infrastructure, the required storage space posts a grant challenge to resource-constrained IIoT infrastructures. To address the storage issue, this paper proposes a hierarchical blockchain storage structure, \textit{ChainSplitter}. Specially, the proposed architecture features a hierarchical storage structure where the majority of the blockchain is stored in the clouds, while the most recent blocks are stored in the overlay network of the individual IIoT networks. The proposed architecture seamlessly binds local IIoT networks, the blockchain overlay network, and the cloud infrastructure together through two connectors, the \textit{blockchain connector} and the \textit{cloud connector}, to construct the hierarchical blockchain storage. The blockchain connector in the overlay network builds blocks in blockchain from data generated in IIoT networks, and the cloud connector resolves the blockchain synchronization issues between the overlay network and the clouds. We also provide a case study to show the efficiency of the proposed hierarchical blockchain storage in a practical Industrial IoT case.
###### Ronald Cramer, Chaoping Xing, Chen Yuan
ePrint Report
Since the mid 2000s, asymptotically-good strongly-multiplicative linear secret sharing schemes over a fixed finite field have turned out as a central theoretical primitive in numerous constant-communication-rate results in multi-party cryptographic scenarios, and, surprisingly, in two-party cryptography as well.

Known constructions of this most powerful class of arithmetic secret sharing schemes all rely heavily on algebraic geometry (AG), i.e., on dedicated AG codes based on asymptotically good towers of algebraic function fields defined over finite fields. It is a well-known open question since the first (explicit) constructions of such schemes appeared in CRYPTO 2006 whether the use of heavy machinery'' can be avoided here. I.e., the question is whether the mere existence of such schemes can also be proved by elementary'' techniques only (say, from classical algebraic coding theory), even disregarding effective construction. So far, there is no progress.

In this paper we show the theoretical result that, (1) {\em no matter whether this open question has an affirmative answer or not}, these schemes {\em can} be constructed explicitly by {\em elementary algorithms} defined in terms of basic algebraic coding theory. This pertains to all relevant operations associated to such schemes, including, notably, the generation of an instance for a given number of players $n$, as well as error correction in the presence of corrupt shares. Moreover, we show that (2) the algorithms are {\em quasi-linear time} (in $n$); this is several asymptotically significantly more efficient than known constructions. That said, the {\em analysis} of the mere termination of these algorithms {\em does} still rely on algebraic geometry, in that it requires blackbox application'' of suitable {\em existence} results for these schemes.

Our method employs a nontrivial, novel adaptation of a classical (and ubiquitous) paradigm from coding theory that enables transformation of {\em existence} results on asymptotically good codes into {\em explicit construction} of such codes via {\em concatenation}, at some constant loss in parameters achieved. In a nutshell, our generating idea is to combine a cascade of explicit but asymptotically-bad-yet-good-enough schemes'' with an asymptotically good one in such a judicious way that the latter can be selected with exponentially small number of players in that of the compound scheme. This opens the door to efficient, elementary exhaustive search.

In order to make this work, we overcome a number of nontrivial technical hurdles. Our main handles include a novel application of the recently introduced notion of Reverse Multiplication-Friendly Embeddings (RMFE) from CRYPTO 2018, as well as a novel application of a natural variant in arithmetic secret sharing from EUROCRYPT 2008.
###### Thijs Veugen, Thomas Attema, Gabriele Spini
ePrint Report
We consider the problem of securely generating the keys of the Paillier crypto system [11] with (t, n) threshold decryption, without a trusted dealer. Nishide and Sakurai [10] describe a solution, secure in the malicious model. We use their ideas to make a simpler solution for the semi-honest model, and further introduce a few optimisations. We implement the secure key generation protocol on a single computer, and consider its performance.
###### Arinjita Paul, S. Sharmila Deva Selvi, C. Pandu Rangan
ePrint Report
Blaze, Bleumer and Strauss introduced the notion of proxy re-encryption (PRE), which enables a semi-trusted proxy to transform ciphertexts under Alice's public key into ciphertexts under Bob's public key. The important property to note here is, the proxy should not learn anything about the plaintext encrypted. In 2009, Weng et al. introduced the concept of conditional proxy re-encryption (CPRE), which permits the proxy to re-encrypt only ciphertexts satisfying a condition specified by Alice into a ciphertext for Bob. CPRE enables fine-grained delegation of decryption rights useful in many practical scenarios, such as blockchain-enabled distributed cloud storage and encrypted email forwarding. Several CPRE schemes exist in the literature based on costly bilinear pairing operation in the random oracle model. We propose the first construction of an efficient CPRE scheme without pairing, satisfying chosen ciphertext security under the computational Diffie Hellman (CDH) assumption and its variant in the random oracle model.

#### 02 October 2019

###### Ronald Cramer, Chaoping Xing
ePrint Report
A {\em blackbox} secret sharing (BBSS) scheme works in exactly the same way for all finite Abelian groups $G$; it can be instantiated for any such group $G$ and {\em only} black-box access to its group operations and to random group elements is required. A secret is a single group element and each of the $n$ players' shares is a vector of such elements. Share-computation and secret-reconstruction is by integer linear combinations. These do not depend on $G$, and neither do the privacy and reconstruction parameters $t,r$. This classical, fundamental primitive was introduced by Desmedt and Frankel (CRYPTO 1989) in their context of threshold cryptography.'' The expansion factor is the total number of group elements in a full sharing divided by $n$. For threshold BBSS with $t$-privacy ($1\leq t \leq n-1$), $t+1$-reconstruction and arbitrary $n$, constructions with minimal expansion $O(\log n)$ exist (CRYPTO 2002, 2005).

These results are firmly rooted in number theory; each makes (different) judicious choices of orders in number fields admitting a vector of elements of very large length (in the number field degree) whose corresponding Vandermonde-determinant is sufficiently controlled so as to enable BBSS by a suitable adaptation of Shamir's scheme. Alternative approaches generally lead to very large expansion. The state of the art of BBSS has not changed for the last 15 years.

Our contributions are two-fold. (1) We introduce a novel, nontrivial, effective construction of BBSS based on {\em coding theory} instead of number theory. For threshold-BBSS we also achieve minimal expansion factor $O(\log n)$. (2) Our method is more versatile. Namely, we show, for the first time, BBSS that is {\em near-threshold}, i.e., $r-t$ is an arbitrarily small constant fraction of $n$, {\em and} that has expansion factor~$O(1)$, i.e., individual share-vectors of {\em constant} length (asymptotically expansionless''). Threshold can be concentrated essentially freely across full range. We also show expansion is minimal for near-threshold and that such BBSS cannot be attained by previous methods.

Our general construction is based on a well-known mathematical principle, the local-global principle. More precisely, we first construct BBSS over local rings through either Reed-Solomon or algebraic geometry codes. We then glue'' these schemes together in a dedicated manner to obtain a global secret sharing scheme, i.e., defined over the integers, which, as we finally prove using novel insights, has the desired BBSS properties. Though our main purpose here is advancing BBSS for its own sake, we also briefly address possible protocol applications.
###### Gang Wang
ePrint Report
Emerging non-volatile memories (NVMs) have been considered promising alternatives to DRAM for future main memory design. Among the NVMs, Phase-Change Memory (PCM) can serve as a good substitute due to its low standby power, high density, and good scalability. However, PCM material also induces security design challenges mainly due to its interior non-volatility. Designing the memory system necessitates considering the challenges which may open the backdoor for attackers. A threat model can help to identify security vulnerabilities in design processes. It is all about finding the security problems, and therefore it should be done early in the design and adoption of manufacture. To our knowledge, this paper is the first attempt to thoroughly discuss the potential threat models for the PCM memory, which can provide a good reference for designing the new generation of PCM. Meanwhile, this paper gives security advice and potential security solutions to design a secure PCM to protect against these potential threats.
###### Sarvar Patel, Giuseppe Persiano, Kevin Yeo
ePrint Report
Encrypted multi-maps (EMMs) enable clients to outsource the storage of a multi-map to a potentially untrusted server while maintaining the ability to perform operations in a privacy-preserving manner. EMMs are an important primitive as they are an integral building block for many practical applications such as searchable encryption and encrypted databases. In this work, we formally examine the tradeoffs between privacy and efficiency for EMMs.

Currently, all known dynamic EMMs with constant overhead reveal if two operations are performed on the same key or not; that is, they leak the $\mathit{global\ key\text{-}equality\ pattern}$. In our main result, we present strong evidence that the leakage of the global key-equality pattern is inherent for any dynamic EMM construction with $O(1)$ efficiency. In particular, we consider the slightly smaller leakage of $\mathit{decoupled\ key\text{-}equality\ pattern}$ where leakage of key-equality between update and query operations is decoupled and the adversary only learns whether two operations of the $\mathit{same\ type}$ are performed on the same key or not. We show that any EMM with at most decoupled key-equality pattern leakage incurs $\Omega(\log n)$ overhead in the $\mathit{leakage\ cell\ probe\ model}$. This is tight as there exist ORAM-based constructions of EMMs with logarithmic slowdown that leak no more than the decoupled key-equality pattern (and actually, much less). Furthermore, we present stronger lower bounds that encrypted multi-maps leaking at most the decoupled key-equality pattern but are able to perform one of either the update or query operations in the plaintext still require $\Omega(\log n)$ overhead. Finally, we extend our lower bounds to show that dynamic, $\mathit{response\text{-}hiding}$ searchable encryption schemes must also incur $\Omega(\log n)$ overhead even when one of either the document updates or searches may be performed in the plaintext.
###### Pasin Manurangsi, Akshayaram Srinivasan, Prashant Nalini Vasudevan
ePrint Report
Robust secret sharing is a strengthening of standard secret sharing that allows the shared secret to be recovered even if some of the shares being used in the reconstruction have been adversarially modified. In this work, we study the setting where out of all the $n$ shares, the adversary is allowed to adaptively corrupt and modify $t$ shares, where $n = 2t+1$. Further, we deal with \textit{rushing} adversaries, meaning that the adversary is allowed to see the honest parties' shares before modifying its own shares.

It is known that when $n = 2t+1$, to share a secret of length $m$ bits and recover it with error less than $2^{-\sec}$, shares of size at least $m+\sec$ bits are needed. Recently, Bishop, Pastro, Rajaraman, and Wichs (EUROCRYPT 2016) constructed a robust secret sharing scheme with shares of size $m + O(\sec\cdot\textrm{polylog}(n,m,\sec))$ bits that is secure in this setting against non-rushing adversaries. Later, Fehr and Yuan (EUROCRYPT 2019) constructed a scheme that is secure against rushing adversaries, but has shares of size $m + O(\sec\cdot n^{\epsilon}\cdot \textrm{polylog}(n,m,\sec))$ bits for an arbitrary constant $\epsilon > 0$. They also showed a variant of their construction with share size $m + O(\sec\cdot\textrm{polylog}(n,m,\sec))$ bits, but with super-polynomial reconstruction time. We present a robust secret sharing scheme that is secure against rushing adversaries, has shares of size $m+O(\sec \log{n} (\log{n}+\log{m}))$ bits, and has polynomial-time sharing and reconstruction. Central to our construction is a polynomial-time algorithm for a problem on semi-random graphs that arises naturally in the paradigm of local authentication of shares used by us and in the aforementioned work.
###### V. Ustimenko
ePrint Report
We suggest new applications of protocols of Non-commutative cryptography defined in terms of subsemigroups of Affine Cremona Semigroups over finite commutative rings and their homomorphic images to the constructions of possible instruments of Post Quantum Cryptography. This approach allows to define cryptosystems which are not public keys. When extended protocol is finished correspondents have the collision multivariate transformation on affine space K ^n or variety (K*)^n where K is a finite commutative ring and K* is nontrivial multiplicative subgroup of K . The security of such protocol rests on the complexity of word problem to decompose element of Affine Cremona Semigroup given in its standard form into composition of given generators. The collision map can serve for the safe delivery of several bijective multivariate maps F_i (generators) on K^n (or (K*)^n) from one correspondent to another. So asymmetric cryptosystem with nonpublic multivariate generators where one side (Alice) knows inverses of F_i but other does not have such a knowledge is possible. We consider the usage of single protocol or combinations of two protocols with platforms of different nature. The usage of two protocols with the collision spaces K^n and (K*)^n allows safe delivery of two sets of generators of different nature. In terms of such sets we define an asymmetric encryption scheme with the plainspace (K*)^n, cipherspace K^n and multivariate non-bijective encryption map of unbounded degree O(n) and polynomial density on K^n with injective restriction on (K*)^n. Algebraic cryptanalysis faces the problem to interpolate a natural decryption transformation which is not a map of polynomial density.
###### Tilen Marc, Miha Stopar, Jan Hartman, Manca Bizjak, Jolanda Modic
ePrint Report
Functional encryption is a generalization of public-key encryption in which possessing a secret functional key allows one to learn a function of what the ciphertext is encrypting. This paper introduces the first fully-fledged open source cryptographic libraries for functional encryption. It also presents how functional encryption can be used to build efficient privacy-enhanced machine learning models and it provides an implementation of three prediction services that can be applied on the encrypted data. Finally, the paper discusses the advantages and disadvantages of the alternative approach for building privacy-enhanced machine learning models by using homomorphic encryption.
###### Alexei Zamyatin, Mustafa Al-Bassam, Dionysis Zindros, Eleftherios Kokoris-Kogias, Pedro Moreno-Sanchez, Aggelos Kiayias, William J. Knottenbelt
ePrint Report
Communication across distributed systems, where each system runs its own consensus, is a problem previously studied only within a single trust domain (e.g., a datacenter). With the appearance of distributed ledgers or blockchains, numerous protocols requiring robustness against adversarial behavior have emerged. Cross-chain communication thereby plays a fundamental role in cryptocurrency exchanges, sharding, as well as the bootstrapping and migration of distributed ledgers. Unfortunately, existing proposals are designed ad-hoc for specific use-cases, making it hard to gain confidence on their correctness and to use them as building blocks for new systems.

In this paper, we provide the first systematic exposition of protocols for cross-chain communication. Through formalization of the underlying research question, which reduces to the fair exchange problem, we identify threat and network model assumptions, necessary for designing correct cross-chain communication protocols. We overview main applications, derive a classification and provide a comparative analysis of existing approaches. Further, we survey and classify techniques for verifying state cross-chain and mechanisms for constructing locks.


text:
# Hadroproduction of W + W − b b ¯ $\overline{\mathrm{b}}$ at NLO accuracy matched with shower Monte Carlo programs

Maria Vittoria Garzelli (Institute of Physics and MTA-DE Particle Physics Research Group, University of Debrecen, H-4010 Debrecen P.O.Box 105, Hungary) ; Adam Kardos (Institute of Physics and MTA-DE Particle Physics Research Group, University of Debrecen, H-4010 Debrecen P.O.Box 105, Hungary) ; Zoltán Trócsányi (Institute of Physics and MTA-DE Particle Physics Research Group, University of Debrecen, H-4010 Debrecen P.O.Box 105, Hungary)

15 August 2014

Abstract: We present the computation of the differential cross section for the process p p ( p ¯ $\overline{p}$ ) → (W + W − b b ¯ $\overline{\mathrm{b}}$ →) e + ν e μ − ν ¯ $\overline{\nu}$ μ b b ¯ $\overline{\mathrm{b}}$ + X at NLO QCD accuracy matched to Shower Monte Carlo (SMC) simulations using PowHel, on the basis of the interface between HELAC-NLO and POWHEG-BOX. We include all resonant and non-resonant contributions. This is achieved by fully taking into account the effect of off-shell t-quarks and off-shell W-bosons in the complex mass scheme. We also present a program called DECAYER that can be used to let the t-quarks present in the event files for p p ( p ¯ $\overline{p}$ ) → t t ¯ $\overline{\mathrm{t}}$ X processes decay including both the finite width of the t-quarks and spin correlations. We present predictions for both the Tevatron and the LHC, with emphasis on differences emerging from three different W + W − b b ¯ $\overline{\mathrm{b}}$ hadroproduction computations: (i) full implementation of the p p ( p ¯ $\overline{p}$ ) → W + W − b b ¯ $\overline{\mathrm{b}}$ process, (ii) generating on-shell t-quarks pushed off-shell with a Breit-Wigner finite width and decayed by Decayer, and (iii) on-shell t-quark production followed by decay in the narrow width approximation, as described by the SMC.

Published in: JHEP 1408 (2014) 069


text:
## Introduction To Hamiltonian Monte Carlo

Introduction to Hamiltonian Monte Carlo One thing that has been occupying my head in the past couple of weeks has been HMC and how it can be used in large data/large model context. HMC stands for Hamiltonian Monte Carlo and it’s the de facto Bayesian method for sampling due to it’s speed. Before getting into big datasets and big models, let me motivate this problem a little bit. If you are new to Bayesian modelling, I have a little primer on the topic so I will assume for the most part you are familiar with basic Bayesianism. [Read More]

## Wasserstein variational autoencoders

Variational auto-encoders (VAEs) are a latent space model. The idea is you have some latent space variable $z \in \mathbb{R}^{k}$ which describes your original variables $x\in\mathbb{R}^d$ in higher dimensional space by a latent model $p(x|z)$. Let’s assume that this distribution is given by a neural network with some parameters $\theta$ so that we assume $$x | z, \theta \sim N(g_\theta(z), 1).$$ Of course in reality, we don’t know $(z, \theta)$, we would like to infer these from the data. [Read More]

## Introduction To Tensorflow Estimator

In this post I am going to introduce tf.estimator library. So first of all, what is this library trying to do? When writing tensorflow code, there is a lot of repeated operations that we need to do: read the data in batches process the data, e.g. convert images to floats run a for loop and take a few gradient descent steps save model weights to disk output metrics to tensorboard The keras library makes this quite a bit easier, but there are times when you might need to use plain old tensorflow (it gets quite hacky to implement some multiple output models and GANs in keras). [Read More]

## FizzBuzz with neural networks and NALU

FizzBuzz is one of the most well-known interview questions. The problem is stated as: Write the numbers from 0 to n replacing any number divisible by 3 with Fizz, divisible by 5 by Buzz and divisible by both 3 and 5 by FizzBuzz. The example program should output 1, 2, Fizz, 3, Buzz, Fizz, 7, 8, Fizz, Buzz. A while back, there was this infamous post where the author claimed to solve this problem in an interview using tensorflow. [Read More]

## From Zero To State Of The Art NLP Part II - Transformers

Welcome to part two of the two part series on a crash course into state of the art natural language processing. This part is going to go through the transformer architecture from Attention Is All You Need. If you haven’t done so already, read the first part which introduces attention mechanisms. This post is all about transformers and assumes you know attention mechanisms.