Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRevisiting the Concrete Security of Goldreichs Pseudorandom Generator
89
0
0.0
(
0
)
Added by
Jing Yang Ms.
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Local pseudorandom generators are a class of fundamental cryptographic primitives having very broad applications in theoretical cryptography. Following Couteau et al.s work in ASIACRYPT 2018, this paper further studies the concrete security of one important class of local pseudorandom generators, i.e., Goldreichs pseudorandom generators. Our first attack is of the guess-and-determine type. Our result significantly improves the state-of-the-art algorithm proposed by Couteau et al., in terms of both asymptotic and concrete complexity, and breaks all the challenge parameters they proposed. For instance, for a parameter set suggested for 128 bits of security, we could solve the instance faster by a factor of about $2^{61}$, thereby destroying the claimed security completely. Our second attack further exploits the extremely sparse structure of the predicate $P_5$ and combines ideas from iterative decoding. This novel attack, named guess-and-decode, substantially improves the guess-and-determine approaches for cryptographic-relevant parameters. All the challenge parameter sets proposed in Couteau et al.s work in ASIACRYPT 2018 aiming for 80-bit (128-bit) security levels can be solved in about $2^{58}$ ($2^{78}$) operations. We suggest new parameters for achieving 80-bit (128-bit) security with respect to our attacks. We also extend the attack to other promising predicates and investigate their resistance.
rate research
Read More
Key extraction via measuring a physical quantity is a class of information theoretic key exchange protocols that rely on the physical characteristics of the communication channel to enable the computation of a shared key by two (or more) parties that share no prior secret information. The key is supposed to be information theoretically hidden to an eavesdropper. Despite the recent surge of research activity in the area, concrete claims about the security of the protocols typically rely on channel abstractions that are not fully experimentally substantiated. In this work, we propose a novel methodology for the {em experimental} security analysis of these protocols. The crux of our methodology is a falsifiable channel abstraction that is accompanied by an efficient experimental approximation algorithm of the {em conditional min-entropy} available to the two parties given the view of the eavesdropper. We focus on the signal strength between two wirelessly communicating transceivers as the measured quantity and we use an experimental setup to compute the conditional min-entropy of the channel given the view of the attacker which we find to be linearly increasing. Armed with this understanding of the channel, we showcase the methodology by providing a general protocol for key extraction in this setting that is shown to be secure for a concrete parameter selection. In this way we provide a first comprehensively analyzed wireless key extraction protocol that is demonstrably secure against passive adversaries. Our methodology uses hidden Markov models as the channel model and a dynamic programming approach to approximate conditional min-entropy but other possible instantiations of the methodology can be motivated by our work.
We provide a new provably-secure steganographic encryption protocol that is proven secure in the complexity-theoretic framework of Hopper et al. The fundamental building block of our steganographic encryption protocol is a one-time stegosystem that allows two parties to transmit messages of length shorter than the shared key with information-theoretic security guarantees. The employment of a pseudorandom generator (PRG) permits secure transmission of longer messages in the same way that such a generator allows the use of one-time pad encryption for messages longer than the key in symmetric encryption. The advantage of our construction, compared to that of Hopper et al., is that it avoids the use of a pseudorandom function family and instead relies (directly) on a pseudorandom generator in a way that provides linear improvement in the number of applications of the underlying one-way permutation per transmitted bit. This advantageous trade-off is achieved by substituting the pseudorandom function family employed in the previous construction with an appropriate combinatorial construction that has been used extensively in derandomization, namely almost t-wise independent function families.
This article discusses the security of McEliece-like encryption schemes using subspace subcodes of Reed-Solomon codes, i.e. subcodes of Reed-Solomon codes over $mathbb{F}_{q^m}$ whose entries lie in a fixed collection of $mathbb{F}_q$-subspaces of $mathbb{F}_{q^m}$. These codes appear to be a natural generalisation of Goppa and alternant codes and provide a broader flexibility in designing code based encryption schemes. For the security analysis, we introduce a new operation on codes called the twisted product which yields a polynomial time distinguisher on such subspace subcodes as soon as the chosen $mathbb{F}_q$-subspaces have dimension larger than $m/2$. From this distinguisher, we build an efficient attack which in particular breaks some parameters of a recent proposal due to Khathuria, Rosenthal and Weger.
In this paper, we specify a class of mathematical problems, which we refer to as Function Density Problems (FDPs, in short), and point out novel connections of FDPs to the following two cryptographic topics; theoretical security evaluations of keyless hash functions (such as SHA-1), and constructions of provably secure pseudorandom generators (PRGs) with some enhanced security property introduced by Dubrov and Ishai [STOC 2006]. Our argument aims at proposing new theoretical frameworks for these topics (especially for the former) based on FDPs, rather than providing some concrete and practical results on the topics. We also give some examples of mathematical discussions on FDPs, which would be of independent interest from mathematical viewpoints. Finally, we discuss possible directions of future research on other cryptographic applications of FDPs and on mathematical studies on FDPs themselves.
We in this paper introduce an advanced eavesdropper that aims to paralyze the artificial-noise-aided secure communications. We consider the M-1-2 Gaussian MISO wiretap channel, which consists of a M-antenna transmitter, a single-antenna receiver, and a two-antenna eavesdropper. This type of eavesdropper, by adopting an optimal Grassmann manifold (OGM) filtering structure, can reduce the maximum achievable secrecy rate (MASR) to be zero by using only two receive antennas, regardless of the number of antennas at the transmitter. Specifically, the eavesdropper exploits linear filters to serially recover the legitimate information symbols and intends to find the optimal filter that minimizes the meansquare error (MSE) in estimating the symbols. During the process, a convex semidefinite programming (SDP) problem with constraints on the filter matrix can be formulated and solved. Interestingly, the resulted optimal filters constitute a complex Grassmann manifold on the matrix space. Based on the filters, a novel expression of MASR is derived and further verified to be zero under the noiseless environment. Besides this, an achievable variable region (AVR) that induces zero MASR is presented analytically in the noisy case. Numerical results are provided to illustrate the huge disaster in the respect of secrecy rate.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
