{"id":168221,"date":"2007-07-01T00:00:00","date_gmt":"2007-07-01T00:00:00","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/ring-signatures-of-sub-linear-size-without-random-oracles\/"},"modified":"2018-10-16T20:10:56","modified_gmt":"2018-10-17T03:10:56","slug":"ring-signatures-of-sub-linear-size-without-random-oracles","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/ring-signatures-of-sub-linear-size-without-random-oracles\/","title":{"rendered":"Ring Signatures of Sub-linear Size Without Random Oracles"},"content":{"rendered":"<p class=\"Para\">Ring signatures, introduced by Rivest, Shamir and Tauman, enable a user to sign a message anonymously on behalf of a \u201cring\u201d. A ring is a group of users, which includes the signer. We propose a ring signature scheme that has size <span id=\"IEq1\" class=\"InlineEquation\"><span id=\"MathJax-Element-1-Frame\" class=\"MathJax\" tabindex=\"0\" data-mathml=\"<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mrow class=\"MJX-TeXAtom-ORD\"><mi class=\"MJX-tex-caligraphic\" mathvariant=\"script\">O<\/mi><\/mrow><mo stretchy=\"false\">(<\/mo><msqrt><mi>N<\/mi><\/msqrt><mo stretchy=\"false\">)<\/mo><\/math>\"><span id=\"MathJax-Span-1\" class=\"math\"><span id=\"MathJax-Span-2\" class=\"mrow\"><span id=\"MathJax-Span-3\" class=\"texatom\"><span id=\"MathJax-Span-4\" class=\"mrow\"><span id=\"MathJax-Span-5\" class=\"mi\">O<\/span><\/span><\/span><span id=\"MathJax-Span-6\" class=\"mo\">(<\/span><span id=\"MathJax-Span-7\" class=\"msqrt\"><span id=\"MathJax-Span-8\" class=\"mrow\"><span id=\"MathJax-Span-9\" class=\"mi\">N<\/span><\/span>\u2212\u2212\u221a<\/span><span id=\"MathJax-Span-10\" class=\"mo\">) <\/span><\/span><\/span><\/span><\/span>where <em class=\"EmphasisTypeItalic \">N<\/em> is the number of users in the ring. An additional feature of our scheme is that it has perfect anonymity. Our ring signature like most other schemes uses the common reference string model. We offer a variation of our scheme, where the signer is guaranteed anony- mity even if the common reference string is maliciously generated.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Ring signatures, introduced by Rivest, Shamir and Tauman, enable a user to sign a message anonymously on behalf of a \u201cring\u201d. A ring is a group of users, which includes the signer. We propose a ring signature scheme that has size O(N\u2212\u2212\u221a) where N is the number of users in the ring. An additional feature [&hellip;]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","footnotes":""},"msr-content-type":[3],"msr-research-highlight":[],"research-area":[13561,13558],"msr-publication-type":[193716],"msr-product-type":[],"msr-focus-area":[],"msr-platform":[],"msr-download-source":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-168221","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-algorithms","msr-research-area-security-privacy-cryptography","msr-locale-en_us"],"msr_publishername":"Springer","msr_edition":"Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland","msr_affiliation":"","msr_published_date":"2007-07-09","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"423\u2013434","msr_chapter":"","msr_isbn":"978-3-540-73419-2","msr_journal":"","msr_volume":"4596","msr_number":"","msr_editors":"","msr_series":"Lecture Notes in Computer Science","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"","msr_publicationurl":"http:\/\/dx.doi.org\/10.1007\/978-3-540-73420-8_38","msr_doi":"","msr_publication_uploader":[{"type":"url","title":"http:\/\/dx.doi.org\/10.1007\/978-3-540-73420-8_38","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_attachments":[{"id":0,"url":"http:\/\/dx.doi.org\/10.1007\/978-3-540-73420-8_38"}],"msr-author-ordering":[{"type":"user_nicename","value":"nichandr","user_id":33084,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=nichandr"},{"type":"text","value":"Jens Groth","user_id":0,"rest_url":false},{"type":"text","value":"Amit Sahai","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[144675,144887,144938],"msr_project":[],"publication":[],"video":[],"download":[],"msr_publication_type":"inproceedings","related_content":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/168221"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":1,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/168221\/revisions"}],"predecessor-version":[{"id":409943,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/168221\/revisions\/409943"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=168221"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=168221"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=168221"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=168221"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=168221"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=168221"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=168221"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=168221"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=168221"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=168221"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=168221"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=168221"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=168221"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=168221"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=168221"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=168221"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}