Abstract
A self-corrector for a function f is an efficient machine that computes f correctly using any untrusted black-box that computes f correctly only with a certain probability. The design of self-correctors for non-verifiable functions, typically decryption functions of public-key cryptographies, was investigated. We present a design method for self-correctors that works even when the black-box returns correct output with probability of less than 1/2. For a practical demonstration of the method, we also present examples of self-correctors for the decryption functions of public-key cryptosystems, such as the ElGamal, the Pailler, and the GHV cryptosystems, and for hidden pairings with trapdoors.
Keywords
- Smart Card
- Success Probability
- Turing Machine
- Stable Class
- Decryption Function
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
This is a preview of subscription content, log in via an institution.
- Chapter
-
USD 29.95
- Price excludes VAT (USA)
- eBook
- USD 39.99
- Price excludes VAT (USA)
- Softcover Book
- USD 54.99
- Price excludes VAT (USA)
Tax calculation will be finalised at checkout
Purchases are for personal use only
') var head = document.getElementsByTagName("head")[0] var script = document.createElement("script") script.type = "text/javascript" script.src = "https://buy.springer.com/assets/js/buybox-bundle-a3cdb49e59.js" script.id = "ecommerce-scripts-" + timestamp head.appendChild(script) var buybox = document.querySelector("[data-id=id_"+ timestamp +"]").parentNode ;[].slice.call(buybox.querySelectorAll(".buying-option")).forEach(initCollapsibles) function initCollapsibles(subscription, index) { var toggle = subscription.querySelector(".buying-option-price") subscription.classList.remove("expanded") var form = subscription.querySelector(".buying-option-form") if (form) { var formAction = form.getAttribute("action") document.querySelector("#ecommerce-scripts-" + timestamp).addEventListener("load", bindModal(form, formAction, timestamp, index), false) } var priceInfo = subscription.querySelector(".price-info") var buyingOption = toggle.parentElement if (toggle && form && priceInfo) { toggle.setAttribute("role", "button") toggle.setAttribute("tabindex", "0") toggle.addEventListener("click", function (event) { var expanded = toggle.getAttribute("aria-expanded") === "true" || false toggle.setAttribute("aria-expanded", !expanded) form.hidden = expanded if (!expanded) { buyingOption.classList.add("expanded") } else { buyingOption.classList.remove("expanded") } priceInfo.hidden = expanded }, false) } } function bindModal(form, formAction, timestamp, index) { var weHasBrowserSupport = window.fetch && Array.from return function() { var Buybox = EcommScripts ? EcommScripts.Buybox : null var Modal = EcommScripts ? EcommScripts.Modal : null if (weHasBrowserSupport && Buybox && Modal) { var modalID = "ecomm-modal_" + timestamp + "_" + index var modal = new Modal(modalID) modal.domEl.addEventListener("close", close) function close() { form.querySelector("button[type=submit]").focus() } var cartURL = "/cart" var cartModalURL = "/cart?messageOnly=1" form.setAttribute( "action", formAction.replace(cartURL, cartModalURL) ) var formSubmit = Buybox.interceptFormSubmit( Buybox.fetchFormAction(window.fetch), function(responseBody) { document.body.dispatchEvent(new Event("updatedCart")) Buybox.triggerModalAfterAddToCartSuccess(modal)(responseBody) }, function() { form.removeEventListener("submit", formSubmit, false) form.setAttribute( "action", formAction.replace(cartModalURL, cartURL) ) form.submit() } ) form.addEventListener("submit", formSubmit, false) document.body.appendChild(modal.domEl) } } } function initKeyControls() { document.addEventListener("keydown", function (event) { if (document.activeElement.classList.contains("buying-option-price") && (event.code === "Space" || event.code === "Enter")) { if (document.activeElement) { event.preventDefault() document.activeElement.click() } } }, false) } function initialStateOpen() { var buyboxWidth = buybox.offsetWidth ;[].slice.call(buybox.querySelectorAll(".buying-option")).forEach(function (option, index) { var toggle = option.querySelector(".buying-option-price") var form = option.querySelector(".buying-option-form") var priceInfo = option.querySelector(".price-info") if (buyboxWidth > 480) { toggle.click() } else { if (index === 0) { toggle.click() } else { toggle.setAttribute("aria-expanded", "false") form.hidden = "hidden" priceInfo.hidden = "hidden" } } }) } initialStateOpen() if (window.buyboxInitialised) return window.buyboxInitialised = true initKeyControls() })()
References
Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof Verification and Intractability of Approximation Problems. Journal of the ACM45, 501–555 (1992); Preliminary version in FOCS 1992
Arora, S., Safra, S.: Probabilistic Checkable Proofs: A New Characterization of NP. Journal of the ACM45, 70–122 (1992); Preliminary version in FOCS 1992
Arora, S., Sudan, M.: Improved low degree testing and its applications. In: STOC 1997, pp. 485–495 (1997)
Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications. In: STOC 1988, pp. 103–112 (1988)
Blum, M., Luby, M., Rubinfeld, R.: Self-Testing/Correcting with Applications to Numerical Problems. In: STOC 1990, pp. 73–83 (1990)
Dent, A.W., Galbraith, S.D.: Hidden Pairings and Trapdoor DDH Groups. In: Dorigo, M., Gambardella, L.M., Birattari, M., Martinoli, A., Poli, R., Stützle, T. (eds.) ANTS 2006. LNCS, vol.4150, pp. 436–451. Springer, Heidelberg (2006)
Feigenbaum, J., Fortnow, L., Laplante, S., Naik, A.V.: On Coherence, Random-self-reducibility, and Self-correction. Computational Complexity7(2), 174–191 (1998)
Article MATH MathSciNet Google Scholar
Gemmell, P., Lipton, R., Rubinfeld, R., Sudan, M., Wigderson, A.: Self-testing/correcting for polynomials and for approximate functions. In: STOC 1991, pp. 32–42 (1991)
Gentry, C., Halevi, S., Vaikuntanathan, V.: A Simple BGN-Type Cryptosystem from LWE. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.6110, pp. 506–522. Springer, Heidelberg (2010)
Chapter Google Scholar
Goldreich, O., Levin, L.: A Hard-Core Predicate for all One-Way Functions. In: STOC 1989, pp. 25–32 (1989)
Hohenberger, S., Lysyanskaya, A.: How to Securely Outsource Cryptographic Computations. In: Kilian, J. (ed.) TCC 2005. LNCS, vol.3378, pp. 264–282. Springer, Heidelberg (2005)
Chapter Google Scholar
Lenstra Jr., H.W.: Factroing Integers with Elliptic Curves. Ann. Math.126, 649–673 (1987)
Maurer, U.M., Wolf, S.: The Relationship Between Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms. SIAM Journal of Computing28, 1689–1721 (1999)
Paillier, P.: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol.1592, pp. 223–238. Springer, Heidelberg (1999)
Chapter Google Scholar
Raz, R., Safra, S.: A subconstant error-probability low-degree test, and a subconstant error-probability PCP characterization of NP. In: STOC 1997, pp. 475–484 (1997)
Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM Journal of Computing25(2), 252–271 (1992); Preliminary version in SODA 1992
Shoup, V.: Lower Bounds for Discrete Logarithms and Related Problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol.1233, pp. 256–266. Springer, Heidelberg (1997)
Chapter Google Scholar
Download references