# Tagged Questions

The tag has no usage guidance.

36 views

### Decomposing an ideal in intersections

Let $R$ be an ring, and let $(a),(b)$ be the ideals generated by $a,b\in R^\times$ respectively. Let $c=a\cdot b$ and $(c)$ the ideal generated by $c$. I am supposing that, given $c$, it is ...
I am struggling to apply Freize et al. paper to break a truncated LCG. A truncated LCG is a pseudo random generator that outputs the $n$ leading bits $y_i$ of $x_i$, where $(x_i)$ is such that $x_{... 0answers 65 views ### Distinguish two ciphers in Ring-LWE? I am fairly new to this topic. so my question is: if I have$A=e_0a+e_1$and$B=e_2a+e_3$where$a$is the agreed public parameter,$e_i \leftarrow \chi$(drawn from the error distribution). if the ... 1answer 41 views ### ZK Proof for SIS Let$A x = 0 \bmod q$with$\Vert x \Vert < \beta$be a lattice SIS problem. Does there exist an efficient zero knowledge proof of knowledge for such a solution? My idea is to use it for an ... 3answers 155 views ### What is a purpose of reducing lattice basis? This may be too broad question but it is not. I have been studying lattices for few months now, more specifically I studied: lattice problems ($SVP$,$CVP$and etc.) lattice cryptography in post ... 0answers 40 views ### In NTRU, if$N$is not prime, prove that one can recover the private key by solving a lattice problem in dimension lower than$2N$In the NTRU cryptosystem, it is suggested to take$N$prime. I want to understand why. In Jeffrey Hoffstein, Jill Pipher and H. Silverman An Introduction to Mathematical Cryptography, they suggest (... 0answers 75 views ### Would LWE problem be still secure if error were like this$e=2e_1$? In the Learning with error problem, if the error term$e$from equation$b=<a,s>/q+e$were of this kind$e=2e_1$, where$e_1$is chosen according to the probability distribution for the LWE ... 1answer 37 views ### ZK proof that two short solutions are equal Let$A_1$and$A_2$two$m \times n$matrices defining SIS problems. Does there exist a zero knowledge proof that two short solutions are the same, i.e. $$y_1 = A_1 x$$ $$y_2= A_2 x$$ $$\Vert x \... 0answers 22 views ### Construct new SIS solutions from given ones Assume we have a lattice SIS problem A x = 0, with \Vert x \Vert < \beta and we are given k solutions x_1, \dots, x_k by, say an oracle. Is it then hard or easy to construct from there a ... 2answers 67 views ### Cardinality of the group of units in a cyclotomic ring? In the NTRU key generation, one samples a polynomial from K = (\mathbb Z/q\mathbb Z)[X]/(X^n+1) and tests if it is invertible. What are the chances of this to happen? In other words: Let q be a ... 1answer 76 views ### Gaussian distribution in lattices In many lattice based cryptosystems, Gaussian distribution is used. Can you explain why only Gaussian distribution is preferred? 0answers 25 views ### Proof that two signatures are done with the same short bases My question is regarding lattice based signatures. Each lattice can have multiple short (secret) bases. Is it possible to proof in zero knowledge that two signatures on a fixed lattice have been ... 1answer 49 views ### Find an example of a lattice such that LLL algorithm can't find the shortest vector of the lattice, satisfying I want to find an example of a basis of a lattice of dimension n such that LLL algorithm can't find the shortest vector of the lattice, and such that the shortest vector of this lattice, say b=... 1answer 76 views ### proof of correctness Ring-LWE cryptosystem I've been studying Ring-LWE based crytposystems such as the one in this paper, but I can't seem to find/come up with a proof of correctness for this particular scheme. The encryption goes as follows: ... 0answers 46 views ### Quantum complexity of LWE As per my understanding LWE is quantum secure because there is no known quantum algorithm to solve LWE in polynomial time. Due to the reductions given by Regev et al. If there is any algorithm that ... 1answer 73 views ### What is the most efficient attack on NTRU? So, I got how finding the private key is equivalent to resolving the SVP. I also understood that the LLL algorithm can only be used in small dimensions. Now, I wonder what is the most efficient attack ... 0answers 51 views ### Is the ring learning with errors problem still hard if the errors are drawn from some subspace? Let R=\mathbb{Z}_p[x]/x^n+1 be the ring used in normal RLWE, which is linear space over \mathbb{Z}_p with dimension of n, let S be a linear subspace of R which described by linear ... 1answer 77 views ### Collisions in the cyclotomic knapsack function I've been working my way through the paper “Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices” by Peikert and Rosen, and I've come across something that doesn't seem ... 1answer 23 views ### Use e in GGH as shared secret? I was wondering if we could construct a symmetric encryption scheme by assuming that the secret key itself in GGH is public and the shared "key" is the error vector e. To encrypt we would take the ... 1answer 412 views ### Is the “New Hope” Lattice Key Exchange vulnerable to a lattice analog of the Bernstein BADA55 Attack? In the paper, "Post Quantum Key Exhange - A New Hope," the authors present a lattice-based key exchange based on the work of Chris Peikert. In this "New Hope" key exchange the authors try to gain ... 2answers 162 views ### How to find the value of a vector modulo a basis in lattice-based cryptography In Gentry's paper on fully homomorphic encryption using ideal lattices, he finds the values of vectors modulo a certain basis. For instance: \psi \leftarrow \psi' \mod B Taken from page 69 of ... 1answer 127 views ### Find collision in Ajtai's hash function using short vector Background What is Ajtai's hash function? Given a matrix A \hookleftarrow U(\mathbb{Z}_q^{n \times m}) and a column vector \vec{m} \in \mathbb{Z}_d^m, the hash of the message \vec{m} is given ... 0answers 40 views ### ISIS as a one-way function The usual formulation of the ISIS problem is the following: Given uniform A and u, find a short e such that Ae = u \bmod q. A different definition (call it ISIS-OWF) is to let f_A(e) = Ae \... 1answer 65 views ### Practical lattice based signatures and key exchange with strong security reduction I am looking for practical lattice-based signatures and key exchange with strong security reductions. Specifically: Provable security under the relevant standard assumptions. Fast in software while ... 1answer 46 views ### Use of orthogonal vectors in lattice-based cryptography In lattice-based cryptography, given the basis of the lattice we compute the orthogonal vectors using Gram-Schmidt Orthogonalization process. What is the use of orthogonal vectors in lattices? 1answer 56 views ### finding the basis of a kernel in a lattice Given a parity check matrix A we define the q-ary lattice$$\Lambda(A) = \{x \in \mathbb Z^m\;:\;Ax\equiv0\pmod q\}$$How to find the basis of the lattice and how to find its hermite normal form? 2answers 330 views ### Using Lattice-based cryptography for TLS\SSL Given the general benefits of Lattice-based cryptography, such as: Post quantum Security Security from worst case scenario Efficiency What could the outlook of shifting from RSA \ ECC-based ... 2answers 55 views ### Gaussian function in lattices Probability density function of gaussian distribution is$$ 1/{\sqrt{2 \pi} \sigma} \times {e^{{(x-c)^2/ 2{\sigma}^2 }}} $$in lattices we assume$$ \sigma =s/\sqrt{2 \pi} $$so the gaussian ... 1answer 255 views ### How can a lattice attack be applied to ECDSA signatures? The aim is to check if it is possible to break the ECDSA cryptosystem under the following criteria. Suppose that each ECDSA signature is generated by using the GLV method for point multiplication (... 0answers 33 views ### Faster discrete Gaussian sampling Our goal is find a faster discrete Gaussian sampling to solve "SVP" problem in lattice: A lattice is discrete subgroup of R^n such that define as below: let \{b_1,\cdots ,b_n\} be a basis in ... 1answer 219 views ### Lattice based attack on RSA Let n=pq be the RSA module and at least one of p,q is a weak prime.It is proved that the number of such 1024bit n is at least 2^{759}. With lattices we can factor these n in a second (I ... 0answers 43 views ### Choise enother scheme to basises of lattice cryptosystem In the lattice cryptosystem to find a good or bad basis we apply "hadamard Ratio". But in high dimension computing of this ratio is hard. dose any other scheme exist to solve this problem? 1answer 112 views ### Is secure lattice based cryptography in future? Lattice cryptography is a post quantum cryptography that work on two NP-hard problem in below: Find shortest nonzero vector from origin and Find minimum distance of a arbitrary point out of lattice ... 2answers 848 views ### What does “Worst-case hardness” mean in lattice-based cryptography? In the wiki page of Lattice-based Cryptography the "Worst-case hardness" is defined as below: Worst-case hardness of lattice problems means that breaking the cryptographic construction (even with ... 0answers 68 views ### Why SIVP Is Worst Case Problem? I just started to study lattice cryptography. I'm now studying worst-case to average-case reduction for SIS. In previous question, "worst means any and average means random". And I wonder why ... 0answers 86 views ### Lattice attacks against Multilinear Maps [CLT13] I am currently studying an article on a construction of Multilinear maps. There are some attacks on the scheme presented by the authors and I got stuck at the one in section 5.1. I will try to ... 0answers 36 views ### NTRUSign Hashing I have some trouble understanding the inner workings of NTRUSign. So what I have understood so far is, that when Alice wants to sign a message she does the following steps Convert Alice's message ... 2answers 125 views ### How to compare performances of lattice-based and pairing-based IBE schemes I try to compare the performances (cost of Enc, Dec, ... size of keys, ciphertexts, ...) of IBE schemes using lattices (LWE hardness assumption) or pairing (Diffie-Hellman hardness assumption). I've ... 0answers 66 views ### special class of lattices in lattice based cryptography A special case of lattices in lattice cryptography is that of q-ary lattices. A q-ary lattice L is defined as that in which any vector which consists of multiples of some scalar q is in ... 1answer 165 views ### Use of q-ary lattices in developing cryptosystems Why q-ary lattices are used to most cryptosystems rather than lattices. In most of the papers q-ary lattices are used. Is there any advantage? and Given$$B=(v_1,v_2,v_3,.....v_n)$$is the basis, ... 1answer 56 views ### apprSVP in lattices The approximate Shortest Vector Problem (apprSVP) is a problem where, given the basis and the approximation factor$\gamma$(a function of the dimension$n$), one must find a vector$v$belonging to ... 2answers 98 views ### What kind of operations are involved in NTRU? I've read that lattice based algorithms involve matrix-vector products. Is this the case of the NTRU algorithm? When I've read the details of the NTRU algorithm, I've seen products of polynoms. Where ... 1answer 163 views ### How to generate new LWE samples Assume we are given a small fixed number of LWE samples with secret$s$and error$e$, where the error distribution is taken so that the LWE problem is hard. My question: How can one further ... 0answers 96 views ### Worst case to average case in Ring LWE I am currently trying to understand this Ring LWE article and I have a question. I don't understand how to apply Lemma 5.11 in order to get the worst case to average case reduction in Lemma 5.12, as ... 1answer 151 views ### Ring-LWE elliptic gaussian distribution I am currently trying to understand this Ring-LWE article: http://www.cims.nyu.edu/~regev/papers/ideal-lwe.pdf and I have a question. Firstly, it is mentioned in the paper that we can view the ... 1answer 132 views ### What is the meaning for a vector mod a matrix in a lattice? I'm reading about the lattice recently.In the paper, it gives a method of a vector mod a matrix: ⃗c mod B as ⃗c−⌊⃗c×B^(−1)⌉×B = [⃗c×B^(−1)]×B. I know that a integer A mod the other integer B is A+-... 2answers 149 views ### What is the difference between the standard representants of$\mathbb Z/q\mathbb Z$? The symbol$\mathbb Z/q\mathbb Z$(given that$q$is prime) represents the prime field$\mathbb Z_q$. Basically, the elements of this field are represented by$\{0, 1, \dots, q-1\}$, let's call this ... 1answer 273 views ### What is a “lattice” in cryptography? There are some questions here concerning lattice-based cryptography and this kind of cryptography seems to be especially useful if quantum computers are assumed to exist. When reading such questions ... 0answers 97 views ### How to recover$e$from$f_A(e) = Ae \mod q$when knowing trapdoor I have a silly question, but I don't know a solution, so I need to question. Assume, with a algorithm$TrapGen(1^\lambda)$, it generates$A\in\mathbb{Z}_q^{n\times m}$with a basis$B \in\mathbb{Z}_q^...
The Inhomogeneous Short Integer Solution (ISIS) problem is as follows: given an integer $q$, a matrix $A \in \mathbb Z^{n\times m}_q$, a vector $b\in \mathbb Z^n_q$, and a real $\beta$, find an ...