Header

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.

Statistics

Citations

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

Altmetrics

Downloads

48 downloads since deposited on 05 Mar 2009
16 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:06 Dec 2017 18:15
Publisher:IEEE
Publisher DOI:https://doi.org/10.1109/ISIT.2008.4595064
Related URLs:http://arxiv.org/abs/0805.0514v1

Download

Download PDF  'Efficient recovering of operation tables of black box groups and rings'.
Preview
Filetype: PDF
Size: 1MB
View at publisher