Random self-reducibility

Random self-reducibility (RSR) is the rule that a good algorithm for the average case implies a good algorithm for the worst case. RSR is the ability to solve all instances of a problem by solving a large fraction of the instances.

Definition

If for a function f evaluating any instance x can be reduced in polynomial time to the evaluation of f on one or more random instances yi, then it is self-reducible (this is also known as a non-adaptive uniform self-reduction). In a random self-reduction, an arbitrary worst-case instance x in the domain of f is mapped to a random set of instances y1, ..., yk. This is done so that f(x) can be computed in polynomial time, given the coin-toss sequence from the mapping, x, and f(y1), ..., f(yk). Therefore, taking the average with respect to the induced distribution on yi, the average-case complexity of f is the same (within polynomial factors) as the worst-case randomized complexity of f.

One special case of note is when each random instance yi is distributed uniformly over the entire set of elements in the domain of f that have a length of |x|. In this case f is as hard on average as it is in the worst case. This approach contains two key restrictions. First the generation of y1, ..., yk is performed non-adaptively. This means that y2 is picked before f(y1) is known. Second, it is not necessary that the points y1, ..., yk be uniformly distributed.

Application in cryptographic protocols

Problems that require some privacy in the data (typically cryptographic problems) can use randomization to ensure that privacy. In fact, the only provably secure cryptographic system (the one-time pad) has its security relying totally on the randomness of the key data supplied to the system.

The field of cryptography utilizes the fact that certain number-theoretic functions are randomly self-reducible. This includes probabilistic encryption and cryptographically strong pseudorandom number generation. Also, instance-hiding schemes (where a weak private device uses a strong public device without revealing its data) are easily exemplified by random self-reductions.

Examples

The discrete logarithm problem, the quadratic residuosity problem, the RSA inversion problem, and the problem of computing the permanent of a matrix are each random self-reducible problems.

Discrete logarithm

Theorem: Given a cyclic group G of size |G|. If a deterministic polynomial time algorithm A computes the discrete logarithm for a 1/poly(n) fraction of all inputs (where n = log |G| is the input size), then there is a randomized polynomial time algorithm for discrete logarithm for all inputs.

Given a generator g of a cyclic group G = { gi | 0 ≤ i < |G| }, and an xG, the discrete log of x to the base g is the integer k (0 ≤ k < |G|) with x = gk. Take B to be distributed uniformly on {0,...,|G| − 1}, then xgB = gk+B is also distributed uniformly on G. Therefore xgB is independent of x, and its logarithm can be computed with probability 1/poly(n) in polynomial time. Then loggx ≡ loggxgB - B (mod |G|) and the discrete logarithm is self-reducible.

Permanent of a matrix

Given the definition of the permanent of a matrix, it is clear that PERM(M) for any n-by-n matrix M is a multivariate polynomial of degree n over the entries in M. Calculating the permanent of a matrix is a difficult computational task—PERM has been shown to be #P-complete (proof). Moreover, the ability to compute PERM(M) for most matrices implies the existence of a random program that computes PERM(M) for all matrices. This demonstrates that PERM is random self-reducible. The discussion below considers the case where the matrix entries are drawn from a finite field Fp for some prime p, and where all arithmetic is performed in that field.

Let X be a random n-by-n matrix with entries from Fp. Since all the entries of any matrix M + kX are linear functions of k, by composing those linear functions with the degree n multivariate polynomial that calculates PERM(M) we get another degree n polynomial on k, which we will call p(k). Clearly, p(0) is equal to the permanent of M.

Suppose we know a program that computes the correct value of PERM(A) for most n-by-n matrices with entries from Fp---specifically, 1 − 1/(3n) of them. Then with probability of approximately two-thirds, we can calculate PERM(M + kX) for k = 1,2,...,n + 1. Once we have those n + 1 values, we can solve for the coefficients of p(k) using interpolation (remember that p(k) has degree n). Once we know p(k) exactly, we evaluate p(0), which is equal to PERM(M).

If we do so, we run the risk of being wrong 1/3 of the time, but by picking multiple random Xs and repeating the above procedure many times, and only providing the majority winner as an answer, we can drive the error rate down very low.

Consequences

References

Read other articles:

Pub in Twickenham, London The Crown, TwickenhamLocation within London Borough of Richmond upon ThamesGeneral informationTypePublic houseLocation174 Richmond Road, Twickenham, London TW1 (in the London Borough of Richmond upon Thames) Listed Building – Grade IIOfficial nameThe Crown Public HouseDesignated25 May 1983Reference no.1250208 The Crown is a pub at 174 Richmond Road, Twickenham, London TW1. It is a Grade II listed building, dating back to the late 18th century.[1] Refer...

 

Baru Aku Tahu Cinta Itu ApaSingel oleh Indah Pertiwidari album HipnotisGenrePopDurasi4:10LabelKeci Music Baru Aku Tahu Cinta Itu Apa adalah lagu utama Indah Pertiwi di album Hipnotis. Dirilis pada tahun 2010. Lagu ini berdurasi 4:10 ini menduduki posisi ke-1 di chart Dahsyat, dan Inbox, 6 di chart MTV Ampuh dan 4 di chart Derings. Lagu ini menduduki posisi chart MTV Ampuh dari bulan Mei hingga Juli 2010. Artikel bertopik lagu, musik, atau alat musik ini adalah sebuah rintisan. Anda dapat memb...

 

Mumbai Metro's Yellow Line 2A metro station Lower OshiwaraMumbai Metro stationGeneral informationLocationVeera Desai Industrial Estate, Jogeshwari West, Mumbai, Maharashtra 400047Coordinates19°08′27″N 72°49′54″E / 19.14079°N 72.83169°E / 19.14079; 72.83169Owned byMumbai Metropolitan Region Development Authority (MMRDA)Operated byMaha Mumbai Metro Operation Corporation Limited (MMMOCL)Line(s)Line 2APlatforms2 (2 side platform)Tracks2ConstructionStructure typ...

Roman mystery cults of the wine god and seer Bacchus Bacchanal redirects here. For the racehorse, see Bacchanal (horse). For the painting, see Bacchanalia (Rubens). For the restaurant, see Bacchanalia (restaurant). Religion inancient RomeMarcus Aurelius (head covered)sacrificing at the Temple of Jupiter Practices and beliefs libation votum temples festivals ludi funerary practices imperial cult mystery religions Priesthoods Pontifices Augures Vestales Flamines Fetiales Epulones Fratres Arvale...

 

Questa voce sugli argomenti calciatori francesi e calciatori congolesi (Repubblica del Congo) è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti dei progetti di riferimento 1, 2. Maël Lépicier Nazionalità  Francia Rep. del Congo (dal 2011) Altezza 184 cm Peso 83 kg Calcio Ruolo Difensore Termine carriera 2023 CarrieraGiovanili  Le MansSquadre di club1 2005-2006 Le Mans 231 (0)2006-2007 Châtellerault36 (0)...

 

Artikel ini memiliki beberapa masalah. Tolong bantu memperbaikinya atau diskusikan masalah-masalah ini di halaman pembicaraannya. (Pelajari bagaimana dan kapan saat yang tepat untuk menghapus templat pesan ini) Artikel biografi ini ditulis menyerupai resume atau daftar riwayat hidup (Curriculum Vitae). Tolong bantu perbaiki agar netral dan ensiklopedis. Gaya atau nada penulisan artikel ini tidak mengikuti gaya dan nada penulisan ensiklopedis yang diberlakukan di Wikipedia. Bantulah memperbaik...

Untuk kegunaan lain, lihat Romanesque (disambiguasi). Ukiran dari Biara Maria Laach, di Eifel, Rhineland. Seni rupa Romanesque adalah sebuah seni rupa di Eropa dari sekitar 1000 Masehi sampai berkembangnya gaya Gothik pada abad ke-13, atau kemudian, tergantung pada wilayahnya. Periode sebelumnya dikenal sebagai periode Pra-Romanesque. Istilah tersebut dicetuskan oleh para sejarawan seni rupa abad ke-19, khususnya untuk arsitektur Romanesque, yang masih menampilkan beberapa dasar gaya arsitekt...

 

Collection of ogham stones in County Kerry, Ireland Kilcoolaght East Ogham StonesNative name Irish: Clocha Oghaim Chill Chuallachta ThoirThe stones with MacGillycuddy's Reeks in the backgroundTypeogham stonesLocationKilcoolaght East, Killorglin,County Kerry, IrelandCoordinates52°04′26″N 9°44′45″W / 52.073956°N 9.745798°W / 52.073956; -9.745798Elevation22 m (72 ft)Ownerstate National monument of IrelandOfficial nameKilcoolaght East Ogham Stones[...

 

2005 album by Ozzy Osbourne For other uses, see Undercover (disambiguation). Under CoverStudio album by Ozzy OsbourneReleased1 November 2005Recorded2003–05Studio Cello Studios Whatinthwhatthe? The Music Machine The Village Recorder Capitol Studios, Los Angeles Sony Music Studios Avatar Studios, New York City Ritz Carlton Hotel, Palm Beach Peninsula Hotel, New York Abbey Road Studios Withfield Street Studios, London, UK GenreRockLength57:10LabelEpicProducerMark HudsonOzzy Osbourne chrono...

Salsa di soiaSalsa di soia della tipica marca KikkomanOriginiLuogo d'origine Cina DiffusioneAsia DettagliCategoriasalsa Ingredienti principalisemi di soia La salsa di soia (in cinese 醬油T, 酱油S, jiàng yóuP, in coreano 간장?, ganjangLR, kanjangMR, in giapponese: 醤油?, shōyu) è una salsa fermentata ottenuta dalla soia (19%), grano tostato (15,99%), acqua (53%), sale (12%) e Aspergillus sp. (<0,01%). Originaria della Cina, la salsa di soia è un comune ingrediente ...

 

ヨハネス12世 第130代 ローマ教皇 教皇就任 955年12月16日教皇離任 964年5月14日先代 アガペトゥス2世次代 レオ8世個人情報出生 937年スポレート公国(中部イタリア)スポレート死去 964年5月14日 教皇領、ローマ原国籍 スポレート公国親 父アルベリーコ2世(スポレート公)、母アルダその他のヨハネステンプレートを表示 ヨハネス12世(Ioannes XII、937年 - 964年5月14日)は、ロ...

 

CisnădieKota Lambang kebesaranNegara RumaniaProvinsiSibiuStatusKotaPemerintahan • Wali kotaJohann KrechLuas • Total138,56 km2 (5,350 sq mi)Populasi (2002) • Total17.871Zona waktuUTC+2 (EET) • Musim panas (DST)UTC+3 (EEST)Situs webCisnadie.Ro Cisnădie (Jerman: Heltaucode: de is deprecated , Transylvanian Saxon dialect: Hielt, bahasa Hongaria: Nagydisznód) adalah kota yang terletak di provinsi Sibiu, Transilvania. K...

本條目存在以下問題,請協助改善本條目或在討論頁針對議題發表看法。 此條目需要編修,以確保文法、用詞、语气、格式、標點等使用恰当。 (2013年8月6日)請按照校對指引,幫助编辑這個條目。(幫助、討論) 此條目剧情、虛構用語或人物介紹过长过细,需清理无关故事主轴的细节、用語和角色介紹。 (2020年10月6日)劇情、用語和人物介紹都只是用於了解故事主軸,輔助�...

 

79-я гвардейская реактивная артиллерийская Новозыбковская Краснознамённая, орденов Суворова и Александра Невского бригада Годы существования 1992[1] — н. в. Страна  Россия Подчинение Сухопутные войска Российской Федерации Входит в Московский военный округ Ти...

 

Businessman and politician The Right HonourableThe Lord Taylor of BlackburnCBE JP DLJune 2013, asking a question about badger cullingMember of the House of LordsLord TemporalIn office4 May 1978 – 25 November 2016Life Peerage Personal detailsBornThomas Taylor(1929-06-10)10 June 1929Died25 November 2016(2016-11-25) (aged 87)CitizenshipUnited KingdomNationalityBritishPolitical partyLabourSpouseKathleenChildren1 son Thomas Taylor, Baron Taylor of Blackburn, CBE, JP...

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Philip Rea, 2nd Baron Rea – news · newspapers · books · scholar · JSTOR (March 2020) (Learn how and when to remove this message) The Right HonourableThe Lord ReaPCPhilip ReaLeader of the Liberal Party in the House of LordsIn office1955–1967Preceded byThe Vis...

 

State's representative in a French department or region You can help expand this article with text translated from the corresponding article in French. (January 2021) Click [show] for important translation instructions. View a machine-translated version of the French article. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy...

 

تاريخ الزراعةمعلومات عامةمجال البحث agrarian history (en) التأثيراتأحد جوانب زراعة فرع من تاريختاريخ اقتصاديتاريخ علم النبات تعديل - تعديل مصدري - تعديل ويكي بيانات زراعة عام أعمال تجارية زراعية علم الإنتاج النباتي حراجة زراعية علم الزراعة تربية الحيوان زراعة موسعة مزرعة نطاق حر �...

Act of the New Zealand Parliament Constitution Act 1986New Zealand Parliament Long title An Act to reform the constitutional law of New Zealand, to bring together into one enactment certain provisions of constitutional significance, and to provide that the New Zealand Constitution Act 1852 of the Parliament of the United Kingdom shall cease to have effect as part of the law of New Zealand Passed13 December 1986Commenced1 January 1987Amended by1987, 1999, 2005Related legislationNew Zealand Bil...

 

Football stadium in Incheon, South Korea Incheon Football Stadium인천축구전용경기장Sungui Arena ParkThe stadium on a matchday in May 2012LocationJung-gu, Incheon, South KoreaCoordinates37°27′56″N 126°38′37″E / 37.4656°N 126.6435°E / 37.4656; 126.6435Capacity20,891SurfaceNatural GrassConstructionBroke groundMay 5, 2008OpenedMarch 11, 2012Construction cost$110 millionTenantsIncheon United (2012–present)2014 Asian Games Incheon Football Stadium, als...