Tag: symmetric

probability theory – First hitting time of a symmetric random walk

Definitions:

Let $xi_n$ be a symmetric random walk, i.e.,
$$
xi_n=eta_1+eta_2+dots+eta_n,
$$
where ${eta_n}$ is a sequence of i.i.d. random variables such that
$$
P{eta_n=1}=P{eta_n=-1}=frac{1}{2}.
$$
Furthermore, we define the first hitting time to be $$tau=minleft{n:|xi_n|=Kright},$$
where $K$ is a positive integer.

I was reading a book on stochastic processes and here we want to show that $tau<infty$ a.s. The book proves this as follows

We want to show that $P{tau=infty}=0.$ To this end we shall estimate $P{tau>2Kn}.$ Notice that $$P{tau>2Kn}le left(1-frac{1}{2^{2K}}right)^nto0$$ as $ntoinfty.$ Thus, we have begin{align}
P{tau=infty}&=bigcap_{n=1}^infty P{tau>2Kn} \ &=lim_{ntoinfty} P{tau>2Kn}=0.
end{align}

After spending so many time, I could not figure out how to get the inequality $$P{tau>2Kn}le left(1-frac{1}{2^{2K}}right)^n$$ in the first line of the proof. Can someone help me understand why this inequality holds?

Many thanks in advance.

key management – Long-term symmetric key storage

I have some sensitive data that I need to encrypt and retain long-term (i.e., 5+ years at least). I’d ideally like to secure it using multiple hardware devices via a Shamir share. Something like:

data_key = gen_symmetric()
encrypted_data = encrypt_and_mac(key=data_key, payload=data_to_encrypt)
s1, s2, s3 = shamir(k=2, n=3, secret=data_key)
k1, k2, k3 = gen_symmetric(), gen_symmetric(), gen_symmetric()
encrypted_secrets = encrypt_and_mac(k1, s1) || encrypt_and_mac(k2, s2) || encrypt_and_mac(k3, s3)
output_to_save = encrypted_data || encrypted_secrets

With the idea to then save k1, k2, and k3 in hardware. (Along with some indication of which was the first, 2nd, 3rd secret).

This feels like I’m reinventing the wheel. Is there an existing standard for doing this or a similar crypto scheme? This related question suggests no. In that case, is the above scheme secure against an attacker that obtains one of the 3 devices?

table – Generate symmetric random tensor

I would like to generate a table $T$ of random values of rank $p$ such that my table is fully symmetric: If I swap any indices I get the same value. For example when $p=3$ I would like $T_{ijk}$ to be random with the following symmetry:
$$T_{ijk}=T_{ikj}=T_{jki}=T_{jik}=T_{kij}=T_{kji}$$

For the case $p=2$, it boils down to generate random matrices and I can simply take the upper triangular part and take its transpose.

I would like something in those lines for example:

T=RandomVariate[NormalDistribution[0, 1],{n,n,n}];

But here $T$ is not symmetric. How could I obtain $T$ such that for any permutations of its indices I get the same value?

Spectrum of symmetric Toeplitz matrix

A matrix is Toeplitz if it is constant on the diagonals parallel to the main diagonal.
I am looking for references on the spectrum of finite symmetric Toeplitz matrices over finite fields.

encryption – symmetric key generation in TLS 1.3

From what I am understanding Diffie-Hellman is used to derive the symmetric key in TLS1.3

I am reading this tls explanation and so many keys are derived

Is the shared secret the symmetric key and from it, we can generate the following keys?

early_secret= HKDF-Extract( salt=00,  key=00...)
empty_hash= SHA256("")
derived_secret= HKDF-Expand-Label(key = early_secret,  label = "derived",  context = empty_hash, len = 32)
handshake_secret= HKDF-Extract(salt = derived_secret, key = shared_secret)
client_handshake_traffic_secret= HKDF-Expand-Label(key = handshake_secret, label = "c hs traffic", context = hello_hash, len = 32)
server_handshake_traffic_secret= HKDF-Expand-Label(key = handshake_secret, label = "s hs traffic", context = hello_hash,len = 32)
client_handshake_key=HKDF-Expand-Label(key= client_handshake_traffic_secret, label = "key", context = "", len = 16)
server_handshake_key=HKDF-Expand-Label(key=server_handshake_traffic_secret, label = "key", context = "",  len = 16)
client_handshake_iv= HKDF-Expand-Label( key = client_handshake_traffic_secret,  label = "iv",  context = "", len = 12)
server_handshake_iv=HKDF-Expand-Label(key= server_handshake_traffic_secret,  label = "iv", context = "", len = 12)

So which is the symmetric key that inserts as input in AEAD?

rt.representation theory – Weakly symmetric Frobenius algebras

Let $A$ be a finite dimensional Frobenius algebra and $e$ and idempotent of $A$.
It is well known that the algebra $eAe$ does not have to be a Frobenius algebra. But if $A$ is additionally symmetric, then $eAe$ is also a symmetric Frobenius algebra for any idempotent $e$.

The Frobenius algebra $A$ is called weakly symmetric if for every indecomposable projective module $P$: $top(P)=soc(P)$.

Question: If $A$ is just weakly symmetric, is $eAe$ also always weakly-symmetric for any idempotent $e$?

co.combinatorics – Number of lattice points in a structural symmetric convex body

Let $f$ is a log-concave symmetric function on the interval $(-a,a)$, i.e., its logarithm $log f(x)$ is concave and $f(-x)=f(x)$ for $forall , xin (-a,a)$. Then we consider a $n$-dimensional convex body in Euclidean space
begin{equation}
mathscr{R}_n=left{ mathbf{x}=left(x_1,cdots,x_n right)in mathbb{R}^n： -sum_{i=1}^n log f(x_i) le nmathsf{A} right},
end{equation}
where the constant $mathsf{A}>-log f(0)$. Clearly, $mathscr{R}_n$ is symmetric about the origin.
I am interested the following problem relating to the lower bound of numbers of the lattice points inside $mathscr{R}_n$:

Does there exit a lattice sequence $left{ Lambda_n right}$ such that the number sequence ${N(n)}$ satisfies
begin{equation}
N(n)=frac{log left( |Lambda_n cap mathscr{R}_n| right)}{n}ge c, ~text{for sufficiently large $n$.}
end{equation}
I also want to know if there exits a best lowerbound $c$ for this asymptotic problem.

This problem is motivated by the answer of Geometry interpretation of any continuous random variable

complexity theory – Symmetric functions in NC¹

A boolean function $f colon {0,1}^n rightarrow {0,1}$ is symmetric if $f(x)$ depends only on the number of $1$s in $x$.
It is known that every boolean function is in $mathrm{NC}^1$, i.e. there is a circuit of depth $O(log n)$ computing it.

What is known about the constant inside the $O()$ notation? Specifically, can one construct, for every $c$, a symmetric function requiring a circuit of depth at least $c log n$? Or there is some constant $c_0$ such that every symmetric function has a circuit of depth at most $c_0log n$?

encryption – Whether TLS session resumption reuse the symmetric keys?

I am learning TLS Session Resumption.

What I got is session resumption can reduce 1 RTT for TLS 1.2 by reusing MasterSecret. Both the client and server needn’t to run key exchange algorithm.

My questions are:

  1. Whether session resumption reuses symmetric encryption keys (to encrypt TLS records).
  2. What factors affect whether to reuse symmetric encryption keys?

I searched around Google, but cannot find a authoritative answer. Here is what I got:

  1. Do not reuse encryption keys. Refer to SSL session key usage when browser opens multiple sockets to same server.
  2. Reuse encryption keys. Refer to https://wiki.openssl.org/index.php/SSL_and_TLS_Protocols#Session_Resumption

Any ideas are welcome.

About symmetric rank-1 random matrices

Consider a $2n-$dimensional symmetric random matrix $M$ of form, $M = begin{bmatrix} aa^T & ab^T \ ba^T & bb^T end{bmatrix}$ where $a$ and $b$ are $n$ dimensional random vectors.

  • Are there conditions known on $a$ and $b$ s.t we have the following property : that for any $hat{x} in S^{2n-1}$ and any $R in SO(2n)$, $Vert M hat{x} Vert$ be equidistributed as $Vert (R M R^T)hat{x} Vert$ ?