[continued from previous message]
Maiorana--McFarland type constructions are basically concatenating the truth tables of linear functions on a smaller number of variables to obtain highly nonlinear ones on larger inputs. Such functions and their different variants have significant
applications in cryptology and coding theory. Straightforward hardware implementation of such functions may require exponential resources on the number of inputs. In this paper, we study such constructions in detail and provide implementation strategies
for a selected subset of this class with polynomial many gates over the number of inputs. We demonstrate that such implementations cover the requirement of cryptographic primitives to a great extent. Several existing constructions are revisited in this
direction and exact implementations are provided with specific depth and gate counts in the hardware implementation. Related combinatorial as well as circuit complexity-related results of theoretical nature are also analyzed in this regard. Finally we
present a novel construction of a new class of balanced Boolean functions having very low absolute indicator and very high nonlinearity that can be implemented in polynomial circuit size over the number of inputs. In conclusion, we present that these
constructions have immediate applications to resist the signature generation in Differential Fault Attack (DFA) and to implement functions on large number of variables in designing ciphers for the paradigm of Fully Homomorphic Encryption (FHE).
## 2023/1971
* Title: The Planck Constant and Quantum Fourier Transformation
* Authors: Zhengjun Cao, Zhenfu Cao
* [Permalink](
https://eprint.iacr.org/2023/1971)
* [Download](
https://eprint.iacr.org/2023/1971.pdf)
### Abstract
Quantum Fourier Transformation (QFT) plays a key role in quantum computation theory. But its transform size has never been discussed. In practice, the Xilinx LogiCORE IP Fast Fourier Transform core has the maximum transform size $N=2^{16}$. Taking into
account the Planck constant $\hbar=6.62607015\times 10^{-34}$ and the difficulty to physically implement basic operator $\left[ \begin{array}{cc} 1& 0\\ 0 & \exp(-2\pi\,i/N)\\ \end{array} \right]$ on a qubit, we think $N=2^{120}$ could be an upper
bound for the transform size of QFT.
## 2023/1972
* Title: Hard Languages in $\mathsf{NP} \cap \mathsf{coNP}$ and NIZK Proofs from Unstructured Hardness
* Authors: Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai
* [Permalink](
https://eprint.iacr.org/2023/1972)
* [Download](
https://eprint.iacr.org/2023/1972.pdf)
### Abstract
The existence of "unstructured" hard languages in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether $\mathsf{P}$ is separated from $\mathsf{NP} \cap \mathsf{coNP}$ relative to a random
oracle, a question that remained open ever since. While a hard language in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ can be constructed in a black-box way from a one-way permutation, for which only few (structured) candidates exist, Bitansky et al. (SICOMP,
2021) ruled out such a construction based on an injective one-way function, an unstructured primitive that is easy to instantiate heuristically. In fact, the latter holds even with a black-box use of indistinguishability obfuscation.
We give the first evidence for the existence of unstructured hard languages in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ by showing that if $\mathsf{UP} \not \subseteq \mathsf{RP}$, which follows from the existence of injective one-way functions, the answer to
Bennett and Gill's question is affirmative: with probability 1 over a random oracle $\cal O$, we have that $\mathsf{P}^{\cal O} \neq \mathsf{NP}^{\cal O} \cap \mathsf{coNP}^{\cal O}$. Our proof gives a constructive non-black-box approach for obtaining
candidate hard languages in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ from cryptographic hash functions.
The above conditional separation builds on a new construction of non-interactive zero-knowledge (NIZK) proofs, with a computationally unbounded prover, to convert a hard promise problem into a hard language. We obtain such NIZK proofs for $\mathsf{NP}$,
with a uniformly random reference string, from a special kind of hash function which is implied by (an unstructured) random oracle. This should be contrasted with previous constructions of such NIZK proofs that are based on one-way permutations or other
structured primitives, as well as with (computationally sound) NIZK arguments in the random oracle model.
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)