Recent Questions - Cryptography Stack Exchange most recent 30 from crypto.stackexchange.com 2023-10-03T16:53:01Z https://crypto.stackexchange.com/feeds https://creativecommons.org/licenses/by-sa/4.0/rdf https://crypto.stackexchange.com/q/108163 0 Worst-case one-way permutations under P different from NP Noel Arteche https://crypto.stackexchange.com/users/111722 2023-10-03T11:22:47Z 2023-10-03T11:22:47Z <p>This is probably obvious, but I cannot find it anywhere, since all textbooks define OWFs for average-case hardness.</p> <p>Do we known if <em>worst-case</em> one-way <em>permutations</em> exist assuming <span class="math-container">$\mathbf{P} \neq \mathbf{NP}$</span>? I don't require average-case hardness, it suffices that the function is hard to invert in the worst-case.</p> https://crypto.stackexchange.com/q/108158 1 If G is a PRG, is G' necessarily a PRG? Steven https://crypto.stackexchange.com/users/111708 2023-10-02T17:48:12Z 2023-10-03T13:58:59Z <p><strong>Given</strong>:</p> <ul> <li>A function <span class="math-container">$$G: \{0,1\}^{3n} \to \{0,1\}^{6n}$$</span> which is known to be a secure Pseudorandom Generator (PRG).</li> <li>A derived function <span class="math-container">$$G'(x_1 \| x_2) = G_b(x_1\|0^n\|x_2), \text{ where } x_1, x_2 \in \{0,1\}^n.$$</span></li> </ul> <p><strong>Question</strong>: Can we assert that <span class="math-container">$G'$</span> is also a PRG?</p> <p><strong>Observations</strong>:</p> <ul> <li><span class="math-container">$G'$</span>'s output maps to a specific subset of <span class="math-container">$G$</span>'s outputs, specifically when the input has the predictable form <span class="math-container">$x_1\|0^n\|x_2$</span>.</li> <li>A PRG's output should be indistinguishable from truly random strings, even with structured input.</li> </ul> <ol> <li>Constructive argument: If ( G ) is secure, its output should be indistinguishable from a random string, even with the ( 0^n ) segment in the seed.</li> <li>Counterexample: The introduction of the ( 0^n ) structure might make ( G' )'s input distribution not uniformly random, which is a requirement for a PRG</li> </ol> <p>What are your thoughts? Is ( G' ) still a PRG given our knowledge of ( G )? Or does the predictable seed invalidates it being a PRG? I've explored both angles but haven't reached a definitive stance. Would love to hear your thoughts on this.</p> https://crypto.stackexchange.com/q/108157 1 AES GCM iv/nonce length under 12 bytes in java Pierre Berget https://crypto.stackexchange.com/users/111704 2023-10-02T16:22:48Z 2023-10-02T19:06:28Z <p>I'm developping an Swift app that communicate with a Java legacy backend using AES GCM, my biggest problem is that Java let you use a 8 bytes iv/nonce (and the legacy code is written with 8 bytes nonce). You can't do that in swift, it result in error. I can't find in javadoc what happen to nonce too short, i guess they transform it (hash maybe ?) Do you have any idea besides upgrading the legacy code ?</p> https://crypto.stackexchange.com/q/108156 1 Finding two inputs [i, j] of a custom Hash function where their Hashes are [H(i), H(j)] = [H(i), H(i)^2] bd55 https://crypto.stackexchange.com/users/104578 2023-10-02T16:14:41Z 2023-10-03T06:01:57Z <p>I came upon the following hash function (pseudo-code):</p> <pre><code>function customHash(integer:user_input) { user_input = user_input modulo 2654435789 user_input = user_input * 2654435789 ret_to_user = user_input &gt;&gt; 32 return ret_to_user } </code></pre> <p>The goal of the problem I am trying to solve is:</p> <ul> <li>Find two inputs [i,j] that can only be lowercase characters, uppercase characters, digits or a compination of them (a-zA-Z0-9) where the customHash(j) == customHash(i)^2. The input to the function is the integer representation of the input (meaning we take the whole input, convert it to integer and then pass this integer to the function). Also, there is no restriction to the length of the input that is passed to customHash function.</li> </ul> <p>For example:</p> <ul> <li>customHash(i) = 5</li> <li>customHash(j) = 25</li> </ul> <p>I tried using code to brute force inputs until I got a solve to this problem but the code was running forever. Also, even if it did find a match, It might not be a solution that is in (a-zA-Z0-9).</p> <p>I got one suggestion that this can be done with lattices, but I am not sure how, so if anyone is proficient with lattices (and it indeed is solvable with lattice approach) or has some other approach to this problem, I would really like an explanation to it.</p> https://crypto.stackexchange.com/q/108155 0 Safe and Sophie Germain primes in Diffie–Hellman key exchange pacman https://crypto.stackexchange.com/users/103942 2023-10-02T14:32:55Z 2023-10-02T15:01:43Z <p>I came across wiki page for <a href="https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes" rel="nofollow noreferrer">Safe and Sophie Germain primes</a>:</p> <blockquote> <p>Safe primes are also important in cryptography because of their use in discrete logarithm-based techniques like Diffie–Hellman key exchange. If <span class="math-container">$2p+1$</span> is a safe prime, the multiplicative group of integers modulo <span class="math-container">$2p+1$</span> has a subgroup of large prime order. It is usually this prime-order subgroup that is desirable, and the reason for using safe primes is so that the modulus is as small as possible relative to <span class="math-container">$p$</span>.</p> </blockquote> <p>I'm looking for an example with some small numbers (like <span class="math-container">$p=11$</span>, <span class="math-container">$2p+1=23$</span>) to understand the paragraph above step by step.</p> https://crypto.stackexchange.com/q/108150 4 is TLS compression used in modern browsers? pacman https://crypto.stackexchange.com/users/103942 2023-10-02T05:42:15Z 2023-10-03T14:04:31Z <p>In 2012 CRIME attack effectively killed TLS compression. Has anything changed since 2012 regarding compression in TLS or have modern browsers sacrificed security over performance? If browsers now use TLS compression how does it bypass CRIME/BREACH?</p> https://crypto.stackexchange.com/q/108149 0 Benaloh cryptosystem Al A https://crypto.stackexchange.com/users/108678 2023-10-01T15:45:00Z 2023-10-01T15:49:32Z <p>I was reading this article on Wikipedia, but I don't seem to understand how this holds: <span class="math-container">$u^\phi \equiv u^0 \mod n$</span>. Can someone explain it to me? Thank you.</p> <blockquote> <h3>Key Generation</h3> <p>Given block size <span class="math-container">$r$</span>, a public/private key pair is generated as follows:</p> <ol> <li>Choose large primes <span class="math-container">$p$</span> and <span class="math-container">$q$</span> such that <span class="math-container">$r \vert (p-1)$</span>, <span class="math-container">$\operatorname{gcd}(r, (p-1)/r)=1$</span>, and <span class="math-container">$\operatorname{gcd}(r, (q-1))=1$</span>.</li> <li>Set <span class="math-container">$n=pq$</span>, <span class="math-container">$\phi=(p-1)(q-1)$</span>.</li> <li>Choose <span class="math-container">$y \in \mathbb{Z}^*_n$</span> such that <span class="math-container">$y^{\phi/r} \not \equiv 1 \mod n$</span>.</li> </ol> <p><strong>Note:</strong> If <span class="math-container">$r$</span> is composite, it was pointed out by Fousse et al. in 2011\cite{ACRYPT} that the above conditions (i.e., those stated in the original paper) are insufficient to guarantee correct decryption, i.e., to guarantee that <span class="math-container">$D(E(m)) = m$</span> in all cases (as should be the case). To address this, the authors propose the following check: let <span class="math-container">$r=p_1p_2\dots p_k$</span> be the prime factorization of <span class="math-container">$r$</span>. Choose <span class="math-container">$y \in \mathbb{Z}^*_n$</span> such that for each factor <span class="math-container">$p_i$</span>, it is the case that <span class="math-container">$y^{\phi/p_i}\ne 1\mod n$</span>.</p> <ol start="4"> <li>Set <span class="math-container">$x=y^{\phi/r}\mod n$</span>.</li> </ol> <p>The public key is then <span class="math-container">$y,n$</span>, and the private key is <span class="math-container">$\phi,x$</span>.</p> <h3>Message Encryption</h3> <p>To encrypt message <span class="math-container">$m\in\mathbb{Z}_r$</span>:</p> <ol> <li>Choose a random <span class="math-container">$u \in \mathbb{Z}^*_n$</span>.</li> <li>Set <span class="math-container">$E_r(m) = y^m u^r \mod n$</span>.</li> </ol> <h3>Message Decryption</h3> <p>To decrypt a ciphertext <span class="math-container">$c\in\mathbb{Z}^*_n$</span>:</p> <ol> <li>Compute <span class="math-container">$a=c^{\phi/r}\mod n$</span>.</li> <li>Output <span class="math-container">$m=\log_x(a)$</span>, i.e., find <span class="math-container">$m$</span> such that <span class="math-container">$x^m\equiv a \mod n$</span>.</li> </ol> <p>To understand decryption, first notice that for any <span class="math-container">$m\in\mathbb{Z}_r$</span> and <span class="math-container">$u\in\mathbb{Z}^*_n$</span> we have:</p> <p><span class="math-container">$a = (c)^{\phi/r} \equiv (y^m u^r)^{\phi/r} \equiv (y^{m})^{\phi/r}(u^r)^{\phi/r} \equiv (y^{\phi/r})^m(u)^{\phi} \equiv (x)^m (u)^0 \equiv x^m \mod n$</span></p> <p>To recover <span class="math-container">$m$</span> from <span class="math-container">$a$</span>, we take the discrete log of <span class="math-container">$a$</span> base <span class="math-container">$x$</span>. If <span class="math-container">$r$</span> is small, we can recover <span class="math-container">$m$</span> by an exhaustive search, i.e. checking if <span class="math-container">$x^i\equiv a \mod n$</span> for all <span class="math-container">$0\dots (r-1)$</span>. For larger values of <span class="math-container">$r$</span>, the Baby-step giant-step algorithm can be used to recover <span class="math-container">$m$</span> in <span class="math-container">$O(\sqrt{r})$</span> time and space.</p> </blockquote> https://crypto.stackexchange.com/q/108146 -1 How to convert the results of point doubling (Rx1 and Ry1) to point addition (Rx2 and Ry2) without knowledge of Qx and Qy Aviril Smith https://crypto.stackexchange.com/users/111159 2023-10-01T11:42:18Z 2023-10-03T08:02:18Z <p>I'm working with the secp256k1 elliptic curve and have point doubling and point addition formulas for this curve.</p> <p>If a point is given Qx and Qy</p> <pre><code>Qx = 112711660439710606056748659173929673102114977341539408544630613555209775888121 Qy = 25583027980570883691656905877401976406448868254816295069919888960541586679410 </code></pre> <p>performing point doubling on the given points <code>(Qx, Qy)</code> will get the below output</p> <pre><code>Rx1 = 115780575977492633039504758427830329241728645270042306223540962614150928364886 Ry1 = 78735063515800386211891312544505775871260717697865196436804966483607426560663 </code></pre> <p>Performing point addition on the given points <code>(Qx, Qy)</code> will get</p> <pre><code>Rx2 = 103388573995635080359749164254216598308788835304023601477803095234286494993683 Ry2 = 37057141145242123013015316630864329550140216928701153669873286428255828810018 </code></pre> <p>Now, I'm looking for a way to convert <code>(Rx1, Ry1)</code> to <code>(Rx2, Ry2)</code> without knowing the original given values <code>(Qx, Qy)</code>. Is there a method or algorithm to achieve this conversion?</p> https://crypto.stackexchange.com/q/108145 0 RSA - Twin Primes across two messages Nasica https://crypto.stackexchange.com/users/111678 2023-10-01T04:32:22Z 2023-10-01T07:04:39Z <p>This was a CTF challenge I was unable to solve, but I thought I may had come close.</p> <p>We were given two <span class="math-container">$N$</span>'s <span class="math-container">$N_1$</span> and <span class="math-container">$N_2$</span> each calculated with <span class="math-container">$P_1 \times Q_1$</span> and <span class="math-container">$P_2 \times Q_2$</span>; however, <span class="math-container">$P_1 = P_2 + 2$</span> where <span class="math-container">$P_2$</span> was still prime. <span class="math-container">$Q_1, P_2, Q_2$</span> where calculated by what I think was a fairly standard method (using sage)</p> <pre><code>bitlen = 1024 t = 32 upper_bound = bitlen+t lower_bound = bitlen-t q1 = random_prime(2^(lower_bound), lbound=2^(lower_bound-1)+2^(lower_bound-2), proof=False) </code></pre> <p>I attempted to attack this algebraically, using <span class="math-container">$$Q_1N_2 + 2Q_1Q_2 - Q_2N_1 = 0$$</span> Then <span class="math-container">$$Q_2 = \frac{N_2}{P_2}$$</span> <span class="math-container">$$Q_1 = \frac{N_1}{P_1}$$</span> <span class="math-container">$$= \frac{N_1}{(P_2 + 2)}$$</span> <span class="math-container">$$= \frac{N_1}{((N_2 / Q_2) + 2)}$$</span> <span class="math-container">$$Q_1 = \frac{(N_1Q_2)}{(N_2 + 2Q_2)}$$</span> And substituting that back into the first equation to have a function with only factors of <span class="math-container">$Q_2$</span>; however, I was left with really ugly quadratics that didn't seem to have solutions <span class="math-container">$\neq 0$</span>. So I assume my math/logic was wrong somewhere along the line and there isn't an algebraic solution.</p> <p>EDIT: I just noticed that when it checked for primality of the twin prime it uses the <code>is_pseudoprime()</code> function and not the <code>is_prime()</code> function.</p> <p>Would anyone be able to suggest how to attack this</p> <p>(This CTF is no longer running, and I have been told a solution will be released very shortly but I was hoping for something more descriptive, please)</p> https://crypto.stackexchange.com/q/108142 0 Is there any publicly available/self-hosted OPRF service/implementation? Tobsec https://crypto.stackexchange.com/users/85606 2023-09-30T19:10:41Z 2023-09-30T19:10:41Z <p>I've recently implemented &amp; hosted an Oblivious Pseudo-Random Function (OPRF) based on <a href="https://github.com/multiparty/oprf" rel="nofollow noreferrer">multiparty/oprf</a> i.e. <a href="https://eprint.iacr.org/2017/111" rel="nofollow noreferrer">Burns et. al. EC-OPRF</a> as an AWS Lambda function / API, that can be recurrently used providing an ID (or getting a random one assigned). Also did some web searches prior and after, but haven't ran across anything similar, yet. So, does anybody of you know any publicly available OPRFs or projects/repos that allow their easy deployment/self-hosting? If not, I'm going to publish my Lambda implementation (only if there isn't anything comparable and more mature / better supported, yet).</p> https://crypto.stackexchange.com/q/108140 1 What is the inverse of this generalised automaton (based on bitwise XOR and modular addition)? lyrically wicked https://crypto.stackexchange.com/users/51525 2023-09-30T06:34:49Z 2023-10-01T11:00:17Z <p>Section 4.1 of the paper “Nonlinear Diffusion Layers” [Y. Liu, V. Rijmen, G. Leander] defines the nonlinear function <span class="math-container">$\rho$</span> over <span class="math-container">$\mathbb{F}_{2^m}$</span> as follows: <span class="math-container">$$\rho : \mathbb{F}_{2^m}^4 \to \mathbb{F}_{2^m}^4 : (x_3, x_2, x_1, x_0) \mapsto (y_3, y_2, y_1, y_0),$$</span> where <span class="math-container">$$y_i = x_i \oplus (x_{i + 1} \boxplus x_{i + 2}), 0 \leq i \leq 3, m \geq 2.$$</span> Here <span class="math-container">$\oplus$</span> is bitwise XOR, <span class="math-container">$\boxplus$</span> is addition modulo <span class="math-container">$2^m.$</span> Then Remark 2 says,</p> <blockquote> <p>Note that <span class="math-container">$\rho$</span> is of a similar nature as the Sbox (<span class="math-container">$\chi$</span> function) adopted in the SHA-3 permutation keccak-f, which is a generalised automaton. Although <span class="math-container">$\rho$</span> is invertible, the inverse of <span class="math-container">$\rho$</span> seems to be of no simple expression.</p> </blockquote> <p>My question is: what is the expression for the inverse of <span class="math-container">$\rho$</span>?</p> https://crypto.stackexchange.com/q/108129 0 Why hash algorithms have many different digest size variants? user111059 https://crypto.stackexchange.com/users/0 2023-09-29T12:21:31Z 2023-10-02T11:35:17Z <p>1- Why SHA2 has SHA224, SHA256, SHA384 and SHA512 variants?</p> <p>2- Can we say SHA512 more secure than SHA256?</p> <p>3- Symmetric ciphers use at most 2^256 security level and I saw on the internet people saying how impossible to reach that then Why SHA2 has a SHA 512 variant? Do we need 2^512 security level? İsn't it overkill?</p> <p>4- İs SHA 512 meant for post quantum world? If it's meant for post quantum world, Why does it not popular? because AES256 already in use by encrypted messengers, password managers.. etc. but I've seen their security whitepapers when it comes to SHA2 most of them use SHA256 instead of SHA512.</p> <p>5- so if we don't need 512 bit security, Why all the state of the art hash algorithms(e.g. BLAKE2, Skein, Grostl, JH, Keccak) have 512 bit variants?</p> <p>6- Let's say there's a key derivation function that uses Skein 256 as a underlying hash function, Would it be still secure in a post quantum world? or Would it be better to use Skein 512? to ask it another way, Why Argon2 settled on using BLAKE2b 512 instead of BLAKE2s 256?</p> https://crypto.stackexchange.com/q/108126 1 Is there still a place for obfuscation (secret algorithms) in encryption? Zonnkq Shad https://crypto.stackexchange.com/users/111643 2023-09-29T09:40:57Z 2023-10-01T00:49:29Z <p>As far as I know, the Second World War was won on codes that used obfuscation, not open source. These were also used during the cold war. For general use (not large companies with hundreds of employees who may or not be trustworthy) surely basic encryption that uses secret algorithms is still of use? I have asked this on another forum and got insulted. So if you feel the need to insult me, please do; but afterwards could you answer the question - it is genuine? A Ferrari is one of the best cars you can buy, but there is still a place for the Honda Civic. I feel the same about different encryption methods.</p> https://crypto.stackexchange.com/q/108118 0 Recursive snarks with a genus-2 no-cycle hyperelliptic curve? Vadym Fedyukovych https://crypto.stackexchange.com/users/18316 2023-09-28T11:50:20Z 2023-10-02T17:53:00Z <ol> <li><p>Any hyperelliptic curve having base field characteristic dividing group order?</p> </li> <li><p>A subgroup of order equal to the basefield characteristic, a large prime?</p> </li> <li><p>Having hard DLP in that subgroup?</p> </li> <li><p>Having pairing?</p> </li> <li><p>New elliptic-hyperelliptic cycle anyone?</p> </li> </ol> <p>SNARKs were introduced with QAP &quot;intermediate&quot; language to define computer-science and real-file problems as systems of equations &quot;with just a single multiplication&quot;, widely known thanx ZCash. Recursive SNARKs suggest verifying &quot;previous&quot; snark-proof(s) as a part of the current problem instance, that could be illustrated with proving a correct transaction and &quot;good&quot; previous blockchain state resulting in good current state.</p> <p>&quot;A cycle of curves&quot; like MNT4-MNT6 is the only known &quot;complete&quot; solution implementing groth16 SNARK. There is a good reason for no single-curve recursive snarks.</p> <p>Group order is roughly twice-bitlength (a square of) the field a genus-2 hyperelliptic curve is defined over. It is not &quot;slightly different&quot; from the field characteristic anymore it was with elliptic curves. Potentially there is a rich structure hopefully admitting recursion with a single curve, or alternative cycles.</p> <p>Hyperelliptic curves are not so popular. Group element is a pair of points on a genus-2 curve, so you need to handle &quot;divisors&quot; rather than points.</p> <p>There was a project 2019-2020 that resulted in a manager claimed me to discover an MNT5 curve, made public on ZCash forum. That team did &quot;proofs for knowledge&quot; and &quot;recurrent proofs&quot; in their papers in a Springer journal and an IEEE conference.</p> <p>Update</p> <p>The last point is the core question, the reason, and potentially a new idea.</p> <p>MNT4-MNT6 elliptic curves pair is the only known &quot;2-cycle&quot;: base field characteristic of the first equal to group order of the second, and vice versa. Informally, &quot;splitting&quot; the first property into two curves.</p> <p>It seems feasible to have group order (Jacobian) to be a product of two primes, the base field characteristic <span class="math-container">$q$</span> and <span class="math-container">$(q+2)$</span> for a genus-2 (but not for elliptic) curve. At least, this is ok with the Hasse-Weil interval. This hopefully would mean avoiding &quot;the largest prime divisor of the order of the Jacobian, is equal to the base field characteristic&quot; (the wikipedia page suggested by Daniel S, thanx!) pre-condition of the known attack on anomalous curves. If confirmed, this might mean a &quot;1-curve cycle&quot; for zk-SNARKs.</p> https://crypto.stackexchange.com/q/108116 2 What is meant by software and hardware implementations of cryptograpic schemes? How to do it? Ganesh https://crypto.stackexchange.com/users/111628 2023-09-28T11:14:01Z 2023-10-02T18:12:22Z <p>I have read many cryptographic papers or articles where I have came across about the <strong>software and hardware implementation</strong> for the cryptographic algorithms. I want to know how its been done. Is there any need to create a separate software to do this. Why there is a need of using FPGA board for the hardware implementation.</p> https://crypto.stackexchange.com/q/108111 1 TR-31 Key Exchange Mode of Use Jonathan Rosenne https://crypto.stackexchange.com/users/47586 2023-09-27T12:36:33Z 2023-09-30T18:55:37Z <p>Using TR-31 key exchange, how is it possible to use restrictive modes of use, such as V (Verify only)? If Alice were to generate such a key, and send it to Bob, Bob would not be able to generate a MAC for Alice to verify. Can this be solved without leaving the safe bounds of Key Blocks? To be specific, I am referring to ASC X9 TR 31-2018, Interoperable Secure Key Exchange Key Block Specification.</p> https://crypto.stackexchange.com/q/108105 0 Does ISAAC really guarantee a cycle length of at least 2**40? Guenther Brunthaler https://crypto.stackexchange.com/users/111600 2023-09-27T09:19:42Z 2023-09-30T14:48:14Z <p>I just noticed that <a href="https://link.springer.com/content/pdf/10.1007/3-540-60865-6_41.pdf" rel="nofollow noreferrer">the FSE 1996 conference paper which defines ISAAC</a> mentions a counter variable <code>cc</code>.</p> <p>This variable is said to be the reason why ISAAC has a guaranteed minimum cycle length of <span class="math-container">$2^{40}$</span>.</p> <p>However, no-one seems to have noticed (until I did just now) that the algorithm does not use the <code>cc</code> variable for anything other than incrementing it. But the incremented values are not used anywhere.</p> <p>Removing the variable does not seem to affect the algorithm's output either. At least not in my implementation.</p> <p>Did I miss something, or is this variable really as completely useless as it seems to be?</p> <p>And if it is, does this mean there is no guarantee that there are no short cycles?</p> https://crypto.stackexchange.com/q/107931 3 State of the art for Graph Isomorphism Gareth Ma https://crypto.stackexchange.com/users/103719 2023-09-12T10:43:04Z 2023-10-01T14:57:15Z <p>I want to know the state of the art result for proving knowledge of graph isomorphism. As described <a href="https://web.cs.ucla.edu/%7Erafail/PUBLIC/03.pdf" rel="nofollow noreferrer">here</a>, the classical Goldreich-Micali-Wigderson (GMW) protocol is a <span class="math-container">$\Sigma$</span>-protocol with soundness error <span class="math-container">$\frac{1}{2}$</span>, so it requires repetition. They then showed a <span class="math-container">$5$</span>-round protocol for GI, essentially forcing the verifier to commit to their challenges to allow for knowledge extraction (please correct me if my understanding is wrong).</p> <p>Question: Is there a <span class="math-container">$\Sigma$</span>-protocol with negligible soundness?</p> https://crypto.stackexchange.com/q/106825 0 Utility Guarantee of Small Data Base Mechanism in Differential Privacy KRWTS https://crypto.stackexchange.com/users/109833 2023-06-12T21:34:33Z 2023-10-02T08:44:03Z <p>I am reading Section 4.1 (An offline algorithm: SmallDB) of <a href="https://www.cis.upenn.edu/%7Eaaroth/Papers/privacybook.pdf" rel="nofollow noreferrer"><em>The Algorithmic Foundations of Differential Privacy</em> by Dwork and Roth</a>. I am stuck at the proof of Proposition 4.4, which is about the utility guarantee of the small database mechanism (Algorithm 4 in page 70).</p> <blockquote> <p><strong>Proposition 4.4.</strong> Let <span class="math-container">$\mathcal{Q}$</span> be any class of linear queries. Let <span class="math-container">$y$</span> be the database output by SmallDB(<span class="math-container">$x,\mathcal{Q},\epsilon,\alpha$</span>). Then with probability <span class="math-container">$1-\beta$</span>: <span class="math-container">$$\max_{f\in\mathcal{Q}}|f(x)-f(y)|\le\alpha+\frac{2\left(\frac{\log|\mathcal{X}|\log|\mathcal{Q}|}{\alpha^2}+\log\left(\frac{1}{\beta}\right)\right)}{\epsilon\|x\|_1}.$$</span> <em>Proof.</em> Applying the utility bounds for the exponential mechanism (Theorem 3.11) with <span class="math-container">$\Delta u=\frac{1}{\|x\|_1}$</span> and <span class="math-container">$\text{OPT}_q(x)\le\alpha$</span> (which follows from Theorem 4.2), we find: <span class="math-container">$$\Pr\left[\max_{f\in\mathcal{Q}}|f(x)-f(y)|\ge\alpha+\frac{2}{\epsilon\|x\|_1}\left(\log|\mathcal{R}|+t\right)\right]\le e^{-t}.$$</span></p> </blockquote> <p>Here <span class="math-container">$\mathcal{R}=\{y\in\mathbb{N}^{|\mathcal{X}|}:\|y\|_1=\log|\mathcal{Q}|/\alpha^2\}$</span> is the collection of small databases, and <span class="math-container">$u:\mathbb{N}^{|\mathcal{X}|}\times\mathcal{R}\to\mathbb{R}$</span> is given by <span class="math-container">$$u(x,y)=-\max_{f\in\mathcal{Q}}|f(x)-f(y)|,$$</span> which measures the similarity between an arbitrary database <span class="math-container">$x$</span> and a small database <span class="math-container">$y\in\mathcal{R}$</span>.</p> <p><strong>My question:</strong> Why is <span class="math-container">$\Delta u=1/\|x\|_1$</span>? According to page 38, <span class="math-container">$\Delta u$</span> is defined by <span class="math-container">$$\Delta u=\max_{y\in\mathcal{R}}\max_{\|x-x'\|_1\le 1}|u(x,y)-u(x',y)|,$$</span> so <span class="math-container">$\Delta u$</span> should not depend on the size of any database <span class="math-container">$x$</span>.</p> https://crypto.stackexchange.com/q/106359 2 Can you re-encrypt data without knowing what the data is or using PRE? Marston https://crypto.stackexchange.com/users/109147 2023-05-02T01:39:57Z 2023-10-02T05:04:30Z <p>I'm currently working on a distributed consensus-based system. I currently give the system a private key through a threshold encryption model, and I want to be able to take some data encrypted with the network's public key and re-encrypt it with an arbitrary public key without any member of the network knowing what the data was.</p> <p>I know proxy re-encryption is a good solution if the person who originally encrypted the data creates a re-encryption key, but this needs to be a specific key rather than an arbitrary one making it not suitable for such a use-case.</p> <p>In the following question that was asked, a comment concerning the ability to simply re-encrypt the data with one's own public key and decrypt it themselves would be of concern. In this model, I believe I have solved that aspect by requiring the network to come to a consensus to re-encrypt anything.</p> <p><a href="https://crypto.stackexchange.com/q/48839/109147">Re-encryption without knowing the secret</a></p> <p>I would love to know if something along these lines is even possible or if I'm just out to lunch.</p> https://crypto.stackexchange.com/q/106348 1 Question about Threshold signature scheme "GG18" Leila Shafiee https://crypto.stackexchange.com/users/109141 2023-05-01T12:15:43Z 2023-09-30T16:00:17Z <p>I recently read the article on the threshold signature scheme “<a href="https://doi.org/10.1145/3243734.3243859" rel="nofollow noreferrer">Fast Multiparty Threshold ECDSA with Fast Trustless Setup</a>” and I have a question.</p> <p>In the key generation section, each player <span class="math-container">$P_i$</span> selects <span class="math-container">$u_i$</span> and then performs a <span class="math-container">$(t, n)$</span> Feldman-VSS of the <span class="math-container">$u_i$</span> value. In this case, other participants can make use of Lagrange interpolation to construct the polynomial related to <span class="math-container">$P_i$</span>, and they can reconstruct <span class="math-container">$u_i$</span> value. Therefore, the values of <span class="math-container">$u_i$</span> of all players can be reconstructed and the adversary participants can obtain the value of the private key.</p> <p><span class="math-container">$$X = \sum u_i$$</span></p> <p>While the private key should not be reconstructable. For example, if we suppose 4 participants include [Alice, Bob, Carol and Dave] and we want to have <span class="math-container">$(4,3)$</span> Tss. In fact 3 people can perform signing. Alice put her <span class="math-container">$u_i$</span> value on a quadratic polynomial and performs <span class="math-container">$(4, 3)$</span> Feldman’s Vss. So Bob,Carol and Dave can reconstruct Alice’s Polynomial and They can obtain her <span class="math-container">$u_i$</span></p> <p>In this way, participants can reconstruct all of others’ <span class="math-container">$u_i$</span> . Due to the fact that Private key</p> <p><span class="math-container">$$X = \sum u_i = u_{\text{Alice}} + u_{\text{Bob}} + u_{\text{Carol}} + u_{\text{Dave}}$$</span></p> <p>they can obtain Private key.</p> <p>Please guide me on this subject.</p> https://crypto.stackexchange.com/q/103563 2 Apply local differential privacy to a datasets xavi https://crypto.stackexchange.com/users/106041 2023-01-03T09:00:48Z 2023-09-30T17:02:15Z <p>How to apply <code>local differential privacy</code> to specific categorical values in order to perform some analysis? Does there exist a tool?</p> <p>For example, I have the following dataset.</p> <pre><code> email address 0 exampleemail1 exampleadress1 1 exampleemail2 exampleadress2 </code></pre> <p>From this dataset, I take as output some results</p> <p>After the injection of statistical noise, I want to have the following <code>dataset</code></p> <pre><code> email address 0 noise exampleadress1 1 exampleemail2 exampleadress2 </code></pre> <p>From this <code>dataset,</code> I take as output also some results.</p> <p>In the end, I want to compare my new results to the previous one.</p> <p>I am looking at different libraries such as <code>pydp</code> or <code>pipeline dp</code> but cannot find an example</p> <p>In fact I want to apply LDP to every PII in my dataset</p> https://crypto.stackexchange.com/q/103060 2 Can export of wrapped secret key to insecure storage be cryptographically secure? Vlad https://crypto.stackexchange.com/users/7350 2022-11-30T06:47:49Z 2023-10-02T08:06:10Z <ol> <li><p>I ask because some vendors of HSM try to avoid the export of wrapped secret key from HSM to insecure storage – storage that does not belong to these vendor’s HSM infrastructure.</p> <p>For example, Thales prefer to backup keys to another Thales HSM – most of their documentation is about cloning between their devices. But Thales has an option when they send traffic via <strong>public</strong> networks: <a href="https://thalesdocs.com/gphsm/luna/7.4/docs/pci/Content/administration/backup_restore/planning.htm" rel="nofollow noreferrer">Backup HSM Installed Using Remote Backup Service (RBS)</a></p> <blockquote> <p>“…It is useful in deployments where backups are stored in a separate location from the SafeNet Luna PCIe HSM, to mitigate the consequences of catastrophic loss (fire, flood, etc).”</p> </blockquote> </li> <li><p>gpg2 man pages say following:</p> <blockquote> <p><code>Note that exporting a secret key can be a security risk if the exported keys are sent over an insecure channel.</code></p> </blockquote> </li> <li><p>From the other side I see that some solutions like AWS CloudHSM <strong>allow</strong> <a href="https://docs.aws.amazon.com/cloudhsm/latest/userguide/manage-aes-key-wrapping.html" rel="nofollow noreferrer">export/wrapping of key to insecure storage</a></p> </li> </ol> <p>Let’s use <strong>similar</strong> approach for AES-256 key wrapping described in this article <a href="https://ellipticsecure.com/ehsm/faq/2018/11/28/how-do-backups-work.html" rel="nofollow noreferrer">How do HSM Backups work?</a> for making a backup of 256-bit key from some HSM:</p> <ol> <li>The HSM generates a unique (per backup) AES 256-bit key (KDF is used) to encrypt each backup of the OTK (the one-time or ephemeral key).</li> <li>AES Key Wrap Algorithm: RFC 3394 (AES Key Wrap with No Padding)</li> </ol> <p>The backup will be stored in the storage publicly available for reading (no write/delete permission). Let’s consider only attacks based on cryptanalysis, brute-force or dictionary attack (not side-channel or other kind of attacks). A dictionary attack is possible because the wrapping of AES-256 key is derived from passphrase (according to standard KDF). Assume that passphrase is strong or may be made strong enough if necessary.</p> <p>All keys in the system have the same policy/purpose.</p> <p>Updated: Since dictionary attack is in scope of this question generation of passphrase should be specified: Nowadays the following usage is common: for operation that happens rarely (like generation of the private key for wallet initialization or unwrapping the key to HSM from backup) 24 words are used (chia is an example). A person can write down these words. Dictionary contains 2048 == 2^11 <a href="https://github.com/bitcoin/bips/blob/master/bip-0039/bip-0039-wordlists.md" rel="nofollow noreferrer">words</a>.</p> <p>2^256 &lt; (2^11)^24 == true</p> <p>The application generates passphrase for the user. Each word from the dictionary is randomly (uniformly) selected. User's manipulations with input devices are used as seeds for RNG. The properties of generated pseudo-random sequences will be tested with randomness tests.</p> <p>Is such export of wrapped secret key to insecure storage cryptographically secure? cryptographically secure means here that attacker cannot obtain secret (wrapped) key in plain text.</p> <p>If mentioned conditions are not sufficient what should be modified?</p> <p>Can the export of a wrapped secret key to insecure storage be cryptographically secure?</p> https://crypto.stackexchange.com/q/100259 0 Elliptic Curve - distinguish between two points after multiplication Robert M https://crypto.stackexchange.com/users/101965 2022-05-22T18:08:34Z 2023-10-02T08:58:35Z <p>If <span class="math-container">$P$</span> and <span class="math-container">$Q$</span> are two points on an elliptic curve of large prime order, given <span class="math-container">$P, Q$</span>, and a point <span class="math-container">$R$</span> which is either (a) <span class="math-container">$nP$</span> or (b) <span class="math-container">$nQ$</span>, is it possible to determine if <span class="math-container">$R$</span> is of form (a) or form (b)? Here <span class="math-container">$n$</span> is a secret.</p> https://crypto.stackexchange.com/q/95216 2 Extending the OR-proof to more than two statements wattlab https://crypto.stackexchange.com/users/96078 2021-09-23T09:33:26Z 2023-09-30T03:54:05Z <p>I have been reading about the sigma protocols, specially the OR-Proof.</p> <p>Many examples just take into account two statements and provide a way to say that one of the statements is valid, but not which one. For example this question <a href="https://crypto.stackexchange.com/questions/47730/zero-knowledge-proof-of-disjunctive-statements-or-proofs">zero-knowledge proof of disjunctive statements (OR proofs)</a>, or protocol 3 in this article <a href="https://medium.com/@loveshharchandani/zero-knowledge-proofs-with-sigma-protocols-91e94858a1fb" rel="nofollow noreferrer">Zero Knowledge Proofs with Sigma Protocols</a>, the section 4 of this work <a href="https://cs.au.dk/%7Eivan/Sigma.pdf" rel="nofollow noreferrer">On Σ-protocols</a> and this 2.4 on these slides <a href="https://www.math.leidenuniv.nl/%7Eedix/oww/mathofcrypt/schoenmakers/sigma-Leiden2003.pdf" rel="nofollow noreferrer">Σ-protocols</a>.</p> <p>I would like to extend this to 1 out of <span class="math-container">$N$</span> statements (instead of the 1 of out 2 of all the examples I have found). Many work refer <a href="https://www.win.tue.nl/%7Eberry/papers/crypto94.pdf" rel="nofollow noreferrer">Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols</a>. I have tried to understand it completely in order to implement a 1 out of <span class="math-container">$N$</span> or-protocol but without luck. The secret sharing is introduced, as I understand, to make it <span class="math-container">$t$</span> out of <span class="math-container">$N$</span>, introducing shares, making it slightly more complicated for me.</p> <p>For the 1 out of 2 protocol, a single challenge is send to the verifier made out of the summation of the &quot;correct&quot; challenge and a &quot;random&quot; challenge. Here is where I guess the extension to more &quot;random&quot; challenges need to take place.</p> <p>Is it possible to extend the protocol to 1 out of <span class="math-container">$N$</span> without using the secret sharing part?</p> https://crypto.stackexchange.com/q/81846 4 Sigma proofs for Pedersen commitments arithmetic under different bases pintor https://crypto.stackexchange.com/users/55097 2020-07-10T13:10:27Z 2023-09-30T03:54:12Z <p>I was wondering if it's possible to prove an equality of openings between <span class="math-container">$3$</span> Pedersen commitments <span class="math-container">$P\cdot Q$</span> and <span class="math-container">$R$</span> when <span class="math-container">$P, Q, R$</span> have different commitment keys.</p> <p>Suppose that commitment <span class="math-container">$R$</span> commits to <span class="math-container">$a+b$</span> and <span class="math-container">$P$</span> and <span class="math-container">$Q$</span> commit to <span class="math-container">$a$</span> and <span class="math-container">$b$</span> respectively. How can we prove, that <span class="math-container">$P$</span> and <span class="math-container">$Q$</span> combined commit to the same value as <span class="math-container">$R$</span> if we don't know relation betwen <span class="math-container">$(g_1, h_1)$</span> and <span class="math-container">$(g_2,h_2)$</span>?</p> <p><span class="math-container">$P = g_1^ah_1^{r_1}$</span>, <span class="math-container">$Q = g_2^b h_2^{r_2}$</span> and <span class="math-container">$R = g_3^{a+b}h_3^{r_3}$</span>.</p> <p><a href="https://eprint.iacr.org/2019/142.pdf" rel="nofollow noreferrer">LegoSNARKs</a> does something similar (<span class="math-container">$CP_{had}$</span>), but I was curious if there is a solution with sigma protocols.</p> https://crypto.stackexchange.com/q/68343 2 Honest Verifier Zero-Knowledge Game for Sigma Protocols eternalmothra https://crypto.stackexchange.com/users/55317 2019-03-27T16:27:04Z 2023-09-30T03:53:26Z <p>I am looking for how an adversary to special HVZK would work. In Boneh and Shoup's book (<a href="https://crypto.stanford.edu/~dabo/cryptobook/" rel="nofollow noreferrer">BonehShoup</a>) they have Attack Game 20.4 for special cHVZK. Here, the adversary produces a pair (x,y) (witness and statement) and sends it to their challenger, who either uses P and V or Sim to produce the transcript.</p> <p>Can I modify this game in the following ways?</p> <ol> <li>Can the adversary generate the challenge?</li> <li>Can I have the adversary ask on polynomially many challenges instead of just one? Why is he limited to a single output here?</li> </ol> https://crypto.stackexchange.com/q/63468 6 Is this Sigma Protocol zero knowledge or is it just a proof of knowledge? fraiser https://crypto.stackexchange.com/users/58477 2018-10-25T21:12:08Z 2023-09-30T03:53:53Z <p>Suppose I have the witness <span class="math-container">$x$</span> and need to prove that I correctly computed <span class="math-container">$(g^x)^x$</span> to a verifier. <span class="math-container">$g$</span> and <span class="math-container">$g^x$</span> are public. The verifier asks me for <span class="math-container">$(g^x)^x$</span>, but wants proof that I've given them the right answer.</p> <p>Here's my attempt at a solution:</p> <p>Let <span class="math-container">$X = g^x$</span> and <span class="math-container">$X' = (g^x)^x$</span></p> <p>Step 1: Prover chooses a random <span class="math-container">$r$</span> and sends <span class="math-container">$R = g^r$</span> and <span class="math-container">$R' = X^r$</span></p> <p>Step 2: Verifier sends a random <span class="math-container">$c$</span> (challenge)</p> <p>Step 3: Prover sends <span class="math-container">$z = r + cx$</span> (response)</p> <p>Step 4: Verifier checks if <span class="math-container">$g^z = RX^c$</span> and <span class="math-container">$X^z = R'(X')^c$</span>.</p> <p>I was wondering whether this is zero knowledge or just a proof of knowledge.</p> <p>Thanks!</p> https://crypto.stackexchange.com/q/59921 18 RSA factorization for special primes $p$ and $q$ Lisbeth https://crypto.stackexchange.com/users/21860 2018-06-10T07:11:24Z 2023-10-01T12:06:08Z <p>I want to factorize the modulus $n = pq$ knowing that $p$ and $q$ are not random, but constructed based on integer numbers $a$ and $b$ as following ($a$ and $b$ are not given):</p> <p>$$p = a^2 + b^2, \qquad q = 2ab + 1$$</p> <p>I'm looking for an <em>efficient</em> algorithm for factorizing such modulus. For example:</p> <pre><code>p = 3905103830521375109989981821052358603060411974175739135178032413678045353995521841398265207464935019588673586293494986686589282006584612622774357122916381 </code></pre> <p>and</p> <pre><code>q = 1591646908070155847916963586885757663611980465519823631755037539680092095045862090726135581178157761817489455092117167782391955226530969795393239461418421 </code></pre> <p>have such property.</p> https://crypto.stackexchange.com/q/32237 8 What is an example of a secure sigma proof? guglielmo london https://crypto.stackexchange.com/users/28016 2016-01-27T16:46:58Z 2023-09-30T03:53:33Z <p>I want to implement Threshold Elgamal as described in <a href="http://www.win.tue.nl/~berry/2WC13/LectureNotes.pdf">section 6.3.1</a> and in the decryption phase each party must broadcast a sigma proof to show that it actually has a valid secret share of the secret key. </p> <p>I read about Schnorr protocol as a solution for sigma proof but it is said to be insecure, in chapter 5 of the same <a href="http://www.win.tue.nl/~berry/2WC13/LectureNotes.pdf">lecture notes</a>.</p> <p>What secure sigma proof could I use ? </p> <p>It would be great if the sigma proof is non-interactive.</p>