Polly Cracker Conceptual public key encryption scheme introduced by Fellows and Koblitz (‘94) Basic idea over Fq[x]:=Fq[x1,…,xn] : - Public key: finite basis of ideal I ≤Fq[x]
- Secret key: common root ξV(I)
- Encrypting mFq: choose representative of m+I
- Decrypting cFq[x]: evaluate c at ξ
Can we get an encryption scheme out of this?
Security of Polly Cracker Polly Cracker by definition homomorphic we can’t expect IND-CCA (S., Geiselmann: CCA easily reveals ξ) IND-CPA has not been achieved so far: - intelligent linear algebra (Lenstra)
- differential attack (Hofheinz, S.)
- improved diff. attack (Levy-dit-Vehel, Perret)
Can we obtain an efficient heuristic scheme?
A Proposal Resistant to Lin. Alg. Levy-dit-Vehel, Perret ‘04: “Reasonably efficient” Polly Cracker system based on 3-SAT: elaborate key generation encryption procedure designed to resist intelligent linear algebra attack, … but the authors note that “the attack … and the improvement we have described… apply to our system too.”
Polly Two Ly (‘02) proposes a new related scheme: Domain parameters: g1,…,gtFq[x] s.t. kernel of φ: Fq[y] Fq[x] yi gi can be computed easily (syzygies of the gi) Public key: sparse generators of I ≤ Fq[y] Secret key: ξFqn with (gi(ξ))iV(I) and (g1 ∙…∙gt)(ξ)≠0
Polly Two (cntd.) Encrypting mFq with public basis {f1,…,fs}: Fix random hi:= αi∙yηi with monomials in c’’:=Σhifi getting canceled. 2. For each monomial of c’’ find a ker(φ)-element canceling it. In c’:=c’’+r (with rker(φ)) none of c’’ ‘s monomials should occur. c:=(c’+m∙yκ, κ) Decryption: evaluate at g(ξ) & divide by g(ξ)κ
Design Rationale sparse high-degree public polynomials impede direct Gröbner basis computation (cf. ENROOT) addition of ker(φ)-element hampers linear algebra attack message expansion more or less acceptable … is “the list” complete? Grassl, S. ‘04: low-degree elements in radical of public ideal allow to solve 1st challenge
“Challenge #2” Domain param.: 11 quadratic binomials over F223 Public basis: 4 trinomials, total deg. 128, 11 indeterminates Ciphertext c: 126 terms, total deg. 256 (indermediate ciphertext c’’: ≤6 terms) Goal of attack: reconstruct encryption step no recovery of secret (or equivalent) key
Recovering the ker(φ)-Part All terms of the ker(φ)-elements canceling terms in Σhifi should occur in c up to – the canceled term (- a term involving yκ ) omit yκ –term from ciphertext c & identify terms of the ≤6 ker(φ)-elements How can we find the terms of a syzygy?
Choice of ker(φ)-Polynomials Likely construction for ker(φ)-elements used in encryption: multiply low-degree syzygy with a term α∙yη fix a term β∙yσ of yκ –free ciphertext ĉ and compute multiset {gcd(yσ, yπ): yπ≠yσ a monomial in ĉ} high multiplicity (say >10) yields yη-candidate Challenge: 137 candidates for yη … only 22 after removing multiples
Finding the Terms of a Syzygy {β∙yσ : β∙yσ is a term of ĉ divisible by yη}. … summing (almost) all of them up should yield “a ker(φ)-element up to one term”. How can we check whether a polynomial is a “syzygy up to one term”?
Validating an “Almost Syzygy” r … in principle: evaluate r at g(x) & check whether r(g1(x),…,gt(x)) is (up to a const.) a power product of the gi … in practice: specialize some xj’s to constants before trial division. In this way we find the missing term, too (& can validate through repeated evaluation).
… Indeed It Works Applying the idea to the challenge: Candidate term sets have ≈20 terms & adding one of these sets up yields 1st syzygy subtract syzygy from ĉ & iterate Five syzygies can be found easily, leaving us with a simplified ĉ consisting of 27 terms.
Tempting: Apply “differential attack” of Hofheinz and S. to simplified ĉ yields only one term h2 … but a simple approach turns out to suffice: Remaining public key polynomials contain term with only two multiples in simplified ĉ. recovery of all secret terms hi
… Getting the Plaintext Subtracting Σhifi + found ker(φ)-part from the ciphertext, yields (short) polynomial that up to the term -m∙yκ is a syzygy. Complete missing term as before to get m. Plaintext underlying the example: 308834
Conclusion? Polly Two not cryptographically secure. Do we want Polly Two+ with a longer list […, linear algebra, differential attack, small degree in radical, this attack]? Need the assumptions underlying the encryption algorithm to be clarified?
Stronger Attacks? Design of encryption algorithm: hide c’’=Σhifi (by adding a syzygy) This attack: “Playing with terms” reveals c’’ Better approaches, e.g.,interpolation? c’’: sparse multivariate polynomial over Fq #terms in c’’ can be guessed bounding tdeg(c’’) not implausible
Sparse Interpolation? Evaluation of c’’+m∙yκ: the domain parameters g1,…,gt. Question: Under which assumptions is this kind of interpolation problem feasible?
Dostları ilə paylaş: |