Academic literature on the topic 'Preimage sampling'

In this paper, we design a new lattice-based linearly homomorphic signature scheme over F 2 . The existing schemes are all constructed based on hash-and-sign lattice-based signature framework, where the implementation of preimage sampling function is Gaussian sampling, and the use of trapdoor basis needs a larger dimension m ≥ 5 n log q . Hence, they cannot resist potential side-channel attacks and have larger sizes of public key and signature. Under Fiat–Shamir with aborting signature framework and general SIS problem restricted condition m ≥ n log q , we use uniform sampling of filtering technology to design the scheme, and then, our scheme has a smaller public key size and signature size than the existing schemes and it can resist side-channel attacks.

This article first describes a paper by Ling, Phan, and Stehle at the CRYPTO 2014 which presented the first encryption scheme for traitor tracing from lattice, and the scheme is almost as efficient as the learning with errors (LWE) encryption. However, their scheme is not constructed on an efficient trapdoor, that is, the trapdoor generation and preimage sampling algorithms are rather complex and not suitable for practice. This article is considered to use the MP12 trapdoor to construct an improved traitor tracing scheme. First, by using batch execution method, this article proposes an improved extracting algorithm for the user's key. Then, this article combines that with multi-bit encryption system to construct an efficient one-to-many encryption scheme. Furthermore, it is presented that a novel projective sampling family has very small hidden constants. Finally, a comparative analysis shows that the parameters of the scheme such as lattice dimension, trapdoor size, and ciphertext expansion rate, etc., all decrease in some degree, and the computational cost is reduced.

We investigate the $\Lambda$-polytopes, a convex-linear structure recently defined and applied to the classical simulation of quantum computation with magic states by sampling. There is one such polytope, $\Lambda_n$, for every number $n$ of qubits. We establish two properties of the family $\{\Lambda_n, n\in \mathbb{N}\}$, namely (i) Any extremal point (vertex) $A_\alpha \in \Lambda_m$ can be used to construct vertices in $\Lambda_n$, for all $n>m$. (ii) For vertices obtained through this mapping, the classical simulation of quantum computation with magic states can be efficiently reduced to the classical simulation based on the preimage $A_\alpha$. In addition, we describe a new class of vertices in $\Lambda_2$ which is outside the known classification. While the hardness of classical simulation remains an open problem for most extremal points of $\Lambda_n$, the above results extend efficient classical simulation of quantum computations beyond the presently known range.

Aiming at the problem that the fully homomorphic encryption scheme based on single identity cannot satisfy the homomorphic operation of ciphertext under different identities, as well as the inefficiency of trapdoor function and the complexity of sampling algorithm, an improved lattice MIBFHE scheme was proposed. Firstly, we combined MP12 trapdoor function with dual LWE algorithm to construct a new IBE scheme under the standard model, and prove that the scheme is IND-sID-CPA security under the selective identity. Secondly, we used the eigenvector method to eliminate the evaluation key, and transform the above efficient IBE scheme into a single identity IBFHE scheme to satisfy the homomorphic operation. Finally, we improved the ciphertext extension method of CM15 and constructed a new Link-mask system that supports the transformation of IBFHE scheme under the standard model, and then, converted the above IBFHE scheme into MIBFHE scheme based on this system. The comparative analysis results showed that the efficiency of this scheme is improved compared with similar schemes in the trapdoor generation and preimage sampling, and the dimension of lattice and ciphertext size are significantly shortened.

In cloud and edge computing, senders of data often want to be anonymous, while recipients of data always expect that the data come from a reliable sender and they are not redundant. Linkable ring signature (LRS) can not only protect the anonymity of the signer, but also detect whether two different signatures are signed by the same signer. Today, most lattice-based LRS schemes only satisfy computational anonymity. To the best of our knowledge, only the lattice-based LRS scheme proposed by Torres et al. can achieve unconditional anonymity. But the efficiency of signature generation and verification of the scheme is very low, and the signature length is also relatively long. With the preimage sampling, trapdoor generation, and rejection sampling algorithms, this study proposed an efficient LRS scheme with unconditional anonymity based on the e-NTRU problem under the random oracle model. We implemented our scheme and Torres et al.’s scheme, as well as other four efficient lattice-based LRS schemes. It is shown that under the same security level, compared with Torres et al.’s scheme, the signature generation time, signature verification time, and signature size of our scheme are reduced by about 94.52%, 97.18%, and 58.03%, respectively.

A central problem in computational statistics is to convert a procedure for sampling combinatorial objects into a procedure for counting those objects, and vice versa. We consider sampling problems coming from Gibbs distributions , which are families of probability distributions over a discrete space \(\Omega\) with probability mass function of the form \(\mu^{\Omega}_{\beta}(\omega)\propto e^{\beta H(\omega)}\) for \(\beta\) in an interval \([\beta_{\min},\beta_{\max}]\) and \(H(\omega)\in\{0\}\cup[1,n]\) . Two important parameters are the partition function , which is the normalization factor \(Z(\beta)=\sum_{\omega\in\Omega}e^{\beta H(\omega)}\) , and the vector of preimage counts \(c_{x}=|H^{-1}(x)|\) . We develop black-box sampling algorithms to estimate the counts using roughly \(\tilde{O}(\frac{n^{2}}{\varepsilon^{2}})\) samples for integer-valued distributions and \(\tilde{O}(\frac{q}{\varepsilon^{2}})\) samples for general distributions, where \(q=\log\frac{Z(\beta_{\max})}{Z(\beta_{\min})}\) (ignoring some second-order terms and parameters). We show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs, independent sets, and perfect matchings. As a key subroutine, we estimate all values of the partition function using \(\tilde{O}(\frac{n^{2}}{\varepsilon^{2}})\) samples for integer-valued distributions and \(\tilde{O}(\frac{q}{\varepsilon^{2}})\) samples for general distributions. This improves over a prior algorithm of Huber (2015) which computes a single point estimate \(Z(\beta_{\max})\) and which uses a slightly larger amount of samples. We show matching lower bounds, demonstrating this complexity is optimal as a function of \(n\) and \(q\) up to logarithmic terms.

AbstractWe present the implementation of Grover’s algorithm in a quantum simulator to perform a quantum search for preimages of two scaled hash functions, whose design only uses modular addition, word rotation and bitwise exclusive or. Our implementation provides the means to assess with precision the scaling of the number of gates and depth of a full-fledged quantum circuit designed to find the preimages of a given hash digest. The detailed construction of the quantum oracle shows that the presence of AND gates, OR gates, shifts of bits and the reuse of the initial state along the computation require extra quantum resources as compared with other hash functions based on modular additions, XOR gates and rotations. We also track the entanglement entropy present in the quantum register at every step along the computation, showing that it becomes maximal at the inner core of the first action of the quantum oracle, which implies that no classical simulation based on tensor networks would be of relevance. Finally, we show that strategies that suggest a shortcut based on sampling the quantum register after a few steps of Grover’s algorithm can only provide some marginal practical advantage in terms of error mitigation.

La transition vers la cryptographie post-quantique est une tâche considérable ayant suscité un nombre important de travaux ces dernières années. En parallèle, la cryptographie pour la protection de la vie privée, visant à pallier aux limitations inhérentes des mécanismes cryptographiques basiques dans ce domaine, a connu un véritable essor. Malgré le succès de chacune de ces branches prises individuellement, combiner les deux aspects de manière efficace s'avère extrêmement difficile. Le but de cette thèse de doctorat consiste alors à proposer de nouvelles constructions visant à garantir une protection efficace et post-quantique de la vie privée, et plus généralement des mécanismes d'authentification avancés. Dans ce but, nous nous consacrons tout d'abord à l'étude de l'une des hypothèses mathématiques fondamentales utilisées en cryptographie sur les réseaux Euclidiens: Module Learning With Errors. Nous prouvons que le problème ne devient pas significativement plus facile même en choisissant des distributions de secret et d'erreur plus courtes. Ensuite, nous proposons des optimisations des échantillonneurs d'antécédents utilisés par de nombreuses signatures avancées. Loin d'être limitées à ce cas d'usage, nous montrons que ces optimisations mènent à la conception de signatures standards efficaces. Enfin, à partir de ces contributions, nous concevons des algorithmes de signatures avec protocoles efficaces, un outil polyvalent utile à la construction d'applications avancées. Nous en montrons les capacités en proposant le premier mécanisme d'accréditation anonyme post-quantique, que nous implémentons afin de mettre en exergue son efficacité aussi bien théorique que pratique
The transition to post-quantum cryptography has been an enormous effort for cryptographers over the last decade. In the meantime, cryptography for the protection of privacy, aiming at addressing the limitations inherent to basic cryptographic mechanisms in this domain, has also attracted a lot of attention. Nevertheless, despite the success of both individual branches, combining both aspects along with practicality turns out to be very challenging. The goal of this thesis then lies in proposing new constructions for practical post-quantum privacy, and more generally advanced authentication mechanisms. To this end, we first focus on the lower level by studying one of the fundamental mathematical assumptions used in lattice-based cryptography: Module Learning With Errors. We show that it does not get significantly easier when stretching the secret and error distributions. We then turn to optimizing preimage samplers which are used in advanced signature designs. Far from being limited to this use case, we show that it also leads to efficient designs of regular signatures. Finally, we use some of the previous contributions to construct so-called signatures with efficient protocols, a versatile building block in countless advanced applications. We showcase it by giving the first post-quantum anonymous credentials, which we implement to demonstrate a theoretical and practical efficiency