# Tagged Questions

Groups are an abstract algebraic concept based on a set and a group law (a binary function which closes the set).

134 views

26 views

### elliptic curve and embedding degree

I am new in ECC. I am confused what the embedding degree in elliptic curve represents and what is the impact of its values on the curve and security ( small values or large values? What does the ...
If an adversary has access to the generator g of a group G and is given access to $g^{x}$ and $g^{(1/x)}$, will it make it any easier to derive the value of $x$ compared to when he had access to only $... 1answer 103 views ### Is every point on an elliptic curve of a prime order group a generator? If the order of elliptic group is prime then every point is a generator of that group. I tested the above statement on some elliptic curves and found it true. Does that really work on all curves? Is ... 3answers 735 views ### Generation of a cyclic group of prime order I am trying to implement a cyclic group generator in Java, but I am running into some issues. In many cryptosystems, the following phrase is expressed during the key generation stage. Let G be ... 1answer 70 views ### Understanding the Hidden Subgroup Problem specific to Integer Factorization I've been reading about the Hidden Subgroup Problem (HSP), specifically trying to understand how it is related to the integer factorization problem. I've read What exactly is the impact of the hidden ... 2answers 351 views ### Why is “multiplying”$g^x$and$g^y$not possible? The computational Diffie-Hellman problem states that for a cyclic group$G$of order$p$and a generator$g$, it is hard to find the value$g^{xy}$given only$g^x$and$g^y$(but easy if either$x$... 1answer 207 views ### Discrete logarithm problem is easy in a cyclic group of order a power of two Let$G=\langle g\rangle$be a cyclic group of order$2^{k}$and let$h\in G$. I have read that it is easy to find$\log _{g} h$, but I haven't been able to figure out how. Do you know why this can be ... 2answers 155 views ### Factoring large$N$given oracle to find square roots modulo$N$When$p$and$q$are distinct odd primes and$N = pq$, the points in$\mathbb Z_N^\ast$have either zero or four square roots. A quarter of the points have four square roots; the rest have no square ... 1answer 128 views ### Given$g,g^t$in a cyclic group of order$pq$, is it hard to compute$g^{t^{-1}}$? Suppose we have a group$G$cyclic of order$pq$, where$p,q$are primes. Let$g$be a generator of$G$and$t\in \mathbb{Z}_{pq}$. Having$g$and$g^t$, it seems to be very hard to find$g^{t^{-1}}$,... 3answers 37 views ### What are possible caveats when generating a group for use as parameters for Diffie-Hellman key exchange? As reusing a widely used group for Diffie-Hellman key exchanges might lead to far easier third-party key discovery through precomputation for that specific group, I would like to know what can ... 2answers 458 views ### How to determine the order of an elliptic curve group from its parameters? Let$\quad E:\; y^2 = x^3 + ax + b \quad$be an elliptic curve defined over a finite field$\mathbb F_q$where$q = p^n$,$a,b \in \mathbb F_q$and$p \neq 2, 3$. By Hasse's theorem we know that the ... 1answer 73 views ### Elliptic Curve ElGamal and DSA - smooth group order and element of large prime order In regular ElGamal and DSA, we choose large primes$p$and$q$such that$p\equiv 1\pmod{q}$, and a group element$g$of order$q$by computing$a^{(p-1)/q}$for some random$a$. This is to prevent ... 1answer 167 views ### Modular Arithmetic in RSA Consider the following the following RSA public key$pk = (N, e) = (1457, 1307)$. (a) Knowing that$187^2 \equiv 1 \pmod {1457}$find the factorization of$N$. (b) Given the factorization of$N$... 1answer 67 views ### How is a group element converted into a key? I've only just started research on cryptography so I apologize if this is a basic question or I'm getting terms confused. I'm researching braid group cryptography and currently looking at the Anshel-... 2answers 269 views ### lcm versus phi in RSA In textbook RSA, the Euler$\varphi$function $$\varphi(pq) := (p-1)(q-1)$$ is used to define the private exponent$d$. On the other hand, real-world cryptographic specifications require the ... 3answers 801 views ### When do we need composite order groups for bilinear maps and when prime order? Why we need bilinear groups of composite order? What's the special security property of the composite order group in comparison with one of prime order? To put it in another way when do we need ... 1answer 51 views ### Number generation for Fujisaki-Okamoto commitment scheme parameters I need to implement the Fujisaki-Okamoto commitment scheme for a project such that I can demonstrate performance of various zero-knowledge proofs in relation to one another, for example Boudot's "... 0answers 51 views ### What is the hardness in Decisional Linear Assumption (DLIN)? I had understood what does the DLIN assumption means and here is a related question. But I fail to understand the 'real hardness' in this problem. I would be grateful if someone can help me to ... 1answer 56 views ### Do$v_1=\alpha\cdot r_1$and$v_2=\alpha\cdot r_2$leak information about$\alpha$Please consider we have finite field$\mathbb{F}_p$for large prime number$p$. We have a fixed field element$\alpha$. By$r_i\leftarrow \mathbb{F}_p$we mean we pick$r_i$uniformly random from the ... 1answer 42 views ### Confusion regarding computing Multiplicative Inverse Modulo P? May be a silly doubt, please rectify my confusion regarding below problem: For concreteness assume$g=2, p=11, a=6$and$x=9$$$A = g^a \bmod p = 2^6 \bmod 11 = 9$$ $$X = g^x \bmod p = 2^9 \bmod 11 ... 3answers 591 views ### Block cipher fixed points (plaintext equal to ciphertext) A block cipher is a bijective map from the set of possible plaintexts to the set of ciphertexts, which are the same size and might as well be considered the same thing: \theta: S\to S. In this there ... 1answer 151 views ### Simple example to describe Bilinear mapping Notation : \mathbb{G} is an additive group and \mathbb{G}_T is multiplicative group of prime order q. Bilinear mapping e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T has to satisfy ... 1answer 237 views ### Do Gap-CDH groups exist? A Gap-CDH group is such that, given group elements g, a = g^x, b = g^y, it is hard to compute g^{xy}, but, given a group element c, easy to verify if c = g^{xy}. While such groups have been ... 1answer 97 views ### Show How to Efficiently Solve the Computational Diffie-Hellman Assumption given an Algorithm that Solves the Square-DH Problem Let q prime number, G a cyclic group with order q and let g \in G be a generator of G. Suppose that you have an algorithm A who takes input the element g^a of G and gives as output the ... 1answer 59 views ### “Order” in cryptographic terms for generators Frequently I have seen people use the term order in cryptography (the group theoretic one). I have a mathematical background and order (say for prime modulus p) is defined as the smallest integer ... 2answers 72 views ### How to compute two EC point multiplication? I would like to know how to compute multiplication of two valid EC points over a curve E with generator G. i.e. Given only P and Q points then how to compute R = P * Q where P = p G, Q = q G and ... 1answer 84 views ### Working on subgroup of \mathbb{Z}^*_p in practice It is said that, given a group \mathbb{Z}^*_p, we can always have a subgroup whose order is prime. To this end, for a safe prime p=2q+1, compute x_i^2 \bmod p for all x_i \in \mathbb{Z}^*_p. ... 2answers 196 views ### In a group, is it hard to calculate the base g given g^a and a? Discrete logarithm, that is: calculate a given g and g^a, is assumed to be a hard problem in some groups. Is it also hard to calculate g given g^a and a? 1answer 106 views ### Hash “Preimage by product” resistance Let H() be a hash function that achieves collision resistance as well as first and second preimage resistance. Let's equip the output set of H of a multiplicative group structure, more precisely a ... 1answer 143 views ### Can we reduce Diffie-Hellman problem to “Discrete-log inversion” problem? Let G be a cyclic multiplicative group of order n. Let g be a (public) generator of G. The Diffie-Hellman (DH) problem asks: Given g^x, g^y\in G for x, y\in \mathbb{Z}^*_n, to compute g^{... 1answer 325 views ### Logjam: “composite order subgroups” explained for TLS developers and system admins? I have read the recent logjam paper Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. On page 11 in the Recommendations section, they state: ... 1answer 98 views ### How to perform homomorphic multiplication in ElGamal? How can I compute homomorphic multiplication in ElGamal? That is: Given two ciphertexts (R_1,c_1) and (R_2,c_2) corresponding to plaintexts m_1 and m_2 under some public key; how can I compute ... 2answers 229 views ### Why does Diffie-Hellman need be a cyclic group? Why is Diffie-Hellman defined on a cyclic group? Doesn't it work for any commutative operation which the inverse is hard to find? Say Alice and Bob agree in a public prime c and both choose a ... 1answer 61 views ### In a additive group is it hard to calculate bg given ag, g, abg The ECDH problem defined that given g,ag,bg it is difficult to calculate abg. But it is also difficult to calculate bg given ag,g,abg. where g is generator and a,b are elements of group. 1answer 159 views ### Generating cyclic group for Ciphertext-Policy Attribute-Based Encryption [closed] I am doing Project under the topic CP-ABE.I need to generate a symmetric bilinear group Go of prime order p and with generator g...Then how to choose random elements from Zp....kindly anyone help me...... 1answer 76 views ### Converting a number to a member of a multiplicative cyclic group I am currently trying to make an implementation of the ElGamal encryption for educational purposes. As I understand it, when using the encryption with multiplicative cyclic groups, one generates a ... 1answer 171 views ### ElGamal and Schnorr groups As I gather, a normal practice for choosing a cyclic group for ElGamal key generation is to find a safe prime p and use a multiplicative cyclic group with modulus p and order q = (p-1)/2. ... 2answers 285 views ### Subgroups generators with respect to group generators of composite order If I have a group \mathcal{G} of order N=npq and subgroups \mathcal{G_n,G_p,G_q} of order n, p, g respectively and if g is a generator of \mathcal{G} why then g^{nq} is a generator ... 1answer 81 views ### Meaning of Multiplicative Group to the power n i.e. Z^n [closed] What does Z_q^n mean in this notation? References: on the 2nd paragraph of page: http://en.wikipedia.org/wiki/Learning_with_errors 1answer 199 views ### Pollard's Rho - Constructing the random function Suppose we are aiming to solve the discrete logarithm problem \alpha^x=\beta in some cyclic group G=<\alpha>. Then we are looking for a (uniformly) random sequence of elements of the form \... 2answers 1k views ### What are Cryptographic Multi-linear Maps? I've encountered this term many times in the fields of Fully-Homomorphic Encryption and Obfuscation. I want to learn those subject and Cryptographic Linear Maps seems to be an obstacle in the way. ... 1answer 161 views ### How can I find the order of the group that an elliptic curve is defined over? I have a Weierstrass elliptic curve (y^2=x^3+a \times x+b \mod p ) How can I find the order of the group itself? I have seen Mathematica has a GroupOrder[] ... 2answers 226 views ### Elliptic curve group over a prime finite field F_p If p is a big prime, and the elliptic curve E is defined over F_p by the equation y^2=x^3+ax+b where a,b\in F_p. The point on E/F_p together with the infinite point \mathcal{O} form a ... 2answers 217 views ### Given g, b, g^{ab}, is finding g^a a hard problem? As in the title, given g, g^{ab} are big elements in a prime group Z_p and b in prime group Z_r (p > r, g is one generator of Z_p). a is unknown and also in Z_r, is finding g^a... 2answers 453 views ### Why is ElGamalEngine in bouncy castle restricting input data to be less than the length of the group parameter p? I am currently using the ElGamalEngine of bouncy castle to implement exponential ElGamal for the purpose of making ElGamal additively homomorphic. To do this i raise the message to be encrypted to the ... 2answers 408 views ### in Bilinear pairings, what is the difference between Type 2 and Type 3? in Bilinear pairings, what is the difference between Type 2 and Type 3? I understand in Type 2, there exists an efficiently computable homomorphic function \phi : G_2 \rightarrow G_1 , which is not ... 1answer 98 views ### Symmetry for finite cyclic groups (Z/pZ)∗ How well is it known that for i such that 1 \leq i \leq \frac{p − 1}2:$$ g^{i+(p−1)/2} = g^{i−1+(p−1)/2} − g^i + g^{i−1} \pmod p$$Whilst working in the finite cyclic group of prime moduli$(Z/...
If there a proof in the literature which says the CONF Problem is equivalent to solving the discrete log ? Let $g$ be a generator of a cyclic group $\mathbb{G}$ of prime order $q$ CONF problem: ...