UZH-Logo

Maintenance Infos

Efficient recovering of operation tables of black box groups and rings


Zumbraegel, J; Maze, G; Rosenthal, J (2008). Efficient recovering of operation tables of black box groups and rings. In: IEEE. Information Theory, 2008.ISIT 2008. Toronto: IEEE, 639-643.

Abstract

People have been studying the following problem: Given a finite set S with a hidden (black box) binary operation ∗ : S × S → S which might come from a group law, and suppose you have access to an oracle that you can ask for the operation x ∗ y of single pairs (x, y) ∈ S2 you choose. What is the minimal number of queries to the oracle until the whole binary operation is recovered, i.e. you know x ∗ y for all x, y ∈ S? This problem can trivially be solved by using |S|2 queries to the oracle, so the question arises under which circumstances you can succeed with a significantly smaller number of queries. In this presentation we give a lower bound on the number of queries needed for general binary operations. On the other hand, we present algorithms solving this problem by using |S| queries, provided that ∗ is an abelian group operation. We also investigate black box rings and give lower und upper bounds for the number of queries needed to solve product recovering in this case.

Abstract

People have been studying the following problem: Given a finite set S with a hidden (black box) binary operation ∗ : S × S → S which might come from a group law, and suppose you have access to an oracle that you can ask for the operation x ∗ y of single pairs (x, y) ∈ S2 you choose. What is the minimal number of queries to the oracle until the whole binary operation is recovered, i.e. you know x ∗ y for all x, y ∈ S? This problem can trivially be solved by using |S|2 queries to the oracle, so the question arises under which circumstances you can succeed with a significantly smaller number of queries. In this presentation we give a lower bound on the number of queries needed for general binary operations. On the other hand, we present algorithms solving this problem by using |S| queries, provided that ∗ is an abelian group operation. We also investigate black box rings and give lower und upper bounds for the number of queries needed to solve product recovering in this case.

Citations

1 citation in Web of Science®
2 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

32 downloads since deposited on 05 Mar 2009
11 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Book Section, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Mathematics
Dewey Decimal Classification:510 Mathematics
Language:English
Date:2008
Deposited On:05 Mar 2009 10:23
Last Modified:05 Apr 2016 13:02
Publisher:IEEE
Publisher DOI:https://doi.org/10.1109/ISIT.2008.4595064
Related URLs:http://arxiv.org/abs/0805.0514v1

Download

[img]
Preview
Filetype: PDF
Size: 1MB
View at publisher

TrendTerms

TrendTerms displays relevant terms of the abstract of this publication and related documents on a map. The terms and their relations were extracted from ZORA using word statistics. Their timelines are taken from ZORA as well. The bubble size of a term is proportional to the number of documents where the term occurs. Red, orange, yellow and green colors are used for terms that occur in the current document; red indicates high interlinkedness of a term with other terms, orange, yellow and green decreasing interlinkedness. Blue is used for terms that have a relation with the terms in this document, but occur in other documents.
You can navigate and zoom the map. Mouse-hovering a term displays its timeline, clicking it yields the associated documents.

Author Collaborations