3

The classic Gaussian Elimination algorithm is $O(n^3)$ runtime regardless of specific field and the Matrix, so in this case a finite field $F_q$ of order $q$ doesn't play a role in the complexity. This runtime is due to the fact that you are zeroing out entries in columns column-by-column to get into row reduced echelon form. For matrices in $GL(n, q)$, the ...


3

No. For example, these pairing-based protocols don't require trusted setup: BLS signatures; tripartite Diffie-Hellman, as mentioned in Elias' answer; some identity-based encryption schemes (when users are their own PKGs, e.g. when using IBE for forward-secure encryption); the Bünz–Maller–Mishra–Vesely polynomial commitment scheme. (This could in principle ...


2

Usually, the brute-force attack is performed with known-plaintext where a message $m$ and its ciphertext $c = \operatorname{XTEA}(k,m)$ is available. Indeed, one may need more than one to exactly found the key since a key selects permutation and at the point $m$ there can be more than one permutation selected by different keys that maps to the same ...


2

There is demonstrably no general solution to this class of problems. Argument: we can construct the output as a Message Authentication Code (e.g. HMAC) of the other inputs, with a random secret fixed key; and what's asked is breaking the MAC. This class of problems is not modern academic cryptography, which assumes the algorithms are known, only the keys are ...


1

If an all-zeroes block creates all-zeroes for every key that's definitely an issue. It's not necessarily likely to be serious, but could leak data about the plaintext and does not qualify as a secure block cipher. However, the solution is fairly simple... simply XOR one of k1 or k2 with a constant value to turn your all-zero block into something that'll ...


Only top voted, non community-wiki answers of a minimum length are eligible