Questions tagged as ['algorithm-design']

(I guess no but why is this the case? Any way to make it possible?)

Out of a given equilateral triangle T1 (with his 3 vertices A,B,C lying in a finite Field $\mathbb F_N^D $) another equilateral triangle T2 can get constructed by mirroring one of the 3 vertices at the edge in between the two other vertices. This will be repeated multiple times.

Given just two random triangle T1 and T2 (and $\mathbb F_N^ ...

There is a field of exchanging information that combines cryptography and game theory. I am interested in understanding this field, but it's a little complex for me. To begin with there is a paper of Barany which shows that instead of having a centralized mechanism of information where a mediator can inform the players about what strategy to follow, the players instead can replace the mediator w ...

I read a paper titled "On the entropy of LEGO", which explains how to calculate the number of ways to combine $n$ $b\times w$ LEGO blocks of the same color. For example, six $2\times4$ bricks have $915103765$ ways to combine. I wonder if could we construct a funny cipher algorithm using LEGO bricks.

Some definitions and symbols:

A $2\times4$ brick $i$ can be defined as: $b_i:=\left( \begin{array}{cc} s_0 ...

I was reading the following paper BA-made it trivial and when talking about BA agreement protocol in page 3, I didn't understand what it meant by soundness here.

A protocol P is an arbitrary-value (respectively, binary) (n, t)-Byzantine agreement (BA) protocol with soundness σ ∈ (0, 1],

so when is the soundness 1 or 0? or is the soundness true if it follows some rules?

Let's consider we have keyed PRNG's and we want to build a cipher. What is better:

• to xor let's say ten such generators with some input as a plaintext (every generator got different key, but the same input),
• make 10 rounds, in which every generator output is new input to the next generator.

We see that usually ciphers have a round design. Is it because this is better?

Depending at the cryptographic function used applying it $i$-times to a given input can be computed in different complexity classes (based at their input size).

$$f^i(m_0) = c_i$$

For example for most block-cipher it takes (even with knowing the secret key) about $i$ times the time as applying it just once (at least as far as I know). Same for $i$ steps backwards. Finding $m_0$ for given $c_i$ also take ...

General problem / Intro: encrypting the (computable) relation in between two random numbers which are members of a as small as possible set while anything except the order of execution is known to the adversary.
This question is about solving that problem with a concatenation of block-cipher.

Simplification:

• we only consider block-cipher which are similar to AES
• instead of $N$ different block-ci ...

Is there a known hash function $H_k: X\to X$ such that: $\forall{x\in{X}},\exists{n\in{\mathbb{N}}}, n<k \land H^n(x)=x$

=== EDIT ===

By hash function I mean that any other way of finding the preimage of $x \in X$ than iterating $H_k$ is computably unfeasible or at least significantly harder.

My motivation is using such a function as sequential POW.

While reading papers on cryptography, a lot of time I have seen that people pick random elements $x\in \mathbb{Z}^*_q$ to do something (like setting secret key and all). How does one randomly pick elements in reality. I mean in practical implementation, what procedure do we follow? Do we use some CSPRNG?

While nowhere near being broken, AES has known attacks like reading from the substitution table, memory-based attacks, etc.

If we keep getting better at breaking ciphers and we eventually get close to taking AES down, what would (in your opinion) be the requirements for a cipher of an era where even Rijndael isn't safe enough?

I'm talking about:

• key sizes
• data sizes
• design (stream/Feistel/PSN, or s ...

For those who don't know, a bijective function is one for which each input yields one and only one output. A block cipher, for example, is guaranteed to be bijective or you could not decrypt.

When a hash function like SHA256 or SHA3 is used with an input the same length as its output, AFAIK this is not or at least should not be bijective. (Is that correct?)

If a hash is not bijective, does this mean ...

In the NTRU Prime submission, principle author, the well-known DJB is adamant that

[the] primary objective [of NTRU Prime] is to eliminate unnecessary complications in security review

So much so, to the extent that the idea of pure cyclotomic ring, module, decryption errors, etc. are exterminated from the design.

I think this is good, as NTRU Prime serve as a model alternative to the other design ...

I am new to cryptography and I am trying to code the RC6 (Rivest cipher 6) algorithm. The algorithm requires addition, subtraction and multiplication in modulo 2³². If I am performing these operations between two 32-bit blocks how would this work?

Any help would be appreciated because I can't seem to find any detailed explanation on this which would help me write code on how to execute these operations. ...

Are both of these concepts related in someway. Can a group signature scheme be transformed into a multi-signature scheme?

In his design of Salsa20, Bernstein writes to ensure non-linearity he chose

32-bit addition (breaking linearity over $Z/2$), 32-bit xor (breaking linearity over $Z/2^32), and constant-distance 32-bit rotation (diffusing changes from high bits to low bits).

Can you help me understand this? A linear function is one such that $f(ax+by) = af(x) + bf(y)$. It sounds like whether addition and xor are linea ...

For the spare-time project I had been working on, I'm evaluating the PKCS#1 padded RSA schemes for implementation.

For PKCS#1 v1.5, encryption doesn't seem to require a hash function, and the signature doesn't need additional mask-generating function (MGF) beyond a digest algorithm for hashing the message.

For PKCS#1 v2.x, both encryption and signature are instantiated with a MGF, a hash function, a ...

I'm new to the Cryptography Stack Exchange, so my question might be very naive.

What encryption algorithms are out there that will allow different decryption keys to decrypt the same piece of encrypted data?

For example : If the data that I'm encrypting is just a simple string : "Test"

Then applying the encryption algorithm changes it to this : "532EAABD9574880DBF76B9B8CC00832C20A6EC113D682299550D7A6E0F ...

Is it Probable to extract the ciphertext's genome and Visualizing it ?

Converting this:

60AD5A78FB4A4030EC542C8974CD15F55384E836554CEDD9A322D5F4135C6267
A9D20970C54E6651070B0144D43844C899320DD8FA7819F7EBC6A7715287332E
C8675C136183B3F8A1F81EF969418267130A756FDBB2C71D9A667446E34E0EAD
9CF31BFB66F816F319D0B7E430A5F2891553986E003720261C7E9022C0D9F11F

To this:

Encryption is like grinding the meat, once yo ...

I was doing some reading today about a major tech company planning to implement a new system for automatically detecting and reporting CSAM in users' photos. Overall, the system as described in their 12-page technical summary seems to be designed quite well, and may be as close as you can get to true privacy, while still allowing for content surveillance.

That being said, the hacker in me can't h ...

Alice selects two random numbers from a finite field $Z_p$ : $a$ and $b$.

Bob does one of the two following steps randomly (sometimes he does step 1; sometimes step 2):

1. He chooses a random number $r$ from $Z_p$ and calculates $a^r\;mod\;p$ and $b^r\;mod\;p$ and gives these two values to Alice
2. He chooses two different random numbers $r$ and $r'$ from $Z_p$ and calculates $a^r\;mod\;p$ and $b^{r'}\;mo ...

Can anyone help me understand this: How do we say that one cryptographic primitive is stronger than another?

The formatting function in Appendix A of NIST-SP-800-38C is a monster enabling CCM to support variable-length nonce from 7-13 bytes, variable-length encoding of the length of the payload. Also, the tag length is encoded in the formatting function making naive truncating of the MAC tag potentially incompatible with ciphertext instances with specific parameters.

The GCM mode and ChaCha20-Poly1305 are much  ...

Let $BC$ be a block cipher with similar security as AES (in ECB mode). This $BC$ is applied to a message $m$ of same bit size. The result is a cipher $c$.

e.g.;

$$BC(key_A,m) = c_A$$ $$BC(key_B,m) = c_B$$

I'm looking for a $BC$ with: $$BC(key_A,c_B) = c_{BA}$$ $$BC(key_B,c_A) = c_{AB}$$ where $$c_{AB}=c_{BA}$$ but for the majority: $$c_{A}\not=c_{B}$$

Is there any way to construct keys $key_A, k ...

In MD5, if M=100, how can we perform padding on it and how many blocks are needed in each round?

These are general questions for understanding padding and rounds.

I remember reading, a few years ago, that you couldn't prohibit encryption without prohibiting signing, as you can always make a public key encryption algorithm from a signing algorithm.

(It might be that you can always make a signing algorithm from a public key encryption algorithm.)

Furthermore I remember than this operated bitwise, so that each bit needed to be signed in some manner in order to e ...

I want to find an encryption algorithm which provides the functionality described below.

Given a key (a vector Vkey) and a data (an image), use this key to encrypt the image; the encrypted image can not be identified afer encryption.

When decrypt, if:

1. use a key = Vkey to decrypt, the decoded image is the same as original one without error.
2. use a key = Vkey_1, and diff(Vkey, Vkey_1) < threshold, ...

Let's consider a block cipher in CTR mode. And let's consider a keyed PRNG or just a good PRNG with a seed as the key. The PRNG has to be very fast.

Is it a good idea to put away the key schedule and do "infinite" key scheduling by generating a keystream? Then every block in the cipher will be encrypted with a different key.

Of course, even a fast PRNG needs some time to generate a few 128 -bit keys ...